Learning low-degree quantum objects
Not on the map. Why?
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.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 10 of its 73 references that are in the map. First posted on arXiv 17 May 2024.
Builds on
10 of 73 references.
References · 10
- 2020Predicting Many Properties of a Quantum System from Very Few Measurementscited by 229
- 2016Efficient quantum tomography IIcited by 54
- 2022Learning to predict arbitrary quantum processescited by 34
- 2018The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulationcited by 30
- 2018Sample Efficient Algorithms for Learning Quantum Channels in PAC Model and the Approximate State Discrimination Problemcited by 16
- 2022Optimal algorithms for learning quantum phase statescited by 10
- 2018Two new results about quantum exact learningcited by 8
- 2021Learning low-degree functions from a logarithmic number of random queriescited by 8
- 2023Lower Bounds on Learning Pauli Channels with Individual Measurementscited by 5
- 2022Low-degree learning and the metric entropy of polynomialscited by 3
Built on by
Citing papers per year: 2024: 1; 2025: 1.
2 papers.