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

A Simple QUBO Formulation of Sudoku

Sascha Mücke

Published Jul 14, 2024• 6 citations
arXivHTMLPDF

Abstract

This article describes how to solve Sudoku puzzles using Quadratic Unconstrained Binary Optimization (QUBO). To this end, a QUBO instance with 729 variables is constructed, encoding a Sudoku grid with all constraints in place, which is then partially assigned to account for clues. The resulting instance can be solved with a Quantum Annealer, or any other strategy, to obtain the fully filled-out Sudoku grid. Moreover, as all valid solutions have the same energy, the QUBO instance can be used to sample uniformly from the space of valid Sudoku grids. We demonstrate the described method using both a heuristic solver and a Quantum Annealer.

DOI
10.1145/3638530.3664106

Related papers

Encoding the At-Most-One Constraint for QUBO and Quantum Annealing: Experiments with the N-Queens problem

Philippe Codognet

We present experiments in solving constrained optimization and constraint satisfaction problems by means of Quantum Annealing in terms of QUBO (Quadratic Unconstrained Binary Optimization). We investigate different QUBO formulations for the encoding of integers into Booleans and for the encoding of the At-Most-One constraint, which is used in combinatorial problems requiring capacity constraints. We compare four different QUBO models and report experiments done on the D-Wave annealing computer and the "quantum-inspired" Fixstars Amplify Annealing Engine. For this, we consider a simple example taken from the domain of Constraint Satisfaction Problems (CSP), the N-queens problem, as its formulation involves multiple instances of the At-Most-One constraints.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 15, 2023•9 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

CUBO-to-QUBO Conversion: Reducing Cubic Formulations to Quadratic Formulations

Shunsuke Tsukiyama, Xiaotian Li, Koji Nakano +5 more

Quadratic Unconstrained Binary Optimization (QUBO) models are defined by quadratic expressions composed of binary variables, each taking a value of either 0 or 1. The objective of the QUBO problem is to find an optimal assignment of these binary variables that minimizes the value of the QUBO model. The QUBO problem has attracted significant research interest due to its versatility in reformulating various NP-complete problems and its potential for efficiently finding heuristic solutions through quantum annealing. This paper focuses on converting Cubic Unconstrained Binary Optimization (CUBO) problems, defined by cubic expressions, into equivalent QUBO models. Through this conversion, CUBO problems can be solved using quantum annealing. Since the important NP-hard problem 3-SAT can be straightforwardly represented as a CUBO problem, investigating the conversion from CUBO to QUBO models is a meaningful endeavor.

IEEE International Symposium on Parallel & Distributed Processing, Workshops and Phd Forum•Jun 3, 2025•1 citation

Encoding Binary Comparison Constraints in QUBO for Quantum Annealing

Philippe Codognet

We consider the encoding in Quadratic Unconstrained Binary Optimization (QUBO) of binary comparison constraints, that is, constraints of the form x < y + c, x ≤ y + c, and x = y + c, where x and y are two integer variables and c is an integer constant. For the sake of simplicity, we will consider that x and y are bounded and belong to the same interval {1,..., n}. We will show that such constraints can be encoded without the need of any extra-variable, conversely to the general scheme for linear inequations, which requires between n - 1 and ⌈log2(n - 1)⌉ extra-variables, depending on the encoding chosen for integers. Limiting the number of extra-variables needed in QUBO formulations is important as each Boolean QUBO variable will be implemented as a (logical) qubit on a quantum device and the number of such qubits is limited in quantum annealing systems such as D-Wave machines.

Genetic and Evolutionary Computation Conference Companion (GECCO Companion)•Jul 14, 2025•0 citations

A Quantum-Inspired Algorithm for Solving Sudoku Puzzles and the MaxCut Problem †

Max Zhao, Fei Li

Abstract We propose and evaluate a quantum-inspired algorithm for solving Quadratic Unconstrained Binary Optimization (QUBO) problems, which are mathematically equivalent to finding ground states of Ising spin-glass Hamiltonians. The algorithm employs Matrix Product States (MPS) to compactly represent large superpositions of spin configurations and utilizes a discrete driving schedule to guide the MPS toward the ground state. At each step, a driver Hamiltonian—incorporating a transverse magnetic field—is combined with the problem Hamiltonian to enable spin flips and facilitate quantum tunneling. The MPS is updated using the standard Density Matrix Renormalization Group (DMRG) method, which iteratively minimizes the system’s energy via multiple sweeps across the spin chain. Despite its heuristic nature, the algorithm reliably identifies global minima, not merely near-optimal solutions, across diverse QUBO instances. We first demonstrate its effectiveness on intermediate-level Sudoku puzzles from publicly available sources, involving over 200 Ising spins with long-range couplings dictated by constraint satisfaction. We then apply the algorithm to MaxCut problems from the Biq Mac library, successfully solving instances with up to 251 nodes and 3,265 edges. We discuss the advantages of this quantum-inspired approach, including its scalability, generalizability, and suitability for industrial-scale QUBO applications.

Quantum Information and Computation•Dec 1, 2025•1 citation

Quadratic Continuous Quantum Optimization

Sascha Mücke, Thore Gerlach, Nico Piatkowski

Quantum annealers can solve QUBO problems efficiently but struggle with continuous optimization tasks like regression due to their discrete nature. We introduce Quadratic Continuous Quantum Optimization (QCQO), an anytime algorithm that approximates solutions to unconstrained quadratic programs via a sequence of QUBO instances. Rather than encoding real variables as binary vectors, QCQO implicitly represents them using continuous QUBO weights and iteratively refines the solution by summing sampled vectors. This allows flexible control over the number of binary variables and adapts well to hardware constraints. We prove convergence properties, introduce a step size adaptation scheme, and validate the method on linear regression. Experiments with simulated and real quantum annealers show that QCQO achieves accurate results with fewer qubits, though convergence slows on noisy hardware. Our approach enables quantum annealing to address a wider class of continuous problems.

quant-pharXiv:2512.24759•Jan 1, 2026•0 citations
This article describes how to solve Sudoku puzzles using Quadratic Unconstrained Binary Optimization (QUBO). To this end, a QUBO instance with 729 variables is constructed, encoding a Sudoku grid with all constraints in place, which is then partially assigned to account for clues. The resulting instance can be solved with a Quantum Annealer, or any other strategy, to obtain the fully filled-out Sudoku grid. Moreover, as all valid solutions have the same energy, the QUBO instance can be used to sample uniformly from the space of valid Sudoku grids. We demonstrate the described method using both a heuristic solver and a Quantum Annealer.
We present experiments in solving constrained optimization and constraint satisfaction problems by means of Quantum Annealing in terms of QUBO (Quadratic Unconstrained Binary Optimization). We investigate different QUBO formulations for the encoding of integers into Booleans and for the encoding of the At-Most-One constraint, which is used in combinatorial problems requiring capacity constraints. We compare four different QUBO models and report experiments done on the D-Wave annealing computer and the "quantum-inspired" Fixstars Amplify Annealing Engine. For this, we consider a simple example taken from the domain of Constraint Satisfaction Problems (CSP), the N-queens problem, as its formulation involves multiple instances of the At-Most-One constraints.
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) models are defined by quadratic expressions composed of binary variables, each taking a value of either 0 or 1. The objective of the QUBO problem is to find an optimal assignment of these binary variables that minimizes the value of the QUBO model. The QUBO problem has attracted significant research interest due to its versatility in reformulating various NP-complete problems and its potential for efficiently finding heuristic solutions through quantum annealing. This paper focuses on converting Cubic Unconstrained Binary Optimization (CUBO) problems, defined by cubic expressions, into equivalent QUBO models. Through this conversion, CUBO problems can be solved using quantum annealing. Since the important NP-hard problem 3-SAT can be straightforwardly represented as a CUBO problem, investigating the conversion from CUBO to QUBO models is a meaningful endeavor.
We consider the encoding in Quadratic Unconstrained Binary Optimization (QUBO) of binary comparison constraints, that is, constraints of the form x < y + c, x ≤ y + c, and x = y + c, where x and y are two integer variables and c is an integer constant. For the sake of simplicity, we will consider that x and y are bounded and belong to the same interval {1,..., n}. We will show that such constraints can be encoded without the need of any extra-variable, conversely to the general scheme for linear inequations, which requires between n - 1 and ⌈log2(n - 1)⌉ extra-variables, depending on the encoding chosen for integers. Limiting the number of extra-variables needed in QUBO formulations is important as each Boolean QUBO variable will be implemented as a (logical) qubit on a quantum device and the number of such qubits is limited in quantum annealing systems such as D-Wave machines.
Abstract We propose and evaluate a quantum-inspired algorithm for solving Quadratic Unconstrained Binary Optimization (QUBO) problems, which are mathematically equivalent to finding ground states of Ising spin-glass Hamiltonians. The algorithm employs Matrix Product States (MPS) to compactly represent large superpositions of spin configurations and utilizes a discrete driving schedule to guide the MPS toward the ground state. At each step, a driver Hamiltonian—incorporating a transverse magnetic field—is combined with the problem Hamiltonian to enable spin flips and facilitate quantum tunneling. The MPS is updated using the standard Density Matrix Renormalization Group (DMRG) method, which iteratively minimizes the system’s energy via multiple sweeps across the spin chain. Despite its heuristic nature, the algorithm reliably identifies global minima, not merely near-optimal solutions, across diverse QUBO instances. We first demonstrate its effectiveness on intermediate-level Sudoku puzzles from publicly available sources, involving over 200 Ising spins with long-range couplings dictated by constraint satisfaction. We then apply the algorithm to MaxCut problems from the Biq Mac library, successfully solving instances with up to 251 nodes and 3,265 edges. We discuss the advantages of this quantum-inspired approach, including its scalability, generalizability, and suitability for industrial-scale QUBO applications.
Quantum annealers can solve QUBO problems efficiently but struggle with continuous optimization tasks like regression due to their discrete nature. We introduce Quadratic Continuous Quantum Optimization (QCQO), an anytime algorithm that approximates solutions to unconstrained quadratic programs via a sequence of QUBO instances. Rather than encoding real variables as binary vectors, QCQO implicitly represents them using continuous QUBO weights and iteratively refines the solution by summing sampled vectors. This allows flexible control over the number of binary variables and adapts well to hardware constraints. We prove convergence properties, introduce a step size adaptation scheme, and validate the method on linear regression. Experiments with simulated and real quantum annealers show that QCQO achieves accurate results with fewer qubits, though convergence slows on noisy hardware. Our approach enables quantum annealing to address a wider class of continuous problems.