Online learning of quantum states

DOI10.1088/1742-5468/AB3988MaRDI QIDQ5854122zbMATH OpenOpenAlexFDO

Authors Scott Aaronson, Xin Yi Chen, Elad Hazan, Satyen Kale, Ashwin Nayak

Publication date 16 March 2021

Published in Journal of Statistical Mechanics: Theory and Experiment (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.09025

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Computational learning theory (68Q32) Quantum measurement theory, state operations, state preparations (81P15)

Abstract: Suppose we have many copies of an unknown $n$-qubit state $ho$. We measure some copies of $ho$ 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 $sigm{a}_t$ about the state $ho$, using the outcomes of the previous measurements. We show that it is possible to do this in a way that guarantees that $|operatornameTr(E_{i}sigm{a}_t)-operatornameTr(E_{i}ho)|$, the error in our prediction for the next measurement, is at least $varepsilon$ at most $operatornameO!left(n/varepsilo{n}^{2}ight)$ 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 $operatornameO!left(sqrtTnight)$ 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.

Recommendations

• The learnability of quantum states
• Quantum learning: asymptotically optimal classification of qubit states
• Quantum learning algorithms for quantum measurements
• Optimal quantum sample complexity of learning algorithms
• Optimal quantum sample complexity of learning algorithms

Cites work

• A combinatorial, primal-dual approach to semidefinite programs
• A full characterization of quantum advice
• Dense quantum coding and quantum finite automata
• Efficient quantum tomography
• scientific article; zbMATH DE number 5957285 (Why is no real title available?)
• Limitations of Quantum Advice and One-Way Communication
• Online learning via sequential complexities
• Quantum state certification
• Sample-optimal tomography of quantum states
• Sequential decoding of a general classical-quantum channel
• Shadow tomography of quantum states
• The learnability of quantum states
• The multiplicative weights update method: a meta-algorithm and applications
• The theory of quantum information

Cited in

(12)

• An online optimization algorithm for the real-time quantum state tomography
• Robust online Hamiltonian learning
• scientific article; zbMATH DE number 6096711 (Why is no real title available?)
• The learnability of quantum states
• Quantum SDP solvers: large speed-ups, optimality, and applications to quantum learning
• Robust online Hamiltonian learning
• Time-Varying Semidefinite Programming: Path Following a Burer–Monteiro Factorization
• Quantum continual learning of quantum data realizing knowledge backward transfer
• Improved quantum data analysis
• Learning linear optical circuits with coherent states
• Quantum learning algorithms for quantum measurements
• Lower bounds for learning quantum states with single-copy measurements

This page was built for publication: Online learning of quantum states

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5854122)