Depth hierarchy theorem proves increasing depth strictly increases power in constant-depth quantum circuits

Summary

This paper proves an explicit depth hierarchy theorem for QNC^0 (constant-depth quantum circuits). For each depth d ≥ 12, the authors construct two-round interactive problems that depth-(d-1) quantum circuits cannot solve with near-perfect success, regardless of gate set, circuit size, or ancillary qubits. The construction can be realized by slightly deeper quantum circuits. Additionally, all bounded fan-in classical circuits of sublogarithmic depth fail on these tasks, demonstrating unconditional quantum advantage of QNC^0 over NC^0. The work develops new lower bound techniques by analyzing how depth affects a circuit's ability to realize nonlocal correlations, using constraint systems and nonlocal games to translate group-theoretic constructions into depth lower bounds.