Tight bounds for Quantum Learning and Testing without Quantum Memory

IQC-QuICS Math-CS Seminar

Jerry Li (Microsoft Research)
Thursday, August 18, 2022 - 2:00pm
Virtual Via Zoom

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