Quantum Circuit Lower Bounds in the Magic Hierarchy
Natalie Parham · 2026
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.