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

Quantum-Compatible Dictionary Learning via Doubly Sparse Models

Angshul Majumdar

quant-pheess.SPSubmitted Jan 12, 2026• Announced Jan 13, 2026• 0 citations
arXivHTMLPDF

Abstract

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.

Related papers

Quantum Sparse Recovery and Quantum Orthogonal Matching Pursuit

Armando Bellante, Stefano Vanerio, Stefano 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.

arXiv:2510.06925•Oct 8, 2025•3 citations

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

Machine Learning with Hybrid Quantum-Classical Approaches: Exploring the Limits of Quantum Computing in Artificial Intelligence

M S N V Lakshmi Kantham A, Abdelhalim Mohammad Jubran, Sorabh Lakhanpal +3 more

The entwining of quantum computing with classical machine learning has proven to be one of the most promising frontiers of artificial intelligence, as it possesses the potential to speed up intricate computations in ways that classical systems will never be able to achieve. This study delves into the theoretical and practical implications of hybrid quantum-classical approaches in machine learning, while also examining their advantages, limitations, and applicability in different domains. Utilizing quantum entanglement and parallelism, hybrid solutions also have the potential to process high-dimensional data, optimize complex functions, and facilitate pattern recognition tasks more efficiently. However, noise, decoherence, and limited qubit connectivity on current hardware pose considerable barriers to practical implementations. The authors discuss hybrid architectures like quantum-enhanced optimizers and variational quantum circuits which include classical pre- and post-processing to alleviate quantum limitations. Moreover, a comparative study is performed to show the effectiveness of hybrid models comparing with classical machine learning state-of-the-art in natural language processing, computer vision and financial modeling. Results indicate that although hybrid quantum–classical approaches provide significant gains in optimization and computational efficiency; these benefits remain limited by hardware limitations and the scalability of quantum algorithms. With these considerations in mind, the paper offers guidance for targeting future research directions in quantum machine learning, including advances in quantum error correction, quantum hardware scalability, and new algorithmic approaches. Additional advancements needed and notably, the study focused on a smaller representation of data Since quantum computing is relatively new and researchers are still exploring its application, it is still early days in terms of machine learning models that are solely, intrinsically quantum.

International Conference on Smart Futuristic Technology (SMARTTECH)•Jan 2, 2026•0 citations

Quantum Machine Learning for Noisy Intermediate-Scale Quantum Devices: A Comprehensive Review

Quantum computing has emerged as a transformative paradigm capable of addressing computational challenges beyond the reach of classical systems.In the current era of Noisy Intermediate-Scale Quantum (NISQ) devices, practical quantum hardware is characterized by limited qubit counts, short coherence times, gate errors, and the absence of full error correction.Despite these constraints, significant progress has been made in developing quantum machine learning (QML) techniques tailored to operate on near-term quantum processors.This paper presents a comprehensive review of Quantum Machine Learning in the context of NISQ computing.We first outline the fundamental principles of quantum computing, including qubits, superposition, entanglement, and quantum parallelism, followed by a detailed discussion of the NISQ computing model and its hardware limitations.The review then examines hybrid quantum-classical learning frameworks, variational quantum algorithms, quantum data encoding strategies, and noise mitigation techniques that enable practical implementation on existing platforms.Emerging applications across healthcare, finance, cybersecurity, climate modeling, and materials science are also surveyed to highlight the real-world potential of QML.Furthermore, key challenges such as scalability, trainability issues, and algorithmic robustness are analyzed, along with current research efforts aimed at overcoming these barriers.The paper concludes by identifying promising future directions for advancing QML toward quantum advantage.This review aims to provide researchers and practitioners with a structured understanding of the capabilities, limitations, and opportunities of quantum machine learning in the NISQ era .

International Research Journal of Modernization in Engineering Technology and Science•Apr 9, 2026•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•7 citations

Quantum Machine Learning: A Step towards the Hybrid Quantum Classical Approaches

Kailash Thakur, Parveen Sadotra, Shaina Mahajan +2 more

Machine Learning (ML) has changed the way computers work by letting them learn from data and make smart choices. However, traditional ML techniques encounter scalability and efficiency constraints as datasets get larger and computational problems become more complicated[1]. These restrictions could be circumvented by the new paradigms that quantum computing offers by using entanglement and superposition [2], [3]. The combination of the Quantum computing with the Machine Learning is called the Quantum Machine Learning(QML), offers efficiency improvements, new algorithmic opportunities, and speedups in certain linear algebraic operations. So, this review dives deeply into quantum-classical algorithms, with a particular emphasis on the approaches like quantum neural network and quantum support vector machines. We examine computational complexity, architectural design, benchmarking findings, and real-world applications (such as optimization, cryptography, and classification). We also discuss important issues including scalability, data encoding, and noise, and we suggest future paths for error prevention and scalable structures.

IEEE International Conference on Recent Trends in Computing and Smart Mobility (RCSM)•Dec 5, 2025•0 citations
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.
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.
The entwining of quantum computing with classical machine learning has proven to be one of the most promising frontiers of artificial intelligence, as it possesses the potential to speed up intricate computations in ways that classical systems will never be able to achieve. This study delves into the theoretical and practical implications of hybrid quantum-classical approaches in machine learning, while also examining their advantages, limitations, and applicability in different domains. Utilizing quantum entanglement and parallelism, hybrid solutions also have the potential to process high-dimensional data, optimize complex functions, and facilitate pattern recognition tasks more efficiently. However, noise, decoherence, and limited qubit connectivity on current hardware pose considerable barriers to practical implementations. The authors discuss hybrid architectures like quantum-enhanced optimizers and variational quantum circuits which include classical pre- and post-processing to alleviate quantum limitations. Moreover, a comparative study is performed to show the effectiveness of hybrid models comparing with classical machine learning state-of-the-art in natural language processing, computer vision and financial modeling. Results indicate that although hybrid quantum–classical approaches provide significant gains in optimization and computational efficiency; these benefits remain limited by hardware limitations and the scalability of quantum algorithms. With these considerations in mind, the paper offers guidance for targeting future research directions in quantum machine learning, including advances in quantum error correction, quantum hardware scalability, and new algorithmic approaches. Additional advancements needed and notably, the study focused on a smaller representation of data Since quantum computing is relatively new and researchers are still exploring its application, it is still early days in terms of machine learning models that are solely, intrinsically quantum.
Quantum computing has emerged as a transformative paradigm capable of addressing computational challenges beyond the reach of classical systems.In the current era of Noisy Intermediate-Scale Quantum (NISQ) devices, practical quantum hardware is characterized by limited qubit counts, short coherence times, gate errors, and the absence of full error correction.Despite these constraints, significant progress has been made in developing quantum machine learning (QML) techniques tailored to operate on near-term quantum processors.This paper presents a comprehensive review of Quantum Machine Learning in the context of NISQ computing.We first outline the fundamental principles of quantum computing, including qubits, superposition, entanglement, and quantum parallelism, followed by a detailed discussion of the NISQ computing model and its hardware limitations.The review then examines hybrid quantum-classical learning frameworks, variational quantum algorithms, quantum data encoding strategies, and noise mitigation techniques that enable practical implementation on existing platforms.Emerging applications across healthcare, finance, cybersecurity, climate modeling, and materials science are also surveyed to highlight the real-world potential of QML.Furthermore, key challenges such as scalability, trainability issues, and algorithmic robustness are analyzed, along with current research efforts aimed at overcoming these barriers.The paper concludes by identifying promising future directions for advancing QML toward quantum advantage.This review aims to provide researchers and practitioners with a structured understanding of the capabilities, limitations, and opportunities of quantum machine learning in the NISQ era .
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.
Machine Learning (ML) has changed the way computers work by letting them learn from data and make smart choices. However, traditional ML techniques encounter scalability and efficiency constraints as datasets get larger and computational problems become more complicated[1]. These restrictions could be circumvented by the new paradigms that quantum computing offers by using entanglement and superposition [2], [3]. The combination of the Quantum computing with the Machine Learning is called the Quantum Machine Learning(QML), offers efficiency improvements, new algorithmic opportunities, and speedups in certain linear algebraic operations. So, this review dives deeply into quantum-classical algorithms, with a particular emphasis on the approaches like quantum neural network and quantum support vector machines. We examine computational complexity, architectural design, benchmarking findings, and real-world applications (such as optimization, cryptography, and classification). We also discuss important issues including scalability, data encoding, and noise, and we suggest future paths for error prevention and scalable structures.