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

QuAnt: Quantum Annealing with Learnt Couplings

Marcel Seelbach Benkner, Maximilian Krahn, Edith Tretschk, Zorah Lähner, Michael Moeller, Vladislav Golyanik

Published Oct 13, 2022• 4 citations
arXivHTMLPDF

Abstract

Modern quantum annealers can find high-quality solutions to combinatorial optimisation objectives given as quadratic unconstrained binary optimisation (QUBO) problems. Unfortunately, obtaining suitable QUBO forms in computer vision remains challenging and currently requires problem-specific analytical derivations. Moreover, such explicit formulations impose tangible constraints on solution encodings. In stark contrast to prior work, this paper proposes to learn QUBO forms from data through gradient backpropagation instead of deriving them. As a result, the solution encodings can be chosen flexibly and compactly. Furthermore, our methodology is general and virtually independent of the specifics of the target problem type. We demonstrate the advantages of learnt QUBOs on the diverse problem types of graph matching, 2D point cloud alignment and 3D rotation estimation. Our results are competitive with the previous quantum state of the art while requiring much fewer logical and physical qubits, enabling our method to scale to larger problems. The code and the new dataset will be open-sourced.

DOI
10.48550/arxiv.2210.08114

Related papers

QuCOOP: A Versatile Framework for Solving Composite and Binary-Parametrised Problems on Quantum Annealers

Natacha Kuete Meli, Vladislav Golyanik, Marcel Seelbach Benkner +1 more

There is growing interest in solving computer vision problems such as mesh or point set alignment using Adiabatic Quantum Computing (AQC). Unfortunately, modern experimental AQC devices such as D-Wave only support Quadratic Unconstrained Binary Optimisation (QUBO) problems, which severely limits their applicability. This paper proposes a new way to overcome this limitation and introduces QuCOOP, an optimisation framework extending the scope of AQC to composite and binary-parametrised, possibly non-quadratic problems. The key idea of QuCOOP is to iteratively approximate the original objective function by a sequel of local (intermediate) QUBO forms, whose binary parameters can be sampled on AQC devices. We experiment with quadratic assignment problems, shape matching and point set registration without knowing the correspondences in advance. Our approach achieves state-of-the-art results across multiple instances of tested problems1.

IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings - IEEE Computer Society Conference on Computer Vision and Pattern Recognition/Proceedings•Jun 10, 2025•3 citations

Automaton-based methodology for implementing optimization constraints for quantum annealing

Hristo N. Djidjev

Quantum annealing computers are designed to produce high-quality solutions to optimization problems that can be formulated as quadratic unconstrained binary optimization (QUBO) problems. While most of the well known NP-hard problems can easily be represented as quadratic binary problems, such formulations usually contain constraints that have to be added as penalties to the objective function in order to obtain QUBOs. In this paper, we propose a method based on finite automaton representation of the constraints for generating penalty implementations for them, which uses fewer qubits than the alternatives and is general enough to be applied to a whole class of constraints.

ACM International Conference on Computing Frontiers (CF)•May 11, 2020•1 citation

Quadratic Unconstrained Binary Optimisation via Quantum-Inspired Annealing

Joseph Bowles, Alexandre Dauphin, Patrick Huembeli +2 more

We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. The algorithm can be seen as an analogue of quantum annealing under the restriction of a product state space, where the dynamical evolution in quantum annealing is replaced with a gradient-descent based method. This formulation is able to quickly find high-quality solutions to large-scale problem instances, and can naturally be accelerated by dedicated hardware such as graphics processing units. We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions. We find that our algorithm offers a similar performance to current state of the art approaches within a comparably simple gradient-based and non-stochastic setting.

arXiv:2108.08064•Aug 18, 2021•0 citations

AutoQubo

Alberto Moraglio, Serban Paul Georgescu, Przemysław Sadowski

This paper presents a general method to derive automatically a Quadratic Unconstrained Binary Optimisation (QUBO) formulation of, in principle, any combinatorial optimisation problem from its high-level description given in any programming language in a free format. Currently ad-hoc approaches to formulating a problem at a time as a QUBO are the norm. The proposed method goes beyond the state-of-the-art as it is general in its applicability. The method is data-driven and based on sampling, but the obtained QUBO is exact rather than only an approximation of the original problem for optimisation problems occurring in practice. The method is of particular interest in the context of Quantum Ising Machines - quantum computers specialised to optimisation tasks. It can be understood as a compiler that makes these machines usable without specific expertise by automating the translation of high-level description of combinatorial optimisation problems to a low-level format suitable for the quantum hardware.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 9, 2022•24 citations

Multi-objective QUBO solver

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•13 citations

Reducing quantum annealing biases for solving the graph partitioning problem

Elijah Pelofske, Georg Hahn, Hristo N. Djidjev

Quantum annealers offer an efficient way to compute high quality solutions of NP-hard problems when expressed in a QUBO (quadratic unconstrained binary optimization) or an Ising form. This is done by mapping a problem onto the physical qubits and couplers of the quantum chip, from which a solution is read after a process called quantum annealing. However, this process is subject to multiple sources of biases, including poor calibration, leakage between adjacent qubits, control biases, etc., which might negatively influence the quality of the annealing results. In this work, we aim at mitigating the effect of such biases for solving constrained optimization problems, by offering a two-step method, and apply it to Graph Partitioning. In the first step, we measure and reduce any biases that result from implementing the constraints of the problem. In the second, we add the objective function to the resulting bias-corrected implementation of the constraints, and send the problem to the quantum annealer. We apply this concept to Graph Partitioning, an important NP-hard problem, which asks to find a partition of the vertices of a graph that is balanced (the constraint) and minimizes the cut size (the objective). We first quantify the bias of the implementation of the constraint on the quantum annealer, that is, we require, in an unbiased implementation, that any two vertices have the same likelihood of being assigned to the same or to different parts of the partition. We then propose an iterative method to correct any such biases. We demonstrate that, after adding the objective, solving the resulting bias-corrected Ising problem on the quantum annealer results in a higher solution accuracy.

arXiv:2103.04963•ACM International Conference on Computing Frontiers (CF)•Apr 29, 2021•2 citations
Modern quantum annealers can find high-quality solutions to combinatorial optimisation objectives given as quadratic unconstrained binary optimisation (QUBO) problems. Unfortunately, obtaining suitable QUBO forms in computer vision remains challenging and currently requires problem-specific analytical derivations. Moreover, such explicit formulations impose tangible constraints on solution encodings. In stark contrast to prior work, this paper proposes to learn QUBO forms from data through gradient backpropagation instead of deriving them. As a result, the solution encodings can be chosen flexibly and compactly. Furthermore, our methodology is general and virtually independent of the specifics of the target problem type. We demonstrate the advantages of learnt QUBOs on the diverse problem types of graph matching, 2D point cloud alignment and 3D rotation estimation. Our results are competitive with the previous quantum state of the art while requiring much fewer logical and physical qubits, enabling our method to scale to larger problems. The code and the new dataset will be open-sourced.
There is growing interest in solving computer vision problems such as mesh or point set alignment using Adiabatic Quantum Computing (AQC). Unfortunately, modern experimental AQC devices such as D-Wave only support Quadratic Unconstrained Binary Optimisation (QUBO) problems, which severely limits their applicability. This paper proposes a new way to overcome this limitation and introduces QuCOOP, an optimisation framework extending the scope of AQC to composite and binary-parametrised, possibly non-quadratic problems. The key idea of QuCOOP is to iteratively approximate the original objective function by a sequel of local (intermediate) QUBO forms, whose binary parameters can be sampled on AQC devices. We experiment with quadratic assignment problems, shape matching and point set registration without knowing the correspondences in advance. Our approach achieves state-of-the-art results across multiple instances of tested problems1.
Quantum annealing computers are designed to produce high-quality solutions to optimization problems that can be formulated as quadratic unconstrained binary optimization (QUBO) problems. While most of the well known NP-hard problems can easily be represented as quadratic binary problems, such formulations usually contain constraints that have to be added as penalties to the objective function in order to obtain QUBOs. In this paper, we propose a method based on finite automaton representation of the constraints for generating penalty implementations for them, which uses fewer qubits than the alternatives and is general enough to be applied to a whole class of constraints.
We present a classical algorithm to find approximate solutions to instances of quadratic unconstrained binary optimisation. The algorithm can be seen as an analogue of quantum annealing under the restriction of a product state space, where the dynamical evolution in quantum annealing is replaced with a gradient-descent based method. This formulation is able to quickly find high-quality solutions to large-scale problem instances, and can naturally be accelerated by dedicated hardware such as graphics processing units. We benchmark our approach for large scale problem instances with tuneable hardness and planted solutions. We find that our algorithm offers a similar performance to current state of the art approaches within a comparably simple gradient-based and non-stochastic setting.
This paper presents a general method to derive automatically a Quadratic Unconstrained Binary Optimisation (QUBO) formulation of, in principle, any combinatorial optimisation problem from its high-level description given in any programming language in a free format. Currently ad-hoc approaches to formulating a problem at a time as a QUBO are the norm. The proposed method goes beyond the state-of-the-art as it is general in its applicability. The method is data-driven and based on sampling, but the obtained QUBO is exact rather than only an approximation of the original problem for optimisation problems occurring in practice. The method is of particular interest in the context of Quantum Ising Machines - quantum computers specialised to optimisation tasks. It can be understood as a compiler that makes these machines usable without specific expertise by automating the translation of high-level description of combinatorial optimisation problems to a low-level format suitable for the quantum hardware.
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.
Quantum annealers offer an efficient way to compute high quality solutions of NP-hard problems when expressed in a QUBO (quadratic unconstrained binary optimization) or an Ising form. This is done by mapping a problem onto the physical qubits and couplers of the quantum chip, from which a solution is read after a process called quantum annealing. However, this process is subject to multiple sources of biases, including poor calibration, leakage between adjacent qubits, control biases, etc., which might negatively influence the quality of the annealing results. In this work, we aim at mitigating the effect of such biases for solving constrained optimization problems, by offering a two-step method, and apply it to Graph Partitioning. In the first step, we measure and reduce any biases that result from implementing the constraints of the problem. In the second, we add the objective function to the resulting bias-corrected implementation of the constraints, and send the problem to the quantum annealer. We apply this concept to Graph Partitioning, an important NP-hard problem, which asks to find a partition of the vertices of a graph that is balanced (the constraint) and minimizes the cut size (the objective). We first quantify the bias of the implementation of the constraint on the quantum annealer, that is, we require, in an unbiased implementation, that any two vertices have the same likelihood of being assigned to the same or to different parts of the partition. We then propose an iterative method to correct any such biases. We demonstrate that, after adding the objective, solving the resulting bias-corrected Ising problem on the quantum annealer results in a higher solution accuracy.