A survey on the complexity of learning quantum states

2023/05/31 by Anurag Anshu, Srinivasan Arunachalam, Anshu, Anurag +1 · 21 citations
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Quantum Computing Algorithms and Architecture #Quantum Information and Cryptography #Quantum Physics (quant-ph)

paper · pdf · doi:10.48550/arxiv.2305.20069

openalex publication_date 2023/05/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We survey various recent results that rigorously study the complexity of learning quantum states. These include progress on quantum tomography, learning physical quantum states, alternate learning models to tomography and learning classical functions encoded as quantum states. We highlight how these results are paving the way for a highly successful theory with a range of exciting open questions. To this end, we distill 25 open questions from these results.

Cited by

• Optimal learning of quantum channels in diamond distance
• Optimal Distributed Similarity Estimation of Quantum Channels
• A Provably Efficient Method for Tensor Ring Decomposition and Its Applications
• Simulating Clifford Circuits with Gaussian Elimination
• Efficient state estimation on quantum processors
• The complexity of perfect quantum state classification
• Statistical phase-space complexity of continuous-variable quantum channels
• Efficient Matrix Product State Learning in Logarithmic Depth
• Learning stabilizer structure of quantum states
• Efficient learning of bosonic Gaussian unitaries
• AiDE-Q: Synthetic Labeled Datasets Can Enhance Learning Models for Quantum Property Estimation
• Quantum State Tomography for Tensor Networks in Two Dimensions
• Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications
• Artificial intelligence for representing and characterizing quantum systems
• Energy-independent tomography of Gaussian states
• Amplitude amplification and estimation require inverses
• State-Based Classical Shadows
• Online Quantum State Tomography via Stochastic Gradient Descent
• The abelian state hidden subgroup problem: Learning stabilizer groups and beyond
• Variational Gibbs state preparation on trapped-ion devices
• Experimental Quantum Tomography of Multimode Gaussian States

Related

• Learning marginals suffices!
• Online Learning of Pure States is as Hard as Mixed States
• Experimental learning of quantum states
• Private learning implies quantum stability
• New Bounds on Quantum Sample Complexity of Measurement Classes