Description
Circuit depth is a fundamental computational resource. In quantum computing, it serves as a direct proxy for the computational execution time before noise and decoherence dominate. A central question in (quantum) computation is whether increasing circuit depth strictly unlocks greater computational power. While crucial for designing scalable architectures, proving such a hierarchy unconditioned on unproven assumptions has remained a major open challenge.
In this work, we present an unconditional depth hierarchy theorem for shallow quantum circuits (circuit class $\mathsf{QNC}^0$), which is the first of its kind in quantum computation. For any depth $d \ge 12$, we construct a family of two-round interactive problems that no depth-$(d-1)$ quantum circuit can solve with near-perfect success, regardless of gate set, size, or ancillas. In contrast, we construct simple quantum circuits of depth just slightly larger than $d$ to solve these problems perfectly. Crucially, these problems are inherently quantum: all classical circuits of sublogarithmic depth fail them entirely, yielding a robust hierarchy of unconditional quantum advantage. To achieve this, we introduce a framework combining unitary synthesis and group-theoretic techniques to analyse how depth constrains a circuit’s ability to generate fine-grained nonlocal correlations.
Beyond the complexity-theoretic breakthrough, our findings offer immediate practical utility for experimental physics:
1. Coherence Benchmarking: Because depth maps to synchronous timesteps, this hierarchy provides a rigorous, classically verifiable benchmark for a device's effective coherence time.
2. Resource Tracking: The framework links depth certification to the scaling of non-Clifford resources—the core ingredient for universal quantum computation.
With a calibrated noise robustness analysis, this verification protocol is highly compatible with noisy intermediate-scale quantum (NISQ) and early fault-tolerant devices. We anticipate our work shall provide an explicit, hardware-accessible route towards establishing universal quantum advantages.
Manuscript reference: https://arxiv.org/abs/2606.16425
| I am the presenting author | Yes |
|---|