Microsoft Research Seminar • Algorithms and Complexity • Tight bounds for Quantum Learning and Testing without Quantum MemoryExport this event to calendar

Thursday, August 18, 2022 — 2:00 PM to 3:00 PM EDT

Please note: This seminar will take place in-person and online.

Jerry Li, Microsoft Research
Institute for Quantum Computing

In this talk, we consider two fundamental tasks in quantum state estimation, namely, quantum tomography and quantum state certification. In the former, we are given n copies of an unknown mixed state rho, and the goal is to learn it to good accuracy in trace norm. In the latter, the goal is to distinguish if rho is equal to some specified state, or far from it. When we are allowed to perform arbitrary (possibly entangled) measurements on our copies, then the exact sample complexity of these problems is well-understood. However, arbitrary measurements are expensive, especially in terms of quantum memory, and impossible to perform on near-term devices. In light of this, a recent line of work has focused on understanding the complexity of these problems when the learner is restricted to making incoherent (aka single-copy) measurements, which can be performed much more efficiently, and crucially, capture the set of measurements that can be performed without quantum memory. However, characterizing the copy complexity of such algorithms has proven to be a challenging task, and closing this gap has been posed as an open question in various previous papers.

In this talk, we give tight bounds on the sample complexity of these problems. More specifically, we show improved lower bounds for both problems which (essentially) match the existing upper bounds in the literature. Our techniques for both problems are based on new reductions to matrix martingale concentration which we believe may be of independent interest.


To join this seminar on Zoom, please go to https://uwaterloo.zoom.us/j/94331500184?pwd=NjUxOE81OVJSSWdoeEltai9MRkNVUT09.

Location 
QNC - Quantum Nano Centre
QNC 1201
200 University Avenue West

Waterloo, ON N2L 3G1
Canada
Event tags 

S M T W T F S
25
26
27
28
29
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
6
  1. 2024 (80)
    1. April (8)
    2. March (22)
    3. February (25)
    4. January (25)
  2. 2023 (296)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (25)
    5. August (30)
    6. July (30)
    7. June (22)
    8. May (23)
    9. April (32)
    10. March (31)
    11. February (18)
    12. January (22)
  3. 2022 (245)
  4. 2021 (210)
  5. 2020 (217)
  6. 2019 (255)
  7. 2018 (217)
  8. 2017 (36)
  9. 2016 (21)
  10. 2015 (36)
  11. 2014 (33)
  12. 2013 (23)
  13. 2012 (4)
  14. 2011 (1)
  15. 2010 (1)
  16. 2009 (1)
  17. 2008 (1)