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

QUBOs for Sorting Lists and Building Trees

Christian Bauckhage, Thore Gerlach, Nico Piatkowski

Published Mar 15, 2022• 0 citations
arXivHTMLPDF

Abstract

We show that the fundamental tasks of sorting lists and building search trees or heaps can be modeled as quadratic unconstrained binary optimization problems (QUBOs). The idea is to understand these tasks as permutation problems and to devise QUBOs whose solutions represent appropriate permutation matrices. We discuss how to construct such QUBOs and how to solve them using Hopfield nets or adiabatic) quantum computing. In short, we show that neurocomputing methods or quantum computers can solve problems usually associated with abstract data structures.

DOI
10.48550/arxiv.2203.08815

Related papers

QUBOs

Christian Bauckhage, Rafet Sifa

Abstract In previous chapters, we already came across an instance of a quadratic unconstrained binary optimization problem or QUBO for short. In this chapter, we will now widen our perspective on QUBOs as our major plot line in this book is that any QUBO can be solved by running a Hopfield net and that any problem that can be solved by running a Hopfield net can be solved on a quantum computer. In other words, we will have a closer look at the characteristics and structure of QUBOs and discuss some of their notable peculiarities. However, we will not yet look at practical examples nor will we discuss how to actually solve QUBOs but leave these aspects to later chapters.

Cognitive technologies•Nov 17, 2025•0 citations

Succinct QUBO formulations for permutation problems by sorting networks

Katalin Friedl, Levente Gegő, László Kabódi +1 more

Quadratic Unconstrained Binary Optimization (QUBO) is a standard NP-hard optimization problem. Recently, it has gained renewed interest through quantum computing, as QUBOs directly reduce to the Ising model, on which quantum annealing devices are based. We introduce a QUBO formulation for permutations using compare-exchange networks, with only $O(n \log^2 n)$ binary variables. This is a substantial improvement over the standard permutation matrix encoding, which requires $n^2$ variables and has a much denser interaction graph. A central feature of our approach is uniformity: each permutation corresponds to a unique variable assignment, enabling unbiased sampling. Our construction also allows additional constraints, including fixed points and parity. Moreover, it provides a representation of permutations that supports the operations multiplication and inversion, and also makes it possible to check the order of a permutation. This can be used to uniformly generate permutations of a given order or, for example, permutations that commute with a specified permutation. To our knowledge, this is the first result linking oblivious compare-exchange networks with QUBO encodings. While similar functionality can be achieved using permutation matrices, our method yields QUBOs that are both smaller and sparser. We expect this method to be practically useful in areas where unbiased sampling of constrained permutations is important, including cryptography and combinatorial design.

quant-pharXiv:2603.07579•Mar 10, 2026•0 citations

Solving Quadratic Unconstrained Binary Optimization with divide-and-conquer and quantum algorithms

Gian Giacomo Guerreschi

Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications. To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost. With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers. Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach. When quantum heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used, our proposal leads to a double advantage: a substantial reduction of quantum resources, specifically an average of ~42% fewer qubits to solve MaxCut on random 3-regular graphs, together with an improvement in the quality of the approximate solutions reached.

arXiv:2101.07813•Jan 19, 2021•25 citations

Techniques to enhance a QUBO solver for permutation-based combinatorial optimization

Siong Thye Goh, Jianyuan Bo, Sabrish Gopalakrishnan +1 more

Many combinatorial optimization problems can be formulated as a problem to determine the order of sequence or to find a corresponding mapping of the objects. We call such problems permutation-based optimization problems. Many such problems can be formulated as a quadratic unconstrained binary optimization (QUBO) or Ising model by introducing a penalty coefficient to the permutation constraint terms. While classical and quantum annealing approaches have been proposed to solve QUBOs to date, they face issues with optimality and feasibility. Here we treat a given QUBO solver as a black box and propose techniques to enhance its performance. First, to ensure an effective search for good quality solutions, a smooth energy landscape is needed; we propose a data scaling approach that reduces the amplitudes of the input without compromising optimality. Second, we need to tune the penalty coefficient. In this paper, we illustrate that for certain problems, it suffices to tune the parameter by performing random sampling on the penalty coefficients to achieve good performance. Finally, to handle possible infeasibility of the solution, we introduce a polynomial-time projection algorithm. We apply these techniques along with a divide-and-conquer strategy to solve some large-scale permutation-based problems and present results for TSP and QAP.

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

Adiabatic Quantum Computing

Christian Bauckhage, Rafet Sifa

Abstract In this chapter, we finally have our first look at quantum computing. In particular, we consider adiabatic quantum computing which is a paradigm tailored to the general problem of bipolar QUBO solving. Given our study up to this point, its basic principles will be easy to understand since Hopfield nets for problem solving and adiabatic quantum computing are closely related concepts. Indeed, we already know about tensor products, Hopfield energies and their representation in terms of Hamiltonians, annealing, the axioms of quantum mechanics, the Schrödinger equation, and quantum superposition. All these concepts will now be jointly put to use and brought together with yet another quantum mechanical principle, namely the adiabatic theorem. Based on two examples of simple QUBO problems, we demonstrate how adiabatic quantum computers can explore their exponentially large search spaces in parallel and thus achieve quadratic speedup over classical exhaustive search procedures.

Cognitive technologies•Nov 17, 2025•0 citations

Quadratic unconstrained binary optimization problem preprocessing: Theory and empirical analysis

Mark W. Lewis, Fred Glover

The Quadratic Unconstrained Binary Optimization problem (QUBO) has become a unifying model for representing a wide range of combinatorial optimization problems, and for linking a variety of disciplines that face these problems. A new class of quantum annealing computer that maps QUBO onto a physical qubit network structure with specific size and edge density restrictions is generating a growing interest in ways to transform the underlying QUBO structure into an equivalent graph having fewer nodes and edges. In this article, we present rules for reducing the size of the QUBO matrix by identifying variables whose value at optimality can be predetermined. We verify that the reductions improve both solution quality and time to solution and, in the case of metaheuristic methods where optimal solutions cannot be guaranteed, the quality of solutions obtained within reasonable time limits. We discuss the general QUBO structural characteristics that can take advantage of these reduction techniques and perform careful experimental design and analysis to identify and quantify the specific characteristics most affecting reduction. The rules make it possible to dramatically improve solution times on a new set of problems using both the exact Cplex solver and a tabu search metaheuristic. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(2), 79–97 2017

arXiv:1705.09844•Networks•Jun 24, 2017•118 citations
We show that the fundamental tasks of sorting lists and building search trees or heaps can be modeled as quadratic unconstrained binary optimization problems (QUBOs). The idea is to understand these tasks as permutation problems and to devise QUBOs whose solutions represent appropriate permutation matrices. We discuss how to construct such QUBOs and how to solve them using Hopfield nets or adiabatic) quantum computing. In short, we show that neurocomputing methods or quantum computers can solve problems usually associated with abstract data structures.
Abstract In previous chapters, we already came across an instance of a quadratic unconstrained binary optimization problem or QUBO for short. In this chapter, we will now widen our perspective on QUBOs as our major plot line in this book is that any QUBO can be solved by running a Hopfield net and that any problem that can be solved by running a Hopfield net can be solved on a quantum computer. In other words, we will have a closer look at the characteristics and structure of QUBOs and discuss some of their notable peculiarities. However, we will not yet look at practical examples nor will we discuss how to actually solve QUBOs but leave these aspects to later chapters.
Quadratic Unconstrained Binary Optimization (QUBO) is a standard NP-hard optimization problem. Recently, it has gained renewed interest through quantum computing, as QUBOs directly reduce to the Ising model, on which quantum annealing devices are based. We introduce a QUBO formulation for permutations using compare-exchange networks, with only O(nlog⁡2n)O(n \log^2 n)O(nlog2n) binary variables. This is a substantial improvement over the standard permutation matrix encoding, which requires n2n^2n2 variables and has a much denser interaction graph. A central feature of our approach is uniformity: each permutation corresponds to a unique variable assignment, enabling unbiased sampling. Our construction also allows additional constraints, including fixed points and parity. Moreover, it provides a representation of permutations that supports the operations multiplication and inversion, and also makes it possible to check the order of a permutation. This can be used to uniformly generate permutations of a given order or, for example, permutations that commute with a specified permutation. To our knowledge, this is the first result linking oblivious compare-exchange networks with QUBO encodings. While similar functionality can be achieved using permutation matrices, our method yields QUBOs that are both smaller and sparser. We expect this method to be practically useful in areas where unbiased sampling of constrained permutations is important, including cryptography and combinatorial design.
Quadratic Unconstrained Binary Optimization (QUBO) is a broad class of optimization problems with many practical applications. To solve its hard instances in an exact way, known classical algorithms require exponential time and several approximate methods have been devised to reduce such cost. With the growing maturity of quantum computing, quantum algorithms have been proposed to speed up the solution by using either quantum annealers or universal quantum computers. Here we apply the divide-and-conquer approach to reduce the original problem to a collection of smaller problems whose solutions can be assembled to form a single Polynomial Binary Unconstrained Optimization instance with fewer variables. This technique can be applied to any QUBO instance and leads to either an all-classical or a hybrid quantum-classical approach. When quantum heuristics like the Quantum Approximate Optimization Algorithm (QAOA) are used, our proposal leads to a double advantage: a substantial reduction of quantum resources, specifically an average of ~42% fewer qubits to solve MaxCut on random 3-regular graphs, together with an improvement in the quality of the approximate solutions reached.
Many combinatorial optimization problems can be formulated as a problem to determine the order of sequence or to find a corresponding mapping of the objects. We call such problems permutation-based optimization problems. Many such problems can be formulated as a quadratic unconstrained binary optimization (QUBO) or Ising model by introducing a penalty coefficient to the permutation constraint terms. While classical and quantum annealing approaches have been proposed to solve QUBOs to date, they face issues with optimality and feasibility. Here we treat a given QUBO solver as a black box and propose techniques to enhance its performance. First, to ensure an effective search for good quality solutions, a smooth energy landscape is needed; we propose a data scaling approach that reduces the amplitudes of the input without compromising optimality. Second, we need to tune the penalty coefficient. In this paper, we illustrate that for certain problems, it suffices to tune the parameter by performing random sampling on the penalty coefficients to achieve good performance. Finally, to handle possible infeasibility of the solution, we introduce a polynomial-time projection algorithm. We apply these techniques along with a divide-and-conquer strategy to solve some large-scale permutation-based problems and present results for TSP and QAP.
Abstract In this chapter, we finally have our first look at quantum computing. In particular, we consider adiabatic quantum computing which is a paradigm tailored to the general problem of bipolar QUBO solving. Given our study up to this point, its basic principles will be easy to understand since Hopfield nets for problem solving and adiabatic quantum computing are closely related concepts. Indeed, we already know about tensor products, Hopfield energies and their representation in terms of Hamiltonians, annealing, the axioms of quantum mechanics, the Schrödinger equation, and quantum superposition. All these concepts will now be jointly put to use and brought together with yet another quantum mechanical principle, namely the adiabatic theorem. Based on two examples of simple QUBO problems, we demonstrate how adiabatic quantum computers can explore their exponentially large search spaces in parallel and thus achieve quadratic speedup over classical exhaustive search procedures.
The Quadratic Unconstrained Binary Optimization problem (QUBO) has become a unifying model for representing a wide range of combinatorial optimization problems, and for linking a variety of disciplines that face these problems. A new class of quantum annealing computer that maps QUBO onto a physical qubit network structure with specific size and edge density restrictions is generating a growing interest in ways to transform the underlying QUBO structure into an equivalent graph having fewer nodes and edges. In this article, we present rules for reducing the size of the QUBO matrix by identifying variables whose value at optimality can be predetermined. We verify that the reductions improve both solution quality and time to solution and, in the case of metaheuristic methods where optimal solutions cannot be guaranteed, the quality of solutions obtained within reasonable time limits. We discuss the general QUBO structural characteristics that can take advantage of these reduction techniques and perform careful experimental design and analysis to identify and quantify the specific characteristics most affecting reduction. The rules make it possible to dramatically improve solution times on a new set of problems using both the exact Cplex solver and a tabu search metaheuristic. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 70(2), 79–97 2017