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

Bulletin of the American Physical Society

Compressed Sensing for Reconstructing Sparse Quantum States

Kenneth Rudinger, Robert Joynt

Published Mar 6, 2014• 0 citations
OpenAlex

Related papers

Compressed sensing of Fourier sparse quasiparticle-interference map

Olli Winberg

•May 24, 2021•0 citations

Practical applications of compressed sensing in quantum state tomography

Carlos A. Riofrío

Bulletin of the American Physical Society•Jun 8, 2017•0 citations

Compressed Sensing Shadow Tomography

Joseph Barreto, Daniel Lidar

Estimating many local expectation values over time is a central measurement bottleneck in quantum simulation and device characterization. We study the task of reconstructing the Pauli-signal matrix $S_{ij}=\text{Tr}(O_i ρ(t_j))$ for a collection of $M$ low-weight Pauli observables $\{O_i\}_{i=1}^M$ over $N$ timesteps $\{t_j\}_{j=1}^N$, while minimizing the total number of device shots. We propose a Compressed Sensing Shadow Tomography (CSST) protocol that combines two complementary reductions. First, local classical shadows reduce the observable dimension by enabling many Pauli expectation values to be estimated from the same randomized snapshots at a fixed time. Second, compressed sensing reduces the time dimension by exploiting the fact that many expectation-value traces are spectrally sparse or compressible in a unitary (e.g., Fourier) transform basis. Operationally, CSST samples $m\ll N$ timesteps uniformly at random, collects shadows only at those times, and then reconstructs each length-$N$ signal via standard $\ell_1$-based recovery in the unitary transform domain. We provide end-to-end guarantees that explicitly combine shadow estimation error with compressed sensing recovery bounds. For exactly $s$-sparse signals in a unitary transform basis, we show that $m=O \left(s\log^2 s \log N\right)$ random timesteps suffice (with high probability), leading to total-shot savings scaling as $\widetildeΘ(N/s)$ (i.e., up to polylogarithmic factors) relative to collecting shadows at all $N$ timesteps. For approximately sparse signals, the reconstruction error decomposes into a compressibility (tail) term plus a noise term. We present numerical experiments on noisy many-qubit dynamics that support strong Fourier compressibility of Pauli traces and demonstrate substantial shot reductions with accurate reconstruction.

quant-pharXiv:2602.12518•Physical Review A•Feb 16, 2026•1 citation

Quantum limits in compressed sensing of optical images

Hui Wang, Shensheng Han, Mikhail I. Kolobov

We discuss the ultimate quantum limits in compressed sensing, a new technique which allows for accurate reconstruction of so-called “sparse” signals even when the sampling rate is far below the Nyquist limit.

Conference on Lasers and Electro-Optics•Jan 1, 2012•2 citations

Compressed sensing for Hamiltonian reconstruction

Kenneth Rudinger, Robert Joynt

In engineered quantum systems, the Hamiltonian is often not completely known and needs to be determined experimentally with accuracy and efficiency. We show that this may be done at temperatures that are higher than the characteristic interaction energies, but not too much higher. The condition for this is that there are not too many multiparticle interactions: the Hamiltonian is sparse in a well-defined sense. The protocol that accomplishes this is related to compressed sensing methods of classical signal processing, in this case applied to sparse rather than low-rank matrices.

arXiv:1410.3029•Physical Review A•Nov 19, 2015•23 citations

Using Compressed Sensing for Quantum Tomography

Steve Flammia

Bulletin of the American Physical Society•Mar 18, 2013•0 citations
Estimating many local expectation values over time is a central measurement bottleneck in quantum simulation and device characterization. We study the task of reconstructing the Pauli-signal matrix Sij=Tr(Oiρ(tj))S_{ij}=\text{Tr}(O_i ρ(t_j))Sij​=Tr(Oi​ρ(tj​)) for a collection of MMM low-weight Pauli observables {Oi}i=1M\{O_i\}_{i=1}^M{Oi​}i=1M​ over NNN timesteps {tj}j=1N\{t_j\}_{j=1}^N{tj​}j=1N​, while minimizing the total number of device shots. We propose a Compressed Sensing Shadow Tomography (CSST) protocol that combines two complementary reductions. First, local classical shadows reduce the observable dimension by enabling many Pauli expectation values to be estimated from the same randomized snapshots at a fixed time. Second, compressed sensing reduces the time dimension by exploiting the fact that many expectation-value traces are spectrally sparse or compressible in a unitary (e.g., Fourier) transform basis. Operationally, CSST samples m≪Nm\ll Nm≪N timesteps uniformly at random, collects shadows only at those times, and then reconstructs each length-NNN signal via standard ℓ1\ell_1ℓ1​-based recovery in the unitary transform domain. We provide end-to-end guarantees that explicitly combine shadow estimation error with compressed sensing recovery bounds. For exactly sss-sparse signals in a unitary transform basis, we show that m=O(slog⁡2slog⁡N)m=O \left(s\log^2 s \log N\right)m=O(slog2slogN) random timesteps suffice (with high probability), leading to total-shot savings scaling as Θ~(N/s)\widetildeΘ(N/s)Θ(N/s) (i.e., up to polylogarithmic factors) relative to collecting shadows at all NNN timesteps. For approximately sparse signals, the reconstruction error decomposes into a compressibility (tail) term plus a noise term. We present numerical experiments on noisy many-qubit dynamics that support strong Fourier compressibility of Pauli traces and demonstrate substantial shot reductions with accurate reconstruction.
In engineered quantum systems, the Hamiltonian is often not completely known and needs to be determined experimentally with accuracy and efficiency. We show that this may be done at temperatures that are higher than the characteristic interaction energies, but not too much higher. The condition for this is that there are not too many multiparticle interactions: the Hamiltonian is sparse in a well-defined sense. The protocol that accomplishes this is related to compressed sensing methods of classical signal processing, in this case applied to sparse rather than low-rank matrices.