Quantum circuit lower bounds in the magic hierarchy

Natalie Parham |  Columbia University

In this talk I’ll introduce the magic hierarchy, a quantum circuit model alternating between arbitrary Clifford circuits and constant-depth circuits with two-qubit gates (QNC0). This framework unifies several existing models, including those with adaptive measurements. I’ll present new lower bounds at the first level of the hierarchy and explain how extending these bounds above a certain level would imply major breakthroughs in classical complexity theory—making the hierarchy a natural testing ground for lower bound techniques.

In particular, I’ll show that certain explicit quantum states—such as ground states of topological Hamiltonians and non-stabilizer codes—cannot be approximately prepared by a Clifford circuit followed by QNC0. These proofs go beyond standard light cone arguments and reveal an infectiousness property: approximating even one state in a high-distance code forces the entire code space to lie near a perturbed stabilizer code. Based on this paper: Quantum circuit lower bounds in the magic hierarchy

Location