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:2405.17676 · Genetic and Evolutionary Computation Conference Companion (GECCO Companion)

Utilising Quantum Hybrid Solver for Bi-objective Quadratic Assignment Problems

Mayowa Ayodele

Published Jul 14, 2024• 2 citations
arXivHTMLPDF

Abstract

The intersection between quantum computing and optimisation has been an area of interest in recent years. There have been numerous studies exploring the application of quantum and quantum-hybrid solvers to various optimisation problems. This work explores scalarisation methods within the context of solving the bi-objective quadratic assignment problem using a quantum-hybrid solver. We show results that are consistent with previous research on a different Ising machine.

DOI
10.1145/3638530.3664097

Related papers

Multi-objective QUBO solver: bi-objective quadratic assignment problem

Mayowa Ayodele, Richard Allmendinger, Manuel López‐Ibáñez +1 more

Quantum and quantum-inspired optimisation algorithms are designed to solve problems represented in binary, quadratic and unconstrained form. Combinatorial optimisation problems are therefore often formulated as Quadratic Unconstrained Binary Optimisation Problems (QUBO) to solve them with these algorithms. Moreover, these QUBO solvers are often implemented using specialised hardware to achieve enormous speedups, e.g. Fujitsu's Digital Annealer (DA) and D-Wave's Quantum Annealer. However, these are single-objective solvers, while many real-world problems feature multiple conflicting objectives. Thus, a common practice when using these QUBO solvers is to scalarise such multi-objective problems into a sequence of single-objective problems. Due to design trade-offs of these solvers, formulating each scalarisation may require more time than finding a local optimum. We present the first attempt to extend the algorithm supporting a commercial QUBO solver as a multi-objective solver that is not based on scalarisation. The proposed multi-objective DA algorithm is validated on the bi-objective Quadratic Assignment Problem. We observe that algorithm performance significantly depends on the archiving strategy adopted, and that combining DA with non-scalarisation methods to optimise multiple objectives outperforms the current scalarised version of the DA in terms of final solution quality.

arXiv:2205.13399•Genetic and Evolutionary Computation Conference (GECCO)•Jul 8, 2022•17 citations

Evaluating the performance of the Quantum Approximate Optimisation Algorithm to solve the Quadratic Assignment Problem

M. T. Khumalo, Krupa Prag, Ken J. Nixon

The performance of the Quantum Approximate Optimisation Algorithm (QAOA) in solving the Quadratic Assignment Problem (QAP) is evaluated, with the Variational Quantum Eigensolver (VQE) as a benchmark. The QAP is directly revelant to numerous industry scenarios. The QAP, a Combinatorial Optimisation Problem (COP), is classified as$\mathcal{NP}$-Hard. This classification means CPU time increases exponentially as the problem size scales when solving the QAP using deterministic optimisation techniques. Therefore, this work investigates the QAOA in search of a non-deterministic optimisation technique to efficiently obtain solutions to the QAP. This research compares two warm start techniques to solve QAP instances of sizes 3 to 7. The metrics of comparison - that measure efficiency and solution quality - were introduced in previous work on this topic. For the QAOA, the impact of the p-value, a determination of circuit depth, is investigated. Of the two quantum hybrid heuristics, the VQE retrieves solutions in a shorter computational time with a smaller circuit size, which allows for solving instances with a larger problem size. Compared to the VQE, the QAOA performs better in terms of feasibility as the problem size scales. The quantum warm start method results implies that the QAOA may not maintain higher solution quality for instances larger than size 4. Still, further investigation should be conducted once quantum devices with more qubits and higher quantum volumes are available.

International Conference on Soft Computing & Machine Intelligence (ISCMI)•Nov 26, 2022•1 citation

Solving assignment problems via Quantum Computing: a case-study in train seating arrangement

Ilaria Gioda, Davide Caputo, Edoardo Fadda +3 more

In recent years, researchers have oriented their studies towards new technologies based on quantum physics that should resolve complex problems currently considered to be intractable. This new research area is called Quantum Computing. What makes Quantum Computing so attractive is the particular way with which quantum technology operates and the great potential it can offer to solve real-world problems. This work focuses on solving assignment-like combinatorial optimization problems by exploiting this novel computational approach. A case-study, denoted as the Seating Arrangement Optimization problem, is considered. It is modeled through the Quadratic Unconstrained Binary Optimization paradigm and solved through two tools made available by the D-Wave Systems company, QBSolv, and a quantum-classical hybrid system. The obtained experimental results are compared in terms of solution quality and computational efficiency.

Annals of Computer Science and Information Systems•Sep 26, 2021•3 citations

Applying Quantum Annealing to the Tail Assignment Problem

Luís Noites Martins

Airline companies struggle every day trying to schedule crew, flights and aircraft.Tail Assignment is the problem of allocating individual aircraft to a set of flights, while ensuring multiple constraints and aiming to minimise an objective function, such as operational costs.Given the enormous amount of possibilities and constraints involved, this problem has been a study case for the last decade.Many solutions have emerged using classical computing, but with limitations regarding performance.Quantum Annealing (QA) is a heuristic technique for finding global minimum energy levels over an energy landscape using quantum mechanics.Due to its characteristics, it has been proved to have a clear advantage in solving some complex optimisation problems, being a promising technique to apply in multiple fields.In this study, Tail Assignment Problem was set as a Quadratic Unconstrained Binary Optimisation (QUBO) model, using two different techniques, and was solved using a classical and two hybrid solvers.Tests were run based on extractions from real-world data, analysing the performance of the implementation in terms of time, scalability and quality (i.e., the lowest operational costs) of the obtained solutions.We concluded that using a library for modelling the problem as well as considering individual flights rather than pre-aggregating them in strings can be a bottleneck when it comes to its scalability.Furthermore, we found out that there was a higher probability of obtaining better solutions for this problem using one of the hybrid solvers when compared with the classical heuristic algorithms such as Simulated Annealing (SA).These findings can serve as foundations for further studies.

•Jul 23, 2020•4 citations

Improving the Solving of Optimization Problems: A Comprehensive Review of Quantum Approaches

Deborah Volpe, Giacomo Orlandi, Giovanna Turvani

Optimization is a crucial challenge across various domains, including finance, resource allocation, and mobility. Quantum computing has the potential to redefine the way we handle complex problems by reducing computational complexity and enhancing solution quality. Optimization, particularly of objective functions, stands to benefit significantly from quantum solvers, which leverage principles of quantum mechanics like superposition, entanglement, and tunneling. The Ising and Quadratic Unconstrained Binary Optimization (QUBO) models are the most suitable formulations for these solvers, involving binary variables and constraints treated as penalties within the overall objective function. To harness quantum approaches for optimization, two primary strategies are employed: exploiting quantum annealers—special-purpose optimization devices—and designing algorithms based on quantum circuits. This review provides a comprehensive overview of quantum optimization methods, examining their advantages, challenges, and limitations. It demonstrates their application to real-world scenarios and outlines the steps to convert generic optimization problems into quantum-compliant models. Lastly, it discusses available tools and frameworks that facilitate the exploration of quantum solutions for optimization tasks.

Quantum Reports•Jan 7, 2025•43 citations

Quadratic Optimization and Quantum Computing

Mark W. Lewis

Recent advances in quantum computing along with increased interest in solving difficult optimization problems is shining a light on a research area that has been quietly growing for the past twenty plus years. This area involves modeling difficult decision problems as Quadratic Unconstrained Binary Optimization (QUBO) problems and then solving them on a new type

Science Trends•Nov 7, 2017•0 citations
The intersection between quantum computing and optimisation has been an area of interest in recent years. There have been numerous studies exploring the application of quantum and quantum-hybrid solvers to various optimisation problems. This work explores scalarisation methods within the context of solving the bi-objective quadratic assignment problem using a quantum-hybrid solver. We show results that are consistent with previous research on a different Ising machine.
Quantum and quantum-inspired optimisation algorithms are designed to solve problems represented in binary, quadratic and unconstrained form. Combinatorial optimisation problems are therefore often formulated as Quadratic Unconstrained Binary Optimisation Problems (QUBO) to solve them with these algorithms. Moreover, these QUBO solvers are often implemented using specialised hardware to achieve enormous speedups, e.g. Fujitsu's Digital Annealer (DA) and D-Wave's Quantum Annealer. However, these are single-objective solvers, while many real-world problems feature multiple conflicting objectives. Thus, a common practice when using these QUBO solvers is to scalarise such multi-objective problems into a sequence of single-objective problems. Due to design trade-offs of these solvers, formulating each scalarisation may require more time than finding a local optimum. We present the first attempt to extend the algorithm supporting a commercial QUBO solver as a multi-objective solver that is not based on scalarisation. The proposed multi-objective DA algorithm is validated on the bi-objective Quadratic Assignment Problem. We observe that algorithm performance significantly depends on the archiving strategy adopted, and that combining DA with non-scalarisation methods to optimise multiple objectives outperforms the current scalarised version of the DA in terms of final solution quality.
The performance of the Quantum Approximate Optimisation Algorithm (QAOA) in solving the Quadratic Assignment Problem (QAP) is evaluated, with the Variational Quantum Eigensolver (VQE) as a benchmark. The QAP is directly revelant to numerous industry scenarios. The QAP, a Combinatorial Optimisation Problem (COP), is classified asNP\mathcal{NP}NP-Hard. This classification means CPU time increases exponentially as the problem size scales when solving the QAP using deterministic optimisation techniques. Therefore, this work investigates the QAOA in search of a non-deterministic optimisation technique to efficiently obtain solutions to the QAP. This research compares two warm start techniques to solve QAP instances of sizes 3 to 7. The metrics of comparison - that measure efficiency and solution quality - were introduced in previous work on this topic. For the QAOA, the impact of the p-value, a determination of circuit depth, is investigated. Of the two quantum hybrid heuristics, the VQE retrieves solutions in a shorter computational time with a smaller circuit size, which allows for solving instances with a larger problem size. Compared to the VQE, the QAOA performs better in terms of feasibility as the problem size scales. The quantum warm start method results implies that the QAOA may not maintain higher solution quality for instances larger than size 4. Still, further investigation should be conducted once quantum devices with more qubits and higher quantum volumes are available.
In recent years, researchers have oriented their studies towards new technologies based on quantum physics that should resolve complex problems currently considered to be intractable. This new research area is called Quantum Computing. What makes Quantum Computing so attractive is the particular way with which quantum technology operates and the great potential it can offer to solve real-world problems. This work focuses on solving assignment-like combinatorial optimization problems by exploiting this novel computational approach. A case-study, denoted as the Seating Arrangement Optimization problem, is considered. It is modeled through the Quadratic Unconstrained Binary Optimization paradigm and solved through two tools made available by the D-Wave Systems company, QBSolv, and a quantum-classical hybrid system. The obtained experimental results are compared in terms of solution quality and computational efficiency.
Airline companies struggle every day trying to schedule crew, flights and aircraft.Tail Assignment is the problem of allocating individual aircraft to a set of flights, while ensuring multiple constraints and aiming to minimise an objective function, such as operational costs.Given the enormous amount of possibilities and constraints involved, this problem has been a study case for the last decade.Many solutions have emerged using classical computing, but with limitations regarding performance.Quantum Annealing (QA) is a heuristic technique for finding global minimum energy levels over an energy landscape using quantum mechanics.Due to its characteristics, it has been proved to have a clear advantage in solving some complex optimisation problems, being a promising technique to apply in multiple fields.In this study, Tail Assignment Problem was set as a Quadratic Unconstrained Binary Optimisation (QUBO) model, using two different techniques, and was solved using a classical and two hybrid solvers.Tests were run based on extractions from real-world data, analysing the performance of the implementation in terms of time, scalability and quality (i.e., the lowest operational costs) of the obtained solutions.We concluded that using a library for modelling the problem as well as considering individual flights rather than pre-aggregating them in strings can be a bottleneck when it comes to its scalability.Furthermore, we found out that there was a higher probability of obtaining better solutions for this problem using one of the hybrid solvers when compared with the classical heuristic algorithms such as Simulated Annealing (SA).These findings can serve as foundations for further studies.
Optimization is a crucial challenge across various domains, including finance, resource allocation, and mobility. Quantum computing has the potential to redefine the way we handle complex problems by reducing computational complexity and enhancing solution quality. Optimization, particularly of objective functions, stands to benefit significantly from quantum solvers, which leverage principles of quantum mechanics like superposition, entanglement, and tunneling. The Ising and Quadratic Unconstrained Binary Optimization (QUBO) models are the most suitable formulations for these solvers, involving binary variables and constraints treated as penalties within the overall objective function. To harness quantum approaches for optimization, two primary strategies are employed: exploiting quantum annealers—special-purpose optimization devices—and designing algorithms based on quantum circuits. This review provides a comprehensive overview of quantum optimization methods, examining their advantages, challenges, and limitations. It demonstrates their application to real-world scenarios and outlines the steps to convert generic optimization problems into quantum-compliant models. Lastly, it discusses available tools and frameworks that facilitate the exploration of quantum solutions for optimization tasks.