QI In the literature: open

Exponential lower bound on the stabilizer rank of magic states

In plain words

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 statement

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.

What would settle it

A proof of an exponential lower bound, or a construction with subexponential rank.