QuICS Special Seminar: Dr. Ben Lee Volk

Tue, Jul 27, 2021 4:00 pm - 5:00 pm


Title: Lower Bounds on Stabilizer Rank
Speaker: Dr. Ben Lee Volk (The University of Texas at Austin)
Time: Tuesday, July 27, 2021 - 4:00pm
Location: Virtual Via Zoom: https://uwaterloo.zoom.us/j/99286649126?pwd=Zml0UjBQMzBCVWZlUGlqTDJkMzlIQT09

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.

Reference: Peleg, Shir, Amir Shpilka, and Ben Lee Volk. "Lower Bounds on Stabilizer Rank." arXiv preprint arXiv:2106.03214 (2021).

This talk is part of the IQC-QuICS Math and Computer Science Seminar.

Upcoming Events

3 Aug
JQI Special Seminar
Date Tue, Aug 3, 2021 9:30 am - 10:30 am
5 Aug
Gravity Theory Seminar
Thu, Aug 5, 2021 3:00 pm - 4:00 pm
10 Aug
QuICS Special Seminar
Tue, Aug 10, 2021 10:00 am - 11:00 am
30 Aug
JQI Seminar
Mon, Aug 30, 2021 11:00 am - 12:00 pm
7 Sep
Physics Colloquium
Tue, Sep 7, 2021 4:00 pm - 5:00 pm