Worst-case depth hierarchy for shallow quantum circuits

• URL: http://arxiv.org/abs/2606.16425v1
• Date: Mon, 15 Jun 2026 09:02:29 GMT
• Title: Worst-case depth hierarchy for shallow quantum circuits
• Abstract summary: We prove an explicit depth hierarchy theorem for $mathsfQNC0$.<n>For each $dge 12$, we construct a family of two-round interactive problems on which no depth-$(d-1)$ quantum circuit can achieve near-perfect success.<n>We show that increasing depth strictly increases computational power within $mathsfQNC0$, establishing a genuinely quantum hierarchy.
• Score: 8.32379529009722
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Verifiable quantum advantage in extremely low depth [52.51019642214249]
  We give a problem that is solvable by shallow quantum circuits, hard for computation in time under lattice-based assumptions.<n>We prove that shallow quantum circuits have sufficient structure to solve certain classically hard tasks whose solutions can be verified efficiently.
  arXiv  Detail & Related papers  (2026-09-01T15:54:34Z)
• Circuit complexity lower bounds for quantum spin glasses [1.2604738912025477]
  We study the circuit complexity of states arising from standard many-body models.<n>We show that entanglement needed to close the product-state gap cannot be generated at shallow depth.<n>Our results give an obstruction in the spirit of the No Low-Energy Trivial States problem of Freedman and Hastings (arXiv:1301.1363)
  arXiv  Detail & Related papers  (2026-07-15T21:56:01Z)
• Exact Quantum Circuit Optimization is co-NQP-hard [4.554892610576937]
  We consider the natural problem of, given a circuit $C$, computing an equivalent circuit $C'$ that minimizes a quantum resource type.<n>We show that, when $C$ is expressed over any gate set that can implement the H and TOF gates exactly, each of the above optimization problems is hard for $textco-NQP$.
  arXiv  Detail & Related papers  (2025-10-18T09:31:23Z)
• Learning Circuits with Infinite Tensor Networks [0.4972323953932129]
  Hamiltonian simulation on quantum computers is constrained by gate counts, motivating techniques to reduce circuit depths.<n>We leverage tensor networks to support circuit design, with datasets of tensor networks enabling a unitary synthesis inspired by quantum machine learning.<n>Our approach finds circuits to efficiently prepare ground states, and perform time evolution on both infinite and finite systems.
  arXiv  Detail & Related papers  (2025-06-02T18:00:01Z)
• Deep Circuit Compression for Quantum Dynamics via Tensor Networks [0.4972323953932129]
  We present a compilation algorithm for generating compressed circuits enabling real-time simulation on digital quantum computers.<n>For a given depth, the algorithm is more accurate than all Trotterizations of the same depth.<n>We demonstrate this by compiling a 52-qubit 2D Transverse-Field Ising propagator onto the IBM Heavy-Hex topology.
  arXiv  Detail & Related papers  (2024-09-24T18:00:05Z)
• The power of shallow-depth Toffoli and qudit quantum circuits [3.212381039696143]
  One of the main goals of quantum circuit complexity is to find problems that can be solved by quantum shallow circuits but require more computational resources classically. We prove new separations between classical and quantum constant-depth circuits. In the infinite-size gateset case, these quantum circuit classes for higher-dimensional Hilbert spaces do not offer any advantage to standard qubit implementations.
  arXiv  Detail & Related papers  (2024-04-28T07:44:27Z)
• A single $T$-gate makes distribution learning hard [56.045224655472865]
  This work provides an extensive characterization of the learnability of the output distributions of local quantum circuits. We show that for a wide variety of the most practically relevant learning algorithms -- including hybrid-quantum classical algorithms -- even the generative modelling problem associated with depth $d=omega(log(n))$ Clifford circuits is hard.
  arXiv  Detail & Related papers  (2022-07-07T08:04:15Z)
• Escaping from the Barren Plateau via Gaussian Initializations in Deep Variational Quantum Circuits [63.83649593474856]
  Variational quantum circuits have been widely employed in quantum simulation and quantum machine learning in recent years.<n>However, quantum circuits with random structures have poor trainability due to the exponentially vanishing gradient with respect to the circuit depth and the qubit number.<n>This result leads to a general standpoint that deep quantum circuits would not be feasible for practical tasks.
  arXiv  Detail & Related papers  (2022-03-17T15:06:40Z)
• Toward Trainability of Deep Quantum Neural Networks [87.04438831673063]
  Quantum Neural Networks (QNNs) with random structures have poor trainability due to the exponentially vanishing gradient as the circuit depth and the qubit number increase. We provide the first viable solution to the vanishing gradient problem for deep QNNs with theoretical guarantees.
  arXiv  Detail & Related papers  (2021-12-30T10:27:08Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• On estimating the entropy of shallow circuit outputs [49.1574468325115]
  Estimating the entropy of probability distributions and quantum states is a fundamental task in information processing. We show that entropy estimation for distributions or states produced by either log-depth circuits or constant-depth circuits with gates of bounded fan-in and unbounded fan-out is at least as hard as the Learning with Errors problem.
  arXiv  Detail & Related papers  (2020-02-27T15:32:08Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.