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

QUBO問題の複雑さに関する研究

LI XIAOTIAN

Published Mar 23, 2025• 0 citations
OpenAlex

Abstract

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.The goal of the QUBO problem is to find an optimal assignment of values to the variables that minimizes the energy function.With the increasing applicability of QUBO problems, QUBO solvers on different computing platforms have been developed.It is necessary to generate hard QUBO instances for improving and evaluating the performance of QUBO solvers.In this dissertation, we research in generating hard QUBO instances.First, we propose an effective method called bit duplication technique for generating hard QUBO instances with adjustable sizes.The idea is to duplicate specified number of 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 (n + m) bits (0 < m ≤ n).Second, in order to avoid the increase in the original size after performing bit duplication technique, we propose a novel technique which we call bit reduction to reduce the size of the original QUBO problem before preforming bit duplication technique.Through this method, hard QUBO instances can be generated without increasing the size of the original QUBO problem.By combining the bit duplication and bit reduction technique, we propose the method for generating hard instance of QUBO problems from any original QUBO problem without changing the size. 1 We use random QUBO problems, N-Queens problems, Traveling Salesman Problem (TSP), maximum weight matching (MWM) problems and Satisfiability problems (SAT) as original QUBO problems to generate hard QUBO instances.The performance of QUBO solvers including Gurobi optimizer, Fixstars Amplify AE, OpenJij with SA, D-Wave Hybrid and ABS2 QUBO solvers are evaluated for solving the generated hard QUBO instances.The experimental results show that generated QUBO instances are much hard for solving.

Related papers

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

Bit duplication technique to generate hard quadratic unconstrained binary optimization problems with adjustable sizes

X. H. Li, Koji Nakano, Yasuaki Ito +7 more

Summary 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 article is to propose the bit duplication technique that can specify the number of duplicated bits, so that it can generate hard QUBO problem with adjustable sizes. The idea is to duplicate specified number of bits and then to give constraints so that the corresponding two bits take the same binary values. By this technique, any QUBO problem with bits is converted to a hard QUBO problem with bits . We use random QUBO problems, N‐Queen problems, traveling salesman problem and maximum weight matching problems for experiments. The performance of QUBO solvers including Gurobi optimizer, Fixstars Amplify AE, OpenJij with SA, D‐Wave samplers with SA, D‐Wave hybrid and ABS2 QUBO solver are evaluated for solving these QUBO problems. The experimental results show that only a small scale of duplicated bits can make QUBO problems harder. 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.

Concurrency and Computation Practice and Experience•Nov 20, 2023•3 citations

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

A benchmark QUBO problem inspired by digital halftoning based on the human visual system

Koji Nakano, Yasuaki Ito, Daisuke Takafuji +5 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. As many NP problems can be reduced to QUBO problems, considerable research has gone into developing QUBO solvers running on various computing platforms such as quantum devices, ASICs, FPGAs, GPUs, and optical fibers. For evaluating the performance of QUBO solvers, QUBO problems reduced from combinatorial optimization problems such as MaxCut, Traveling Salesman Problem (TSP), and Quadratic Assignment Problem (QAP) are commonly used. This paper presents a new benchmark QUBO problem inspired by digital halftoning, which aims to find a binary image reproducing an input grayscale image. The characteristics of this QUBO problem reduced from digital halftoning are quite unique. Solutions of the QUBO problem can be converted into binary images, from which we can visually evaluate the solution quality. Good approximation solutions for the QUBO problem can be obtained by a simple heuristic algorithm very quickly. However, it is very hard to find an optimal solution. Moreover, quite interestingly, we can create a QUBO problem for digital halftoning with a known optimal solution for a benchmarking purpose. Thus, we can exactly compute the gap between the optimal solution and an approximate solution obtained by a QUBO solver. We have developed an OpenMP-based sparse QUBO solver that can find good approximate solutions for QUBO problems reduced from digital halftoning. We have evaluated the performance of QUBO solvers including the D-Wave Hybrid solver, Gurobi optimizer, Open.Jij, and our sparse QUBO solver. The experimental results show that our OpenMP-based sparse QUBO solver attains the best performance.

International Symposium on Computing and Networking•Nov 1, 2022•1 citation

An External Definition of the One-Hot Constraint and Fast QUBO Generation for High-Performance Combinatorial Clustering

Masahito Kumagai, Kazuhiko Komatsu, Fumiyo Takano +3 more

Recently, a clustering method using a combinatorial optimization problem, called combinatorial clustering, has been drawing attention due to the rapid spreads of quantum annealing and simulated annealing.Combinatorial clustering is performed by minimizing an objective function under a condition to satisfy a one-hot constraint.The objective function and the constraint function are generally formulated to a unified objective function of a QUBO (Quadratic Unconstrained Binary Optimization) problem using the method of the Lagrange multiplier.The coefficients of the QUBO function can be represented by a square matrix, which is called the QUBO matrix.Although the Lagrange multiplier needs to be large enough to avoid violating the constraint, it is usually hard to be set appropriately due to the limitation of the bit precision.For example, the latest quantum annealer can handle values represented by only six or fewer bits.Even conventional computing systems cannot control the larger value of the Lagrange multiplier as the number of data points increases.Besides, the execution time for combinatorial clustering increases exponentially as the problem size increases.This is because the time for the QUBO matrix generation is long and a dominant factor of the total execution time when the problem size is large.To solve these problems, this paper proposes combinatorial clustering that overcomes the limitation of the method of the Lagrange multiplier.The proposed method uses a QUBO solver that can externally define the one-hot constraint independent from the objective function, and the externally-defined constraint is satisfied by the operations with multiple bit-flips.As the QUBO function contains only the objective function, the method of the Lagrange multiplier is not necessary.The proposed method can optimize the objective function sufficiently even when the problem size is large.Since the constraint function is not included in the QUBO function, the proposed method also reduces the time for the QUBO matrix generation.The experimental results obtained using the artificial and real data show that the proposed method can improve the quality of annealing-based clustering results in all data sets.The experimental results also clarify that the quality of the proposed method is almost equal to or better than that of quasi-optimal clustering methods such as K-means.The evaluation using the multiple traveling salesman problem shows that the proposed method can obtain shorter tour lengths than the conventional annealing-based clustering in all 13 cases and K-means++ in 6 out of 12 cases with a significant difference.Furthermore, the proposed method can accelerate the execution time for combinatorial clustering because there is no need to calculate the coefficients of the constraint function.

International Journal of Networking and Computing•Jan 1, 2021•14 citations

Various QUBO Formulations of the Graph Isomorphism Problem and Related Problems

Daisuke Takafuji, 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 graph isomorphism problem is one of the applications of combinatorial optimization, and is not known to be solvable in polynomial time. The problem is also not known to be NP-complete. We propose four QUBO formulations for graph isomorphism problem instances. We also propose four QUBO formulations for induced subgraph isomorphism problem instances and two QUBO formulations for subgraph isomorphism problem instances, which are NP-complete problems. We solve QUBO instances defined by our QUBO formulations, using known QUBO solvers: Gurobi optimizer, Fixstars Amplify AE and OpenJij with SA.

Bulletin of Networking, Computing, Systems, and Software•Mar 1, 2024•0 citations
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.The goal of the QUBO problem is to find an optimal assignment of values to the variables that minimizes the energy function.With the increasing applicability of QUBO problems, QUBO solvers on different computing platforms have been developed.It is necessary to generate hard QUBO instances for improving and evaluating the performance of QUBO solvers.In this dissertation, we research in generating hard QUBO instances.First, we propose an effective method called bit duplication technique for generating hard QUBO instances with adjustable sizes.The idea is to duplicate specified number of 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 (n + m) bits (0 < m ≤ n).Second, in order to avoid the increase in the original size after performing bit duplication technique, we propose a novel technique which we call bit reduction to reduce the size of the original QUBO problem before preforming bit duplication technique.Through this method, hard QUBO instances can be generated without increasing the size of the original QUBO problem.By combining the bit duplication and bit reduction technique, we propose the method for generating hard instance of QUBO problems from any original QUBO problem without changing the size. 1 We use random QUBO problems, N-Queens problems, Traveling Salesman Problem (TSP), maximum weight matching (MWM) problems and Satisfiability problems (SAT) as original QUBO problems to generate hard QUBO instances.The performance of QUBO solvers including Gurobi optimizer, Fixstars Amplify AE, OpenJij with SA, D-Wave Hybrid and ABS2 QUBO solvers are evaluated for solving the generated hard QUBO instances.The experimental results show that generated QUBO instances are much hard for solving.
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.
Summary 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 article is to propose the bit duplication technique that can specify the number of duplicated bits, so that it can generate hard QUBO problem with adjustable sizes. The idea is to duplicate specified number of bits and then to give constraints so that the corresponding two bits take the same binary values. By this technique, any QUBO problem with bits is converted to a hard QUBO problem with bits . We use random QUBO problems, N‐Queen problems, traveling salesman problem and maximum weight matching problems for experiments. The performance of QUBO solvers including Gurobi optimizer, Fixstars Amplify AE, OpenJij with SA, D‐Wave samplers with SA, D‐Wave hybrid and ABS2 QUBO solver are evaluated for solving these QUBO problems. The experimental results show that only a small scale of duplicated bits can make QUBO problems harder. 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.
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.
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. As many NP problems can be reduced to QUBO problems, considerable research has gone into developing QUBO solvers running on various computing platforms such as quantum devices, ASICs, FPGAs, GPUs, and optical fibers. For evaluating the performance of QUBO solvers, QUBO problems reduced from combinatorial optimization problems such as MaxCut, Traveling Salesman Problem (TSP), and Quadratic Assignment Problem (QAP) are commonly used. This paper presents a new benchmark QUBO problem inspired by digital halftoning, which aims to find a binary image reproducing an input grayscale image. The characteristics of this QUBO problem reduced from digital halftoning are quite unique. Solutions of the QUBO problem can be converted into binary images, from which we can visually evaluate the solution quality. Good approximation solutions for the QUBO problem can be obtained by a simple heuristic algorithm very quickly. However, it is very hard to find an optimal solution. Moreover, quite interestingly, we can create a QUBO problem for digital halftoning with a known optimal solution for a benchmarking purpose. Thus, we can exactly compute the gap between the optimal solution and an approximate solution obtained by a QUBO solver. We have developed an OpenMP-based sparse QUBO solver that can find good approximate solutions for QUBO problems reduced from digital halftoning. We have evaluated the performance of QUBO solvers including the D-Wave Hybrid solver, Gurobi optimizer, Open.Jij, and our sparse QUBO solver. The experimental results show that our OpenMP-based sparse QUBO solver attains the best performance.
Recently, a clustering method using a combinatorial optimization problem, called combinatorial clustering, has been drawing attention due to the rapid spreads of quantum annealing and simulated annealing.Combinatorial clustering is performed by minimizing an objective function under a condition to satisfy a one-hot constraint.The objective function and the constraint function are generally formulated to a unified objective function of a QUBO (Quadratic Unconstrained Binary Optimization) problem using the method of the Lagrange multiplier.The coefficients of the QUBO function can be represented by a square matrix, which is called the QUBO matrix.Although the Lagrange multiplier needs to be large enough to avoid violating the constraint, it is usually hard to be set appropriately due to the limitation of the bit precision.For example, the latest quantum annealer can handle values represented by only six or fewer bits.Even conventional computing systems cannot control the larger value of the Lagrange multiplier as the number of data points increases.Besides, the execution time for combinatorial clustering increases exponentially as the problem size increases.This is because the time for the QUBO matrix generation is long and a dominant factor of the total execution time when the problem size is large.To solve these problems, this paper proposes combinatorial clustering that overcomes the limitation of the method of the Lagrange multiplier.The proposed method uses a QUBO solver that can externally define the one-hot constraint independent from the objective function, and the externally-defined constraint is satisfied by the operations with multiple bit-flips.As the QUBO function contains only the objective function, the method of the Lagrange multiplier is not necessary.The proposed method can optimize the objective function sufficiently even when the problem size is large.Since the constraint function is not included in the QUBO function, the proposed method also reduces the time for the QUBO matrix generation.The experimental results obtained using the artificial and real data show that the proposed method can improve the quality of annealing-based clustering results in all data sets.The experimental results also clarify that the quality of the proposed method is almost equal to or better than that of quasi-optimal clustering methods such as K-means.The evaluation using the multiple traveling salesman problem shows that the proposed method can obtain shorter tour lengths than the conventional annealing-based clustering in all 13 cases and K-means++ in 6 out of 12 cases with a significant difference.Furthermore, the proposed method can accelerate the execution time for combinatorial clustering because there is no need to calculate the coefficients of the constraint function.
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 graph isomorphism problem is one of the applications of combinatorial optimization, and is not known to be solvable in polynomial time. The problem is also not known to be NP-complete. We propose four QUBO formulations for graph isomorphism problem instances. We also propose four QUBO formulations for induced subgraph isomorphism problem instances and two QUBO formulations for subgraph isomorphism problem instances, which are NP-complete problems. We solve QUBO instances defined by our QUBO formulations, using known QUBO solvers: Gurobi optimizer, Fixstars Amplify AE and OpenJij with SA.