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:2609.35648

Learning sparse quantum states from single-qubit measurements

Su-un Lee, Liang Jiang, Kunal Sharma

quant-phcs.DScs.ITSubmitted Sep 28, 2026• Announced Sep 29, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

AI Summary

The paper asks whether an $n$-qubit state whose density matrix has at most $s$ nonzero entries in an unknown product basis can be reconstructed using only single-qubit measurements. This class includes long-range-entangled states, such as GHZ states, whose global phases cannot be recovered from proper reduced density matrices. For a known sparsifying basis, reconstruction to trace-norm error $\varepsilon$ uses $O(s^4\log s/\varepsilon^2)$ copies and $O(ns^4\log s/\varepsilon^2)$ classical time, at constant failure probability. The underlying selected-entry tomography estimates any specified matrix element using $O(\varepsilon^{-2}\log(1/\delta))$ copies, independently of $n$, through randomized product-Pauli measurements. For arbitrary unknown product bases, one algorithm achieves sample complexity and runtime $2^{O(s(\log s)^2)}(n/\varepsilon)^{O(s)}$, polynomial for constant $s$. Sparse-distribution Fourier bounds and contractions of low-order Pauli-moment tensors recover most local bases after enumerating a small exceptional qubit set. A second algorithm recursively merges reconstructed blocks and searches for sparse representations. It uses $O(n^6s^{12}\varepsilon^{-4}\log^2(ns))$ copies, but takes $(ns/\varepsilon)^{O(n)}$ classical time in general. If local bases belong to a known fixed finite set, a Donoho–Stark uncertainty bound restricts basis changes to $O(\log s)$ qubits, reducing runtime to $n^{O(\log s)}/\varepsilon^4$. Measurements adapt between copies, without within-copy feed-forward. General polynomial-time reconstruction for polynomial $s$ remains unestablished. Outputs are sparse operators, not necessarily physical density matrices. A constant-sparsity testing extension distinguishes distance $O(\varepsilon^4/n)$ from distance greater than $\varepsilon$ to sparse operators.

No sign of AI-generated text

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

Optimal Algorithms for Learning Quantum Phase States

Srinivasan Arunachalam, Sergey B. Bravyi, Arkopal Dutt +1 more

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.

arXiv:2208.07851•Leibniz international proceedings in informatics•Aug 16, 2022•56 citations

Reconstructing Quantum States from Sparse Measurements

Yufan Xie, Chu Guo, Zhihui Peng

Quantum state tomography (QST) is a central technique to fully characterize an unknown quantum state. However, standard QST requires an exponentially growing number of quantum measurements against the system size, which limits its application to smaller systems. Here, we explore the sparsity of underlying quantum state and propose a QST scheme that combines the matrix product states’ representation of the quantum state with a supervised machine learning algorithm. Our method could reconstruct the unknown sparse quantum states with very high precision using only a portion of the measurement data in a randomly selected basis set. In particular, we demonstrate that the Wolfgang states could be faithfully reconstructed using around 25% of the whole basis, and that the randomly generated quantum states, which could be efficiently represented as matrix product states, could be faithfully reconstructed using a number of bases that scales sub-exponentially against the system size.

Electronics•Feb 22, 2023•1 citation

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•63 citations

Learning shallow quantum circuits with many-qubit gates

Francisca Vasconcelos, Hsin-Yuan Huang

We present the first computationally-efficient algorithm for average-case learning of shallow quantum circuits with many-qubit gates. Specifically, we provide a quasi-polynomial time and sample complexity algorithm for learning unknown QAC$^0$ circuits -- constant-depth circuits with arbitrary single-qubit gates and polynomially many $CZ$ gates of unbounded width -- with at most logarithmic ancilla, up to inverse-polynomially small error. Furthermore, we show that the learned unitary can be efficiently synthesized in poly-logarithmic depth. This work expands the family of efficiently learnable quantum circuits, notably since in finite-dimensional circuit geometries, QAC$^0$ circuits require polynomial depth to implement.

arXiv:2410.16693•Oct 22, 2024•11 citations

An Efficient Algorithm for Sparse Quantum State Preparation

Niels Gleinig, Torsten Hoefler

Generating quantum circuits that prepare specific states is an essential part of quantum compilation. Algorithms that solve this problem for general states generate circuits at grow exponentially in the number of qubits. However, in contrast to general states, many practically relevant states are sparse in the standard basis. In this paper we show how sparsity can be used for efficient state preparation. We present a polynomial-time algorithm that generates polynomial-size quantum circuits (linear in the number of nonzero coefficients times number of qubits) that prepare given states, making computer-aided design of sparse state preparation scalable.

ACM/IEEE Design Automation Conference (DAC)•Nov 8, 2021•61 citations

Learning and Generating Mixed States Prepared by Shallow Channel Circuits

Fangjun Hu, Christian Kokail, Milan Kornjača +5 more

Learning quantum states from measurement data is a central problem in quantum information and computational complexity. In this work, we study the problem of learning to generate mixed states on a finite-dimensional lattice. Motivated by recent developments in mixed state phases of matter, we focus on arbitrary states in the trivial phase. A state belongs to the trivial phase if there exists a shallow preparation channel circuit under which local reversibility is preserved throughout the preparation. We prove that any mixed state in this class can be efficiently learned from measurement access alone. Specifically, given copies of an unknown trivial phase mixed state, our algorithm outputs a shallow local channel circuit that approximately generates this state in trace distance. The sample complexity and runtime are polynomial (or quasi-polynomial) in the number of qubits, assuming constant (or polylogarithmic) circuit depth and gate locality. Importantly, the learner is not given the original preparation circuit and relies only on its existence. Our results provide a structural foundation for quantum generative models based on shallow channel circuits. In the classical limit, our framework also inspires an efficient algorithm for classical diffusion models using only a polynomial overhead of training and generation.

quant-pharXiv:2604.01197•Apr 2, 2026•5 citations
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.
The paper asks whether an nnn-qubit state whose density matrix has at most sss nonzero entries in an unknown product basis can be reconstructed using only single-qubit measurements. This class includes long-range-entangled states, such as GHZ states, whose global phases cannot be recovered from proper reduced density matrices.
For a known sparsifying basis, reconstruction to trace-norm error ε\varepsilonε uses O(s4log⁡s/ε2)O(s^4\log s/\varepsilon^2)O(s4logs/ε2) copies and O(ns4log⁡s/ε2)O(ns^4\log s/\varepsilon^2)O(ns4logs/ε2) classical time, at constant failure probability. The underlying selected-entry tomography estimates any specified matrix element using O(ε−2log⁡(1/δ))O(\varepsilon^{-2}\log(1/\delta))O(ε−2log(1/δ)) copies, independently of nnn, through randomized product-Pauli measurements.
For arbitrary unknown product bases, one algorithm achieves sample complexity and runtime 2O(s(log⁡s)2)(n/ε)O(s)2^{O(s(\log s)^2)}(n/\varepsilon)^{O(s)}2O(s(logs)2)(n/ε)O(s), polynomial for constant sss. Sparse-distribution Fourier bounds and contractions of low-order Pauli-moment tensors recover most local bases after enumerating a small exceptional qubit set. A second algorithm recursively merges reconstructed blocks and searches for sparse representations. It uses O(n6s12ε−4log⁡2(ns))O(n^6s^{12}\varepsilon^{-4}\log^2(ns))O(n6s12ε−4log2(ns)) copies, but takes (ns/ε)O(n)(ns/\varepsilon)^{O(n)}(ns/ε)O(n) classical time in general. If local bases belong to a known fixed finite set, a Donoho–Stark uncertainty bound restricts basis changes to O(log⁡s)O(\log s)O(logs) qubits, reducing runtime to nO(log⁡s)/ε4n^{O(\log s)}/\varepsilon^4nO(logs)/ε4.
Measurements adapt between copies, without within-copy feed-forward. General polynomial-time reconstruction for polynomial sss remains unestablished. Outputs are sparse operators, not necessarily physical density matrices. A constant-sparsity testing extension distinguishes distance O(ε4/n)O(\varepsilon^4/n)O(ε4/n) from distance greater than ε\varepsilonε to sparse operators.
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.
Quantum state tomography (QST) is a central technique to fully characterize an unknown quantum state. However, standard QST requires an exponentially growing number of quantum measurements against the system size, which limits its application to smaller systems. Here, we explore the sparsity of underlying quantum state and propose a QST scheme that combines the matrix product states’ representation of the quantum state with a supervised machine learning algorithm. Our method could reconstruct the unknown sparse quantum states with very high precision using only a portion of the measurement data in a randomly selected basis set. In particular, we demonstrate that the Wolfgang states could be faithfully reconstructed using around 25% of the whole basis, and that the randomly generated quantum states, which could be efficiently represented as matrix product states, could be faithfully reconstructed using a number of bases that scales sub-exponentially against the system size.
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.
We present the first computationally-efficient algorithm for average-case learning of shallow quantum circuits with many-qubit gates. Specifically, we provide a quasi-polynomial time and sample complexity algorithm for learning unknown QAC0^00 circuits -- constant-depth circuits with arbitrary single-qubit gates and polynomially many CZCZCZ gates of unbounded width -- with at most logarithmic ancilla, up to inverse-polynomially small error. Furthermore, we show that the learned unitary can be efficiently synthesized in poly-logarithmic depth. This work expands the family of efficiently learnable quantum circuits, notably since in finite-dimensional circuit geometries, QAC0^00 circuits require polynomial depth to implement.
Generating quantum circuits that prepare specific states is an essential part of quantum compilation. Algorithms that solve this problem for general states generate circuits at grow exponentially in the number of qubits. However, in contrast to general states, many practically relevant states are sparse in the standard basis. In this paper we show how sparsity can be used for efficient state preparation. We present a polynomial-time algorithm that generates polynomial-size quantum circuits (linear in the number of nonzero coefficients times number of qubits) that prepare given states, making computer-aided design of sparse state preparation scalable.
Learning quantum states from measurement data is a central problem in quantum information and computational complexity. In this work, we study the problem of learning to generate mixed states on a finite-dimensional lattice. Motivated by recent developments in mixed state phases of matter, we focus on arbitrary states in the trivial phase. A state belongs to the trivial phase if there exists a shallow preparation channel circuit under which local reversibility is preserved throughout the preparation. We prove that any mixed state in this class can be efficiently learned from measurement access alone. Specifically, given copies of an unknown trivial phase mixed state, our algorithm outputs a shallow local channel circuit that approximately generates this state in trace distance. The sample complexity and runtime are polynomial (or quasi-polynomial) in the number of qubits, assuming constant (or polylogarithmic) circuit depth and gate locality. Importantly, the learner is not given the original preparation circuit and relies only on its existence. Our results provide a structural foundation for quantum generative models based on shallow channel circuits. In the classical limit, our framework also inspires an efficient algorithm for classical diffusion models using only a polynomial overhead of training and generation.