Lower Bounds on Stabilizer Rank
Dr. Ben Lee Volk, The University of Texas at Austin
The stabilizer rank of a quantum state ψ is the minimal integer r such that ψ can be written as a linear combination of r stabilizer states. The running time of several classical simulation methods for quantum circuits is determined by the stabilizer rank of the n-th tensor power of single-qubit magic states.
In this talk we'll present a recent improved lower bound of Ω(n) on the stabilizer rank of such states, and an Ω(sqrt{n}/log n) lower bound on the rank of any state which approximates them to a high enough accuracy.
Our techniques rely on the representation of stabilizer states as quadratic functions over affine subspaces of the boolean cube, along with some tools from computational complexity theory.
Based on a joint work with Shir Peleg and Amir Shpilka: https://arxiv.org/abs/2106.03214
Join the seminar on Zoom!
Meeting link: https://uwaterloo.zoom.us/j/99286649126?pwd=Zml0UjBQMzBCVWZlUGlqTDJkMzlIQT09
Add event to calendar
Apple Google Office 365 Outlook Outlook.com Yahoo
This virtual seminar is jointly sponsored by the Institute for Quantum Computing and the Joint Center for Quantum Information and Computer Science.
If you are interested in presenting at a future seminar, please email either Daniel Grier (daniel.grier@uwaterloo.ca) or Hakop Pashayan (hpashaya@uwaterloo.ca).