{"id":"arxiv/2606.16425","url":"https://arxiv.org/abs/2606.16425","tags":["quant-ph","cs.CC"],"score":0,"title":"Worst-case depth hierarchy for shallow quantum circuits","domain":"quant-ph","source":"arxiv","authors":["Min-Hsiu Hsieh","Michael de Oliveira","Sathyawageeswar Subramanian","Xingjian Zhang"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-06-15","reactions":{}}