# Quantum Sparse Coding

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 59 references that are in the map.
- First posted on arXiv 8 Sep 2022.

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

- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [QUBO Formulations for Training Machine Learning Models](https://mlsanity.com/paper/2008.02369/) (2020)
- [Towards Feature Selection for Ranking and Classification Exploiting Quantum Annealers](https://mlsanity.com/paper/2205.04346/) (2022)
- [Quantum Computing at the Frontiers of Biological Sciences](https://mlsanity.com/paper/1911.07127/) (2019)
- [High-Dimensional Similarity Search with Quantum-Assisted Variational Autoencoder](https://mlsanity.com/paper/2006.07680/) (2020)
- [Trainlets: Dictionary Learning in High Dimensions](https://mlsanity.com/paper/1602.00212/) (2016)
- [An Ensemble Approach for Compressive Sensing with Quantum](https://mlsanity.com/paper/2006.04682/) (2020)

## Built on by (most cited first, 3 of 3)

- [Lightsolver challenges a leading deep learning solver for Max-2-SAT problems](https://mlsanity.com/paper/2302.06926/) (2023)
- [Comparing Quantum Annealing and Spiking Neuromorphic Computing for Sampling Binary Sparse Coding QUBO Problems](https://mlsanity.com/paper/2405.20525/) (2024)
- [Implicit Binarization via Complex Phase Dynamics in Combinatorial Optimization](https://mlsanity.com/paper/2605.24502/) (2026)

## Abstract (arXiv)

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.