Quantum Circuit Lower Bounds in the Magic Hierarchy
We introduce the magic hierarchy, a quantum circuit model that alternates between arbitrary-sized Clifford circuits and constant-depth circuits with two-qubit gates (QNC0). This model unifies existing circuit models, such as QACf0 and models with adaptive intermediate measurements. Despite its generality, we are able to prove nontrivial lower bounds.
Authors
- Natalie Parham (ORCID: https://orcid.org/0000-0002-8792-1229)
Institutions
- Columbia University (US)
Publication Details
- Published
- 2026-06-09
- DOI
- https://doi.org/10.1145/3798129.3800788
- Primary Topic
- Quantum Computing Algorithms and Architecture
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- U.S. Department of Energy
- Simons Institute for the Theory of Computing, University of California Berkeley