# Learning low-degree quantum objects

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 73 references that are in the map.
- First posted on arXiv 17 May 2024.

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

- [Predicting Many Properties of a Quantum System from Very Few Measurements](https://mlsanity.com/paper/2002.08953/) (2020)
- [Efficient quantum tomography II](https://mlsanity.com/paper/1612.00034/) (2016)
- [Learning to predict arbitrary quantum processes](https://mlsanity.com/paper/2210.14894/) (2022)
- [The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation](https://mlsanity.com/paper/1804.01973/) (2018)
- [Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problem](https://mlsanity.com/paper/1810.10938/) (2018)
- [Optimal algorithms for learning quantum phase states](https://mlsanity.com/paper/2208.07851/) (2022)
- [Two new results about quantum exact learning](https://mlsanity.com/paper/1810.00481/) (2018)
- [Learning low-degree functions from a logarithmic number of random queries](https://mlsanity.com/paper/2109.10162/) (2021)
- [Lower Bounds on Learning Pauli Channels with Individual Measurements](https://mlsanity.com/paper/2301.09192/) (2023)
- [Low-degree learning and the metric entropy of polynomials](https://mlsanity.com/paper/2203.09659/) (2022)

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

- [Quantum advantage for learning shallow neural networks with natural data distributions](https://mlsanity.com/paper/2503.20879/) (2025)
- [Predicting quantum channels over general product distributions](https://mlsanity.com/paper/2409.03684/) (2024)

## Abstract (arXiv)

We consider the problem of learning low-degree quantum objects up to varepsilon-error in ℓ2-distance. We show the following results: (i) unknown n-qubit degree-d (in the Pauli basis) quantum channels and unitaries can be learned using O(1/varepsilond) queries (independent of n), (ii) polynomials p:-1,1nrightarrow [-1,1] arising from d-query quantum algorithms can be classically learned from O((1/varepsilon)d· log n) many random examples (x,p(x)) (which implies learnability even for d=O(log n)), and (iii) degree-d polynomials p:-1,1n→ [-1,1] can be learned through O(1/varepsilond) queries to a quantum unitary Up that block-encodes p. Our main technical contributions are new Bohnenblust-Hille inequalities for quantum channels and completely bounded~polynomials.