JQI

Abstract: The approximate stabilizer rank of a quantum state is the minimum number of terms in any approximate decomposition of that state into stabilizer states. We expect that the approximate stabilizer rank of n-th tensor power of the “magic” T state scale exponentially in n, otherwise there is a polynomial time classical algorithm to simulate arbitrary polynomial time quantum computations.  Despite this intuition, several attempts using various techniques could not lead to a better than a linear lower bound on the “exact” rank.