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(\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.
What would settle it
A proof of an exponential lower bound, or a construction with subexponential rank.
Results
No results have been posted on this problem yet.
Post a result · how results are checked
Sign in to follow or save this problem
Comments (0)
Comments are not records: they are not signed, stamped or logged. How comments work
No comments yet.
Sign in to comment.