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

Cognitive technologies

QUBO Models

Christian Bauckhage, Rafet Sifa

Published Nov 17, 2025• 0 citations
Publisher

Abstract

Abstract Having previously studied general aspects of QUBO models, we now study application specific examples and how to derive or set them up. Our application examples will consider problems in areas like combinatorial optimization, constraint satisfaction, data mining, and machine learning and are supposed to illustrate that QUBOs provide us with a surprisingly versatile and widely applicable modeling framework. Put differently, our overall goal with this chapter is to demonstrate how to rethink familiar, seemingly unrelated problems in terms of an overarching formalism that will later allow for running Hopfield nets and quantum implementations. This will largely be an exercise in applied linear algebra since we will extensively work with matrix-vector formulations of QUBOs for which we will point out and discuss simplifying modeling assumptions whenever necessary.

DOI
10.1007/978-3-031-99402-9_5

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

A Tutorial on Formulating QUBO Models.

Fred Glover, Gary A. Kochenberger

The field of Combinatorial Optimization (CO) is one of the most important areas in the general field of optimization, with important applications found in every industry, including both the private and public sectors. It is also one of the most active research areas pursued by the research communities of Operations Research, Computer Science, and Analytics as they work to design and test new methods for solving real world CO problems. In recent years, we have discovered that a mathematical formulation known as QUBO, an acronym for a Quadratic Unconstrained Binary Optimization problem, can embrace a large variety of important CO problems found in industry and government. Through special reformulation techniques that are easy to apply, the power of QUBO solvers can be used to efficiently solve many important problems once they are put into the QUBO framework. This two-step process of first re-casting an original model into the form of a QUBO model and then solving it with appropriate software enables the QUBO model to become a unifying framework for combinatorial optimization. The alternative path that results for effectively modeling and solving many important problems is a new development in the field of combinatorial optimization. The materials provided in subsequent sections illustrate the process of reformulating important optimization problems as QUBO models through a series of explicit examples. Collectively these examples highlight the application breadth of the QUBO model. We do not focus here on modeling a given problem in the form classically adopted in the optimization community. Rather, our examples disclose the methods that can be used to recast a given problem, perhaps existing in a classical mathematical form, into an equivalent QUBO model.

•Nov 13, 2018•24 citations

A Tutorial on Formulating and Using QUBO Models

Fred Glover, Gary A. Kochenberger, Yu Du

The Quadratic Unconstrained Binary Optimization (QUBO) model has gained prominence in recent years with the discovery that it unifies a rich variety of combinatorial optimization problems. By its association with the Ising problem in physics, the QUBO model has emerged as an underpinning of the quantum computing area known as quantum annealing and has become a subject of study in neuromorphic computing. Through these connections, QUBO models lie at the heart of experimentation carried out with quantum computers developed by D-Wave Systems and neuromorphic computers developed by IBM. Computational experience is being amassed by both the classical and the quantum computing communities that highlights not only the potential of the QUBO model but also its effectiveness as an alternative to traditional modeling and solution methodologies. This tutorial discloses the basic features of the QUBO model that give it the power and flexibility to encompass the range of applications that have thrust it onto center stage of the optimization field. We show how many different types of constraining relationships arising in practice can be embodied within the "unconstrained" QUBO formulation in a very natural manner using penalty functions, yielding exact model representations in contrast to the approximate representations produced by customary uses of penalty functions. Each step of generating such models is illustrated in detail by simple numerical examples, to highlight the convenience of using QUBO models in numerous settings. We also describe recent innovations for solving QUBO models that offer a fertile avenue for integrating classical and quantum computing and for applying these models in machine learning.

arXiv:1811.11538•Nov 13, 2018•504 citations

AutoQUBO v2: Towards Efficient and Effective QUBO Formulations for Ising Machines

Justin Pauckert, Mayowa Ayodele, Marcos Diez García +2 more

The QUBO framework provides a way to model, in principle, any combinatorial optimization problem and enables the use of Ising machines to solve it. Ising machines are devices designed to quickly find good solutions to QUBO problems. In previous work, Auto-QUBO was designed to automatically generate QUBO formulations from a high-level problem description. We address two shortcomings of this method. It only works on a per-instance basis, making repeated formulations for similar problems inefficient, and relies on the user to specify penalty weights. This work introduces symbolic sampling, which provides QUBO formulations for entire problem classes. We demonstrate the speedup that can be achieved with this approach using instances of the maximum clique problem. Additionally, we use proven methods to compute valid penalty weights automatically to simplify the translation process. By providing a user-friendly way to generate QUBO formulations in an efficient manner, both in terms of time and problem difficulty, we enable more people to use Ising machines for combinatorial optimization.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 15, 2023•16 citations

Hopfield Nets and Quantum Mechanics

Christian Bauckhage, Rafet Sifa

Abstract Previously, we viewed Hopfield nets from the point of view of statistical mechanics. In this chapter, we widen our perspective one again and view them from the point of view of quantum mechanics. This requires us to introduce completely different representations of the states and energy functions of Hopfield nets and relate them to the kind of tensor product spaces we studied earlier. At this point, this different perspective on Hopfield nets is of purely theoretical interest because it generally defies practical implementations on digital computers. However, it establishes a connection between Hopfield nets and important quantum mechanical concepts. In particular, we will get to know the notion of the Hamiltonian of a physical system, its eigenstates, and eigenvalues. Since the material in this chapter is more abstract and less intuitive than in previous chapters, we develop our ideas by looking at an exemplary simple Hopfield net and support our technical claims through practical computations and code examples.

Cognitive technologies•Nov 17, 2025•0 citations

Efficient mapping of multi-constraint satisfaction problems to Rydberg platforms

Robert Gloeckner, Shahram Panahiyan, Frederik Koch +2 more

We present a hardware-native gadget framework for solving constraint satisfaction problems on Rydberg quantum computing architectures. Our approach introduces a compact $xor_1$ gadget that enforces exactly-one constraints, ubiquitous in combinatorial optimization, directly through geometric embedding and blockade interactions. A key advantage of the $xor_1$ gadget is its fixed, problem-size-independent detuning requirements: enforcing constraints through blockade interactions eliminates the need for large penalty terms, thereby substantially reducing the detuning range compared to Quadratic Unconstrained Binary Optimization (QUBO) formulations and improving experimental feasibility. By tailoring the construction to the geometric connectivity of Rydberg atom arrays, the framework bypasses the all-to-all physical couplings often assumed in logical encodings. This enables embeddings compatible with planar layouts and avoids highly connected arrangements. We develop scalable implementations that reduce atom count and connectivity overhead while avoiding extensive classical preprocessing, making them compatible with near-term neutral-atom hardware. As illustrations, we apply our framework to the gate-assignment and $N$-queens problems, highlighting its practicality, resource efficiency, and hardware compatibility. In these examples, we observe reductions in detuning range of up to $99\%$ and savings in atom count and connectivity overhead of up to $54\%$ compared to the QUBO method. These results establish a route toward implementing large-scale combinatorial optimization on Rydberg platforms beyond the limits of existing encodings.

quant-pharXiv:2604.27030•Physical Review Research•Apr 30, 2026•0 citations
Abstract Having previously studied general aspects of QUBO models, we now study application specific examples and how to derive or set them up. Our application examples will consider problems in areas like combinatorial optimization, constraint satisfaction, data mining, and machine learning and are supposed to illustrate that QUBOs provide us with a surprisingly versatile and widely applicable modeling framework. Put differently, our overall goal with this chapter is to demonstrate how to rethink familiar, seemingly unrelated problems in terms of an overarching formalism that will later allow for running Hopfield nets and quantum implementations. This will largely be an exercise in applied linear algebra since we will extensively work with matrix-vector formulations of QUBOs for which we will point out and discuss simplifying modeling assumptions whenever necessary.
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.
The field of Combinatorial Optimization (CO) is one of the most important areas in the general field of optimization, with important applications found in every industry, including both the private and public sectors. It is also one of the most active research areas pursued by the research communities of Operations Research, Computer Science, and Analytics as they work to design and test new methods for solving real world CO problems. In recent years, we have discovered that a mathematical formulation known as QUBO, an acronym for a Quadratic Unconstrained Binary Optimization problem, can embrace a large variety of important CO problems found in industry and government. Through special reformulation techniques that are easy to apply, the power of QUBO solvers can be used to efficiently solve many important problems once they are put into the QUBO framework. This two-step process of first re-casting an original model into the form of a QUBO model and then solving it with appropriate software enables the QUBO model to become a unifying framework for combinatorial optimization. The alternative path that results for effectively modeling and solving many important problems is a new development in the field of combinatorial optimization. The materials provided in subsequent sections illustrate the process of reformulating important optimization problems as QUBO models through a series of explicit examples. Collectively these examples highlight the application breadth of the QUBO model. We do not focus here on modeling a given problem in the form classically adopted in the optimization community. Rather, our examples disclose the methods that can be used to recast a given problem, perhaps existing in a classical mathematical form, into an equivalent QUBO model.
The Quadratic Unconstrained Binary Optimization (QUBO) model has gained prominence in recent years with the discovery that it unifies a rich variety of combinatorial optimization problems. By its association with the Ising problem in physics, the QUBO model has emerged as an underpinning of the quantum computing area known as quantum annealing and has become a subject of study in neuromorphic computing. Through these connections, QUBO models lie at the heart of experimentation carried out with quantum computers developed by D-Wave Systems and neuromorphic computers developed by IBM. Computational experience is being amassed by both the classical and the quantum computing communities that highlights not only the potential of the QUBO model but also its effectiveness as an alternative to traditional modeling and solution methodologies. This tutorial discloses the basic features of the QUBO model that give it the power and flexibility to encompass the range of applications that have thrust it onto center stage of the optimization field. We show how many different types of constraining relationships arising in practice can be embodied within the "unconstrained" QUBO formulation in a very natural manner using penalty functions, yielding exact model representations in contrast to the approximate representations produced by customary uses of penalty functions. Each step of generating such models is illustrated in detail by simple numerical examples, to highlight the convenience of using QUBO models in numerous settings. We also describe recent innovations for solving QUBO models that offer a fertile avenue for integrating classical and quantum computing and for applying these models in machine learning.
The QUBO framework provides a way to model, in principle, any combinatorial optimization problem and enables the use of Ising machines to solve it. Ising machines are devices designed to quickly find good solutions to QUBO problems. In previous work, Auto-QUBO was designed to automatically generate QUBO formulations from a high-level problem description. We address two shortcomings of this method. It only works on a per-instance basis, making repeated formulations for similar problems inefficient, and relies on the user to specify penalty weights. This work introduces symbolic sampling, which provides QUBO formulations for entire problem classes. We demonstrate the speedup that can be achieved with this approach using instances of the maximum clique problem. Additionally, we use proven methods to compute valid penalty weights automatically to simplify the translation process. By providing a user-friendly way to generate QUBO formulations in an efficient manner, both in terms of time and problem difficulty, we enable more people to use Ising machines for combinatorial optimization.
Abstract Previously, we viewed Hopfield nets from the point of view of statistical mechanics. In this chapter, we widen our perspective one again and view them from the point of view of quantum mechanics. This requires us to introduce completely different representations of the states and energy functions of Hopfield nets and relate them to the kind of tensor product spaces we studied earlier. At this point, this different perspective on Hopfield nets is of purely theoretical interest because it generally defies practical implementations on digital computers. However, it establishes a connection between Hopfield nets and important quantum mechanical concepts. In particular, we will get to know the notion of the Hamiltonian of a physical system, its eigenstates, and eigenvalues. Since the material in this chapter is more abstract and less intuitive than in previous chapters, we develop our ideas by looking at an exemplary simple Hopfield net and support our technical claims through practical computations and code examples.
We present a hardware-native gadget framework for solving constraint satisfaction problems on Rydberg quantum computing architectures. Our approach introduces a compact xor1xor_1xor1​ gadget that enforces exactly-one constraints, ubiquitous in combinatorial optimization, directly through geometric embedding and blockade interactions. A key advantage of the xor1xor_1xor1​ gadget is its fixed, problem-size-independent detuning requirements: enforcing constraints through blockade interactions eliminates the need for large penalty terms, thereby substantially reducing the detuning range compared to Quadratic Unconstrained Binary Optimization (QUBO) formulations and improving experimental feasibility. By tailoring the construction to the geometric connectivity of Rydberg atom arrays, the framework bypasses the all-to-all physical couplings often assumed in logical encodings. This enables embeddings compatible with planar layouts and avoids highly connected arrangements. We develop scalable implementations that reduce atom count and connectivity overhead while avoiding extensive classical preprocessing, making them compatible with near-term neutral-atom hardware. As illustrations, we apply our framework to the gate-assignment and NNN-queens problems, highlighting its practicality, resource efficiency, and hardware compatibility. In these examples, we observe reductions in detuning range of up to 99%99\%99% and savings in atom count and connectivity overhead of up to 54%54\%54% compared to the QUBO method. These results establish a route toward implementing large-scale combinatorial optimization on Rydberg platforms beyond the limits of existing encodings.