⚛️ quantum physics

Verifiable quantum advantage in extremely low depth

This paper presents a sampling problem solvable by extremely shallow quantum circuits (either $\mathsf{QNC}^0[\log\log]$ or $\mathsf{QAC}^0$ ) that is classically hard under lattice-based assumptions and efficiently verifiable by a classical computer, thereby demonstrating verifiable quantum advantage without mid-circuit measurements or feed-forward.

Original authors: Alexandru Gheorghiu

Published 2026-09-02

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Alexandru Gheorghiu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the quest to understand the true power of quantum computers, scientists are constantly asking a deceptively simple question: how much quantum machinery is actually required to solve a problem that a classical computer cannot? For decades, the prevailing view suggested that to gain a decisive advantage, a quantum system needed to perform complex, deep calculations, weaving together thousands of operations in a long, intricate sequence. This depth was thought to be the source of the machine's unique ability to explore possibilities that remain hidden to ordinary computers. However, a new line of inquiry challenges this intuition, probing whether the most restricted, shallow versions of quantum circuits—those that perform only a handful of operations—can still outsmart the best classical algorithms. The stakes are high because if such a minimal quantum system can solve a hard problem, it would prove that quantum advantage is not just a feature of massive, error-prone machines, but a fundamental property of even the simplest quantum structures. Crucially, for this advantage to be useful, a human observer using a standard computer must be able to verify the result quickly and with certainty, turning a theoretical possibility into a practical test.

A researcher has now constructed a specific mathematical puzzle that demonstrates this phenomenon. They designed a task that a quantum computer can solve using an incredibly shallow circuit, one so short that it barely rises above the level of basic logic gates. Yet, solving this same puzzle remains effectively impossible for any classical computer operating within a reasonable timeframe, assuming certain standard mathematical difficulties hold true. What makes this achievement particularly striking is that the solution is not a black box; a classical observer can check the answer efficiently and confirm that the quantum machine truly performed the feat. The researcher achieved this by creating two different ways to build the quantum solver. The first uses a circuit that is slightly deeper but relies only on standard, simple connections between qubits. The second, even more impressive, uses a circuit of constant depth, meaning it does not get deeper no matter how large the problem becomes, but it requires a specific type of gate that can handle many inputs at once. Both versions succeed where classical computers fail, and both produce results that can be instantly verified. Furthermore, because circuits with unbounded fan-in can be simulated by circuits with unbounded fan-out, the task is also solvable by the latter, though the author emphasizes the constant-depth unbounded fan-in version as the more significant achievement.

The core of the discovery lies in how the researcher translated a known cryptographic challenge into a format suitable for these shallow machines. They started with a problem based on the difficulty of finding hidden patterns in noisy data, a concept known as learning with errors. In previous attempts to prove quantum advantage using similar ideas, the quantum computer had to perform a long, multi-step process involving measurements in the middle of the calculation and feeding those results back into the machine to guide the next steps. This "interactive" approach required the quantum state to remain coherent and stable for a long time, which is difficult to maintain. The new work bypasses this entirely. The researcher developed a method to encode the problem so that the quantum computer can run a single, short, unbroken sequence of operations and then measure the result just once at the very end. This eliminates the need for mid-circuit measurements and feedback, simplifying the hardware requirements significantly.

To make this work, the researcher had to rely on a slightly stronger set of mathematical assumptions than those used in earlier studies. They introduced a specific condition regarding how certain bits of information, known as carry bits, behave when numbers are added together in a modular system. While this assumption is not yet proven to be true based on standard mathematics, the author provided strong evidence supporting its validity. They argued that if a classical computer could solve their puzzle, it would imply a breakthrough in breaking these underlying mathematical assumptions, which is widely believed to be impossible. The result is a robust demonstration that shallow quantum circuits possess enough internal structure to solve classically hard problems. The researcher showed that the quantum machine prepares a superposition of many possible inputs, processes them through a local, shallow encoding, and then measures the output to reveal a pattern that encodes the solution.

The implications of this work are twofold. First, it narrows the gap between what is theoretically possible and what is practically achievable with near-term quantum devices. By showing that constant-depth circuits can achieve this advantage, the study suggests that future quantum tests of "quantumness" might not require the massive, deep circuits that are currently beyond our engineering capabilities. Second, it clarifies the boundary between quantum and classical power. The researcher explicitly noted that their result also applies to circuits with unbounded fan-out gates, a different type of powerful operation that is known to be computationally stronger than their constant-depth unbounded fan-in model. Instead, their success relies on the specific structure of their encoding and the hardness of the underlying lattice problems. The study does not claim to have solved the problem of building a universal quantum computer, nor does it suggest that these shallow circuits can factor large numbers or break current encryption. Rather, it provides a precise, verifiable sampling task that serves as a clear benchmark.

The construction involves a challenge-and-response protocol where a verifier sends a public key to a prover. The prover, acting as the quantum machine, prepares a quantum state, applies the shallow circuit, and returns a set of numbers. The verifier then checks if these numbers satisfy a specific relationship. If the prover is a classical computer, it will fail to produce the correct relationship more than three-quarters of the time, even with the best possible strategies. If the prover is the honest quantum machine, it succeeds almost every time. The researcher verified that their quantum implementation uses only polynomial width, meaning the number of qubits grows reasonably with the problem size, and the depth remains extremely low. This balance of low depth, classical hardness, and efficient verification marks a significant step forward in understanding the minimal requirements for quantum advantage.

While the study relies on assumptions that are not yet fully proven, the author is careful to frame their results as conditional on these mathematical beliefs. They acknowledge that the specific "carry-predicate" assumption they use is a new addition to the field, though they provide partial evidence that it likely holds. This transparency ensures that the scientific community can test and refine the assumptions further. The work also highlights the limitations of current approaches; for instance, they note that reducing the circuit depth even further to use only standard gates without the special fan-in gates remains an open challenge. The researcher suggests that achieving a truly constant-depth circuit with only simple gates might require new mathematical constructions that are currently difficult to find.

Ultimately, this paper offers a concrete example of how a quantum system can outperform a classical one with minimal resources. It moves the conversation from abstract complexity theory to a tangible, verifiable protocol. By stripping away the need for deep circuits and mid-circuit measurements, the researcher has shown that the essence of quantum advantage can be found in very shallow structures. This finding broadens the horizon for what might be possible with early quantum devices and provides a new, rigorous standard for testing whether a machine is truly harnessing quantum mechanics. The path forward involves refining these assumptions and exploring whether similar techniques can be applied to other cryptographic tasks, but the core result stands: a shallow quantum circuit can indeed solve a problem that is hard for classical computers and easy to verify.

Technical Summary: Verifiable Quantum Advantage in Extremely Low Depth

Problem Statement
The paper addresses a fundamental gap in quantum complexity theory: the lack of a task that is simultaneously solvable by extremely shallow quantum circuits, hard for polynomial-time classical algorithms, and efficiently verifiable by a classical computer. While previous work established that constant-depth quantum circuits (specifically those with unbounded fan-out, $QNC^0_f$ ) can solve classically hard problems, and that interactive proofs of quantumness exist, no known "white-box" problem satisfies all three criteria using only bounded-arity gates in sub-logarithmic depth or constant depth with unbounded fan-in. Specifically, existing low-depth proofs of quantumness often rely on mid-circuit measurements, classical feed-forward, or black-box random oracles, which obscure the circuit depth guarantees or require unbounded fan-out gates. The central question is whether a verifiable quantum advantage can be achieved within the restricted classes $QNC^0[\log \log]$ (log-logarithmic depth with bounded fan-in) and $QAC^0$ (constant depth with unbounded fan-in).

Methodology
The author constructs a sampling problem based on the Learning with Errors (LWE) framework, compiling the single-round proof of quantumness by Arabadjieva et al. [AGGM25] into very low-depth circuits. The core technical innovation is the use of randomized encodings to transform the evaluation of LWE-based trapdoor claw-free functions (TCFs) into a local, shallow computation.

Protocol Structure: The protocol is a single-round challenge-response task. The verifier samples either a TCF $f$ (based on LWE) or an injective function $g$ (based on a lattice knowledge assumption) that are computationally indistinguishable. The prover must return a response $(y, d)$ (or an encoded equivalent) that satisfies specific algebraic relations.
Randomized Encoding: To achieve low depth, the author generalizes a binary affine map encoding to maps over a ring $\mathbb{Z}_q$ $Z_{q}$ . The encoding replaces the global computation of $Mv + \eta$ $M v + η$ (where $M$ $M$ is a matrix, $v$ $v$ is an input vector, and $\eta$ $η$ is noise) with a string of locally computable symbols.
- Path-Mask Encoding: The sum of inputs is encoded using "path masks" ( $h$ ) that shuttle random values along a path, canceling out upon summation. This ensures that each output symbol depends on only a constant number of source values.
- Input Masking: To prevent input reuse across rows (which would break locality), a second layer of masks ( $r$ ) is applied.
- Locality: Every encoded symbol depends on at most three source words (input, mask, or noise). This allows the quantum prover to evaluate the encoding in parallel.
Quantum Strategy: The honest quantum prover prepares a superposition over the branch bit, input, noise, and encoding masks. It evaluates the encoding locally, erases the noise register (which is now entangled with the output), and measures the registers in the Hadamard basis. This yields a direction $D$ and a bit $C$ satisfying a parity relation derived from the "claw" structure of the TCF.
Verification: The verifier uses a trapdoor to either check the validity of the image (in the injective case) or recover the two preimages and their associated masks (in the TCF case) to verify the parity equation.

Key Assumptions
The classical hardness of the problem relies on two non-standard but well-motivated assumptions:

Subexponential Knowledge-of-Lattice-Point (LK-1/4): An algorithm that outputs a point close to a lattice must "know" the closest lattice vector. This is used to extract preimages for the injective function $g$ .
Adaptive-Hardcore-Bit with Carry Predicates: A strengthened variant of the adaptive-hardcore-bit property for LWE. It posits that no efficient classical algorithm can predict a parity of the secret that includes not only linear terms but also "carry bits" arising from the partial sums of LWE equations. The author provides evidence for this assumption but notes it is not currently known to follow directly from standard LWE.

Results
The paper presents two implementations of the quantum sampler:

$QNC^0[\log \log]$ : A circuit of depth $O(\log \log \lambda)$ using only one- and two-qubit gates (bounded fan-in).
$QAC^0$ : A circuit of constant depth $O(1)$ using unbounded fan-in gates (generalized Toffoli gates).

Theorem 1.1 (Informal): Under the stated assumptions, there exists a family of sampling problems where:

An honest quantum sampler is accepted with probability $1 - \text{negl}(\lambda)$ .
Any uniform classical sampler running in time $2^{o(\lambda)}$ is accepted with probability at most $3/4 + \text{negl}(\lambda)$ .
The quantum computation requires no mid-circuit measurements or feed-forward; it consists of a single unitary circuit followed by a final measurement layer.

Significance and Claims
The paper claims to provide the first example of a verifiable quantum advantage that does not require unbounded fan-out gates (which are powerful enough to collapse depth hierarchies) or mid-circuit measurements. By compiling the AGGM protocol using randomized encodings, the author demonstrates that shallow quantum circuits possess sufficient structure to solve classically hard tasks whose solutions are efficiently verifiable.

The author is modest about the limitations:

The construction relies on the non-standard "carry-predicate" assumption, which is not yet proven to follow from standard LWE.
The circuit width is polynomial but large (estimated as $e^{O(\lambda^4 \log^6 \lambda)}$ ), making immediate near-term experimental implementation infeasible.
The result does not yet achieve a constant-depth circuit using only bounded-arity gates (true $QNC^0$ ), as the arithmetic on $L$ -bit numbers ( $L = \Theta(\log^2 \lambda)$ ) necessitates either $O(\log \log \lambda)$ depth or unbounded fan-in.

The work broadens the understanding of shallow quantum computation by showing that even without the power of unbounded fan-out or interactive feedback, quantum circuits can maintain a verifiable advantage over classical computation under plausible cryptographic assumptions.

More like this