# Noise-tolerant learnability of shallow quantum circuits from statistics and the cost of quantum pseudorandomness

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 26 of its 62 references that are in the map.
- First posted on arXiv 20 May 2024.

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

- [Online Learning of Quantum States](https://mlsanity.com/paper/1802.09025/) (2018)
- [Learning to predict arbitrary quantum processes](https://mlsanity.com/paper/2210.14894/) (2022)
- [Reformulation of the No-Free-Lunch Theorem for Entangled Data Sets](https://mlsanity.com/paper/2007.04900/) (2020)
- [A General Characterization of the Statistical Query Complexity](https://mlsanity.com/paper/1608.02198/) (2016)
- [Learning shallow quantum circuits](https://mlsanity.com/paper/2401.10095/) (2024)
- [Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problem](https://mlsanity.com/paper/1810.10938/) (2018)
- [Learning quantum states and unitaries of bounded gate complexity](https://mlsanity.com/paper/2310.19882/) (2023)
- [Classical Shadows With Noise](https://mlsanity.com/paper/2011.11580/) (2020)
- [On the average-case complexity of learning output distributions of quantum circuits](https://mlsanity.com/paper/2305.05765/) (2023)
- [On the Hardness of PAC-learning Stabilizer States with Noise](https://mlsanity.com/paper/2102.05174/) (2021)
- [Query-optimal estimation of unitary channels in diamond distance](https://mlsanity.com/paper/2302.14066/) (2023)
- [Quantum hardness of learning shallow classical circuits](https://mlsanity.com/paper/1903.02840/) (2019)
- [Tight bounds on Pauli channel learning without entanglement](https://mlsanity.com/paper/2309.13461/) (2023)
- [Cryptography from Pseudorandom Quantum States](https://mlsanity.com/paper/2112.10020/) (2021)
- [Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom](https://mlsanity.com/paper/2209.14530/) (2022)
- [Unifying (Quantum) Statistical and Parametrized (Quantum) Algorithms](https://mlsanity.com/paper/2310.17716/) (2023)
- [Lower Bounds on Learning Pauli Channels with Individual Measurements](https://mlsanity.com/paper/2301.09192/) (2023)
- [On the Role of Entanglement and Statistics in Learning](https://mlsanity.com/paper/2306.03161/) (2023)
- [Pseudorandom unitaries are neither real nor sparse nor noise-robust](https://mlsanity.com/paper/2306.11677/) (2023)
- [Learning unitaries with quantum statistical queries](https://mlsanity.com/paper/2310.02254/) (2023)
- [Learning Quantum Processes with Quantum Statistical Queries](https://mlsanity.com/paper/2310.02075/) (2023)
- [Quantum Pseudorandomness and Classical Complexity](https://mlsanity.com/paper/2103.09320/) (2021)
- [Quantum Cryptography in Algorithmica](https://mlsanity.com/paper/2212.00879/) (2022)
- [Simple constructions of linear-depth t-designs and pseudorandom unitaries](https://mlsanity.com/paper/2404.12647/) (2024)
- [Efficient unitary designs and pseudorandom unitaries from permutations](https://mlsanity.com/paper/2404.16751/) (2024)
- [Applications of Machine Learning in Cryptography: A Survey](https://mlsanity.com/paper/1902.04109/) (2019)

## Abstract (arXiv)

In this work, we study the learnability of quantum circuits in the near term. We demonstrate the natural robustness of quantum statistical queries for learning quantum processes, motivating their use as a theoretical tool for near-term learning problems. We adapt a learning algorithm for constant-depth quantum circuits to the quantum statistical query setting, and show that such circuits can be learned in our setting with only a linear overhead in the query complexity. We prove average-case quantum statistical query lower bounds for learning, within diamond distance, random quantum circuits with depth at least logarithmic and at most linear in the system size. Finally, we prove that pseudorandom unitaries (PRUs) cannot be constructed using circuits of constant depth by constructing an efficient distinguisher using existing learning algorithms. To show the correctness of our distinguisher, we prove a new variation of the quantum no free lunch theorem.