Verifiable quantum advantage in extremely low depth

arXiv:2609.01448 · quant-ph, cs.CR · Submitted 2026-09-01 · Read on arXiv

quant-ph, cs.CR

Submitted: 2026-09-01

Updated: 2026-10-01

Terminology

• Verifier — 39× in this paper · explained in 2 episodes
• Quantum Circuits — 17× in this paper · explained in 2 episodes
• Admissibility — 15× in this paper · explained in 2 episodes
• Verification — 12× in this paper · explained in 2 episodes
• Decode — 6× in this paper · explained in 2 episodes
• Adam — 4× in this paper · explained in 2 episodes
• Learning with Errors — 4× in this paper
• Accuracy — 2× in this paper · explained in 1 episode
• Adaptivity — 2× in this paper · explained in 1 episode
• BQP — 2× in this paper · explained in 2 episodes
• Entanglement — 2× in this paper · explained in 3 episodes
• Sample Complexity — 2× in this paper · explained in 15 episodes
• Agnostic Learning — 1× in this paper · explained in 1 episode
• Ancilla Qubits — 1× in this paper · explained in 1 episode
• Benchmark — 1× in this paper · explained in 2 episodes
• Consistency — 1× in this paper · explained in 3 episodes
• Core — 1× in this paper · explained in 2 episodes
• Dense-Sparse Learning Parity with Noise — 1× in this paper
• Hilbert Space — 1× in this paper · explained in 2 episodes

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
• Theory of quantum-enhanced interferometry with general Markovian light sources
• A convergent hierarchy of spectral gap certificates for qubit Hamiltonians
• Universal Bound and Phase Transition in Many-Body Fermionic Non-Gaussianity