IQC-QuICS Math and Computer Science SeminarExport this event to calendar

Tuesday, July 27, 2021 — 4:00 PM EDT

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

S M T W T F S
25
26
27
28
29
30
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
  1. 2021 (44)
    1. November (1)
    2. October (5)
    3. September (3)
    4. August (4)
    5. July (4)
    6. June (5)
    7. May (3)
    8. April (4)
    9. March (5)
    10. February (4)
    11. January (6)
  2. 2020 (31)
    1. December (2)
    2. November (5)
    3. October (4)
    4. September (3)
    5. August (2)
    6. June (4)
    7. April (1)
    8. March (3)
    9. February (5)
    10. January (2)
  3. 2019 (139)
  4. 2018 (142)
  5. 2017 (131)
  6. 2016 (88)
  7. 2015 (82)
  8. 2014 (94)
  9. 2013 (91)
  10. 2012 (122)
  11. 2011 (117)
  12. 2010 (41)
  13. 2009 (4)
  14. 2008 (1)
  15. 2005 (1)
  16. 2004 (3)