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:2602.23038 · Scientific Reports

Parallelizable search-space decomposition for large-scale combinatorial optimization problems using quadratic unconstrained binary optimization

Eiji Kawase, Shuta Kikuchi, Hideaki Tamai, Shu Tanaka

Published Jun 17, 2026• 0 citations
arXivHTMLPDF

Abstract

Combinatorial optimization problems are crucial in industry. However, many COPs are NP-hard, causing the search space to grow exponentially with problem size and rendering large-scale instances computationally intractable. Conventional solvers typically treat problems as monolithic entities, leading to significant efficiency degradation as structural complexity increases. To address this issue, we propose a novel search-space decomposition method that leverages the inherent structure of variables to systematically reduce the size of the master problem. We formulate interaction costs between variables and individual variable costs as a constrained maximum cut problem and convert it into a quadratic unconstrained binary optimization formulation using penalty terms. An Ising-model solver is used to rapidly decompose the problem into independent small-scale subproblems, which are subsequently solved in parallel using mathematical optimization solvers. We validated this method on the capacitated vehicle routing problem. Results demonstrate three significant benefits: a substantial enhancement in feasible solution rates, accelerated convergence, achieving in 1 min the accuracy that the naive method required 30 min to reach, and a variable reduction of up to 95.32%. These findings suggest that search-space decomposition is a promising strategy for efficiently solving large-scale combinatorial optimization problems.

DOI
10.1038/s41598-026-57443-z

Related papers

Compressed Quadratization of Higher Order Binary Optimization Problems

Avradip Mandal, Arnab Roy, Sarvagya Upadhyay +1 more

Recent hardware advances in quantum and quantum-inspired annealers promise substantial speedup for solving NP-hard combinatorial optimization problems compared to general-purpose computers. These special-purpose hardware are built for solving hard instances of Quadratic Unconstrained Binary Optimization (QUBO) problems. In terms of number of variables and precision of these hardware are usually resource-constrained and they work either in Ising space or in Boolean space. Many naturally occurring problem instances are higher-order in nature. The known method to reduce the degree of a higher-order optimization problem uses Rosenberg's polynomial. The method works in Boolean space by reducing the degree of one term by introducing one extra variable. In this work, we prove that in Ising space the degree reduction of one term requires the introduction of two variables. Our proposed method of degree reduction works directly in Ising space, as opposed to converting an Ising polynomial to Boolean space and applying previously known Rosenberg's polynomial. For sparse higher-order Ising problems, this results in a more compact representation of the resultant QUBO problem, which is crucial for utilizing resource-constrained QUBO solvers.

arXiv:2001.00658•DCC•Mar 1, 2020•33 citations

Geometric Characteristics of Subproblems in Ising-Machine-Assisted Large Neighborhood Search

Masashi Yamashita, Shu Tanaka

Large-scale quadratic unconstrained binary optimization (QUBO) formulations of constrained combinatorial optimization problems often exceed the input-size limit of present Ising machines or suffer from degraded solution quality as the number of binary variables increases. Large neighborhood search (LNS) mitigates this difficulty by sequentially optimizing restricted subproblems, but the structural factors that distinguish subproblems beyond the number of binary variables remain insufficiently characterized. In this study, we examine vehicle routing problems and compare a construction based on the vehicle routes of the current solution, denoted by LNS-K, with a construction based on QUBO variables and constraint relations, denoted by LNS-Q, while controlling the number of binary variables in the subproblems. Under the tested conditions, LNS-K obtained shorter total distances than LNS-Q in the matched-size comparisons, and the position variance, a measure of the spatial spread of the selected customers, decreased during the iterations in LNS-K. These observations suggest that subproblem design for sequential optimization with Ising machines should consider not only subproblem size but also semantic and geometric structures inherited from the current solution.

cond-mat.stat-mechCross-listedarXiv:2607.05014•Jul 7, 2026•0 citations

Construction of SubQUBOs by K-Means Clustering of QUBO Variables

Yuko Kamishima, Shuta Kikuchi, Shu Tanaka

Ising machines are specialized solvers for combinatorial optimization problems (COPs), which are typically formulated as quadratic unconstrained binary optimization (QUBO) models. To enhance their performance, various methods have been proposed to construct subQUBOs by reducing the number of variables in the original QUBO. This study proposes a general subQUBO construction method applicable to a wide range of problems. The variables are clustered based on their interaction structure using theK-means clustering. A subQUBO is constructed from a randomly selected cluster and a pre-obtained tentative solution and then solved. This process of cluster selection and subQUBOs is performed iteratively. We evaluated the performance of the method on the quadratic assignment problem and compared it with two baselines: one that randomly reduces variables and another that directly solves the original QUBO without any variable reduction. Experimental evaluations demonstrated that the proposed method achieves high-accuracy solutions within the same computation time, particularly for large problem sizes.

IEEE Access•Jan 1, 2025•1 citation

Resource-Constrained Heuristic for Max-SAT

Brian Matejek, Daniel Elenius, Cale M. Gentry +2 more

We propose a resource-constrained heuristic for instances of Max-SAT that iteratively decomposes a larger problem into smaller subcomponents that can be solved by optimized solvers and hardware. The unconstrained outer loop maintains the state space of a given problem and selects a subset of the SAT variables for optimization independent of previous calls. The resource-constrained inner loop maximizes the number of satisfiable clauses in the "sub-SAT" problem. Our outer loop is agnostic to the mechanisms of the inner loop, allowing for the use of traditional solvers for the optimization step. However, we can also transform the selected "sub-SAT" problem into a quadratic unconstrained binary optimization (QUBO) one and use specialized hardware for optimization. In contrast to existing solutions that convert a SAT instance into a QUBO one before decomposition, we choose a subset of the SAT variables before QUBO optimization. We analyze a set of variable selection methods, including a novel graph-based method that exploits the structure of a given SAT instance. The number of QUBO variables needed to encode a (sub-)SAT problem varies, so we additionally learn a model that predicts the size of sub-SAT problems that will fit a fixed-size QUBO solver. We empirically demonstrate our results on a set of randomly generated Max-SAT instances as well as real world examples from the Max-SAT evaluation benchmarks and outperform existing QUBO decomposer solutions.

arXiv:2410.09173•Oct 11, 2024•1 citation

Encoding Matters: Benchmarking Binary and D-ary Representations for Quantum Combinatorial Optimization

Shashank Sanjay Bhat, Peiyong Wang, Joseph West +1 more

Combinatorial optimization problems are typically formulated using Quadratic Unconstrained Binary Optimization (QUBO), where constraints are enforced through penalty terms that introduce auxiliary variables and rapidly increase Hamiltonian complexity, limiting scalability on near term quantum devices. In this work, we systematically study Quadratic Unconstrained D-ary Optimization (QUDO) as an alternative formulation in which decision variables are encoded directly in higher dimensional Hilbert spaces. We demonstrate that QUDO naturally captures structural constraints across a range of problem classes, including the Traveling Salesman Problem, two variants of the Vehicle Routing Problem, graph coloring, job scheduling, and Max-K-Cut, without the need for extensive penalty constructions. Using a qudit-level implementation of the Quantum Approximate Optimization Algorithm (qudit QAOA), we benchmark these formulations against their binary QUBO counterparts and exact classical solutions. Our study show consistently improved approximation ratios and substantially reduced computational overhead at comparable circuit depths, highlighting QUDO as a scalable and expressive representation for quantum combinatorial optimization.

quant-pharXiv:2602.07357•Feb 10, 2026•0 citations

Linearizing Binary Optimization Problems Using Variable Posets for Ising Machines

Kentaro Ohno, Nozomu Togawa

Ising machines are next-generation computers expected to efficiently sample near-optimal solutions of combinatorial optimization problems. Combinatorial optimization problems are modeled as quadratic unconstrained binary optimization (QUBO) problems to apply an Ising machine. However, current state-of-the-art Ising machines still often fail to output nearoptimal solutions due to the complicated energy landscape of QUBO problems. Furthermore, the physical implementation of Ising machines severely restricts the size of QUBO problems to be input as a result of limited hardware graph structures. In this study, we take a new approach to these challenges by injecting auxiliary penalties preserving the optimum, which reduces quadratic terms in QUBO objective functions. The process simultaneously simplifies the energy landscape of QUBO problems, allowing the search for near-optimal solutions, and makes QUBO problems sparser, facilitating encoding into Ising machines with restriction on the hardware graph structure. We propose linearization of QUBO problems using variable posets as an outcome of the approach. By applying the proposed method to synthetic QUBO instances and to multi-dimensional knapsack problems, we empirically validate the effects on enhancing minorembedding of QUBO problems and the performance of Ising machines.

arXiv:2307.05125•IEEE Transactions on Emerging Topics in Computing•May 30, 2024•4 citations
Combinatorial optimization problems are crucial in industry. However, many COPs are NP-hard, causing the search space to grow exponentially with problem size and rendering large-scale instances computationally intractable. Conventional solvers typically treat problems as monolithic entities, leading to significant efficiency degradation as structural complexity increases. To address this issue, we propose a novel search-space decomposition method that leverages the inherent structure of variables to systematically reduce the size of the master problem. We formulate interaction costs between variables and individual variable costs as a constrained maximum cut problem and convert it into a quadratic unconstrained binary optimization formulation using penalty terms. An Ising-model solver is used to rapidly decompose the problem into independent small-scale subproblems, which are subsequently solved in parallel using mathematical optimization solvers. We validated this method on the capacitated vehicle routing problem. Results demonstrate three significant benefits: a substantial enhancement in feasible solution rates, accelerated convergence, achieving in 1 min the accuracy that the naive method required 30 min to reach, and a variable reduction of up to 95.32%. These findings suggest that search-space decomposition is a promising strategy for efficiently solving large-scale combinatorial optimization problems.
Recent hardware advances in quantum and quantum-inspired annealers promise substantial speedup for solving NP-hard combinatorial optimization problems compared to general-purpose computers. These special-purpose hardware are built for solving hard instances of Quadratic Unconstrained Binary Optimization (QUBO) problems. In terms of number of variables and precision of these hardware are usually resource-constrained and they work either in Ising space or in Boolean space. Many naturally occurring problem instances are higher-order in nature. The known method to reduce the degree of a higher-order optimization problem uses Rosenberg's polynomial. The method works in Boolean space by reducing the degree of one term by introducing one extra variable. In this work, we prove that in Ising space the degree reduction of one term requires the introduction of two variables. Our proposed method of degree reduction works directly in Ising space, as opposed to converting an Ising polynomial to Boolean space and applying previously known Rosenberg's polynomial. For sparse higher-order Ising problems, this results in a more compact representation of the resultant QUBO problem, which is crucial for utilizing resource-constrained QUBO solvers.
Large-scale quadratic unconstrained binary optimization (QUBO) formulations of constrained combinatorial optimization problems often exceed the input-size limit of present Ising machines or suffer from degraded solution quality as the number of binary variables increases. Large neighborhood search (LNS) mitigates this difficulty by sequentially optimizing restricted subproblems, but the structural factors that distinguish subproblems beyond the number of binary variables remain insufficiently characterized. In this study, we examine vehicle routing problems and compare a construction based on the vehicle routes of the current solution, denoted by LNS-K, with a construction based on QUBO variables and constraint relations, denoted by LNS-Q, while controlling the number of binary variables in the subproblems. Under the tested conditions, LNS-K obtained shorter total distances than LNS-Q in the matched-size comparisons, and the position variance, a measure of the spatial spread of the selected customers, decreased during the iterations in LNS-K. These observations suggest that subproblem design for sequential optimization with Ising machines should consider not only subproblem size but also semantic and geometric structures inherited from the current solution.
Ising machines are specialized solvers for combinatorial optimization problems (COPs), which are typically formulated as quadratic unconstrained binary optimization (QUBO) models. To enhance their performance, various methods have been proposed to construct subQUBOs by reducing the number of variables in the original QUBO. This study proposes a general subQUBO construction method applicable to a wide range of problems. The variables are clustered based on their interaction structure using theK-means clustering. A subQUBO is constructed from a randomly selected cluster and a pre-obtained tentative solution and then solved. This process of cluster selection and subQUBOs is performed iteratively. We evaluated the performance of the method on the quadratic assignment problem and compared it with two baselines: one that randomly reduces variables and another that directly solves the original QUBO without any variable reduction. Experimental evaluations demonstrated that the proposed method achieves high-accuracy solutions within the same computation time, particularly for large problem sizes.
We propose a resource-constrained heuristic for instances of Max-SAT that iteratively decomposes a larger problem into smaller subcomponents that can be solved by optimized solvers and hardware. The unconstrained outer loop maintains the state space of a given problem and selects a subset of the SAT variables for optimization independent of previous calls. The resource-constrained inner loop maximizes the number of satisfiable clauses in the "sub-SAT" problem. Our outer loop is agnostic to the mechanisms of the inner loop, allowing for the use of traditional solvers for the optimization step. However, we can also transform the selected "sub-SAT" problem into a quadratic unconstrained binary optimization (QUBO) one and use specialized hardware for optimization. In contrast to existing solutions that convert a SAT instance into a QUBO one before decomposition, we choose a subset of the SAT variables before QUBO optimization. We analyze a set of variable selection methods, including a novel graph-based method that exploits the structure of a given SAT instance. The number of QUBO variables needed to encode a (sub-)SAT problem varies, so we additionally learn a model that predicts the size of sub-SAT problems that will fit a fixed-size QUBO solver. We empirically demonstrate our results on a set of randomly generated Max-SAT instances as well as real world examples from the Max-SAT evaluation benchmarks and outperform existing QUBO decomposer solutions.
Combinatorial optimization problems are typically formulated using Quadratic Unconstrained Binary Optimization (QUBO), where constraints are enforced through penalty terms that introduce auxiliary variables and rapidly increase Hamiltonian complexity, limiting scalability on near term quantum devices. In this work, we systematically study Quadratic Unconstrained D-ary Optimization (QUDO) as an alternative formulation in which decision variables are encoded directly in higher dimensional Hilbert spaces. We demonstrate that QUDO naturally captures structural constraints across a range of problem classes, including the Traveling Salesman Problem, two variants of the Vehicle Routing Problem, graph coloring, job scheduling, and Max-K-Cut, without the need for extensive penalty constructions. Using a qudit-level implementation of the Quantum Approximate Optimization Algorithm (qudit QAOA), we benchmark these formulations against their binary QUBO counterparts and exact classical solutions. Our study show consistently improved approximation ratios and substantially reduced computational overhead at comparable circuit depths, highlighting QUDO as a scalable and expressive representation for quantum combinatorial optimization.
Ising machines are next-generation computers expected to efficiently sample near-optimal solutions of combinatorial optimization problems. Combinatorial optimization problems are modeled as quadratic unconstrained binary optimization (QUBO) problems to apply an Ising machine. However, current state-of-the-art Ising machines still often fail to output nearoptimal solutions due to the complicated energy landscape of QUBO problems. Furthermore, the physical implementation of Ising machines severely restricts the size of QUBO problems to be input as a result of limited hardware graph structures. In this study, we take a new approach to these challenges by injecting auxiliary penalties preserving the optimum, which reduces quadratic terms in QUBO objective functions. The process simultaneously simplifies the energy landscape of QUBO problems, allowing the search for near-optimal solutions, and makes QUBO problems sparser, facilitating encoding into Ising machines with restriction on the hardware graph structure. We propose linearization of QUBO problems using variable posets as an outcome of the approach. By applying the proposed method to synthetic QUBO instances and to multi-dimensional knapsack problems, we empirically validate the effects on enhancing minorembedding of QUBO problems and the performance of Ising machines.