Online Learning of Quantum States

Abstract

Suppose we have many copies of an unknown $n$-qubit state $\rho$. We measure some copies of $\rho$ using a known two-outcome measurement $E_1$, then other copies using a measurement $E_2$, and so on. At each stage $t$, we generate a current hypothesis ${\sigma }_t$ about the state $\rho$, using the outcomes of the previous measurements. We show that it is possible to do this in a way that guarantees that $|\mathrm{Tr}(E_i{\sigma }_t)-\mathrm{Tr}(E_i\rho )|$, the error in our prediction for the next measurement, is at least $\epsilon$ at most $O\left(n/{\epsilon }^2\right)$ times. Even in the "non-realizable" setting---where there could be arbitrary noise in the measurement outcomes---we show how to output hypothesis states that do significantly worse than the best possible states at most $O\left(\sqrt{Tn}\right)$ times on the first $T$ measurements. These results generalize a 2007 theorem by Aaronson on the PAC-learnability of quantum states, to the online and regret-minimization settings. We give three different ways to prove our results---using convex optimization, quantum postselection, and sequential fat-shattering dimension---which have different advantages in terms of parameters and portability.

18 pages

References in corpus (5)

• Sample-optimal tomography of quantum states
• Limitations of Quantum Advice and One-Way Communication
• Quantum union bounds for sequential projective measurements
• Sequential decoding of a general classical-quantum channel
• The Learnability of Quantum States

Cited by in corpus (16)

• Fermionic partial tomography via classical shadows
• Experimental Estimation of Quantum State Properties from Classical Shadows
• Beyond Quantum Noise Spectroscopy: modelling and mitigating noise with quantum feature engineering
• Flexible learning of quantum states with generative query neural networks
• Faster quantum and classical SDP approximations for quadratic binary optimization
• Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix
• Limitations of optimization algorithms on noisy quantum devices
• Multi-armed quantum bandits: Exploration versus exploitation when learning properties of quantum states
• On the Hardness of PAC-learning Stabilizer States with Noise
• Exponential learning advantages with conjugate states and minimal quantum memory
• Lower Bounds for Learning Quantum States with Single-Copy Measurements
• Time-Varying Semidefinite Programming: Path Following a Burer-Monteiro Factorization
• Efficient Quantum State Tracking in Noisy Environments
• Learning quantum graph states with product measurements
• Adaptive Online Learning of Quantum States
• Quantum Learning Theory Beyond Batch Binary Classification