# Learning unitaries with quantum statistical queries

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 84 references that are in the map.
- First posted on arXiv 3 Oct 2023.

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

- [Supervised quantum machine learning models are kernel methods](https://mlsanity.com/paper/2101.11020/) (2021)
- [Quantum noise protects quantum classifiers against adversaries](https://mlsanity.com/paper/2003.09416/) (2020)
- [Exponential separations between learning with and without quantum memory](https://mlsanity.com/paper/2111.05881/) (2021)
- [Out-of-distribution generalization for learning quantum dynamics](https://mlsanity.com/paper/2204.10268/) (2022)
- [Classical surrogates for quantum learning models](https://mlsanity.com/paper/2206.11740/) (2022)
- [Learning to predict arbitrary quantum processes](https://mlsanity.com/paper/2210.14894/) (2022)
- [Shadows of quantum machine learning](https://mlsanity.com/paper/2306.00061/) (2023)
- [Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix](https://mlsanity.com/paper/2212.04471/) (2022)
- [Quantum statistical query learning](https://mlsanity.com/paper/2002.08240/) (2020)
- [Quantum Local Differential Privacy and Quantum Statistical Query Model](https://mlsanity.com/paper/2203.03591/) (2022)
- [Optimal algorithms for learning quantum phase states](https://mlsanity.com/paper/2208.07851/) (2022)
- [Quantum Learning Boolean Linear Functions w.r.t. Product Distributions](https://mlsanity.com/paper/1902.08753/) (2019)
- [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)
- [Classical Verification of Quantum Learning](https://mlsanity.com/paper/2306.04843/) (2023)
- [On the Role of Entanglement and Statistics in Learning](https://mlsanity.com/paper/2306.03161/) (2023)

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

- [Barren Plateaus in Variational Quantum Computing](https://mlsanity.com/paper/2405.00781/) (2024)
- [Does provable absence of barren plateaus imply classical simulability?](https://mlsanity.com/paper/2312.09121/) (2023)
- [Learning the structure of any Hamiltonian from minimal assumptions](https://mlsanity.com/paper/2410.21635/) (2024)
- [A Quantum Tensor Network-Based Viewpoint for Modeling and Analysis of Time Series Data](https://mlsanity.com/paper/2511.13514/) (2025)
- [Noise-tolerant learnability of shallow quantum circuits from statistics and the cost of quantum pseudorandomness](https://mlsanity.com/paper/2405.12085/) (2024)

## Abstract (arXiv)

We propose several algorithms for learning unitary operators from quantum statistical queries with respect to their Choi-Jamiolkowski state. Quantum statistical queries capture the capabilities of a learner with limited quantum resources, which receives as input only noisy estimates of expected values of measurements. Our approach leverages quantum statistical queries to estimate the Fourier mass of a unitary on a subset of Pauli strings, generalizing previous techniques developed for uniform quantum examples. Specifically, we show that the celebrated quantum Goldreich-Levin algorithm can be implemented with quantum statistical queries, whereas the prior version of the algorithm involves oracle access to the unitary and its inverse. As an application, we prove that quantum Boolean functions with constant total influence or with constant degree are efficiently learnable in our model. Moreover, we prove that O(log n)-juntas are efficiently learnable and constant-depth circuits are learnable query-efficiently with quantum statistical queries. On the other hand, all previous algorithms for these tasks demand significantly greater resources, such as oracle access to the unitary or direct access to the Choi-Jamiolkowski state. We also demonstrate that, despite these positive results, quantum statistical queries lead to an exponentially larger query complexity for certain tasks, compared to separable measurements to the Choi-Jamiolkowski state. In particular, we show an exponential lower bound for learning a class of phase-oracle unitaries and a double exponential lower bound for testing the unitarity of channels. Taken together, our results indicate that quantum statistical queries offer a unified framework for various unitary learning tasks, with potential applications in quantum machine learning, many-body physics and benchmarking of near-term devices.