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

Sparse Signal Reconstruction with QUBO Formulation in l0-regularized Linear Regression

Ide, Naoki, Masayuki Ohzeki

Published Jan 31, 2022• 1 citation
arXivHTMLPDF

Abstract

An l0-regularized linear regression for a sparse signal reconstruction is implemented based on the quadratic unconstrained binary optimization (QUBO) formulation. In this method, the signal values are quantized and expressed as bit sequences. By transforming l0-norm to a quadratic form of these bits, the fully quadratic objective function is provided and optimized by the solver specialized for QUBO, such as the quantum annealer. Numerical experiments with a commercial quantum annealer show that the proposed method performs slightly better than conventional methods based on orthogonal matching pursuit (OMP) and the least absolute shrinkage and selection operator (LASSO) under several limited conditions.

DOI
10.48550/arxiv.2202.00452

Related papers

Derivation of QUBO Formulations for Sparse Estimation

Tomohiro Yokota, Makiko Konoshima, Hirotaka Tamura +1 more

We propose a quadratic unconstrained binary optimization (QUBO) formulation of the l1-norm, which enables us to perform sparse estimation of Ising-type annealing methods such as quantum annealing. The QUBO formulation is derived using the Legendre transformation and the Wolfe theorem, which have recently been employed to derive the QUBO formulations of ReLU-type functions. It is shown that a simple application of the derivation method to the l1-norm case results in a redundant variable. Finally a simplified QUBO formulation is obtained by removing the redundant variable.

arXiv:2001.03715•Journal of the Physical Society of Japan•Feb 27, 2020•2 citations

Quantum sparse coding

Yaniv Romano, Harel Primack, Talya Vaknin +5 more

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.

arXiv:2209.03788•Quantum Machine Intelligence•Jan 30, 2024•2 citations

On the Influence of Numerical Representations in Quantum-Annealing-Based Linear Regression

Pedro Faria Albuquerque, Leonardo Tomazeli Duarte

Quantum annealers are a class of quantum technologies that have attracted increasing attention due to their natural suitability for solving combinatorial optimization problems.Recent works reformulated the linear regression as a Quadratic Unconstrained Binary Optimization (QUBO) problem, enabling its implementation on quantum annealers and offering potential speed-ups for large datasets.However, this QUBO-based formulation requires the definition of a precision vector to represent the real-valued regression coefficients as integers variables, which introduces limitations related to the quantization accuracy.In this work, we investigate several numerical representations strategies for defining the precision vector.By performing a set of numerical experiments with synthetic datasets, we analyze the performance of these strategies in different configurations.Our results that the strategy usually known as conventional binary representation provides the best trade-off between performance and resource efficiency for quantum-assisted linear regression.

Anais de XXXV Simpósio Brasileiro de Telecomunicações e Processamento de Sinais•Jan 1, 2025•0 citations

How to Approximate any Objective Function via Quadratic Unconstrained Binary Optimization

Thomas Gabor, Marian Lingsch-Rosenfeld, Claudia Linnhoff–Popien +1 more

Quadratic unconstrained binary optimization (QUBO) has become the standard format for optimization using quantum computers, i.e., for both the quantum approximate optimization algorithm (QAOA) and quantum annealing (QA). We present a toolkit of methods to transform almost arbitrary problems to QUBO by (i) approximating them as a polynomial and then (ii) translating any polynomial to QUBO. We showcase the usage of our approaches on two example problems (ratio cut and logistic regression).

arXiv:2204.11035•IEEE International Conference on Software Analysis, Evolution and Reengineering (SANER)•Mar 1, 2022•10 citations

Degeneracy engineering for classical and quantum annealing: A case study of sparse linear regression in collider physics

Eric R. Anschuetz, Lena Funcke, Patrick Komiske +2 more

Classical and quantum annealing are computing paradigms that have been proposed to solve a wide range of optimization problems. In this paper, we aim to enhance the performance of annealing algorithms by introducing the technique of degeneracy engineering, through which the relative degeneracy of the ground state is increased by modifying a subset of terms in the objective Hamiltonian. We illustrate this novel approach by applying it to the example of ${\ensuremath{\ell}}_{0}$-norm regularization for sparse linear regression, which is, in general, an $\mathsf{NP}$-hard optimization problem. Specifically, we show how to cast ${\ensuremath{\ell}}_{0}$-norm regularization as a quadratic unconstrained binary optimization (QUBO) problem, suitable for implementation on annealing platforms. As a case study, we apply this QUBO formulation to energy flow polynomials in high-energy collider physics, finding that degeneracy engineering substantially improves the annealing performance. Our results motivate the application of degeneracy engineering to a variety of regularized optimization problems.

arXiv:2205.10375•Physical review. D/Physical review. D.•Sep 12, 2022•4 citations

Quadratic Continuous Quantum Optimization

Sascha Mücke, Thore Gerlach, Nico Piatkowski

Quantum annealers can solve QUBO problems efficiently but struggle with continuous optimization tasks like regression due to their discrete nature. We introduce Quadratic Continuous Quantum Optimization (QCQO), an anytime algorithm that approximates solutions to unconstrained quadratic programs via a sequence of QUBO instances. Rather than encoding real variables as binary vectors, QCQO implicitly represents them using continuous QUBO weights and iteratively refines the solution by summing sampled vectors. This allows flexible control over the number of binary variables and adapts well to hardware constraints. We prove convergence properties, introduce a step size adaptation scheme, and validate the method on linear regression. Experiments with simulated and real quantum annealers show that QCQO achieves accurate results with fewer qubits, though convergence slows on noisy hardware. Our approach enables quantum annealing to address a wider class of continuous problems.

quant-pharXiv:2512.24759•Jan 1, 2026•0 citations
An l0-regularized linear regression for a sparse signal reconstruction is implemented based on the quadratic unconstrained binary optimization (QUBO) formulation. In this method, the signal values are quantized and expressed as bit sequences. By transforming l0-norm to a quadratic form of these bits, the fully quadratic objective function is provided and optimized by the solver specialized for QUBO, such as the quantum annealer. Numerical experiments with a commercial quantum annealer show that the proposed method performs slightly better than conventional methods based on orthogonal matching pursuit (OMP) and the least absolute shrinkage and selection operator (LASSO) under several limited conditions.
We propose a quadratic unconstrained binary optimization (QUBO) formulation of the l1-norm, which enables us to perform sparse estimation of Ising-type annealing methods such as quantum annealing. The QUBO formulation is derived using the Legendre transformation and the Wolfe theorem, which have recently been employed to derive the QUBO formulations of ReLU-type functions. It is shown that a simple application of the derivation method to the l1-norm case results in a redundant variable. Finally a simplified QUBO formulation is obtained by removing the redundant variable.
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.
Quantum annealers are a class of quantum technologies that have attracted increasing attention due to their natural suitability for solving combinatorial optimization problems.Recent works reformulated the linear regression as a Quadratic Unconstrained Binary Optimization (QUBO) problem, enabling its implementation on quantum annealers and offering potential speed-ups for large datasets.However, this QUBO-based formulation requires the definition of a precision vector to represent the real-valued regression coefficients as integers variables, which introduces limitations related to the quantization accuracy.In this work, we investigate several numerical representations strategies for defining the precision vector.By performing a set of numerical experiments with synthetic datasets, we analyze the performance of these strategies in different configurations.Our results that the strategy usually known as conventional binary representation provides the best trade-off between performance and resource efficiency for quantum-assisted linear regression.
Classical and quantum annealing are computing paradigms that have been proposed to solve a wide range of optimization problems. In this paper, we aim to enhance the performance of annealing algorithms by introducing the technique of degeneracy engineering, through which the relative degeneracy of the ground state is increased by modifying a subset of terms in the objective Hamiltonian. We illustrate this novel approach by applying it to the example of ${\ensuremath{\ell}}_{0}$-norm regularization for sparse linear regression, which is, in general, an NP\mathsf{NP}NP-hard optimization problem. Specifically, we show how to cast ${\ensuremath{\ell}}_{0}$-norm regularization as a quadratic unconstrained binary optimization (QUBO) problem, suitable for implementation on annealing platforms. As a case study, we apply this QUBO formulation to energy flow polynomials in high-energy collider physics, finding that degeneracy engineering substantially improves the annealing performance. Our results motivate the application of degeneracy engineering to a variety of regularized optimization problems.
Quantum annealers can solve QUBO problems efficiently but struggle with continuous optimization tasks like regression due to their discrete nature. We introduce Quadratic Continuous Quantum Optimization (QCQO), an anytime algorithm that approximates solutions to unconstrained quadratic programs via a sequence of QUBO instances. Rather than encoding real variables as binary vectors, QCQO implicitly represents them using continuous QUBO weights and iteratively refines the solution by summing sampled vectors. This allows flexible control over the number of binary variables and adapts well to hardware constraints. We prove convergence properties, introduce a step size adaptation scheme, and validate the method on linear regression. Experiments with simulated and real quantum annealers show that QCQO achieves accurate results with fewer qubits, though convergence slows on noisy hardware. Our approach enables quantum annealing to address a wider class of continuous problems.