  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 conduct numerical experiments with
simulated data on LightSolver's quantum-inspired digital platform to verify the
correctness of our QUBO formulation and to demonstrate its advantage over
baseline methods.

Quantum Physics;Machine Learning