Revision 2

Accepted · core change · record

Changes against revision 1:

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 · changed · core: Revision 1: 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.; Revision 2: The stabilizer rank $\chi(\psi)$ is the least number of stabilizer states whose linear combination equals $\psi$. Prove $\chi(\left|T\right>^{\otimes n}) \ge 2^{c n}$ for some constant $c > 0$, where $\left|T\right> = (\left|0\right> + e^{i \pi/4} \left|1\right>)/\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

Decisions