Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper presents a sampling problem that can be efficiently solved by shallow quantum circuits while remaining hard for polynomial-time classical algorithms based on lattice assumptions. The authors introduce two implementations: one utilizing log-logarithmic-depth circuits and the other employing constant-depth circuits with unbounded fan-in gates, both of which allow for efficient classical verification. Notably, this work demonstrates that shallow quantum circuits can tackle classically hard problems without the need for mid-circuit measurements or feed-forward mechanisms, highlighting their potential for practical applications in quantum computing.
Shallow quantum circuits can efficiently solve classically hard sampling problems, challenging the limits of classical computation.
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.