# Learning quantum states and unitaries of bounded gate complexity

arXiv: https://arxiv.org/abs/2310.19882 · HTML: https://mlsanity.com/paper/2310.19882/

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 54 references that are in the map.
- First posted on arXiv 30 Oct 2023.

## Builds on (most cited first, 12 of 12)

- [Error bounds for approximations with deep ReLU networks](https://mlsanity.com/paper/1610.01145/) (2016)
- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Generalization in quantum machine learning from few training data](https://mlsanity.com/paper/2111.05292/) (2021)
- [Quantum advantage in learning from experiments](https://mlsanity.com/paper/2112.00778/) (2021)
- [Encoding-dependent generalization bounds for parametrized quantum circuits](https://mlsanity.com/paper/2106.03880/) (2021)
- [Out-of-distribution generalization for learning quantum dynamics](https://mlsanity.com/paper/2204.10268/) (2022)
- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [Pseudo-dimension of quantum circuits](https://mlsanity.com/paper/2002.01490/) (2020)
- [Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix](https://mlsanity.com/paper/2212.04471/) (2022)
- [Sample Complexity of Learning Parametric Quantum Circuits](https://mlsanity.com/paper/2107.09078/) (2021)
- [Transition Role of Entangled Data in Quantum Machine Learning](https://mlsanity.com/paper/2306.03481/) (2023)
- [Empirical Sample Complexity of Neural Network Mixed State Reconstruction](https://mlsanity.com/paper/2307.01840/) (2023)

## Built on by (most cited first, 15 of 15)

- [A Primer on Quantum Machine Learning](https://mlsanity.com/paper/2511.15969/) (2025)
- [Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits](https://mlsanity.com/paper/2408.12199/) (2024)
- [Learning the structure of any Hamiltonian from minimal assumptions](https://mlsanity.com/paper/2410.21635/) (2024)
- [Learning finitely correlated states: stability of the spectral reconstruction](https://mlsanity.com/paper/2312.07516/) (2023)
- [Entanglement-induced provable and robust quantum learning advantages](https://mlsanity.com/paper/2410.03094/) (2024)
- [Concept learning of parameterized quantum models from limited measurements](https://mlsanity.com/paper/2408.05116/) (2024)
- [Mildly-Interacting Fermionic Unitaries are Efficiently Learnable](https://mlsanity.com/paper/2504.11318/) (2025)
- [Separable Power of Classical and Quantum Learning Protocols Through the Lens of No-Free-Lunch Theorem](https://mlsanity.com/paper/2405.07226/) (2024)
- [No-Free-Lunch Theories for Tensor-Network Machine Learning Models](https://mlsanity.com/paper/2412.05674/) (2024)
- [Quantum circuit complexity and unsupervised machine learning of topological order](https://mlsanity.com/paper/2508.04486/) (2025)
- [Instance-Optimal Matrix Multiplicative Weight Update and Its Quantum Applications](https://mlsanity.com/paper/2509.08911/) (2025)
- [Noise-tolerant learnability of shallow quantum circuits from statistics and the cost of quantum pseudorandomness](https://mlsanity.com/paper/2405.12085/) (2024)
- [Few measurement shots challenge generalization in learning to classify entanglement](https://mlsanity.com/paper/2411.06600/) (2024)
- [Learning to erase quantum states: thermodynamic implications of quantum learning theory](https://mlsanity.com/paper/2504.07341/) (2025)
- [Physics-Aware Learnability: From Set-Theoretic Independence to Operational Constraints](https://mlsanity.com/paper/2603.00417/) (2026)

## Abstract (arXiv)

While quantum state tomography is notoriously hard, most states hold little interest to practically-minded tomographers. Given that states and unitaries appearing in Nature are of bounded gate complexity, it is natural to ask if efficient learning becomes possible. In this work, we prove that to learn a state generated by a quantum circuit with G two-qubit gates to a small trace distance, a sample complexity scaling linearly in G is necessary and sufficient. We also prove that the optimal query complexity to learn a unitary generated by G gates to a small average-case error scales linearly in G. While sample-efficient learning can be achieved, we show that under reasonable cryptographic conjectures, the computational complexity for learning states and unitaries of gate complexity G must scale exponentially in G. We illustrate how these results establish fundamental limitations on the expressivity of quantum machine learning models and provide new perspectives on no-free-lunch theorems in unitary learning. Together, our results answer how the complexity of learning quantum states and unitaries relate to the complexity of creating these states and unitaries.