# Optimal algorithms for learning quantum phase states

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Aug 2022.

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

- [A survey on the complexity of learning quantum states](https://mlsanity.com/paper/2305.20069/) (2023)
- [Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates](https://mlsanity.com/paper/2305.13409/) (2023)
- [Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom](https://mlsanity.com/paper/2209.14530/) (2022)
- [On the Role of Entanglement and Statistics in Learning](https://mlsanity.com/paper/2306.03161/) (2023)
- [Learning unitaries with quantum statistical queries](https://mlsanity.com/paper/2310.02254/) (2023)
- [Agnostic Tomography of Stabilizer Product States](https://mlsanity.com/paper/2404.03813/) (2024)
- [Learning low-degree quantum objects](https://mlsanity.com/paper/2405.10933/) (2024)
- [Testing classical properties from quantum data](https://mlsanity.com/paper/2411.12730/) (2024)
- [Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates II: Single-Copy Measurements](https://mlsanity.com/paper/2308.07175/) (2023)
- [Learning to erase quantum states: thermodynamic implications of quantum learning theory](https://mlsanity.com/paper/2504.07341/) (2025)

## Abstract (arXiv)

We analyze the complexity of learning n-qubit quantum phase states. A degree-d phase state is defined as a superposition of all 2n basis vectors x with amplitudes proportional to (-1)f(x), where f is a degree-d Boolean polynomial over n variables. We show that the sample complexity of learning an unknown degree-d phase state is Theta(nd) if we allow separable measurements and Theta(nd-1) if we allow entangled measurements. Our learning algorithm based on separable measurements has runtime textsfpoly(n) (for constant d) and is well-suited for near-term demonstrations as it requires only single-qubit measurements in the Pauli X and Z bases. We show similar bounds on the sample complexity for learning generalized phase states with complex-valued amplitudes. We further consider learning phase states when f has sparsity-s, degree-d in its mathbbF2 representation (with sample complexity O(2d sn)), f has Fourier-degree-t (with sample complexity O(22t)), and learning quadratic phase states with varepsilon-global depolarizing noise (with sample complexity O(n1+varepsilon)). These learning algorithms give us a procedure to learn the diagonal unitaries of the Clifford hierarchy and IQP~circuits.