The weighted Max-Cut problem is an NP-hard problem with application implications. It is investigated on a cubic lattice with 113 nodes and mixed-signed random edge weights. For a fixed upper bound on edge weights, it has been demonstrated that the computational difficulty increases as the lower bound on edge weights becomes more negative. The solution time for the problem using a novel error-mitigated quantum annealing approach is compared with standard D-Wave quantum annealing (QA) and BQM hybrid solvers, as well as various classical solvers. For the QPU-embeddable weighted Max-Cut instances with mixed-signed edge weights, it has been quantitatively demonstrated that the SEMO (spin-error mitigation for optimisation) error-mitigated quantum annealing achieved substantially shorter time-to solution than standard D-Wave QA, D-Wave BQM, simulated annealing and Tabu search baselines. The error-mitigated quantum annealing approach presented in this article potentially elevates the efficiency and application scope of quantum annealing and would be applicable in solving other discrete optimisation problems that can be formulated as QUBO or Ising instances. The promising solution time advantage would be particularly impactful for time-critical optimisation applications.
The weighted Max-Cut problem is an NP-hard problem with application implications. It is investigated on a cubic lattice with 113 nodes and mixed-signed random edge weights. For a fixed upper bound on edge weights, it has been demonstrated that the computational difficulty increases as the lower bound on edge weights becomes more negative. The solution time for the problem using a novel error-mitigated quantum annealing approach is compared with standard D-Wave quantum annealing (QA) and BQM hybrid solvers, as well as various classical solvers. For the QPU-embeddable weighted Max-Cut instances with mixed-signed edge weights, it has been quantitatively demonstrated that the SEMO (spin-error mitigation for optimisation) error-mitigated quantum annealing achieved substantially shorter time-to solution than standard D-Wave QA, D-Wave BQM, simulated annealing and Tabu search baselines. The error-mitigated quantum annealing approach presented in this article potentially elevates the efficiency and application scope of quantum annealing and would be applicable in solving other discrete optimisation problems that can be formulated as QUBO or Ising instances. The promising solution time advantage would be particularly impactful for time-critical optimisation applications.
ABSTRACT Quantum annealing (QA) has the potential to solve complex optimization problems, but its broad adoption is hindered by qubit errors, which cause an exponential slowdown in computing the global optimal solution as problem size increases. To address this limitation, we present a novel post‐processing error mitigation for optimization technique, known as SEMO (spin‐error mitigation for optimization), designed to improve QA computational efficiency. Its effectiveness is demonstrated through a correlated 3D image segmentation model for material microstructures, formulated as a quadratic unconstrained binary optimization (QUBO) problem. The technique significantly reduces the computing time required to reach the global optimum solution, demonstrating a time‐to‐solution advantage over the standard D‐Wave Systems Advantage QA, simulated annealing (SA), and other post‐processing techniques. Because it operates at the fundamental QUBO level, this approach is applicable to a wide range of discrete combinatorial optimization problems that can be expressed in QUBO format. As the number of qubits in quantum computers continues to increase, this method will become increasingly impactful.
Abstract This paper benchmarks quantum, classical, and hybrid solvers on NP-hard Max-Cut and QUBO problems, emphasizing solution quality relative to known global optima. We evaluate D-Wave’s fast annealing QPU and Hybrid solver against classical simulated annealing (SA) and Toshiba’s simulated bifurcation machine (SBM) using 139 Max-Cut instances (100 to 10,000 nodes). For small instances ( ≤ ≤ 250 nodes) with known global optima, Hybrid and SA consistently achieve optimal solutions, outperforming the QPU. For larger instances, SBM and slower SA yield superior solutions, while Hybrid and faster SA perform less effectively. Computation time varies across solvers.
In this study, we address the formidable challenge of solving large-scale Max-Cut problems (MCP). We introduce a rapid computational procedure utilizing a hybrid 1-flip/r-flip local search heuristic. This innovative strategy significantly reduces the computational time required for MCP problems while consistently generating solutions of exceptional quality. The paper presents substantial computational insights, showcasing the effectiveness of our approach on very-large-scale Max-Cut instances with varying densities. Our proposed heuristic is rigorously evaluated by comparing its performance against a quantum annealing solver, leveraging a multi-start Tabu Search framework. The results underscore the potency of this unique combination as an efficient and effective solution for large-scale QUBO problems. Notably, our hybrid heuristic consistently delivers high-quality solutions within the stringent CPU time limits of 600 seconds, demonstrating its efficacy across Max-Cut instances ranging from 10,000 to 40,000 variables. This research contributes to advancing the state-of-the-art in large-scale QUBO problem-solving, offering a powerful and time-efficient approach with broad applicability.
This study addresses the formidable challenge of solving large-scale Max-Cut problems (MCP). We introduce a rapid computational procedure utilizing a hybrid 1-flip/r-flip local search heuristic. This innovative strategy significantly reduces the computational time required for MCP problems while consistently generating solutions of exceptional quality. The paper presents substantial computational insights, showcasing the effectiveness of our approach on large-scale Max-Cut instances with varying densities. Our proposed heuristic is rigorously evaluated by comparing its performance against a quantum annealing solver, leveraging a multi-start Tabu Search framework. The results underscore the potency of this unique combination as an efficient and effective solution for large-scale QUBO problems. Notably, our hybrid heuristic consistently delivers high-quality solutions within the stringent CPU time limits of 600 seconds, demonstrating its efficacy across Max-Cut instances ranging from 10,000 to 40,000 variables. This research contributes to advancing the state-of-the-art in large-scale QUBO problem-solving, offering a powerful and time-efficient approach with broad applicability.
The recent availability of the first commercial quantum computers has provided a promising tool to tackle NP hard problems which can only be solved heuristically with present techniques. However, it is unclear if the current state of quantum computing already provides a quantum advantage over the current state of the art in classical computing. This article assesses the performance of the D-Wave 2X quantum annealer on two NP hard graph problems, in particular clique finding and graph partitioning. For this, we provide formulations as Qubo and Ising Hamiltonians suitable for the quantum annealer and compare a variety of quantum solvers (Sapi, QBSolv, QSage provided by D-Wave Sys, Inc.) to current classical algorithms (METIS, Simulated Annealing, third-party clique finding and graph splitting heuristics) on certain test sets of graphs. We demonstrate that for small graph instances, classical methods still outperform the quantum annealer in terms of computing time, even though the quality of the best solutions obtained is comparable. Nevertheless, due to the limited problem size which can be embedded on the D-Wave 2X chip, the aforementioned finding applies to most of problems of general nature solvable on the quantum annealer. For instances specifically designed to fit the D-Wave 2X architecture, we observe substantial speed-ups in computing time over classical approaches.
Abstract Quadratic unconstrained binary optimization (QUBO) formulations of combinatorial optimization problems allow for solving them using various quantum heuristics. While large-scale quantum computations are currently still out of reach, we can already numerically test such QUBO formulations on a perhaps surprisingly large scale. In this work, we benchmark Fujitsu’s Digital Annealer (DA) on the Max-Cut problem, which captures the main complexity of the QUBO problem. We make a comprehensive benchmark against leading other heuristic algorithms on graphs with up to 53,000 variables by focusing on the wall-clock time. Moreover, we compare the DA performance against published performance results of the D-Wave hybrid quantum–classical annealer and the recently proposed QIS3 heuristic. Based on performance statistics for over 2000 graphs from the MQLib, we find that the DA yields competitive results. We hope that this benchmark demonstrates the extent to which large QUBO instances can be heuristically solved today, yielding consistent results across different solvers.