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

Quantum Sparse Recovery and Quantum Orthogonal Matching Pursuit

Armando Bellante, Stefano Vanerio, Stefano Zanero

Published Oct 8, 2025• 0 citations
arXivHTMLPDF

Abstract

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 $\ell_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 $\ell_2$ norm, achieving query complexity $\widetilde{O}(\sqrt{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=\widetilde{O}(1)$ on a well-conditioned subdictionary, this circumvents the $\widetildeΩ(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.

DOI
10.48550/arxiv.2510.06925

Related papers

Preprint arXiv:2510.06925 Submitted on 8 Oct 2025

Armando Bellante, Stefano Vanerio, S. Zanero

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 $\ell_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 $\ell_2$ norm, achieving query complexity $\widetilde{O}(\sqrt{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=\widetilde{O}(1)$ on a well-conditioned subdictionary, this circumvents the $\widetildeΩ(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.

•Oct 9, 2025•0 citations

Quantum matching pursuit: A quantum algorithm for sparse representations

Armando Bellante, Stefano Zanero

Representing signals with sparse vectors has a wide spectrum of applications that ranges from image and video coding to shape representation and health monitoring. In many applications with real-time requirements or that deal with high-dimensional signals, the computational complexity of the encoder that finds the sparse representation plays an important role. Quantum computing has recently shown promising speedups in many representation learning tasks. In this work, we propose a quantum version of the well-known matching-pursuit algorithm. Assuming the availability of a fault-tolerant quantum random access memory, our quantum matching pursuit lowers the complexity of its classical counterpart by a polynomial factor, at the cost of some error in the computation of the inner products, enabling the computation of sparse representations of high-dimensional signals. Besides proving the computational complexity of our algorithm, we provide numerical experiments that show that its error is negligible in practice. This work opens the path to further research on quantum algorithms for finding sparse representations, showing suitable quantum computing applications in signal processing.

arXiv:2208.04145•Physical Review A•Feb 11, 2022•6 citations

Quantum-Compatible Dictionary Learning via Doubly Sparse Models

Angshul Majumdar

Dictionary learning (DL) is a core tool in signal processing and machine learning for discovering sparse representations of data. In contrast with classical successes, there is currently no practical quantum dictionary learning algorithm. We argue that this absence stems from structural mismatches between classical DL formulations and the operational constraints of quantum computing. We identify the fundamental bottlenecks that prevent efficient quantum realization of classical DL and show how a structurally restricted model, doubly sparse dictionary learning (DSDL), naturally avoids these problems. We present a simple, hybrid quantum-classical algorithm based on projection-based randomized Kaczmarz iterations with Qiskit-compatible quantum inner products. We outline practical considerations and share an open-source implementation at https://github.com/AngshulMajumdar/quantum-dsdl-kaczmarz. The goal is not to claim exponential speedups, but to realign dictionary learning with the realities of near-term quantum devices.

quant-pharXiv:2601.07210•Jan 13, 2026•0 citations

Quantum sparse coding

Yaniv Romano, Harel Primack, Talya Vaknin +5 more

Abstract The ultimate goal of any sparse coding method is to accurately recover from a few noisy linear measurements, an unknown sparse vector. Unfortunately, this estimation problem is NP-hard in general, and it is therefore always approached with an approximation method, such as lasso or orthogonal matching pursuit, thus trading off accuracy for less computational complexity. In this paper, we develop a quantum-inspired algorithm for sparse coding, with the premise that the emergence of quantum computers and Ising machines can potentially lead to more accurate estimations compared to classical approximation methods. To this end, we formulate the most general sparse coding problem as a quadratic unconstrained binary optimization (QUBO) task, which can be efficiently minimized using quantum technology. To derive at a QUBO model that is also efficient in terms of the number of spins (space complexity), we separate our analysis into three different scenarios. These are defined by the number of bits required to express the underlying sparse vector: binary, 2-bit, and a general fixed-point representation. We finally conduct numerical experiments with simulated data on LightSolver's quantum-inspired digital platform to verify the correctness of our QUBO formulation and to demonstrate that we obtain more accurate solutions in regimes where the baseline methods fail.

arXiv:2209.03788•Quantum Machine Intelligence•Jan 30, 2024•2 citations

Solving Sparse SDPs in Sublinear Time: A Classical Algorithm Inspired by the Quantum OR Lemma

Fernando G. S. L. Brandão, Alexander M. Dalzell, András Gilyén +1 more

We give the first sublinear-time classical solvers for sparse semidefinite programs in the bounded-radius regime, without low-rank assumptions or Frobenius norm dependence on the constraint matrices. For constant precision and bounded primal and dual radii, prior quantum algorithms of Brandão et al. (2019) and van Apeldoorn and Gilyén (2019) achieved $\widetilde{O}(\sqrt{n}+\sqrt{m})$ dependence on matrix dimension $n$ and constraint number $m$. Compared with the $\widetilde{O}(mn)$ runtime of existing classical methods, this suggests a quartic quantum speedup when $m \approx n$. Beyond a usual Grover speedup, this separation relies on the Quantum OR lemma, whose sample-reuse mechanism decouples the cost of Gibbs-state preparation from constraint search. We show that this reuse mechanism is classically realizable for sparse SDPs. Our main technical contribution is a classical procedure for simultaneously estimating many expectation values with respect to a sparse Hamiltonian's Gibbs state. This combines randomized Lánczos filtering with an efficient sampling-based estimator. We also introduce a stochastic online-learning framework for SDP solving, substantially improving accuracy-dependence over standard oracle-based MMWU approaches. Let $s$ denote the the input matrix sparsity and $γ:=Rr/\varepsilon$ capture dependence on the primal $(R)$ and dual $(r)$ radii as well as target accuracy $(\varepsilon)$. When $γ^2\leq\min\{m,n/s\}$, our solver runs in time $\widetilde{O}\left(nsγ^{4.5}+msγ^2\right)$. For $γ=O(1)$, this is $\widetilde{O}\left((n+m)s\right)$ and sublinear in the $O(mns)$ input size. Similar to the quantum algorithms, this matches known lower bounds with respect to $m$ and $n$, up to logarithmic factors. This implies that, with respect to dimensions $m$ and $n$, there is no super-quadratic quantum advantage for generic sparse SDP solving.

quant-pharXiv:2609.40302•Oct 1, 2026•0 citations

Optimal T Counts under Sparsity: from QROM to State Preparation and Block Encoding

Tongyang Li, Fengning Ou, Xinzhao Wang +3 more

Many quantum algorithms require coherent access to classical data, often modeled by quantum read-only memory (QROM). We initiate the study of the $\mathrm{T}$ count of sparse QROM, in which only $s$ of the $2^n$ addresses store nonzero data. We prove that the optimal $\mathrm{T}$ count is $Θ\left(n+\min\left\{s,\sqrt{s\left(m+\log(2^{n+1}/s)\right)}\right\}\right)$. Our upper bounds use a multilevel hashing scheme, while our lower bounds reduce sparse QROM to state preparation and use counting arguments for adaptive Clifford+$\mathrm{T}$ circuits. The lower bounds thus hold even when mid-circuit measurements and classically controlled operations are allowed. As applications, we obtain matching $\mathrm{T}$-count bounds $Θ\left(\min\left\{s,\sqrt{s\log(2^{n+1}/s)}\right\} +\sqrt{s\log(1/\varepsilon)}+\log(1/\varepsilon)\right)$ for $s$-sparse state preparation and $Θ\left(\sqrt{2^n s\left(n+\log(1/\varepsilon_{\rm BE})\right)} +\log(1/\varepsilon_{\rm BE})\right)$ for block encoding of $s$-sparse matrices, where $\varepsilon$ and $\varepsilon_{\rm BE}$ are the precision of state preparation and block encoding, respectively.

quant-pharXiv:2607.28260•Jul 31, 2026•0 citations
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\ell_2ℓ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 KKK-sparse state in polynomial time. As an application, we give the first framework for sparse quantum tomography with non-orthogonal dictionaries in ℓ2\ell_2ℓ2​ norm, achieving query complexity O~(N/ε)\widetilde{O}(\sqrt{N}/ε)O(N​/ε) in favorable regimes and reducing tomography to estimating only KKK coefficients instead of NNN amplitudes. In particular, for pure-state tomography with m=O(N)m=O(N)m=O(N) dictionary vectors and sparsity K=O~(1)K=\widetilde{O}(1)K=O(1) on a well-conditioned subdictionary, this circumvents the Ω~(N/ε)\widetildeΩ(N/ε)Ω(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 mmm vectors in O(m/ε)O(m/ε)O(m/ε) queries, improving over both deterministic and quantum-inspired classical methods.
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\ell_2ℓ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 KKK-sparse state in polynomial time. As an application, we give the first framework for sparse quantum tomography with non-orthogonal dictionaries in ℓ2\ell_2ℓ2​ norm, achieving query complexity O~(N/ε)\widetilde{O}(\sqrt{N}/ε)O(N​/ε) in favorable regimes and reducing tomography to estimating only KKK coefficients instead of NNN amplitudes. In particular, for pure-state tomography with m=O(N)m=O(N)m=O(N) dictionary vectors and sparsity K=O~(1)K=\widetilde{O}(1)K=O(1) on a well-conditioned subdictionary, this circumvents the Ω~(N/ε)\widetildeΩ(N/ε)Ω(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 mmm vectors in O(m/ε)O(m/ε)O(m/ε) queries, improving over both deterministic and quantum-inspired classical methods.
Representing signals with sparse vectors has a wide spectrum of applications that ranges from image and video coding to shape representation and health monitoring. In many applications with real-time requirements or that deal with high-dimensional signals, the computational complexity of the encoder that finds the sparse representation plays an important role. Quantum computing has recently shown promising speedups in many representation learning tasks. In this work, we propose a quantum version of the well-known matching-pursuit algorithm. Assuming the availability of a fault-tolerant quantum random access memory, our quantum matching pursuit lowers the complexity of its classical counterpart by a polynomial factor, at the cost of some error in the computation of the inner products, enabling the computation of sparse representations of high-dimensional signals. Besides proving the computational complexity of our algorithm, we provide numerical experiments that show that its error is negligible in practice. This work opens the path to further research on quantum algorithms for finding sparse representations, showing suitable quantum computing applications in signal processing.
Dictionary learning (DL) is a core tool in signal processing and machine learning for discovering sparse representations of data. In contrast with classical successes, there is currently no practical quantum dictionary learning algorithm. We argue that this absence stems from structural mismatches between classical DL formulations and the operational constraints of quantum computing. We identify the fundamental bottlenecks that prevent efficient quantum realization of classical DL and show how a structurally restricted model, doubly sparse dictionary learning (DSDL), naturally avoids these problems. We present a simple, hybrid quantum-classical algorithm based on projection-based randomized Kaczmarz iterations with Qiskit-compatible quantum inner products. We outline practical considerations and share an open-source implementation at https://github.com/AngshulMajumdar/quantum-dsdl-kaczmarz. The goal is not to claim exponential speedups, but to realign dictionary learning with the realities of near-term quantum devices.
Abstract The ultimate goal of any sparse coding method is to accurately recover from a few noisy linear measurements, an unknown sparse vector. Unfortunately, this estimation problem is NP-hard in general, and it is therefore always approached with an approximation method, such as lasso or orthogonal matching pursuit, thus trading off accuracy for less computational complexity. In this paper, we develop a quantum-inspired algorithm for sparse coding, with the premise that the emergence of quantum computers and Ising machines can potentially lead to more accurate estimations compared to classical approximation methods. To this end, we formulate the most general sparse coding problem as a quadratic unconstrained binary optimization (QUBO) task, which can be efficiently minimized using quantum technology. To derive at a QUBO model that is also efficient in terms of the number of spins (space complexity), we separate our analysis into three different scenarios. These are defined by the number of bits required to express the underlying sparse vector: binary, 2-bit, and a general fixed-point representation. We finally conduct numerical experiments with simulated data on LightSolver's quantum-inspired digital platform to verify the correctness of our QUBO formulation and to demonstrate that we obtain more accurate solutions in regimes where the baseline methods fail.
We give the first sublinear-time classical solvers for sparse semidefinite programs in the bounded-radius regime, without low-rank assumptions or Frobenius norm dependence on the constraint matrices. For constant precision and bounded primal and dual radii, prior quantum algorithms of Brandão et al. (2019) and van Apeldoorn and Gilyén (2019) achieved O~(n+m)\widetilde{O}(\sqrt{n}+\sqrt{m})O(n​+m​) dependence on matrix dimension nnn and constraint number mmm. Compared with the O~(mn)\widetilde{O}(mn)O(mn) runtime of existing classical methods, this suggests a quartic quantum speedup when m≈nm \approx nm≈n. Beyond a usual Grover speedup, this separation relies on the Quantum OR lemma, whose sample-reuse mechanism decouples the cost of Gibbs-state preparation from constraint search. We show that this reuse mechanism is classically realizable for sparse SDPs. Our main technical contribution is a classical procedure for simultaneously estimating many expectation values with respect to a sparse Hamiltonian's Gibbs state. This combines randomized Lánczos filtering with an efficient sampling-based estimator. We also introduce a stochastic online-learning framework for SDP solving, substantially improving accuracy-dependence over standard oracle-based MMWU approaches. Let sss denote the the input matrix sparsity and γ:=Rr/εγ:=Rr/\varepsilonγ:=Rr/ε capture dependence on the primal (R)(R)(R) and dual (r)(r)(r) radii as well as target accuracy (ε)(\varepsilon)(ε). When γ2≤min⁡{m,n/s}γ^2\leq\min\{m,n/s\}γ2≤min{m,n/s}, our solver runs in time O~(nsγ4.5+msγ2)\widetilde{O}\left(nsγ^{4.5}+msγ^2\right)O(nsγ4.5+msγ2). For γ=O(1)γ=O(1)γ=O(1), this is O~((n+m)s)\widetilde{O}\left((n+m)s\right)O((n+m)s) and sublinear in the O(mns)O(mns)O(mns) input size. Similar to the quantum algorithms, this matches known lower bounds with respect to mmm and nnn, up to logarithmic factors. This implies that, with respect to dimensions mmm and nnn, there is no super-quadratic quantum advantage for generic sparse SDP solving.
Many quantum algorithms require coherent access to classical data, often modeled by quantum read-only memory (QROM). We initiate the study of the T\mathrm{T}T count of sparse QROM, in which only sss of the 2n2^n2n addresses store nonzero data. We prove that the optimal T\mathrm{T}T count is Θ(n+min⁡{s,s(m+log⁡(2n+1/s))})Θ\left(n+\min\left\{s,\sqrt{s\left(m+\log(2^{n+1}/s)\right)}\right\}\right)Θ(n+min{s,s(m+log(2n+1/s))​}). Our upper bounds use a multilevel hashing scheme, while our lower bounds reduce sparse QROM to state preparation and use counting arguments for adaptive Clifford+T\mathrm{T}T circuits. The lower bounds thus hold even when mid-circuit measurements and classically controlled operations are allowed. As applications, we obtain matching T\mathrm{T}T-count bounds Θ(min⁡{s,slog⁡(2n+1/s)}+slog⁡(1/ε)+log⁡(1/ε))Θ\left(\min\left\{s,\sqrt{s\log(2^{n+1}/s)}\right\} +\sqrt{s\log(1/\varepsilon)}+\log(1/\varepsilon)\right)Θ(min{s,slog(2n+1/s)​}+slog(1/ε)​+log(1/ε)) for sss-sparse state preparation and Θ(2ns(n+log⁡(1/εBE))+log⁡(1/εBE))Θ\left(\sqrt{2^n s\left(n+\log(1/\varepsilon_{\rm BE})\right)} +\log(1/\varepsilon_{\rm BE})\right)Θ(2ns(n+log(1/εBE​))​+log(1/εBE​)) for block encoding of sss-sparse matrices, where ε\varepsilonε and εBE\varepsilon_{\rm BE}εBE​ are the precision of state preparation and block encoding, respectively.