Verifiable quantum advantage in extremely low depth
quant-ph, cs.CR
Submitted: 2026-09-01
Updated: 2026-10-01
Comments: Revised admissibility conditions, corrected and clarified the supporting security analysis, and expanded the discussion of assumptions and related work. 48 pages, 1 table, 1 figure
License: http://creativecommons.org/licenses/by/4.0/
The gist: We give a sampling problem that is solvable by shallow quantum circuits, hard for polynomial-time classical algorithms under lattice-based assumptions, and efficiently verifiable by a classical
Terminology
Abstract
We give a sampling problem that is solvable by shallow quantum circuits, hard for polynomial-time classical algorithms under lattice-based assumptions, and efficiently verifiable by a classical computer. The quantum sampler admits two implementations: one uses log-logarithmic-depth quantum circuits with one- and two-qubit gates, i.e., 0[] circuits, while the other uses constant-depth quantum circuits with unbounded fan-in gates, i.e., 0 circuits. Our construction can be seen as compiling the Learning with Errors (LWE)-based single-round proof of quantumness of Arabadjieva et al. (2025) to very low depth. The price paid for this compilation is the reliance on less standard, though well-motivated, assumptions: in addition to the lattice knowledge assumption used by Arabadjieva et al. (2025), we require a strengthened variant of the adaptive-hardcore-bit property of LWE, for which we provide supporting evidence. Unlike previous low-depth proofs of quantumness, the quantum computation here requires no mid-circuit measurements or feed-forward: it consists only of running a shallow circuit and sampling from its output distribution. This shows that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
Sources
- BQP and the Polynomial Hierarchy
- Single-Round Proofs of Quantumness from Knowledge Assumptions
- On Certified Randomness from Fourier Sampling or Random Circuit Sampling
- Provable and Verifiable Quantum Advantage in Sample Complexity
- Instantaneous Quantum Polynomial-Time Sampling and Verifiable Quantum Advantage: Stabilizer Scheme and Classical Security
- A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device
- Quantum advantage with shallow circuits
- Quantum advantage with noisy shallow circuits in 3D
- Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
- Simpler Proofs of Quantumness
- Noise-Tolerant Learning, the Parity Problem, and the Statistical Query Model
- Average-case complexity versus approximate simulation of commuting quantum computations
- Unconditional and exponentially large violation of classicality
- Architectures for quantum simulation showing a quantum speedup
- Exponential separation between shallow quantum circuits and unbounded fan-in shallow classical circuits
- Trading locality for time: certifiable randomness from low-depth circuits
- Fast parallel circuits for the quantum Fourier transform
- Lossy Cryptography from Code-Based Assumptions
- Random Unitaries in Constant (Quantum) Time
- On estimating the entropy of shallow circuit outputs
Related papers
- Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
- Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
- Polynomial-time classical and quantum simulation of quantum impurity models
- A quasiparticle-protected superconducting qubit
- Theory of quantum-enhanced interferometry with general Markovian light sources
- A convergent hierarchy of spectral gap certificates for qubit Hamiltonians