Center for Global Studies

View Full Calendar

Mehrdad Tahmasbi "Lower bounds on stabilizer rank"

Event Type
Illinois Computer Science
3401 Siebel Center for Computer Science
Oct 23, 2023   10:00 am  
Mehrdad Tahmasbi (UIUC)
Candice Steidinger
Originating Calendar
Computer Science Speakers Calendar

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. .

link for robots only