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

International Symposium on Computing and Networking

Solving the N-Queens Puzzle by a QUBO Model with Quadratic Size

Shunsuke Tsukiyama, Koji Nakano, Yasuaki Ito, Takashi Yazane, Junko Yano, Takumi Kato, Shiro Ozaki, Rie Mori, Ryota Katsuki

Published Nov 28, 2023• 4 citations
Publisher

Abstract

A quadratic unconstrained binary optimization (QUBO) model is defined by an objective function that consists of a quadratic formula involving multiple binary variables. The goal of the QUBO problem is to find an optimal assignment of values to the variables that minimizes the objective function. One of the most well-known problems that can be reduced to a QUBO problem is the N-Queens problem. The N-Queens problem seeks to find a configuration of n queens on an $n\times n$ chessboard such that no two queens can attack each other. It is widely recognized that a conventional technique can be used to design a QUBO model with an $n\times n$ matrix of binary variables representing the chessboard, where a queen is placed in a particular position if and only if the corresponding binary variable is set to 1. This technique involves incorporating terms in the objective function to ensure that the sum of each row and column is 1, and the sum of each diagonal and anti-diagonal is either 0 or 1. The resulting reduced QUBO model contains $\displaystyle \frac{5}{3}n^{3}-2n^{2}+\frac{1}{3}n$ quadratic terms. Due to the simplicity and straightforwardness of designing such a QUBO model, there are numerous resources available that explain this model as an easy example of QUBO models. However, to the best of our knowledge, no fundamentally different approach to designing a QUBO model for the N-Queens problem has been discovered. The prevailing view within the community is that this approach is the only method for designing a QUBO model for the N-Queens problem, and no superior alternative has been found. In this paper, we will present a counterintuitive result that demonstrates a more efficient QUBO model for the N-Queens problem, requiring fewer quadratic terms. Surprisingly, this alternative model involves only $12n^{2}-24n+12$ quadratic terms, which is smaller than the conventional QUBO model whenever n is greater than or equal to 7. This discovery marks a significant breakthrough in the theoretical challenge of minimizing a QUBO model for solving the N-Queens problem.

DOI
10.1109/candar60563.2023.00015

Related papers

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

Generating hard quadratic unconstrained binary optimization instances via the method of combining bit reduction and duplication technique

X. H. Li, Koji Nakano, Shunsuke Tsukiyama +3 more

Quadratic Unconstrained Binary Optimization (QUBO) is a combinatorial optimization problem defined by an energy function that consists of a quadratic formula involving multiple binary variables. We propose the method of combing bit reduction and duplication technique that can generate hard instances of QUBO problems from any original QUBO problem without changing the size. The idea is to reduce the original QUBO problem for a specified number of bits and duplicate the same number of bits while ensuring all duplicated pair of bits take the same binary values. Experimental results show that generated QUBO instances are much hard for solving.

International Journal of Parallel Emergent and Distributed Systems•Jul 9, 2024•2 citations

Breaking SHA-1 through QUBO models

Shunsuke Tsukiyama, Koji Nakano, Yasuaki Ito +2 more

A Quadratic Unconstrained Binary Optimization (QUBO) model is defined by a quadratic objective function comprising binary variables, each taking values of 0 or 1. The objective of the QUBO problem is to determine the optimal assignment of these binary variables to minimize the QUBO model. QUBO models are instrumental in solving various combinatorial optimization problems, leading to extensive research on solver development, as many combinatorial optimization problems can be reformulated as QUBO problems. Notably, D-Wave Systems, a company specializing in quantum technologies, has developed quantum annealers which are programmable QUBO solvers that utilize quantum mechanics. SHA-1 is a cryptographic hash function that generates a 160-bit hash value from a message of an arbitrary length. This hash value makes it difficult to compute the original message within a practical timeframe. A pre-image attack, which aims to compute the original message from a hash value, is important in cryptographic hash functions. Previous research has shown that a QUBO can be designed to simulate SHA-1, facilitating the execution of a pre-image attack. In this paper, we present a novel QUBO model with fewer bits, linear terms, and quadratic terms than previous QUBO models for simulating hash values and pre-image calculations in SHA-1. While the previous QUBO model requires 34,016 bits, 32,584 linear terms, and 168,188 quadratic terms, our new model requires only 32,096 bits, 26,600 linear terms, and 157,308 quadratic terms. This approach can efficiently execute pre-image attacks using a quantum annealer, providing valuable insights for evaluating the robustness of cryptographic security systems.

International Symposium on Computing and Networking Workshops (CANDARW)•Nov 26, 2024•0 citations

Bit duplication technique to generate hard QUBO problems

Xiaotian Li, Koji Nakano, Yasuaki Ito +6 more

Quadratic Unconstrained Binary Optimization (QUBO) is a combinatorial optimization to find an optimal binary solution vector that minimizes the energy value defined by a quadratic formula of binary variables in the vector. The main contribution of this paper is to present the bit duplication technique, which can generate a hard QUBO problem from any QUBO problem so that their optimal solutions take the same energy value. The idea of the bit duplication technique is to duplicate bits and then to give constraints so that the corresponding two bits take the same binary values. By this technique, any QUBO problem with$n$bits is converted to a hard QUBO problem with$2n$bits. We use random QUBO problems and N-Queen QUBO problems for experiments. The performance of QUBO solvers including Gurobi optimizer, Fixstars Amplify AE, OpenJij with SA, D-Wave Hybrid solver, and ABS QUBO solver are evaluated for solving these QUBO problems. The experimental results show that generated QUBO problems by the bit duplication technique are much harder than the original QUBO problems. Hence, the bit duplication technique is a potent method to generate hard QUBO problems and generated QUBO problems can be used as benchmark problems for evaluating the search performance of QUBO solvers.

International Symposium on Computing and Networking Workshops (CANDARW)•Nov 1, 2022•2 citations

Dual-Matrix Domain Wall: A Novel Technique for Generating Permutations by QUBO and Ising Models with Quadratic Sizes

Koji Nakano, Shunsuke Tsukiyama, Yasuaki Ito +6 more

The Ising model is defined by an objective function using a quadratic formula of qubit variables. The problem of an Ising model aims to determine the qubit values of the variables that minimize the objective function, and many optimization problems can be reduced to this problem. In this paper, we focus on optimization problems related to permutations, where the goal is to find the optimal permutation out of the n! possible permutations of n elements. To represent these problems as Ising models, a commonly employed approach is to use a kernel that applies one-hot encoding to find any one of the n! permutations as the optimal solution. However, this kernel contains a large number of quadratic terms and high absolute coefficient values. The main contribution of this paper is the introduction of a novel permutation encoding technique called the dual-matrix domain wall, which significantly reduces the number of quadratic terms and the maximum absolute coefficient values in the kernel. Surprisingly, our dual-matrix domain-wall encoding reduces the quadratic term count and maximum absolute coefficient values from n3−n2 and 2n−4 to 6n2−12n+4 and 2, respectively. We also demonstrate the applicability of our encoding technique to partial permutations and Quadratic Unconstrained Binary Optimization (QUBO) models. Furthermore, we discuss a family of permutation problems that can be efficiently implemented using Ising/QUBO models with our dual-matrix domain-wall encoding.

arXiv:2308.01024•Technologies•Oct 17, 2023•9 citations

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
A quadratic unconstrained binary optimization (QUBO) model is defined by an objective function that consists of a quadratic formula involving multiple binary variables. The goal of the QUBO problem is to find an optimal assignment of values to the variables that minimizes the objective function. One of the most well-known problems that can be reduced to a QUBO problem is the N-Queens problem. The N-Queens problem seeks to find a configuration of n queens on an n×nn\times nn×n chessboard such that no two queens can attack each other. It is widely recognized that a conventional technique can be used to design a QUBO model with an n×nn\times nn×n matrix of binary variables representing the chessboard, where a queen is placed in a particular position if and only if the corresponding binary variable is set to 1. This technique involves incorporating terms in the objective function to ensure that the sum of each row and column is 1, and the sum of each diagonal and anti-diagonal is either 0 or 1. The resulting reduced QUBO model contains 53n3−2n2+13n\displaystyle \frac{5}{3}n^{3}-2n^{2}+\frac{1}{3}n35​n3−2n2+31​n quadratic terms. Due to the simplicity and straightforwardness of designing such a QUBO model, there are numerous resources available that explain this model as an easy example of QUBO models. However, to the best of our knowledge, no fundamentally different approach to designing a QUBO model for the N-Queens problem has been discovered. The prevailing view within the community is that this approach is the only method for designing a QUBO model for the N-Queens problem, and no superior alternative has been found. In this paper, we will present a counterintuitive result that demonstrates a more efficient QUBO model for the N-Queens problem, requiring fewer quadratic terms. Surprisingly, this alternative model involves only 12n2−24n+1212n^{2}-24n+1212n2−24n+12 quadratic terms, which is smaller than the conventional QUBO model whenever n is greater than or equal to 7. This discovery marks a significant breakthrough in the theoretical challenge of minimizing a QUBO model for solving the N-Queens problem.
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.
Quadratic Unconstrained Binary Optimization (QUBO) is a combinatorial optimization problem defined by an energy function that consists of a quadratic formula involving multiple binary variables. We propose the method of combing bit reduction and duplication technique that can generate hard instances of QUBO problems from any original QUBO problem without changing the size. The idea is to reduce the original QUBO problem for a specified number of bits and duplicate the same number of bits while ensuring all duplicated pair of bits take the same binary values. Experimental results show that generated QUBO instances are much hard for solving.
A Quadratic Unconstrained Binary Optimization (QUBO) model is defined by a quadratic objective function comprising binary variables, each taking values of 0 or 1. The objective of the QUBO problem is to determine the optimal assignment of these binary variables to minimize the QUBO model. QUBO models are instrumental in solving various combinatorial optimization problems, leading to extensive research on solver development, as many combinatorial optimization problems can be reformulated as QUBO problems. Notably, D-Wave Systems, a company specializing in quantum technologies, has developed quantum annealers which are programmable QUBO solvers that utilize quantum mechanics. SHA-1 is a cryptographic hash function that generates a 160-bit hash value from a message of an arbitrary length. This hash value makes it difficult to compute the original message within a practical timeframe. A pre-image attack, which aims to compute the original message from a hash value, is important in cryptographic hash functions. Previous research has shown that a QUBO can be designed to simulate SHA-1, facilitating the execution of a pre-image attack. In this paper, we present a novel QUBO model with fewer bits, linear terms, and quadratic terms than previous QUBO models for simulating hash values and pre-image calculations in SHA-1. While the previous QUBO model requires 34,016 bits, 32,584 linear terms, and 168,188 quadratic terms, our new model requires only 32,096 bits, 26,600 linear terms, and 157,308 quadratic terms. This approach can efficiently execute pre-image attacks using a quantum annealer, providing valuable insights for evaluating the robustness of cryptographic security systems.
Quadratic Unconstrained Binary Optimization (QUBO) is a combinatorial optimization to find an optimal binary solution vector that minimizes the energy value defined by a quadratic formula of binary variables in the vector. The main contribution of this paper is to present the bit duplication technique, which can generate a hard QUBO problem from any QUBO problem so that their optimal solutions take the same energy value. The idea of the bit duplication technique is to duplicate bits and then to give constraints so that the corresponding two bits take the same binary values. By this technique, any QUBO problem withnnnbits is converted to a hard QUBO problem with2n2n2nbits. We use random QUBO problems and N-Queen QUBO problems for experiments. The performance of QUBO solvers including Gurobi optimizer, Fixstars Amplify AE, OpenJij with SA, D-Wave Hybrid solver, and ABS QUBO solver are evaluated for solving these QUBO problems. The experimental results show that generated QUBO problems by the bit duplication technique are much harder than the original QUBO problems. Hence, the bit duplication technique is a potent method to generate hard QUBO problems and generated QUBO problems can be used as benchmark problems for evaluating the search performance of QUBO solvers.
The Ising model is defined by an objective function using a quadratic formula of qubit variables. The problem of an Ising model aims to determine the qubit values of the variables that minimize the objective function, and many optimization problems can be reduced to this problem. In this paper, we focus on optimization problems related to permutations, where the goal is to find the optimal permutation out of the n! possible permutations of n elements. To represent these problems as Ising models, a commonly employed approach is to use a kernel that applies one-hot encoding to find any one of the n! permutations as the optimal solution. However, this kernel contains a large number of quadratic terms and high absolute coefficient values. The main contribution of this paper is the introduction of a novel permutation encoding technique called the dual-matrix domain wall, which significantly reduces the number of quadratic terms and the maximum absolute coefficient values in the kernel. Surprisingly, our dual-matrix domain-wall encoding reduces the quadratic term count and maximum absolute coefficient values from n3−n2 and 2n−4 to 6n2−12n+4 and 2, respectively. We also demonstrate the applicability of our encoding technique to partial permutations and Quadratic Unconstrained Binary Optimization (QUBO) models. Furthermore, we discuss a family of permutation problems that can be efficiently implemented using Ising/QUBO models with our dual-matrix domain-wall encoding.
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.