Circuit depth is a central resource in complexity theory. While bounded-depth classical circuits admit well-understood hierarchy theorems, the internal structure of constant-depth quantum computation remains comparatively unexplored.
We prove an explicit depth hierarchy theorem for $\mathsf{QNC}^0$. For each $d\ge 12$, we construct a family of two-round interactive problems on which no depth-$(d-1)$ quantum circuit can achieve near-perfect success, regardless of gate set, circuit size, or ancillary qubits. In contrast, we prove that our construction admits realizations by simple bounded fan-in quantum circuits of depth larger than $d$ by a small constant factor. Moreover, all bounded fan-in classical circuits of sublogarithmic depth (in the input size) fail to achieve perfect success on these tasks for every $d$, yielding a hierarchy of problems that show unconditional quantum advantage of $\mathsf{QNC}^0$ over $\mathsf{NC}^0$.
A key obstacle is the scarcity of lower bound techniques for quantum circuits. To address this, we develop methods to analyze how depth affects a circuit's ability to realize nonlocal correlations amongst its output qubits in a fine-grained manner. Our approach exploits the correspondence between constraint systems and nonlocal games, translating group-theoretic constructions into rigid operator-valued constraint systems and then into non-local games. In particular, we construct constraint systems whose unique faithful operator-valued solutions require every perfect strategy, and every near-perfect strategy to a fixed precision, to implement multi-controlled phase operations. This reduces to a nonlocal unitary-synthesis problem, yielding depth lower bounds for both shallow quantum and classical circuits.
These results show that increasing depth strictly increases computational power within $\mathsf{QNC}^0$, establishing a genuinely quantum hierarchy.
Circuit depth is a central resource in complexity theory. While bounded-depth classical circuits admit well-understood hierarchy theorems, the internal structure of constant-depth quantum computation remains comparatively unexplored.
We prove an explicit depth hierarchy theorem for QNC0. For each d≥12, we construct a family of two-round interactive problems on which no depth-(d−1) quantum circuit can achieve near-perfect success, regardless of gate set, circuit size, or ancillary qubits. In contrast, we prove that our construction admits realizations by simple bounded fan-in quantum circuits of depth larger than d by a small constant factor. Moreover, all bounded fan-in classical circuits of sublogarithmic depth (in the input size) fail to achieve perfect success on these tasks for every d, yielding a hierarchy of problems that show unconditional quantum advantage of QNC0 over NC0.
A key obstacle is the scarcity of lower bound techniques for quantum circuits. To address this, we develop methods to analyze how depth affects a circuit's ability to realize nonlocal correlations amongst its output qubits in a fine-grained manner. Our approach exploits the correspondence between constraint systems and nonlocal games, translating group-theoretic constructions into rigid operator-valued constraint systems and then into non-local games. In particular, we construct constraint systems whose unique faithful operator-valued solutions require every perfect strategy, and every near-perfect strategy to a fixed precision, to implement multi-controlled phase operations. This reduces to a nonlocal unitary-synthesis problem, yielding depth lower bounds for both shallow quantum and classical circuits.
These results show that increasing depth strictly increases computational power within QNC0, establishing a genuinely quantum hierarchy.
We achieve the first constant-depth circuit for arbitrary single-qubit gate synthesis. Unlike prior approaches, the construction is fully unitary and requires no pre-supplied catalyst. For any constant δ>0, it ε-approximates an arbitrary single-qubit gate using O(log1+δ(1/ε)) clean ancillae, Hadamard and T single-qubit gates, O(log(1/ε))-width generalized Toffoli gates, and sublogarithmic-width Fan-Out gates. We further eliminate Fan-Out entirely, showing that Hadamard, T, and generalized Toffoli gates alone suffice for constant-depth synthesis. When restricted to the standard bounded-width gate model, our construction has depth O(loglog(1/ε)), and we prove a matching Ω(loglog(1/ε))-depth lower bound. Overall, we establish that Θ(loglog(1/ε))-depth is unavoidable with only bounded-width gates, yet allowing even logarithmic-width multi-qubit gates suffices to achieve constant-depth synthesis.
These results also reveal new structure in shallow quantum circuit complexity. We give a depth-preserving real simulation of bounded-error decision computation, showing that every depth-d QAC circuit can be simulated in depth O(d) using only Hadamard, X, and generalized Toffoli gates. Thus arbitrary single-qubit rotations and complex amplitudes do not increase the bounded-error decision power of QAC, even at constant depth. In particular, this reduces the long-standing conjecture Parity∈/QAC0 to proving a Parity lower bound against circuits consisting only of Hadamard, X, and generalized Toffoli gates. More generally, this real normal form exposes a direct correspondence between the standard shallow-depth quantum circuit hierarchy and a hierarchy of Forrelation circuits with restricted oracle families.
Classical circuits with unbounded fan-in can compute any Boolean function in constant depth when their size is unrestricted. We ask whether removing the restrictions on circuit size and ancillary qubits also allows quantum circuits built from arbitrary single-qubit gates and generalised Toffoli gates to implement every unitary in constant depth.
We give exact constant-depth constructions for arbitrary permutations of computational basis states, diagonal unitaries and the preparation of arbitrary pure states. These connect quantum state preparation to reversible classical computation and the preparation of probability distributions. With fanout in the gate set, they use exponentially many gates and ancillary qubits and return all ancillary qubits to zero. Replacing fanout by an exact circuit over the original gate set preserves constant depth, although the size bounds can become doubly exponential.
The implementation of arbitrary unitaries in constant depth remains open. We give equivalent formulations in terms of copying the vectors of a specified orthonormal basis, extracting their labels and implementing restricted families of unitaries. We also reduce arbitrary unitary implementation to that of traceless unitary involutions using one additional clean qubit. With adaptive measurements, gate teleportation gives depth proportional to the level of a gate in the Clifford hierarchy.
Towards arbitrary unitary implementation in constant depth, we use port-based teleportation: for input dimension d and M≥d2−1 ports, we construct a unitary circuit of depth O(d), independent of M and including resource preparation and port selection, with entanglement fidelity at least (1−(d2−1)/(2M))2. Thus, at fixed d, the approximation can be made arbitrarily accurate without increasing depth. Whether the dependence on d can also be removed remains open.
Quantum computers were initially proposed to surpass the limitations of classical computers in simulating physical systems. Soon after, the field of quantum computing advanced through landmark discoveries of quantum algorithms, with some conjectured to provide exponential advantages over classical counterparts. These include Shor’s factoring algorithm, which has profound implications in cryptography. Additionally, moderate yet significant polynomial separations have further increased interest in the field. However, despite this progress, unconditional proofs confirming quantum superiority on the theoretical side remain elusive. At the same time, large, noise-resilient quantum computations on the experimental side, which could challenge the extended Church-Turing thesis by potentially breaking classical computational barriers, have yet to be achieved. Meanwhile, our understanding of the differences between classical and quantum mechanics has deepened. We now possess rigorous theoretical tools, such as Bell inequalities and nonlocal games, to describe behaviors unique to these theories. Moreover, the main loopholes for observing non-classical correlations have been closed experimentally, showing that correlations in the physical world exceed those predicted by classical mechanics. This thesis investigates computational complexity differences between quantum and classical models by studying shallow-depth circuits. The primary focus lies in identifying, elucidating, and proving computational quantum advantages. Additionally, the analysis delves into the bijection between these circuits and foundational non-local game constructions, exploring how quantum-classical deviations in multi-party correlation settings translate to computational advantages. A key question addressed is how to synthesize constant-depth quantum circuits for various problems to leverage quantum advantages. To this end, circuit synthesis techniques tailored to measurement-based quantum computation are developed, enabling simultaneously optimal quantum strategies for certain nonlocal games based on a particular bijection between this model and XOR non-local games. Building on this work, we confront a pivotal challenge: If a candidate quantum circuit potentially provides a computational advantage, how can we prove that no classical circuit surpasses it? This work presents new unconditional quantum-classical separations within shallow-depth settings, distinguishing for the first time constant-depth quantum circuits with one- and two-qubit gates from biased polynomial threshold circuits, which incorporate neural-network-type functionalities. These separations extend to prime-dimensional quantum systems, and we conjecture to have identified Razborov-Smolensky-type problems uniquely solvable by specific prime dimensions. The thesis also differentiates constant-depth quantum circuits with multi-qubit Toffoli gates from their classical counterparts, emphasizing the power of parallel quantum computation. Finally, verifying shallow-depth quantum computations is challenging due to conjectured exponential separations from classical computations, limiting correctness verification through simulation. While specific quantum algorithms within BQP have been addressed, we explore whether a quantum computer can reliably execute any instance from a fixed class of quantum circuits. Moving beyond heuristic-based solutions, we propose a benchmarking protocol that certifies, with exponentially high confidence, the execution of arbitrary circuits of specified dimensions, widths, and depths.
Understanding the dynamics of interacting quantum systems is a central goal of quantum simulation. For geometrically local Hamiltonians, locality suggests that digital simulation should retain much of the parallelism of the underlying dynamics. For a target accuracy ε, we construct a nearest-neighbor quantum circuit that simulates the dynamics of an n-qubit, time-independent, finite-range Hamiltonian with normalized local interaction strength on a fixed-dimensional lattice for time T≥1, with circuit depth O(Tlog(nT/ε)) and gate count O(nTlog(nT/ε)). This reduces the polylogarithmic overhead of Haah, Hastings, Kothari, and Low to a single logarithm. On logarithmic-scale blocks from the Lieb--Robinson decomposition, a shallow but highly accurate implementation is essential for reducing the circuit depth. Our key observation is that spatial localization also controls the cost of high precision. In each block, the error of a constant-order product formula is compensated for by a correction, yielding exponential accuracy. The correction can be implemented with depth proportional to the block diameter, introducing no additional asymptotic depth scale beyond that required by spatial localization.
Furthermore, we prove an unconditional circuit-depth lower bound for uniform XXZ Hamiltonians: at fixed evolution time T in the stated regime and sufficiently small fixed error ε, any nearest-neighbor quantum circuit simulating these dynamics requires depth Ω(logn/loglogn). This matches our O(logn) upper bound up to a doubly logarithmic factor, establishing near-optimal circuit depth for lattice Hamiltonian simulation in this regime. Together, these results clarify the role of locality and precision in determining the circuit complexity of quantum dynamics and suggest broader principles for spatially constrained quantum computation.
Quantum advantage is widely expected to require sufficiently deep circuits, where correlations and global computational structure can grow beyond the reach of efficient classical simulation. This expectation is especially stark for constant-depth circuits with local readout: the expectation value of any fixed local observable lies within a bounded backward lightcone and is therefore classically tractable. Here we show that measurement feedback changes this picture. We establish a strict hierarchy of computational power: at fixed coherent depth, increasing the number of feedback outcomes strictly enlarges the class of functions accessible through a local expectation value. The two ends of this hierarchy exhibit distinct computational regimes. With logarithmic feedback, local expectation values for product-state inputs are efficiently classically simulable. Polynomial feedback, by contrast, enables an explicit family of adaptive shallow circuits to encode prime-field discrete logarithm problem~(DLP) into a fixed single-qubit expectation. Assuming the standard worst-case classical hardness of DLP, estimating this expectation value is classically hard. These results reveal a feedback-driven complexity transition, with further implications for resource lower bounds on DLP and the complexity of local-observable estimation under area-law entanglement. Our results open a new route to quantum advantage with shallow quantum circuits.
Mid-circuit measurements with feedforward reduce the optimal worst-case quantum depth for exact n-qubit unitary synthesis from Θ(n) to O(1), using arbitrary one- and two-qubit gates and unrestricted ancillary space. Measurements and resets without feedforward remain subject to the circuit causal-cone bound. Our deterministic construction uses single-qubit measurements, O(1) rounds of parity feedforward, and O(n4nlog(n+2)) total qubits, with all ancillas starting and ending in ∣0⟩. Classical processing is not counted in quantum depth. We teleport only the matrix error of an approximation by Nehoran and Yuen. An exactly prepared ancillary state encodes this error, whose action is added back by coherent interference. At operator-norm error 2−n, one step of amplitude amplification suffices. Coherent fanout circuits achieve the same constant-depth bound, while circuits using only one- and two-qubit gates attain depth Θ(n) with O(4nlog2(n+2)) gates. Generic targets require Ω(4n/(h+1)) qubits at depth h, even under unrestricted classical control. Our depth-width trade-offs meet this bound within a factor O(n2) for 1≤h≤2n.