Worst-case depth hierarchy for shallow quantum circuits
2026-06-15 • Computational Complexity
Computational Complexity
AI summaryⓘ
The authors study the power of very shallow quantum circuits (constant-depth circuits) and show that deeper circuits in this class can solve problems that shallower ones cannot, demonstrating a clear hierarchy. They create specific problems that require circuits at least a certain depth to succeed nearly perfectly, proving that adding even a small amount of depth increases computational ability. Their work also shows these quantum circuits outperform very shallow classical circuits on these problems. To do this, they develop new techniques linking quantum circuit depth to the ability to generate complicated quantum correlations, using ideas from group theory and nonlocal games.
quantum circuit depthQNC^0constant-depth circuitsnonlocal gamesquantum-classical separationmulti-controlled phase operationsoperator-valued constraint systemscircuit lower boundshierarchy theoremquantum advantage
Authors
Min-Hsiu Hsieh, Michael de Oliveira, Sathyawageeswar Subramanian, Xingjian Zhang
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.