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:1310.1933 · Physical Review A

Quadratic constrained mixed discrete optimization with an adiabatic quantum optimizer

Rishabh Chandra, N. Tobias Jacobson, Jonathan E. Moussa, Steven H. Frankel, Sabre Kais

Published Jul 8, 2014• 3 citations
arXivHTMLPDF

Abstract

We extend the family of problems that may be implemented on an adiabatic quantum optimizer (AQO). When a quadratic optimization problem has at least one set of discrete controls and the constraints are linear, we call this a quadratic constrained mixed discrete optimization (QCMDO) problem. QCMDO problems are NP-hard, and no efficient classical algorithm for their solution is known. Included in the class of QCMDO problems are combinatorial optimization problems constrained by a linear partial differential equation (PDE) or system of linear PDEs. An essential complication commonly encountered in solving this type of problem is that the linear constraint may introduce many intermediate continuous variables into the optimization while the computational cost grows exponentially with problem size. We resolve this difficulty by developing a constructive mapping from QCMDO to quadratic unconstrained binary optimization (QUBO) such that the size of the QUBO problem depends only on the number of discrete control variables. With a suitable embedding, taking into account the physical constraints of the realizable coupling graph, the resulting QUBO problem can be implemented on an existing AQO. The mapping itself is efficient, scaling cubically with the number of continuous variables in the general case and linearly in the PDE case if an efficient preconditioner is available.

DOI
10.1103/physreva.90.012308

Related papers

Partial differential equations constrained combinatorial optimization on an adiabatic quantum computer

Rishabh Chandra

Partial differential equation-constrained combinatorial optimization (PDECCO) problems are a mixture of continuous and discrete optimization problems. PDECCO problems have discrete controls, but since the partial differential equations (PDE) are continuous, the optimization space is continuous as well. Such problems have several applications, such as gas/water network optimization, traffic optimization, micro-chip cooling optimization, etc. Currently, no efficient classical algorithm which guarantees a global minimum for PDECCO problems exists. A new mapping has been developed that transforms PDECCO problem, which only have linear PDEs as constraints, into quadratic unconstrained binary optimization (QUBO) problems that can be solved using an adiabatic quantum optimizer (AQO). The mapping is efficient, it scales polynomially with the size of the PDECCO problem, requires only one PDE solve to form the QUBO problem, and if the QUBO problem is solved correctly and efficiently on an AQO, guarantees a global optimal solution for the original PDECCO problem.

•Jan 1, 2013•1 citation

REDUCING DISCRETE OPTIMIZATION PROBLEMS TO THE QUBO FORM

A.M. Semenov, S.R. Usmanov, Aleksey K. Fedorov

Practical discrete optimization problems often contain multidimensional arrays of variables with linear constraints, which complicates their conversion to QUBO (quadratic unconstrained binary optimization) form. The article proposes a systematic approach to transforming such problems, which includes three key steps: the transition from a multidimensional representation of variables to a one-dimensional one using the Kronecker product of matrices, the reduction of mixed variables to binary ones, and the introduction of linear constraints into the objective function through quadratic penalties. Explicit computational formulas are obtained for each stage, simplifying their software implementation. The developed method is illustrated with examples from graph theory and combinatorial optimization, including classical formulations, confirming its universality. The results of the article allow standardizing the process of adapting problems for solving on quantum annealing algorithms (e.g., D-Wave) and classical QUBO solvers.

Problems of Information Transmission•Jan 1, 2025•2 citations

Adiabatic Quantum Linear Optimal Control for Discrete Time Dynamical Systems

Mayank Jha, Prasanna Date

This paper presents a novel approach for solving finite-horizon linear optimal control based on block-Toeplitz least-squares problem, by recasting the latter as Quadratic Unconstrained Binary Optimization (QUBO) suitable for adiabatic quantum computing (AQC). Classical block-Toeplitz leastsquares problem, scales as$O\left((N m)^{3}\right)$for horizon length$N$and control dimension$m$. We demonstrate that this Toeplitzstructured least-squares cost can be transformed into a QUBO formulation by introducing binary precision vectors that encode each continuous control parameter into finite number of bits. We establish the general case in mathematically rigorous manner wherein the total number of binary decision variables remain dependent on$N$. To respect current quantum annealer capabilities, we propose a basis-function parametrization that approximates the full control sequence with a small set of basis coefficients, reducing the total number of binary-variables and rendering the latter independent of$N$. Through simulation study, we show that, for large datasets, the QUBO pipeline, comprising of hardware-constant anneal step outperforms classical least square based solvers by several factors whilst demonstrating acceptable accuracy.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations

Constraint Embedding for Solving Optimization Problems on Quantum Annealers

Tomáš Vyskočil, Hristo N. Djidjev

Quantum annealers such as the commercially available D-Wave machines are designed to natively solve quadratic unconstrained binary optimization (QUBO) problems. While most of the well-known NP-hard optimization problems can easily be formulated as quadratic binary problems, such formulations also contain constraints, which commonly are added to the objective function in the form of penalties to obtain a QUBO version. However, the standard method for defining such penalties leads to QUBOs that are dense and therefore take too much of the resources of the quantum annealer. In this paper, we describe an alternative approach to the constraint embedding problem that uses mixed-integer linear programming (MILP) and is scalable to problems of arbitrary number of variables.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•May 1, 2019•2 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 Efficient Hybrid Classical Quantum Algorithm for Mixed-Integer Constrained Optimization

Amit Surana

Widely used quantum optimization algorithms such as quantum annealing and quantum approximate optimization algorithm (QAOA) for quadratically unconstrained binary optimization (QUBO) problems cannot systematically and efficiently handle constraints and mixed discrete and continuous decision variables. To address this, we present a novel hybrid classicalquantum approach which combines classical alternating direction method of multipliers (ADMM) with QAOA. Compared to conventional penalty-based method, this approach avoids quantization of continuous variables, eliminates the need for additional qubits to capture constraints on a quantum device and leads to reduced QAOA circuit depth suitable for near term implementation. We illustrate the efficacy of our approach on several constrained mixed integer optimization problems.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Aug 30, 2025•0 citations
We extend the family of problems that may be implemented on an adiabatic quantum optimizer (AQO). When a quadratic optimization problem has at least one set of discrete controls and the constraints are linear, we call this a quadratic constrained mixed discrete optimization (QCMDO) problem. QCMDO problems are NP-hard, and no efficient classical algorithm for their solution is known. Included in the class of QCMDO problems are combinatorial optimization problems constrained by a linear partial differential equation (PDE) or system of linear PDEs. An essential complication commonly encountered in solving this type of problem is that the linear constraint may introduce many intermediate continuous variables into the optimization while the computational cost grows exponentially with problem size. We resolve this difficulty by developing a constructive mapping from QCMDO to quadratic unconstrained binary optimization (QUBO) such that the size of the QUBO problem depends only on the number of discrete control variables. With a suitable embedding, taking into account the physical constraints of the realizable coupling graph, the resulting QUBO problem can be implemented on an existing AQO. The mapping itself is efficient, scaling cubically with the number of continuous variables in the general case and linearly in the PDE case if an efficient preconditioner is available.
Partial differential equation-constrained combinatorial optimization (PDECCO) problems are a mixture of continuous and discrete optimization problems. PDECCO problems have discrete controls, but since the partial differential equations (PDE) are continuous, the optimization space is continuous as well. Such problems have several applications, such as gas/water network optimization, traffic optimization, micro-chip cooling optimization, etc. Currently, no efficient classical algorithm which guarantees a global minimum for PDECCO problems exists. A new mapping has been developed that transforms PDECCO problem, which only have linear PDEs as constraints, into quadratic unconstrained binary optimization (QUBO) problems that can be solved using an adiabatic quantum optimizer (AQO). The mapping is efficient, it scales polynomially with the size of the PDECCO problem, requires only one PDE solve to form the QUBO problem, and if the QUBO problem is solved correctly and efficiently on an AQO, guarantees a global optimal solution for the original PDECCO problem.
Practical discrete optimization problems often contain multidimensional arrays of variables with linear constraints, which complicates their conversion to QUBO (quadratic unconstrained binary optimization) form. The article proposes a systematic approach to transforming such problems, which includes three key steps: the transition from a multidimensional representation of variables to a one-dimensional one using the Kronecker product of matrices, the reduction of mixed variables to binary ones, and the introduction of linear constraints into the objective function through quadratic penalties. Explicit computational formulas are obtained for each stage, simplifying their software implementation. The developed method is illustrated with examples from graph theory and combinatorial optimization, including classical formulations, confirming its universality. The results of the article allow standardizing the process of adapting problems for solving on quantum annealing algorithms (e.g., D-Wave) and classical QUBO solvers.
This paper presents a novel approach for solving finite-horizon linear optimal control based on block-Toeplitz least-squares problem, by recasting the latter as Quadratic Unconstrained Binary Optimization (QUBO) suitable for adiabatic quantum computing (AQC). Classical block-Toeplitz leastsquares problem, scales asO((Nm)3)O\left((N m)^{3}\right)O((Nm)3)for horizon lengthNNNand control dimensionmmm. We demonstrate that this Toeplitzstructured least-squares cost can be transformed into a QUBO formulation by introducing binary precision vectors that encode each continuous control parameter into finite number of bits. We establish the general case in mathematically rigorous manner wherein the total number of binary decision variables remain dependent onNNN. To respect current quantum annealer capabilities, we propose a basis-function parametrization that approximates the full control sequence with a small set of basis coefficients, reducing the total number of binary-variables and rendering the latter independent ofNNN. Through simulation study, we show that, for large datasets, the QUBO pipeline, comprising of hardware-constant anneal step outperforms classical least square based solvers by several factors whilst demonstrating acceptable accuracy.
Quantum annealers such as the commercially available D-Wave machines are designed to natively solve quadratic unconstrained binary optimization (QUBO) problems. While most of the well-known NP-hard optimization problems can easily be formulated as quadratic binary problems, such formulations also contain constraints, which commonly are added to the objective function in the form of penalties to obtain a QUBO version. However, the standard method for defining such penalties leads to QUBOs that are dense and therefore take too much of the resources of the quantum annealer. In this paper, we describe an alternative approach to the constraint embedding problem that uses mixed-integer linear programming (MILP) and is scalable to problems of arbitrary number of variables.
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.
Widely used quantum optimization algorithms such as quantum annealing and quantum approximate optimization algorithm (QAOA) for quadratically unconstrained binary optimization (QUBO) problems cannot systematically and efficiently handle constraints and mixed discrete and continuous decision variables. To address this, we present a novel hybrid classicalquantum approach which combines classical alternating direction method of multipliers (ADMM) with QAOA. Compared to conventional penalty-based method, this approach avoids quantization of continuous variables, eliminates the need for additional qubits to capture constraints on a quantum device and leads to reduced QAOA circuit depth suitable for near term implementation. We illustrate the efficacy of our approach on several constrained mixed integer optimization problems.