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:1605.03152 · Electronic Notes in Theoretical Computer Science

Multiobjective Optimization in a Quantum Adiabatic Computer

Benjamín Barán, Marcos Villagra

Published Dec 1, 2016• 10 citations
arXivHTMLPDF

Abstract

In this work we propose what we consider the first quantum algorithm for multiobjective combinatorial optimization, at least to the best of our knowledge. The proposed algorithm is based on the adiabatic algorithm of Farhi et al. and it is constructed by mapping a multiobjective combinatorial optimization problem into a Hamiltonian using a convex combination among objectives. We present mathematical properties of the eigenspectrum of the associated Hamiltonian and prove that the quantum adiabatic algorithm can find Pareto-optimal solutions provided certain convex combinations of objectives are used and the underlying multiobjective problem meets certain restrictions.

DOI
10.1016/j.entcs.2016.12.003

Related papers

A Quantum Adiabatic Algorithm for Multiobjective Combinatorial Optimization

Benjamín Barán, Marcos Villagra

In this work we show how to use a quantum adiabatic algorithm to solve multiobjective optimization problems. For the first time, we demonstrate a theorem proving that the quantum adiabatic algorithm can find Pareto-optimal solutions in finite-time, provided some restrictions to the problem are met. A numerical example illustrates an application of the theorem to a well-known problem in multiobjective optimization. This result opens the door to solve multiobjective optimization problems using current technology based on quantum annealing.

Axioms•Mar 9, 2019•1 citation

Variational quantum multiobjective optimization

Linus Ekstrøm, Hao Wang, Sebastian Schmitt

Solving combinatorial optimization problems on near-term quantum devices has gained a lot of attention in recent years. Currently, most studies have focused on single-objective problems, whereas many real-world applications need to consider multiple, mostly conflicting objectives, such as cost and quality. We present a variational quantum optimization algorithm to solve discrete multiobjective optimization problems on quantum computers. The proposed quantum multiobjective optimization (QMOO) algorithm incorporates all cost Hamiltonians representing the classical objective functions in the quantum circuit and produces a quantum state consisting of Pareto-optimal solutions in superposition. From this state, we retrieve a set of solutions and utilize the widely applied hypervolume indicator to determine its quality as an approximation to the Pareto front. The variational parameters of the QMOO circuit are tuned by maximizing the hypervolume indicator in a quantum-classical hybrid fashion. We show the effectiveness of the proposed algorithm on several benchmark problems with up to five objectives. We investigate the influence of the classical optimizer and the circuit depth, and compare them to results from classical optimization algorithms. We find that the algorithm is robust to shot noise and produces good results with as few as 128 measurement shots in each iteration. These promising results open the possibility to run the algorithm on near-term quantum hardware.

arXiv:2312.14151•Physical Review Research•May 12, 2025•20 citations

Quantum Algorithms for Multiobjective Combinatorial Optimization

Gerardo G. Fogel

This thesis studies multiobjective optimization problems in the context of quantum computing. Quantum computing is a computational paradigm based on the laws of quantum physics as superposition, interference and entanglement. New quantum algorithms have emerged that proved to be more efficient than classical algorithms. Particularly, Grover’s search algorithm can find a specific element out of a set of N elements with complexity O(√N). Applications of Grover’s algorithm to optimization problems are currently being studied by other researchers, and in this thesis, a new adaptive search method based on Grover’s algorithm applied to several biobjective optimization problems is introduced. This new algorithm is compared against one of the most cited multiobjective optimization algorithms known as NSGA-II. Experimental evidence suggests that the quantum optimization method proposed in this work is at least as effective as NSGA-II in average, considering an equal number of executions. The proposed quantum algorithm, however, only requires approximately the square root of the number of evaluations executed by NSGA-II. Also, two different types of oracles with regard to the proposed algorithm were considered and the experimental results have shown that one of this oracles has requiered less iterations for similar performance.

•Jan 1, 2017•0 citations

Case studies in quantum adiabatic optimization

David Gosset

Quantum adiabatic optimization is a quantum algorithm for solving classical optimization problems (E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser. Quantum computation by adiabatic evolution, 2000. arXiv:quant-ph/0001106). The solution to an optimization prob-lem is encoded in the ground state of a "problem Hamiltonian " Hp which acts on the Hilbert space of n spin 1/2 particles and is diagonal in the Pauli z basis. To produce this ground state, one first initializes the quantum system in the ground state of a different Hamiltonian and then adiabatically changes the Hamiltonian into Hp. Farhi et al suggest the interpolating Hamiltonian i where the parameter s is slowly changed as a function of time between 0 and 1. The running time of this algorithm is related to the minimum spectral gap of H(s) for s E (0, 11. We study such transverse field spin Hamiltonians using both analytic and numerical techniques. Our approach is example-based, that is, we study some specific choices for the problem Hamiltonian Hp which illustrate the breadth of phenomena which can occur. We

•Jan 1, 2011•1 citation

Multiobjective Optimization and Network Routing With Near-Term Quantum Computers

Shao-Hen Chiew, Kilian Poirier, Rajesh Mishra +6 more

Multi-objective optimization is a ubiquitous problem that arises naturally in many scientific and industrial areas. Network routing optimization with multi-objective performance demands falls into this problem class, and finding good quality solutions at large scales is generally challenging. In this work, we develop a scheme with which near-term quantum computers can be applied to solve multi-objective combinatorial optimization problems. We study the application of this scheme to the network routing problem in detail, by first mapping it to the multi-objective shortest path problem. Focusing on an implementation based on the quantum approximate optimization algorithm (QAOA) – the go-to approach for tackling optimization problems on near-term quantum computers – we examine the Pareto plot that results from the scheme, and qualitatively analyze its ability to produce Pareto-optimal solutions. We further provide theoretical and numerical scaling analyses of the resource requirements and performance of QAOA, and identify key challenges associated with this approach. Finally, through Amazon Braket we execute small-scale implementations of our scheme on the IonQ Harmony 11-qubit quantum computer.

arXiv:2308.08245•IEEE Transactions on Quantum Engineering•Jan 1, 2024•16 citations

Q-CHOP: Quantum constrained Hamiltonian optimization

Michael A. Perlin, Ruslan Shaydulin, Benjamin Hall +7 more

Combinatorial optimization problems that arise in science and industry typically have constraints. Yet the presence of constraints makes them challenging to tackle using both classical and quantum optimization algorithms. We propose a new quantum algorithm for constrained optimization, which we call quantum constrained Hamiltonian optimization (Q-CHOP). Our algorithm leverages the observation that for many problems, while the best solution is difficult to find, the worst feasible (constraint-satisfying) solution is known. The basic idea of Q-CHOP is to enforce a Hamiltonian constraint at all times, thereby restricting evolution to the subspace of feasible states, and slowly “rotate” an objective Hamiltonian to trace an adiabatic path from the worst feasible state to the best feasible state. Q-CHOP thereby assigns qualitatively distinct roles to the constraint and objective functions of a constrained optimization problem. We additionally propose a version of Q-CHOP that can start in any feasible state. Finally, we benchmark Q-CHOP against the commonly-used adiabatic algorithm of quantum annealing with an objective function that penalizes constraint violation, and find that Q-CHOP consistently performs significantly better on a wide range of problems, including textbook graph problems, knapsack problems, combinatorial auctions, and a real-world financial use case of bond exchange-traded fund basket optimization.

arXiv:2403.05653•ACM Transactions on Quantum Computing•Dec 2, 2025•4 citations
In this work we propose what we consider the first quantum algorithm for multiobjective combinatorial optimization, at least to the best of our knowledge. The proposed algorithm is based on the adiabatic algorithm of Farhi et al. and it is constructed by mapping a multiobjective combinatorial optimization problem into a Hamiltonian using a convex combination among objectives. We present mathematical properties of the eigenspectrum of the associated Hamiltonian and prove that the quantum adiabatic algorithm can find Pareto-optimal solutions provided certain convex combinations of objectives are used and the underlying multiobjective problem meets certain restrictions.
In this work we show how to use a quantum adiabatic algorithm to solve multiobjective optimization problems. For the first time, we demonstrate a theorem proving that the quantum adiabatic algorithm can find Pareto-optimal solutions in finite-time, provided some restrictions to the problem are met. A numerical example illustrates an application of the theorem to a well-known problem in multiobjective optimization. This result opens the door to solve multiobjective optimization problems using current technology based on quantum annealing.
Solving combinatorial optimization problems on near-term quantum devices has gained a lot of attention in recent years. Currently, most studies have focused on single-objective problems, whereas many real-world applications need to consider multiple, mostly conflicting objectives, such as cost and quality. We present a variational quantum optimization algorithm to solve discrete multiobjective optimization problems on quantum computers. The proposed quantum multiobjective optimization (QMOO) algorithm incorporates all cost Hamiltonians representing the classical objective functions in the quantum circuit and produces a quantum state consisting of Pareto-optimal solutions in superposition. From this state, we retrieve a set of solutions and utilize the widely applied hypervolume indicator to determine its quality as an approximation to the Pareto front. The variational parameters of the QMOO circuit are tuned by maximizing the hypervolume indicator in a quantum-classical hybrid fashion. We show the effectiveness of the proposed algorithm on several benchmark problems with up to five objectives. We investigate the influence of the classical optimizer and the circuit depth, and compare them to results from classical optimization algorithms. We find that the algorithm is robust to shot noise and produces good results with as few as 128 measurement shots in each iteration. These promising results open the possibility to run the algorithm on near-term quantum hardware.
This thesis studies multiobjective optimization problems in the context of quantum computing. Quantum computing is a computational paradigm based on the laws of quantum physics as superposition, interference and entanglement. New quantum algorithms have emerged that proved to be more efficient than classical algorithms. Particularly, Grover’s search algorithm can find a specific element out of a set of N elements with complexity O(√N). Applications of Grover’s algorithm to optimization problems are currently being studied by other researchers, and in this thesis, a new adaptive search method based on Grover’s algorithm applied to several biobjective optimization problems is introduced. This new algorithm is compared against one of the most cited multiobjective optimization algorithms known as NSGA-II. Experimental evidence suggests that the quantum optimization method proposed in this work is at least as effective as NSGA-II in average, considering an equal number of executions. The proposed quantum algorithm, however, only requires approximately the square root of the number of evaluations executed by NSGA-II. Also, two different types of oracles with regard to the proposed algorithm were considered and the experimental results have shown that one of this oracles has requiered less iterations for similar performance.
Quantum adiabatic optimization is a quantum algorithm for solving classical optimization problems (E. Farhi, J. Goldstone, S. Gutmann, and M. Sipser. Quantum computation by adiabatic evolution, 2000. arXiv:quant-ph/0001106). The solution to an optimization prob-lem is encoded in the ground state of a "problem Hamiltonian " Hp which acts on the Hilbert space of n spin 1/2 particles and is diagonal in the Pauli z basis. To produce this ground state, one first initializes the quantum system in the ground state of a different Hamiltonian and then adiabatically changes the Hamiltonian into Hp. Farhi et al suggest the interpolating Hamiltonian i where the parameter s is slowly changed as a function of time between 0 and 1. The running time of this algorithm is related to the minimum spectral gap of H(s) for s E (0, 11. We study such transverse field spin Hamiltonians using both analytic and numerical techniques. Our approach is example-based, that is, we study some specific choices for the problem Hamiltonian Hp which illustrate the breadth of phenomena which can occur. We
Multi-objective optimization is a ubiquitous problem that arises naturally in many scientific and industrial areas. Network routing optimization with multi-objective performance demands falls into this problem class, and finding good quality solutions at large scales is generally challenging. In this work, we develop a scheme with which near-term quantum computers can be applied to solve multi-objective combinatorial optimization problems. We study the application of this scheme to the network routing problem in detail, by first mapping it to the multi-objective shortest path problem. Focusing on an implementation based on the quantum approximate optimization algorithm (QAOA) – the go-to approach for tackling optimization problems on near-term quantum computers – we examine the Pareto plot that results from the scheme, and qualitatively analyze its ability to produce Pareto-optimal solutions. We further provide theoretical and numerical scaling analyses of the resource requirements and performance of QAOA, and identify key challenges associated with this approach. Finally, through Amazon Braket we execute small-scale implementations of our scheme on the IonQ Harmony 11-qubit quantum computer.
Combinatorial optimization problems that arise in science and industry typically have constraints. Yet the presence of constraints makes them challenging to tackle using both classical and quantum optimization algorithms. We propose a new quantum algorithm for constrained optimization, which we call quantum constrained Hamiltonian optimization (Q-CHOP). Our algorithm leverages the observation that for many problems, while the best solution is difficult to find, the worst feasible (constraint-satisfying) solution is known. The basic idea of Q-CHOP is to enforce a Hamiltonian constraint at all times, thereby restricting evolution to the subspace of feasible states, and slowly “rotate” an objective Hamiltonian to trace an adiabatic path from the worst feasible state to the best feasible state. Q-CHOP thereby assigns qualitatively distinct roles to the constraint and objective functions of a constrained optimization problem. We additionally propose a version of Q-CHOP that can start in any feasible state. Finally, we benchmark Q-CHOP against the commonly-used adiabatic algorithm of quantum annealing with an objective function that penalizes constraint violation, and find that Q-CHOP consistently performs significantly better on a wide range of problems, including textbook graph problems, knapsack problems, combinatorial auctions, and a real-world financial use case of bond exchange-traded fund basket optimization.