{"id":"arxiv/2609.01448","url":"https://arxiv.org/abs/2609.01448","tags":["quant-ph","cs.CR"],"score":0,"title":"Verifiable quantum advantage in extremely low depth","domain":"quant-ph","source":"arxiv","authors":["Alexandru Gheorghiu"],"reviews":0,"subject":"quant-ph","summary":"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., $\\mathsf{QNC}^0[\\log\\log]$ circuits, while the other uses constant-depth quantum circuits with unbounded fan-in gates, i.e., $\\mathsf{QAC}^0$ circuits. Our construction can be seen as compiling the Learning with Errors (LWE)-based single-round proof of…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-01","reactions":{}}