We look forward to seeing you in person in 3401 Siebel Center on Monday, 10/23.
Abstract: The stabilizer rank of a quantum state is the minimum number of terms in any approximate decomposition of that state into stabilizer states. Bravyi and Gosset showed that the approximate stabilizer rank of a so-called magic state, up to polynomial factors, is an upper bound on the number of classical operations required to simulate an arbitrary quantum circuit. As a result, an exponential lower bound on this quantity seems inevitable. Despite this intuition, several attempts using various techniques could not lead to a better than linear lower bound. In this talk, I will introduce a quadratic lower bound on the approximate rank of magic states for a wide range of approximation parameters. An immediate corollary of our result is the existence of polynomial time computable functions that require a super-linear number of terms in any decomposition into exponentials of quadratic forms over finite fields of size 2. Our approach is based on a strong lower bound on the approximate rank of a quantum state sampled from the Haar measure, a step-by-step analysis of the approximate rank of a magic-state teleportation protocol to sample from the Haar measure, and a result about trading Clifford operations with T gates.
Joint work with Saeed Mehraban. https://arxiv.org/abs/2305.10277 .
