Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2305.20069

A survey on the complexity of learning quantum states

Anurag Anshu, Srinivasan Arunachalam

Published May 31, 2023• 3 citations
arXivHTMLPDF

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.

DOI
10.48550/arxiv.2305.20069

Related papers

Quantum Algorithms: A Survey of Applications and End-to-end Complexities

Alexander M. Dalzell, Sam McArdle, Mario Berta +10 more

The anticipated applications of quantum computers span across science and industry, ranging from quantum chemistry and many-body physics to optimization, finance, and machine learning. Proposed quantum solutions in these areas typically combine multiple quantum algorithmic primitives into an overall quantum algorithm, which must then incorporate the methods of quantum error correction and fault tolerance to be implemented correctly on quantum hardware. As such, it can be difficult to assess how much a particular application benefits from quantum computing, as the various approaches are often sensitive to intricate technical details about the underlying primitives and their complexities. Here we present a survey of several potential application areas of quantum algorithms and their underlying algorithmic primitives, carefully considering technical caveats and subtleties. We outline the challenges and opportunities in each area in an "end-to-end" fashion by clearly defining the problem being solved alongside the input-output model, instantiating all "oracles," and spelling out all hidden costs. We also compare quantum solutions against state-of-the-art classical methods and complexity-theoretic limitations to evaluate possible quantum speedups. The survey is written in a modular, wiki-like fashion to facilitate navigation of the content. Each primitive and application area is discussed in a standalone section, with its own bibliography of references and embedded hyperlinks that direct to other relevant sections. This structure mirrors that of complex quantum algorithms that involve several layers of abstraction, and it enables rapid evaluation of how end-to-end complexities are impacted when subroutines are altered.

arXiv:2310.03011•Oct 4, 2023•49 citations

Efficient learning of mixed-state tomography for photonic quantum walk

Qin-Qin Wang, Shaojun Dong, Xiao-Wei Li +7 more

Noise-enhanced applications in open quantum walk (QW) has recently seen a surge due to their ability to improve performance. However, verifying the success of open QW is challenging, as mixed-state tomography is a resource-intensive process, and implementing all required measurements is almost impossible due to various physical constraints. To address this challenge, we present a neural-network-based method for reconstructing mixed states with a high fidelity (∼97.5%) while costing only 50% of the number of measurements typically required for open discrete-time QW in one dimension. Our method uses a neural density operator that models the system and environment, followed by a generalized natural gradient descent procedure that significantly speeds up the training process. Moreover, we introduce a compact interferometric measurement device, improving the scalability of our photonic QW setup that enables experimental learning of mixed states. Our results demonstrate that highly expressive neural networks can serve as powerful alternatives to traditional state tomography.

arXiv:2411.03640•Science Advances•Mar 15, 2024•11 citations

The Quantum Learning Menagerie (A survey on Quantum learning for Classical concepts)

Sagnik Chatterjee

This paper surveys various results in the field of Quantum Learning theory, specifically focusing on learning quantum-encoded classical concepts in the Probably Approximately Correct (PAC) framework. The cornerstone of this work is the emphasis on query, sample, and time complexity separations between classical and quantum learning that emerge under learning with query access to different labeling oracles. This paper aims to consolidate all known results in the area under the above umbrella and underscore the limits of our understanding by leaving the reader with 23 open problems.

quant-pharXiv:2602.01054•Feb 3, 2026•0 citations

A survey of quantum learning

Richard Bonner, Rūsiņš Freivalds

We survey papers on problems of learning by quantum computers.The quest of quantum learning, as that of quantum computation,is to produce tractable quantum algorithms in situations, where tractable ...

•Jan 1, 2003•12 citations

A survey on the complexity of learning quantum states

Anurag Anshu, Srinivasan Arunachalam

Nature Reviews Physics•Dec 11, 2023•78 citations

Cloning is as Hard as Learning for Stabilizer States

Nikhil Bansal, Matthias C. Caro, Gaurav Mahajan

The impossibility of simultaneously cloning non-orthogonal states lies at the foundations of quantum theory. Even when allowing for approximation errors, cloning an arbitrary unknown pure state requires as many initial copies as needed to fully learn the state. Rather than arbitrary unknown states, modern quantum learning theory often considers structured classes of states and exploits such structure to develop learning algorithms that outperform general-state tomography. This raises the question: How do the sample complexities of learning and cloning relate for such structured classes? We answer this question for an important class of states. Namely, for $n$-qubit stabilizer states, we show that the optimal sample complexity of cloning is $Θ(n)$. Thus, also for this structured class of states, cloning is as hard as learning. To prove these results, we use representation-theoretic tools in the recently proposed Abelian State Hidden Subgroup framework and a new structured version of the recently introduced random purification channel to relate stabilizer state cloning to a variant of the sample amplification problem for probability distributions that was recently introduced in classical learning theory. This allows us to obtain our cloning lower bounds by proving new sample amplification lower bounds for classes of distributions with an underlying linear structure. Our results provide a more fine-grained perspective on No-Cloning theorems, opening up connections from foundations to quantum learning theory and quantum cryptography.

quant-pharXiv:2604.15269•Apr 17, 2026•0 citations
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.
The anticipated applications of quantum computers span across science and industry, ranging from quantum chemistry and many-body physics to optimization, finance, and machine learning. Proposed quantum solutions in these areas typically combine multiple quantum algorithmic primitives into an overall quantum algorithm, which must then incorporate the methods of quantum error correction and fault tolerance to be implemented correctly on quantum hardware. As such, it can be difficult to assess how much a particular application benefits from quantum computing, as the various approaches are often sensitive to intricate technical details about the underlying primitives and their complexities. Here we present a survey of several potential application areas of quantum algorithms and their underlying algorithmic primitives, carefully considering technical caveats and subtleties. We outline the challenges and opportunities in each area in an "end-to-end" fashion by clearly defining the problem being solved alongside the input-output model, instantiating all "oracles," and spelling out all hidden costs. We also compare quantum solutions against state-of-the-art classical methods and complexity-theoretic limitations to evaluate possible quantum speedups. The survey is written in a modular, wiki-like fashion to facilitate navigation of the content. Each primitive and application area is discussed in a standalone section, with its own bibliography of references and embedded hyperlinks that direct to other relevant sections. This structure mirrors that of complex quantum algorithms that involve several layers of abstraction, and it enables rapid evaluation of how end-to-end complexities are impacted when subroutines are altered.
Noise-enhanced applications in open quantum walk (QW) has recently seen a surge due to their ability to improve performance. However, verifying the success of open QW is challenging, as mixed-state tomography is a resource-intensive process, and implementing all required measurements is almost impossible due to various physical constraints. To address this challenge, we present a neural-network-based method for reconstructing mixed states with a high fidelity (∼97.5%) while costing only 50% of the number of measurements typically required for open discrete-time QW in one dimension. Our method uses a neural density operator that models the system and environment, followed by a generalized natural gradient descent procedure that significantly speeds up the training process. Moreover, we introduce a compact interferometric measurement device, improving the scalability of our photonic QW setup that enables experimental learning of mixed states. Our results demonstrate that highly expressive neural networks can serve as powerful alternatives to traditional state tomography.
This paper surveys various results in the field of Quantum Learning theory, specifically focusing on learning quantum-encoded classical concepts in the Probably Approximately Correct (PAC) framework. The cornerstone of this work is the emphasis on query, sample, and time complexity separations between classical and quantum learning that emerge under learning with query access to different labeling oracles. This paper aims to consolidate all known results in the area under the above umbrella and underscore the limits of our understanding by leaving the reader with 23 open problems.
The impossibility of simultaneously cloning non-orthogonal states lies at the foundations of quantum theory. Even when allowing for approximation errors, cloning an arbitrary unknown pure state requires as many initial copies as needed to fully learn the state. Rather than arbitrary unknown states, modern quantum learning theory often considers structured classes of states and exploits such structure to develop learning algorithms that outperform general-state tomography. This raises the question: How do the sample complexities of learning and cloning relate for such structured classes? We answer this question for an important class of states. Namely, for nnn-qubit stabilizer states, we show that the optimal sample complexity of cloning is Θ(n)Θ(n)Θ(n). Thus, also for this structured class of states, cloning is as hard as learning. To prove these results, we use representation-theoretic tools in the recently proposed Abelian State Hidden Subgroup framework and a new structured version of the recently introduced random purification channel to relate stabilizer state cloning to a variant of the sample amplification problem for probability distributions that was recently introduced in classical learning theory. This allows us to obtain our cloning lower bounds by proving new sample amplification lower bounds for classes of distributions with an underlying linear structure. Our results provide a more fine-grained perspective on No-Cloning theorems, opening up connections from foundations to quantum learning theory and quantum cryptography.