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. For the “approximate” rank, which is more realistically related to the cost of simulating quantum circuits, no lower bound better than Ω(sqrt(n)) was known. In this talk I will present my result with Mehrdad Tahmasbi (STOC 24, QIP 24) in which we improve the lower bound on the approximate rank to (nearly) quadratic for a wide range of the approximation parameters. I will discuss connections with other problems in quantum information and computational complexity. 

*We strongly encourage attendees to use their full name (and if possible, their UMD credentials) to join the zoom session.*