Decomposition of Large-Scale Quadratic Unconstrained Binary Optimization Problems for Quantum Annealers and Quantum-Inspired Annealers
Jehn‐Ruey Jiang, Qiao-Yi Lin · 2026
We study the decomposition of large-scale Quadratic Unconstrained Binary Optimization Problems (QUBO) formulations for quantum and quantum-inspired annealers and propose two decomposition mechanisms. The first is one-way-one-hot (1W1H), which replaces a linear inequality with exactly one indicator bank and naturally decomposes the model into many small, parallel subproblems. The second is slack variable range search (SVRS), which introduces a binary-encoded slack and scans restricted windows to balance the number of subproblems and the per-subproblem variable count. Evaluation results using the P08 knapsack problem instance on the Compal Graphic Processing Unit Annealer (CGA) show that SVRS provides a favorable scalability–quality trade-off, while 1W1H remains attractive when the admissible range is small to medium and massive parallelism is available. These results motivate integrating both mechanisms into the National Central University Annealer (NCUA).