Stefano Zanero

We study quantum sparse recovery in non-orthogonal, overcomplete dictionaries: given quantum access to a state and a dictionary of vectors, the goal is to approximate the state using as few vectors as possible. We prove that the general 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 accumulation across iterations. Under 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 obtain the first framework for sparse quantum tomography in non-orthogonal dictionaries, achieving query complexity $\widetilde{O}(\sqrt{N}/\epsilon)$ in favorable regimes and reducing tomography to estimating only $K$ coefficients instead of $N$ amplitudes. Beyond tomography, we also 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 in $O(\sqrt{m}/\epsilon)$ queries, improving over classical and quantum-inspired methods.