Quantum circuit lower bounds in the magic hierarchy
Natalie Parham · 2025
Read Quantum circuit lower bounds in the magic hierarchy by Natalie Parham (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-19966.txt.
Introduction
Natalie Parham proves in a 2025 paper new lower bounds for quantum circuits in a model she names the magic hierarchy. The model alternates big Clifford blocks with shallow two qubit layers. It swallows several known circuit models, including ones with mid course measures.
Despite that breadth, some explicit quantum states defy preparation by its first level circuits. Blocked states include ground states of topologically ordered matter and non stabilizer code states. The proof leans on the rigid shape of stabilizer codes and a spread effect she defines. If one high distance code state were easy, the whole code space would sit near a stabilizer code. Pushing bounds higher would force classical bounds past current reach, she shows.
Catalog record
| CREATOR | Natalie Parham |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 176 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-19966
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Quantum circuit lower bounds in the magic hierarchy Natalie Parham Abstract We introduce the magic hierarchy , a quantum circuit model that alternates between arbitrary-sized Clifford circuits and constant-depth circuits with two-qubit gates ( QNC 0 \textsf{QNC}^{0} ). This model unifies existing circuit models, such as 𝖰𝖠𝖢 f 0 \mathsf{QAC}^{0}_{f} and models with adaptive intermediate measurements. Despite its generality, we are able to prove nontrivial lower bounds. We prove new lower bounds in the first level of the hierarchy, showing that certain explicit quantum states cannot be approximately prepared by circuits consisting of a Clifford circuit followed by QNC 0 \textsf{QNC}^{0} . These states include ground states of some topologically ordered Hamiltonians and nonstabilizer quantum codes. Our techniques exploit the rigid structure of stabilizer codes and introduce an infectiousness property: if even a single state in a high distance code can be approximately prepared by one of these circuits, then the entire subspace must lie close to a perturbed stabilizer code. We also show that proving state preparation lower bounds beyond a certain level of the hierarchy would imply classical circuit lower bounds beyond the reach of current techniques in complexity theory. More broadly, our techniques go beyond lightcone-based methods and highlight how the magic hierarchy provides a natural framework for connecting circuit complexity, condensed matter, and Hamiltonian complexity. 1 Introduction Understanding the limitations of quantum circuits is a central question at the intersection of quantum computing and many-body physics. A quantum circuit lower bound means proving that a certain class of circuits cannot perform a specific task— such as preparing a target state \ket{\psi} or implementing a unitary U . Classical circuit lower bounds have led to breakthroughs across theoretical computer science, establishing deep connections to pseudorandomness [ RR94 , Bra08 ] and learning theory [ CIKK16 , OS16 , LMN93 ] . Furthermore, quantum circuit lower bounds have interesting implications for fundamental questions in quantum matter. In condensed matter physics, circuit depth provides a notion of equivalence between quantum phases: states in the same phase can be connected by shallow circuits, while lower bounds indicate phase transitions or topological order [ CGW10 , CPG19 ] . In Hamiltonian complexity, if no low energy states of a Hamiltonian can be prepared within a certain circuit class, it suggests long-range entanglement beyond the circuit’s expressive power, pointing to exotic quantum phases that persist even at higher temperatures [ Nir22 ] . A key challenge is developing techniques beyond the lightcone argument . This principle originates as Lieb-Robinson bounds in many-body physics [ LR72 ] , which formalizes the idea that quantum information propagates at a limited speed through local interactions, reaching only regions within its lightcone . Constant-depth quantum circuits with local gates ( \mathsf{QNC}^{0} circuits) have lightcones of constant size, severely limiting their computational power. Any two regions with nonintersecting backwards lightcones can not be more entangled than their backwards lightcones on the input state. Thus globally entangled states such as the n -qubit CAT state \frac{1}{\sqrt{2}}(\ket{0^{n}}+\ket{1^{n}}) cannot be prepared by constant depth circuits starting from the unentangled \ket{0^{n}} state. In contrast, nonlocal circuits — such as those with logarithmic-depth, or many-qubit gates— have unbounded lightcones, making the argument ineffective for proving lower bounds. Figure 1: A (backwards) lightcone of a qubit. The lightcone argument can also be used to prove lower bounds for classical circuits with local gates, so long as the depth is below \log(n) . Any output bit of the circuit can only depend on the inputs in its backwards lightcone. Again, once the circuit depth is logarithmic, the lightcone argument is no longer useful. In fact, proving lower bounds against O(\log n) -depth classical circuits, \mathsf{NC}^{1} , remains a major open problem in complexity theory. However, in the classical world, we have been able to push beyond the lightcone argument with circuits that have unbounded lightcones but are still more restricted than \mathsf{NC}^{1} circuits. A prominent example is \mathsf{AC}^{0} circuits— boolean circuits of constant depth with AND and OR gates that are allowed arbitrarily many input bits, or “unbounded fan-in”. Thus the outputs of the circuit can depend on all inputs, rendering the lightcone argument useless. Despite this, the structure of the model has enabled the development of powerful lower bound techniques, such as random restrictions [ FSS84 , Hås86 ] , Fourier analysis [ LMN93 ] , and combinatorial methods [ Smo87 ] . These tools have yielded strong lower bounds and insights across complexity theory [ FSS84 , RST15 ] , pseudorandomness [ CHLT18 , Bra08 , CHHL19 ] , learning theory [ KM93 , EIS22 , KKMS08 ] , quantum-classical separations [ RT22 ] , and more. The success in going beyond lightcone arguments in classical complexity theory can be attributed to three key aspects of the \mathsf{AC}^{0} model: it is useful , as lower bounds are actually provable; interesting , due to its connections to broader areas of complexity theory and computation; and natural , as it generalizes constant-depth boolean circuits and models parallel computation. In the quantum setting, there has been some effort towards adapting techniques that were successful for proving classical \mathsf{AC}^{0} lower bounds. In 1999 Moore proposed a quantum analogue, \mathsf{QAC}^{0} , constant depth quantum circuits with arbitrary single qubit gates and the multi-qubit quantum AND gate \ket{x}\to(-1)^{\textsf{AND}(x)}\ket{x} [ Moo99 ] . While it resembles \mathsf{AC}^{0} , \mathsf{QAC}^{0} has resisted the application of classical techniques— such as random restrictions or Fourier methods— that underlie many classical lower bounds. Recent work has adapted Fourier analytic methods to quantum circuits [ NPVY24 ] , mirroring [ LMN93 ] , though these methods have not yet yielded lower bounds as strong as those known classically. To date, lower bounds for \mathsf{QAC}^{0} have only been established for depth-two circuits [ PFGT20 , Ros21 ] or models with few ancilla qubits [ FFG+03 , NPVY24 , ADOY24 ] . The difficulty of proving lower bounds for \mathsf{QAC}^{0} suggests the need for a circuit model that’s expressive— capable, for example, of generating global entanglement — but is more tractable to analyze. In this work, we introduce the magic hierarchy, a quantum circuit model consisting of circuits that alternate between arbitrary-size Clifford circuits and constant-depth circuits with arbitrary two-qubit gates ( \mathsf{QNC}^{0} ). We define the k th level of the magic hierarchy as circuits alternating k times between Clifford and \mathsf{QNC}^{0} circuits. The level in the hierarchy reflects increasing complexity of long-range magic —that is, nonstabilizerness that cannot be removed with a low-depth circuit [ WL25 ] — hence the name In this paper we aim to demonstrate that, just like the classical \mathsf{AC}^{0} model, the magic hierarchy is interesting, useful, and natural: Useful: We demonstrate the usefulness of the magic hierarchy by proving lower bounds at its first level, pushing beyond existing lower bounds. Our techniques exploit the rigid structure of both Clifford and \mathsf{QNC}^{0} circuits. While each of these circuit models is individually well-understood, their respective analysis tools—such as stabilizer methods for Clifford circuits and lightcone arguments for \mathsf{QNC}^{0} — do not extend naturally to the other. This tension necessitates the development of novel approaches to establish lower bounds. Interesting: We highlight interesting connections between the magic hierarchy and condensed matter physics,