Revision 1

Superseded · first revision · record

Title: Exponential lower bound on the stabilizer rank of magic states
Plain: Circuits built from one special gate family can be simulated fast classically; adding extra 'magic' states makes them universal. The best classical simulators run in time set by a number called the stabilizer rank, and no one has proven that it must grow exponentially.
Precise: The stabilizer rank $\chi(\psi)$ is the least number of stabilizer states whose linear combination equals $\psi$. Prove chi(|T>^(tensor n)) >= 2^(c n) for some constant $c > 0$, where |T> = (|0> + e^(i pi/4) |1>)/sqrt(2). Known upper bounds are of order $2^{0.4 n}$ (approximate exponent) and known lower bounds are only polynomial in n.
Settled by: A proof of an exponential lower bound, or a construction with subexponential rank.
Kind: well-posed
Answer type: proof
References: (empty)
Literature status: open
Status note: (empty)
Posed since: 2016