This study proposes a GPU-based solver for higherorder unconstrained binary optimization (HUBO). The solver is designed for deployment on consumer-grade GPUs and aims to provide a practical software alternative to specialized quantum and quantum-inspired hardware platforms, such as the D-Wave quantum annealer (QA) and the Fujitsu digital annealer (DA). It incorporates multi-strategy multi-start initialization and amortized O(1) incremental cost function update of bit flips for massively parallel neighborhood search across thousands of GPU threads. Under a uniform 1800-second time limit, experimental results on 48 benchmark cubic knapsack problem (CKP) instances demonstrate that the proposed solver, running on a consumer-grade NVIDIA GPU platform, matches all the previously reported best-known solutions.
This study proposes a GPU-based solver for higherorder unconstrained binary optimization (HUBO). The solver is designed for deployment on consumer-grade GPUs and aims to provide a practical software alternative to specialized quantum and quantum-inspired hardware platforms, such as the D-Wave quantum annealer (QA) and the Fujitsu digital annealer (DA). It incorporates multi-strategy multi-start initialization and amortized O(1) incremental cost function update of bit flips for massively parallel neighborhood search across thousands of GPU threads. Under a uniform 1800-second time limit, experimental results on 48 benchmark cubic knapsack problem (CKP) instances demonstrate that the proposed solver, running on a consumer-grade NVIDIA GPU platform, matches all the previously reported best-known solutions.
We perform an end-to-end benchmark of a hybrid sequential quantum computing (HSQC) solver for higher-order unconstrained binary optimization (HUBO), executed on IBM Heron r3 quantum processors to evaluate the potential of current quantum hardware for combinatorial optimization with sub-second end-to-end runtimes. All reported runtimes include the complete pipeline--from preprocessing to QPU execution and postprocessing--under strict wall-clock accounting. Across 20 benchmark instances, a single hybrid attempt produces high-quality solutions in less than one second, matching the ground-state energy in 14 cases. At the same runtime, CPU-based solvers, including simulated annealing, memetic tabu search, and EasySolve, do not reach the value obtained by HSQC, whereas an enhanced parallel tempering method and the GPU-accelerated solver ABS3 reach or surpass it. These results show that HSQC, executed on a single QPU, can achieve performance competitive with strong classical solvers running on 128 vCPUs or 8 NVIDIA A100 GPUs, while also providing a reproducible system-level benchmark for tracking progress as quantum hardware and hybrid sequential workflows improve.
This study investigates the effectiveness of quantum methods in tackling the cubic knapsack problem (CKP). The CKP is not only NP-hard but also extremely difficult to solve in practice. Benchmark instances of small size (including some with only 60 items) remain unsolved to proven optimality. We solve the CKP using the latest Digital Annealer (DA) prototype, an extended Ising machine available through the Quantum-Inspired Integrated Optimization (QIIO) service on Fujitsu's Kozuchi platform. Specifically, we propose two formulations: a higher-order unconstrained binary optimization (HUBO) and a quadratic unconstrained binary optimization. The latter is derived by reformulating the HUBO model into an equivalent quadratic form. These models are solved using the QIIO solver and compared with three state-of-the-art algorithms, a greedy heuristic, and two mixed integer programs. Additionally, we introduce a postprocessing heuristic to ensure the feasibility of solutions generated by the DA solver, as within short time limits, it does not always produce feasible solutions. Computational experiments are conducted on instances with up to 200 items and varying densities of nonzero objective coefficients. The results indicate that the HUBO formulation is highly competitive with state-of-the-art algorithms, achieving the best new solutions for six large instances.
We introduce VeloxQ, a fast solver for Quadratic Unconstrained Binary Optimization (QUBO) problems, which are central to many real-world optimization tasks. Unlike approaches that depend on emerging quantum hardware, VeloxQ can be deployed on conventional computing infrastructure. We benchmark VeloxQ against state-of-the-art QUBO solvers from several families. These include quantum annealers, specifically D-Wave's Advantage and Advantage2 platforms; the digital-quantum BF-DCQO algorithm for Higher-Order Unconstrained Binary Optimization (HUBO) developed by Kipu Quantum; physics-inspired algorithms including Simulated Bifurcation, Parallel Annealing, and tropical tensor networks; and conventional methods including CPLEX, brute force, BEIT's Chimera solver, and Branch-and-Bound variants. The benchmark suite covers native quantum-annealer topologies, embedded all-to-all instances, HUBO-derived instances, planted-solution instances, certified-solver regimes, and dense Branch-and-Bound test cases. Across the benchmark suite, VeloxQ delivers competitive solution quality and runtime, and in several regimes outperforms the compared solvers. VeloxQ also demonstrates strong scalability. Among the solvers considered in this study, it was the only method we could run on the largest sparse instances within our computational budget, including problems with up to 108 sparsely connected variables. These findings position VeloxQ as a competitive and practical tool for tackling large-scale QUBO/HUBO problems, offering a practical alternative to existing quantum and classical optimization methods.
Quadratic Unconstraint Binary Optimization (QUBO) is a combinatorial optimization problem such that ann×nupper triangle matrixWis given and the objective is to find an n-bit vectorXthat minimizes the energy valueE(X)=XTWX. A QUBO instanceWis sparse if instanceWhas few non-zero elements. The D-Wave 2000Qis a quantum annealer that can solve 2048-bit sparse QUBO instances represented as a Chimera graph topology. We present a sparse QUBO solver running on GPUs for 2048-bit sparse QUBO with a Chimera graph topology. We have evaluated the performance of our sparse QUBO solver and the D-Wave 2000Q for solving 2048-bit QUBO instances with various resolutions. The experimental results show that our sparse QUBO solver running on a GPU cloud server with 8 NVIDIA A100 GPUs can find optimal solutions in less than 3ms for all instances while the D-Wave 2000Qcannot find them in 996.7ms. Hence, our QUBO solver can find better solutions than the D-Wave 2000Q in less than 1/300 running time. We can think that our QUBO solver is a quantum annealer simulator with better performance in terms of the accuracy of solutions and the running time. Our result implies that quantum annealer D-Wave 2000Qdoes not achieve quantum supremacy yet.
The increasing complexity of industrial scheduling and transport routing problems motivates the study of alternative optimization formulations and computational paradigms. In this work, we study how higher-order unconstrained binary optimization (HUBO) formulations of such problems map onto quantum optimization workflows in both noisy and fault-tolerant regimes. We consider three representative logistics and manufacturing use cases and formulate each as a HUBO problem. This captures process intricacies, such as highly correlated assembly-line scheduling rules, which are difficult to express faithfully with the standard quadratic (QUBO) form, while at the same time reducing the number of binary variables required in the quantum mapping, thus lowering qubit demand. We compare the HUBO formulations with corresponding QUBO encodings, highlighting a key trade-off: while HUBO reduces qubit requirements through compact binary encoding, it introduces higher-order interaction terms that increase circuit depth, limiting feasibility on current quantum hardware. The proposed formulations are validated using classical solvers across several problem instances and benchmark small routing problem instances using bias-field digitized counterdiabatic quantum optimization in classical simulation. We complement these results with a resource and scalability analysis, focusing on the capacitated vehicle routing problem as a representative large-scale industrial use case. Our analysis indicates that while HUBO formulations offer advantages in qubit scaling compared to QUBO encodings, their practical implementation is constrained by gate fidelity, coherence, and circuit depth, making hybrid quantum-classical workflows and early fault-tolerant quantum hardware the most plausible settings for their practical use.
The quadratic unconstrained binary optimization (QUBO) is recently gathering attention in conjunction with quantum annealing (QA), since it is equivalent to finding the ground state of an Ising model. Due to the limitation of current QA systems, classical computers may outperform them. Researchers have thus been proposed to solve QUBO on FPGAs, GPUs, and special purpose processors. In this paper, we propose an adaptive bulk search (ABS), a framework for solving QUBO that can perform many searches in parallel on multiple GPUs. It supports fully-connected Ising models with up to 32k spins and 16-bit weights. In our ABS, a CPU host performs genetic algorithm (GA) while GPUs asynchronously perform local searches. A bottleneck for solving QUBO exists in the evaluation of the energy function, which requires computational cost for each solution. We show this can be reduced to in our ABS. The experimental results show that, with four NVIDIA GeForce RTX 2080 Ti GPUs, our framework can search up to 1.24 × 1012 solutions per second. We also show that our system quickly solves maximum cut and traveling salesman problems.