National Center for Supercomputing Applications master calendar

View Full Calendar

NCSA staff who would like to submit an item for the calendar can email

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