Researchers have demonstrated verifiable quantum advantage using extremely low-depth quantum circuits. They have designed a sampling problem that can be solved by these shallow circuits, yet is computationally hard for classical polynomial-time algorithms, based on lattice assumptions. The quantum solution is, furthermore, efficiently verifiable by a classical computer. This advance is significant because it shows that even very simple quantum circuits possess the necessary structure to tackle computational tasks that are intractable for classical computing, and whose results can be efficiently confirmed.

The proposed quantum sampler can be implemented in two ways: one uses log-logarithmic-depth quantum circuits with one- and two-qubit gates (QNC^0[log log] circuits), and the other employs constant-depth quantum circuits with unbounded fan-in gates (QAC^0 circuits). This work builds upon the LWE (Learning with Errors)-based single-round proof of quantumness by Arabadjieva et al. (2025), but compiles it to a much lower depth. The price paid for this compilation is the reliance on less standard, though well-motivated, assumptions: in addition to the lattice knowledge assumption, a strengthened variant of the adaptive-hardcore-bit property of LWE is required, for which the authors 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 simplifies implementation and reduces the complexity of the quantum devices needed. This finding underscores the potential of shallow quantum circuits to solve hard computational problems, opening new avenues for the development of quantum computing with more modest hardware requirements.