# Quantum Sparse Recovery and Quantum Orthogonal Matching Pursuit

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 67 references that are in the map.
- First posted on arXiv 8 Oct 2025.

## Builds on (most cited first, 10 of 10)

- [Quantum Recommendation Systems](https://mlsanity.com/paper/1603.08675/) (2016)
- [q-means: A quantum algorithm for unsupervised machine learning](https://mlsanity.com/paper/1812.03584/) (2018)
- [The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation](https://mlsanity.com/paper/1804.01973/) (2018)
- [A Quantum Interior Point Method for LPs and SDPs](https://mlsanity.com/paper/1808.09266/) (2018)
- [Quantum Algorithms and Lower Bounds for Linear Regression with Norm Constraints](https://mlsanity.com/paper/2110.13086/) (2021)
- [Quantum Regularized Least Squares](https://mlsanity.com/paper/2206.13143/) (2022)
- [Quantum tomography using state-preparation unitaries](https://mlsanity.com/paper/2207.08800/) (2022)
- [Amplitude amplification and estimation require inverses](https://mlsanity.com/paper/2507.23787/) (2025)
- [Quantum algorithms for SVD-based data representation and analysis](https://mlsanity.com/paper/2104.08987/) (2021)
- [Quantum Algorithms for the Pathwise Lasso](https://mlsanity.com/paper/2312.14141/) (2023)

## Abstract (arXiv)

We study quantum sparse recovery in non-orthogonal, overcomplete dictionaries: given coherent quantum access to a state and a dictionary of vectors, the goal is to reconstruct the state up to ℓ2 error using as few vectors as possible. We first show that the general recovery problem is NP-hard, ruling out efficient exact algorithms in full generality. To overcome this, we introduce Quantum Orthogonal Matching Pursuit (QOMP), the first quantum analogue of the classical OMP greedy algorithm. QOMP combines quantum subroutines for inner product estimation, maximum finding, and block-encoded projections with an error-resetting design that avoids iteration-to-iteration error accumulation. Under standard mutual incoherence and well-conditioned sparsity assumptions, QOMP provably recovers the exact support of a K-sparse state in polynomial time. As an application, we give the first framework for sparse quantum tomography with non-orthogonal dictionaries in ℓ2 norm, achieving query complexity widetildeO(√N/ε) in favorable regimes and reducing tomography to estimating only K coefficients instead of N amplitudes. In particular, for pure-state tomography with m=O(N) dictionary vectors and sparsity K=widetildeO(1) on a well-conditioned subdictionary, this circumvents the widetildeOmega(N/ε) lower bound that holds in the dense, orthonormal-dictionary setting, without contradiction, by leveraging sparsity together with non-orthogonality. Beyond tomography, we analyze QOMP in the QRAM model, where it yields polynomial speedups over classical OMP implementations, and provide a quantum algorithm to estimate the mutual incoherence of a dictionary of m vectors in O(m/ε) queries, improving over both deterministic and quantum-inspired classical methods.