Curator's Take
AI Commentary
This article demonstrates that even log‑log‑depth quantum circuits—far shallower than the tens‑of‑layers needed for most supremacy proposals—can solve a sampling problem that is provably hard for classical polynomial‑time algorithms under lattice‑based assumptions, and whose output can be checked efficiently on a classical computer. By compiling the recent LWE‑based proof‑of‑quantumness protocol into QNC⁰[log log] or constant‑depth QAC⁰ circuits without any mid‑circuit measurements or feed‑forward, it shows that near‑term devices with very limited coherence times could already exhibit a verifiable quantum advantage. The result is significant for hardware developers because it lowers the experimental overhead required to demonstrate supremacy, though its security rests on a strengthened adaptive‑hardcore‑bit property of LWE that remains an extra theoretical assumption.
— Mark Eatherly
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 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.