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

Partial differential equations constrained combinatorial optimization on an adiabatic quantum computer

Rishabh Chandra

Published Jan 1, 2013• 1 citation
OpenAlex

Abstract

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.

Related papers

Quadratic constrained mixed discrete optimization with an adiabatic quantum optimizer

Rishabh Chandra, N. Tobias Jacobson, Jonathan E. Moussa +2 more

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.

arXiv:1310.1933•Physical Review A•Jul 8, 2014•3 citations

Explicit block-encoding for partial differential equation-constrained optimization

Yuki Sato, Jumpei Kato, Hiroshi Yano +2 more

Partial differential equation (PDE)-constrained optimization, where an optimization problem is subject to PDE constraints, arises in various applications such as design, control, and inference. Solving such problems is computationally demanding because it requires repeatedly solving a PDE and using its solution within an optimization process. In this paper, we first propose a fully coherent quantum algorithm for solving PDE-constrained optimization problems. The proposed method combines a quantum PDE solver that prepares the solution vector as a quantum state, and a quantum optimizer that assumes oracle access to a quantized objective function. The central idea is the explicit construction of the oracle in a form of block-encoding for the objective function, which coherently uses the output of a quantum PDE solver. This enables us to avoid classical access to the full solution that requires quantum state tomography canceling out the potential quantum speedups. We also derive the overall computational complexity of the proposed method with respect to parameters for optimization and PDE simulation, where quantum speedup is inherited from the underlying quantum PDE solver. We numerically demonstrate the validity of the proposed method by applications, including a parameter calibration problem in the Black-Scholes equation and a material parameter design problem in the wave equation. This work presents the concept of composing quantum subroutines so that the weakness of one (i.e., prohibitive readout overhead) is neutralized by the strength of another (i.e., coherent oracle access), toward a bottleneck-free quantum algorithm.

quant-pharXiv:2511.14420•Nov 19, 2025•0 citations

Combinatorial Optimization on Gate Model Quantum Computers: A Survey

Ehsan Zahedinejad, Arman Zaribafiyan

The advent of quantum computing processors with possibility to scale beyond experimental capacities magnifies the importance of studying their applications. Combinatorial optimization problems can be one of the promising applications of these new devices. These problems are recurrent in industrial applications and they are in general difficult for classical computing hardware. In this work, we provide a survey of the approaches to solving different types of combinatorial optimization problems, in particular quadratic unconstrained binary optimization (QUBO) problems on a gate model quantum computer. We focus mainly on four different approaches including digitizing the adiabatic quantum computing, global quantum optimization algorithms, the quantum algorithms that approximate the ground state of a general QUBO problem, and quantum sampling. We also discuss the quantum algorithms that are custom designed to solve certain types of QUBO problems.

arXiv:1708.05294•Aug 16, 2017•29 citations

Quantum Permutation Synchronization

Tolga Birdal, Vladislav Golyanik, Christian Theobalt +1 more

We present QuantumSync, the first quantum algorithm for solving a synchronization problem in the context of computer vision. In particular, we focus on permutation synchronization which involves solving a non-convex optimization problem in discrete variables. We start by formulating synchronization into a quadratic unconstrained binary optimization problem (QUBO). While such formulation respects the binary nature of the problem, ensuring that the result is a set of permutations requires extra care. Hence, we: (i) show how to insert permutation constraints into a QUBO problem and (ii) solve the constrained QUBO problem on the current generation of the adiabatic quantum computers D-Wave. Thanks to the quantum annealing, we guarantee global optimality with high probability while sampling the energy landscape to yield confidence estimates. Our proof-of-concepts realization on the adiabatic D-Wave computer demonstrates that quantum machines offer a promising way to solve the prevalent yet difficult synchronization problems.

arXiv:2101.07755•IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings•Jun 1, 2021•37 citations

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

Variational Quantum Framework for Partial Differential Equation Constrained Optimization

Amit Surana, Abeynaya Gnanasekaran

We present a novel variational quantum framework for linear partial differential equation (PDE) constrained optimization problems. Such problems arise in many scientific and engineering domains. For instance, in aerodynamics, the PDE constraints are the conservation laws such as momentum, mass and energy balance, the design variables are vehicle shape parameters and material properties, and the objective could be to minimize the effect of transient heat loads on the vehicle or to maximize the lift-to-drag ratio. The proposed framework utilizes the variational quantum linear solver (VQLS) algorithm and a black box optimizer as its two main building blocks. VQLS is used to solve the linear system, arising from the discretization of the PDE constraints for given design parameters, and evaluate the design cost/objective function. The black box optimizer is used to select next set of parameter values based on this evaluated cost, leading to nested bi-level optimization structure within a hybrid classical-quantum setting. We present detailed computational error and complexity analysis to highlight the potential advantages of our proposed framework over classical techniques. We implement our framework using the PennyLane library, apply it to a heat transfer optimization problem, and present simulation results using Bayesian optimization as the black box optimizer. We also demonstrate that by using an alternative tensor product decomposition which better exploits the sparsity and structure of linear systems arising from PDE discretizations, one can substantially overcome the key computational bottleneck in VQLS arising from commonly employed Pauli basis for the linear combination of unitary (LCU) decomposition step within VQLS.

arXiv:2405.16651•ACM Transactions on Quantum Computing•Aug 23, 2025•6 citations
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.
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 (PDE)-constrained optimization, where an optimization problem is subject to PDE constraints, arises in various applications such as design, control, and inference. Solving such problems is computationally demanding because it requires repeatedly solving a PDE and using its solution within an optimization process. In this paper, we first propose a fully coherent quantum algorithm for solving PDE-constrained optimization problems. The proposed method combines a quantum PDE solver that prepares the solution vector as a quantum state, and a quantum optimizer that assumes oracle access to a quantized objective function. The central idea is the explicit construction of the oracle in a form of block-encoding for the objective function, which coherently uses the output of a quantum PDE solver. This enables us to avoid classical access to the full solution that requires quantum state tomography canceling out the potential quantum speedups. We also derive the overall computational complexity of the proposed method with respect to parameters for optimization and PDE simulation, where quantum speedup is inherited from the underlying quantum PDE solver. We numerically demonstrate the validity of the proposed method by applications, including a parameter calibration problem in the Black-Scholes equation and a material parameter design problem in the wave equation. This work presents the concept of composing quantum subroutines so that the weakness of one (i.e., prohibitive readout overhead) is neutralized by the strength of another (i.e., coherent oracle access), toward a bottleneck-free quantum algorithm.
The advent of quantum computing processors with possibility to scale beyond experimental capacities magnifies the importance of studying their applications. Combinatorial optimization problems can be one of the promising applications of these new devices. These problems are recurrent in industrial applications and they are in general difficult for classical computing hardware. In this work, we provide a survey of the approaches to solving different types of combinatorial optimization problems, in particular quadratic unconstrained binary optimization (QUBO) problems on a gate model quantum computer. We focus mainly on four different approaches including digitizing the adiabatic quantum computing, global quantum optimization algorithms, the quantum algorithms that approximate the ground state of a general QUBO problem, and quantum sampling. We also discuss the quantum algorithms that are custom designed to solve certain types of QUBO problems.
We present QuantumSync, the first quantum algorithm for solving a synchronization problem in the context of computer vision. In particular, we focus on permutation synchronization which involves solving a non-convex optimization problem in discrete variables. We start by formulating synchronization into a quadratic unconstrained binary optimization problem (QUBO). While such formulation respects the binary nature of the problem, ensuring that the result is a set of permutations requires extra care. Hence, we: (i) show how to insert permutation constraints into a QUBO problem and (ii) solve the constrained QUBO problem on the current generation of the adiabatic quantum computers D-Wave. Thanks to the quantum annealing, we guarantee global optimality with high probability while sampling the energy landscape to yield confidence estimates. Our proof-of-concepts realization on the adiabatic D-Wave computer demonstrates that quantum machines offer a promising way to solve the prevalent yet difficult synchronization problems.
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.
We present a novel variational quantum framework for linear partial differential equation (PDE) constrained optimization problems. Such problems arise in many scientific and engineering domains. For instance, in aerodynamics, the PDE constraints are the conservation laws such as momentum, mass and energy balance, the design variables are vehicle shape parameters and material properties, and the objective could be to minimize the effect of transient heat loads on the vehicle or to maximize the lift-to-drag ratio. The proposed framework utilizes the variational quantum linear solver (VQLS) algorithm and a black box optimizer as its two main building blocks. VQLS is used to solve the linear system, arising from the discretization of the PDE constraints for given design parameters, and evaluate the design cost/objective function. The black box optimizer is used to select next set of parameter values based on this evaluated cost, leading to nested bi-level optimization structure within a hybrid classical-quantum setting. We present detailed computational error and complexity analysis to highlight the potential advantages of our proposed framework over classical techniques. We implement our framework using the PennyLane library, apply it to a heat transfer optimization problem, and present simulation results using Bayesian optimization as the black box optimizer. We also demonstrate that by using an alternative tensor product decomposition which better exploits the sparsity and structure of linear systems arising from PDE discretizations, one can substantially overcome the key computational bottleneck in VQLS arising from commonly employed Pauli basis for the linear combination of unitary (LCU) decomposition step within VQLS.