Verifiable quantum advantage in extremely low depth
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., QNC0[loglog] circuits, while the other uses constant-depth quantum circuits with unbounded fan-in gates, i.e., QAC0 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.
Related
- Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation
- Towards verifiable quantum advantage with random circuits: Observables that survive concentration
- Verifiable quantum advantage based on polynomials with planted structures
- Verifiable Sampling for Delegated Generative Quantum Machine Learning
- Qyantram: A Transparent and Verifiable Quantum Computing Platform
BibTeX
@misc{gheorghiu2026verifiable,
title = {{Verifiable quantum advantage in extremely low depth}},
author = {Alexandru Gheorghiu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.01448},
eprint = {2609.01448},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.01448},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Verifiable quantum advantage in extremely low depth
AU - Alexandru Gheorghiu
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2609.01448
UR - https://arxiv.org/abs/2609.01448
AB - 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., QNC^0[loglog] circuits, while the other uses constant-depth quantum circuits with unbounded fan-in gates, i.e., QAC^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.
ER -