Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2208.07851 · Leibniz international proceedings in informatics

Optimal Algorithms for Learning Quantum Phase States

Srinivasan Arunachalam, Sergey B. Bravyi, Arkopal Dutt, Theodore J. Yoder

Published Aug 16, 2022• 11 citations
arXivHTMLPDF

Abstract

We analyze the complexity of learning $n$-qubit quantum phase states. A degree-$d$ phase state is defined as a superposition of all $2^n$ 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 $Θ(n^d)$ if we allow separable measurements and $Θ(n^{d-1})$ if we allow entangled measurements. Our learning algorithm based on separable measurements has runtime $\textsf{poly}(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 $\mathbb{F}_2$ representation (with sample complexity $O(2^d sn)$), $f$ has Fourier-degree-$t$ (with sample complexity $O(2^{2t})$), and learning quadratic phase states with $\varepsilon$-global depolarizing noise (with sample complexity $O(n^{1+\varepsilon})$). These learning algorithms give us a procedure to learn the diagonal unitaries of the Clifford hierarchy and IQP~circuits.

DOI
10.4230/lipics.tqc.2023.3

Related papers

Learning sparse quantum states from single-qubit measurements

Su-un Lee, Liang Jiang, Kunal Sharma

We study the problem of learning a sparse quantum state, an $n$-qubit quantum state whose density matrix has at most $s$ nonzero matrix entries in an unknown product basis. While such states admit compact classical descriptions, they can carry long-range entanglement that prevents reconstruction from local reduced density matrices alone. Therefore, previous learning approaches addressed such long-range-entangled states using many entangling gates to extract the necessary information. In this work, we show that sparse states can nevertheless be efficiently learned using only single-qubit measurements. Specifically, when the sparsity $s$ is constant, our algorithm can learn sparse states from single-qubit measurements with polynomial sample complexity and classical computational complexity. When $s$ grows polynomially with $n$, sparse states can still be learned from single-qubit measurements with polynomial sample complexity, although efficient classical computation is not guaranteed in general. In this regime, however, the classical computational complexity becomes quasipolynomial when the state is sparse in an unknown basis that is a product of a known fixed finite set of single-qubit bases (e.g., eigenbases of Pauli operators). These results establish efficient learning of sparse states with long-range entanglement without entangling gates, and the single-qubit measurement requirements make our algorithms compatible with current quantum devices.

quant-pharXiv:2609.35648•Sep 29, 2026•0 citations

Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates

Sabee Grewal, Vishnu Iyer, William Kretschmer +1 more

We give a pair of algorithms that efficiently learn a quantum state prepared by Clifford gates and O ( log ⁡ n ) non-Clifford gates. Specifically, for an n -qubit state | ψ ⟩ prepared with at most t non-Clifford gates, our algorithms use p o l y ( n , 2 t , 1 / ε ) time and copies of | ψ ⟩ to learn | ψ ⟩ to trace distance at most ε .The first algorithm for this task is more efficient, but requires entangled measurements across two copies of | ψ ⟩ . The second algorithm uses only single-copy measurements at the cost of polynomial factors in runtime and sample complexity. Our algorithms more generally learn any state with sufficiently large stabilizer dimension, where a quantum state has stabilizer dimension k if it is stabilized by an abelian group of 2 k Pauli operators. We also develop an efficient property testing algorithm for stabilizer dimension, which may be of independent interest.

arXiv:2305.13409•Quantum•Nov 6, 2025•11 citations

Sample-optimal learning of stabilizer states

Rebecca Chang, Matthias C. Caro, Martin Larocca +1 more

It is well-known that learning a pure $n$-qubit stabilizer state $|ψ\rangle$ both requires, and can be accomplished with, access to a number of copies of $|ψ\rangle$ linear in $n$. However, the precise constant coefficient of this scaling does not appear to have been determined. Here we prove that $L_δ(n)$, the smallest number of copies from which a quantum procedure can identify any stabilizer state with failure probability at most $0<δ<1/8$, satisfies $n+\lceil\log_2(1/δ)\rceil-3\leq L_δ(n)\leq n+\left\lceil\log_2(1/δ)\right\rceil+4$. We present a polynomial-time quantum learning algorithm that saturates this bound, achieving a constant factor improvement in sample-complexity over previously known approaches. As an immediate corollary, we obtain via the Choi-Jamiolkowski isomorphism an algorithm for learning an unknown $n$-qubit Clifford unitary from $2n+\left\lceil\log_2(1/δ)\right\rceil+4$ queries, the $n$-dependence of which we show to be optimal. Our proof technique, which involves Fourier analysis on the abelian group $\mathbb{Z}_4^n \times \mathbb{F}_2^{n(n-1)/2}$, seems to be qualitatively different to previous approaches to stabilizer state learning, and may be of some independent interest; in particular, it admits natural generalisations to further problems in quantum learning theory.

quant-pharXiv:2609.10974•Sep 11, 2026•0 citations

Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions

Zekun Ye

We study the number of uniform quantum examples needed to exactly learn a Boolean function with at most $k$ nonzero Fourier coefficients. We give a learner with near-optimal $\widetilde{O}(k)$ sample complexity independent of the input length $n$. The learner uses only separate measurements of individual examples. This improves the previous $O(k^{3/2}\log^2 k)$ upper bound (Arunachalam, Chakraborty, Lee, Paraashar, and de Wolf, 2021). The main ingredient is a candidate set formed by symmetric differences of subsets from independent groups of Fourier samples. A multilinear majority polynomial combines unbiased random approximations into an accurate witness whose Fourier support lies in this set. Granularity then forces the set to contain the entire Fourier support, including subsets never directly sampled. For comparison, we derive the tight classical sample complexity $Θ(nk)$ by combining known sparse-recovery and lower-bound results.

quant-pharXiv:2610.17648•Oct 14, 2026•0 citations

Efficient Learning of Quantum States Prepared With Few Non-Clifford Gates II: Single-Copy Measurements

Sabee Grewal, Vishnu Iyer, William Kretschmer +1 more

Recent work has shown that $n$-qubit quantum states output by circuits with at most $t$ single-qubit non-Clifford gates can be learned to trace distance $ε$ using $\mathsf{poly}(n,2^t,1/ε)$ time and samples. All prior algorithms achieving this runtime use entangled measurements across two copies of the input state. In this work, we give a similarly efficient algorithm that learns the same class of states using only single-copy measurements.

arXiv:2308.07175•Aug 14, 2023•0 citations

Quantum State Classification via Quantum Fourier.

Mohsen Heidari, Wojciech Szpankowski A

We study learning from quantum data, in particular quantum state classification which has applications, among others, in classifying the separability of quantum states. In this learning model, there are $n$ quantum states with classical labels as the training samples. Predictors are quantum measurements that when applied to the next unseen quantum state predict its classical label. By integrating learning theory with quantum information, we introduce a quantum counterpart of the PAC framework for learning with respect to classes of measurements. We argue that major challenges arising from the quantum nature of the problem are measurement incompatibility and the no-cloning principle -- prohibiting sample reuse. Then, after introducing a Fourier expansion through Pauli's operators, we study learning with respect to an infinite class of quantum measurements whose operator's Fourier spectrum is concentrated on low degree terms. We propose a quantum learning algorithm and show that the quantum sample complexity depends on the ``compatibility structure of such measurement classes -- the more compatible the class is, the lower the quantum sample complexity will be. We further introduce $k$-junta measurements as a special class of low-depth quantum circuits whose Fourier spectrum is concentrated on low degrees.

•Feb 10, 2021•0 citations
We analyze the complexity of learning nnn-qubit quantum phase states. A degree-ddd phase state is defined as a superposition of all 2n2^n2n basis vectors xxx with amplitudes proportional to (−1)f(x)(-1)^{f(x)}(−1)f(x), where fff is a degree-ddd Boolean polynomial over nnn variables. We show that the sample complexity of learning an unknown degree-ddd phase state is Θ(nd)Θ(n^d)Θ(nd) if we allow separable measurements and Θ(nd−1)Θ(n^{d-1})Θ(nd−1) if we allow entangled measurements. Our learning algorithm based on separable measurements has runtime poly(n)\textsf{poly}(n)poly(n) (for constant ddd) and is well-suited for near-term demonstrations as it requires only single-qubit measurements in the Pauli XXX and ZZZ 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 fff has sparsity-sss, degree-ddd in its F2\mathbb{F}_2F2​ representation (with sample complexity O(2dsn)O(2^d sn)O(2dsn)), fff has Fourier-degree-ttt (with sample complexity O(22t)O(2^{2t})O(22t)), and learning quadratic phase states with ε\varepsilonε-global depolarizing noise (with sample complexity O(n1+ε)O(n^{1+\varepsilon})O(n1+ε)). These learning algorithms give us a procedure to learn the diagonal unitaries of the Clifford hierarchy and IQP~circuits.
We study the problem of learning a sparse quantum state, an nnn-qubit quantum state whose density matrix has at most sss nonzero matrix entries in an unknown product basis. While such states admit compact classical descriptions, they can carry long-range entanglement that prevents reconstruction from local reduced density matrices alone. Therefore, previous learning approaches addressed such long-range-entangled states using many entangling gates to extract the necessary information. In this work, we show that sparse states can nevertheless be efficiently learned using only single-qubit measurements. Specifically, when the sparsity sss is constant, our algorithm can learn sparse states from single-qubit measurements with polynomial sample complexity and classical computational complexity. When sss grows polynomially with nnn, sparse states can still be learned from single-qubit measurements with polynomial sample complexity, although efficient classical computation is not guaranteed in general. In this regime, however, the classical computational complexity becomes quasipolynomial when the state is sparse in an unknown basis that is a product of a known fixed finite set of single-qubit bases (e.g., eigenbases of Pauli operators). These results establish efficient learning of sparse states with long-range entanglement without entangling gates, and the single-qubit measurement requirements make our algorithms compatible with current quantum devices.
We give a pair of algorithms that efficiently learn a quantum state prepared by Clifford gates and O ( log ⁡ n ) non-Clifford gates. Specifically, for an n -qubit state | ψ ⟩ prepared with at most t non-Clifford gates, our algorithms use p o l y ( n , 2 t , 1 / ε ) time and copies of | ψ ⟩ to learn | ψ ⟩ to trace distance at most ε .The first algorithm for this task is more efficient, but requires entangled measurements across two copies of | ψ ⟩ . The second algorithm uses only single-copy measurements at the cost of polynomial factors in runtime and sample complexity. Our algorithms more generally learn any state with sufficiently large stabilizer dimension, where a quantum state has stabilizer dimension k if it is stabilized by an abelian group of 2 k Pauli operators. We also develop an efficient property testing algorithm for stabilizer dimension, which may be of independent interest.
It is well-known that learning a pure nnn-qubit stabilizer state ∣ψ⟩|ψ\rangle∣ψ⟩ both requires, and can be accomplished with, access to a number of copies of ∣ψ⟩|ψ\rangle∣ψ⟩ linear in nnn. However, the precise constant coefficient of this scaling does not appear to have been determined. Here we prove that Lδ(n)L_δ(n)Lδ​(n), the smallest number of copies from which a quantum procedure can identify any stabilizer state with failure probability at most 0<δ<1/80<δ<1/80<δ<1/8, satisfies n+⌈log⁡2(1/δ)⌉−3≤Lδ(n)≤n+⌈log⁡2(1/δ)⌉+4n+\lceil\log_2(1/δ)\rceil-3\leq L_δ(n)\leq n+\left\lceil\log_2(1/δ)\right\rceil+4n+⌈log2​(1/δ)⌉−3≤Lδ​(n)≤n+⌈log2​(1/δ)⌉+4. We present a polynomial-time quantum learning algorithm that saturates this bound, achieving a constant factor improvement in sample-complexity over previously known approaches. As an immediate corollary, we obtain via the Choi-Jamiolkowski isomorphism an algorithm for learning an unknown nnn-qubit Clifford unitary from 2n+⌈log⁡2(1/δ)⌉+42n+\left\lceil\log_2(1/δ)\right\rceil+42n+⌈log2​(1/δ)⌉+4 queries, the nnn-dependence of which we show to be optimal. Our proof technique, which involves Fourier analysis on the abelian group Z4n×F2n(n−1)/2\mathbb{Z}_4^n \times \mathbb{F}_2^{n(n-1)/2}Z4n​×F2n(n−1)/2​, seems to be qualitatively different to previous approaches to stabilizer state learning, and may be of some independent interest; in particular, it admits natural generalisations to further problems in quantum learning theory.
We study the number of uniform quantum examples needed to exactly learn a Boolean function with at most kkk nonzero Fourier coefficients. We give a learner with near-optimal O~(k)\widetilde{O}(k)O(k) sample complexity independent of the input length nnn. The learner uses only separate measurements of individual examples. This improves the previous O(k3/2log⁡2k)O(k^{3/2}\log^2 k)O(k3/2log2k) upper bound (Arunachalam, Chakraborty, Lee, Paraashar, and de Wolf, 2021). The main ingredient is a candidate set formed by symmetric differences of subsets from independent groups of Fourier samples. A multilinear majority polynomial combines unbiased random approximations into an accurate witness whose Fourier support lies in this set. Granularity then forces the set to contain the entire Fourier support, including subsets never directly sampled. For comparison, we derive the tight classical sample complexity Θ(nk)Θ(nk)Θ(nk) by combining known sparse-recovery and lower-bound results.
Recent work has shown that nnn-qubit quantum states output by circuits with at most ttt single-qubit non-Clifford gates can be learned to trace distance εεε using poly(n,2t,1/ε)\mathsf{poly}(n,2^t,1/ε)poly(n,2t,1/ε) time and samples. All prior algorithms achieving this runtime use entangled measurements across two copies of the input state. In this work, we give a similarly efficient algorithm that learns the same class of states using only single-copy measurements.
We study learning from quantum data, in particular quantum state classification which has applications, among others, in classifying the separability of quantum states. In this learning model, there are nnn quantum states with classical labels as the training samples. Predictors are quantum measurements that when applied to the next unseen quantum state predict its classical label. By integrating learning theory with quantum information, we introduce a quantum counterpart of the PAC framework for learning with respect to classes of measurements. We argue that major challenges arising from the quantum nature of the problem are measurement incompatibility and the no-cloning principle -- prohibiting sample reuse. Then, after introducing a Fourier expansion through Pauli's operators, we study learning with respect to an infinite class of quantum measurements whose operator's Fourier spectrum is concentrated on low degree terms. We propose a quantum learning algorithm and show that the quantum sample complexity depends on the ``compatibility structure of such measurement classes -- the more compatible the class is, the lower the quantum sample complexity will be. We further introduce kkk-junta measurements as a special class of low-depth quantum circuits whose Fourier spectrum is concentrated on low degrees.