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.
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.
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 O(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=O(1) on a well-conditioned subdictionary, this circumvents the Ω(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.
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 O(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=O(1) on a well-conditioned subdictionary, this circumvents the Ω(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.
Along with the development of quantum technology, finding useful applications of quantum computers has been a central pursuit. Despite various quantum algorithms have been developed, many of them often require strong input assumptions, which is hardware demanding. In particular, recent advances on dequantization have revealed that the quantum advantage is more of a mere artifact of strong input assumptions. In this work, we propose a variant of these algorithms, leveraging both classical and quantum resources. Provided the classical knowledge (the entries) of the matrix/vector of interest, a classical procedure is used to pre-process this information. Then they are fed into a quantum circuit which is shown to be a block encoding of the matrix of interest. From this block-encoding, we show how to use it to tackle a wide range of problems, including principal component analysis, linear equation solving, Hamiltonian simulation, preparing ground state, and data fitting. We also analyze our protocol, showing that both the classical and quantum procedure can achieve logarithmic complexity in the input dimension, thus implying its potential for near term realization. We then discuss several implications and corollaries of our result. First,, our results suggest there are certain matrices/Hamiltonians where our method can provide exponential improvement compared to the existing ones with respect to the sparsity. Regarding dense linear systems, our method achieves exponential speed-up with respect to the inverse of error tolerance, compared to the best previously known quantum algorithm for dense systems. Last, and most importantly, regarding quantum data fitting, we show how the output of our quantum algorithms can be leveraged to predict unseen data. Thus, it provides an end-to-end application, which has been an open aspect of the previous quantum data fitting algorithm.
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.
Encoding classical data into quantum systems is a foundational step in the execution of nearly all quantum algorithms, and a critical bottleneck in realizing practical quantum advantage. This review provides a comprehensive account of the concepts, algorithms, and practical considerations associated with quantum data encoding. We trace the development from its early conceptual foundations to recent advances, considering commonly used access models, such as quantum state preparation, unitary synthesis, QRAM and block encoding. We survey the circuit size, depth, space-time tradeoffs, as well as non-Clifford resources required for fault-tolerant implementation. We also discuss the roles of different access models in quantum algorithms. Special attention is given to structured data, such as sparse data, Boolean functions and data represented by tensor networks. This review bridges theory and applications, serving both as a pedagogical guide for newcomers and as a reference for active researchers. We also highlight the pivotal role of quantum data encoding in quantum computing and provide insights into future directions that will enable quantum advantage.