The Quest for Quantum Advantage in Combinatorial Optimization: End-to-end Benchmarking of Quantum Solvers vs. Multi-core Classical Solvers

• URL: http://arxiv.org/abs/2603.13607v1
• Date: Fri, 13 Mar 2026 21:29:20 GMT
• Title: The Quest for Quantum Advantage in Combinatorial Optimization: End-to-end Benchmarking of Quantum Solvers vs. Multi-core Classical Solvers
• Abstract summary: We perform an end-to-end benchmark of a hybrid sequential quantum computing solver for higher-order unconstrained binary optimization (HUBO) on IBM Heron r3 quantum processors.<n>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.
• Score: 34.734652426291525
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Parallel Circuit Execution for Scalable Quantum Computation [0.7747796552298198]
  We introduce an error- and topology-aware method for mapping multiple independent circuits onto disjoint regions of a single large-scale QPU for parallel circuit execution.<n>We demonstrate the approach on IBM's 156-qubit ibm_boston processor using standard QED-C benchmark and Hamiltonian-based observable-estimation workloads.
  arXiv  Detail & Related papers  (2026-09-10T20:00:16Z)
• Classic and Quantum Task-Based Intelligent Runtime for QIRs Running on Multiple QPUs [1.212250364181868]
  We introduce an intelligent, task-based runtime that marries the Intelligent RuntIme System (IRIS) scheduler with a quantum programming stack through the Quantum Intermediate Representation Execution Engine (QIR-EE)<n>Our design allows programs written in the quantum intermediate representation (QIR) to be dispatched concurrently to a variety of back-ends, including multiple quantum simulators and nascent quantum processors, enabling genuine hybrid execution on a single node.
  arXiv  Detail & Related papers  (2026-05-12T01:14:13Z)
• Towards High Performance Quantum Computing (HPQ): Parallelisation of the Hamiltonian Auto Decomposition Optimisation Framework (HADOF) [0.0]
  Hamiltonian Auto Decomposition Optimisation Framework (HADOF) addresses this by decomposing large quantum QUBOs into smaller subproblems.<n>This allows the scalability of quantum QUBO algorithms beyond device limits, as well as their simulation on classical devices.<n>We show that even single QPU execution benefits from parallelised job orchestration and execution, yielding up to 3x speedup.
  arXiv  Detail & Related papers  (2026-04-30T13:22:02Z)
• Parallelizing Program Execution on Distributed Quantum Systems via Compiler/Hardware Co-Design [39.81714981855818]
  This paper introduces a novel approach to enhance the execution of quantum algorithms on distributed quantum systems.<n>The proposed method involves the development of a hardware design that supports parallel instruction execution and a compiler that modifies the order of instructions to increase parallelism opportunities.<n>The results demonstrate a significant speedup, achieving a maximum average speedup of 16.5x and a maximum single-benchmark speedup of 56.2x relative to a baseline, serial execution model.
  arXiv  Detail & Related papers  (2025-11-18T10:05:20Z)
• Hybrid Sequential Quantum Computing [33.72751145910978]
  We introduce hybrid sequential quantum computing (HSQC)<n>HSQC systematically integrates classical and quantum methods within a structured, stage-wise workflow.<n>Compared to standalone classical solvers, HSQC achieves a speedup of up to 700 times over SA and up to 9 times over runtime.
  arXiv  Detail & Related papers  (2025-10-07T12:15:43Z)
• Scalable parallel simulation of quantum circuits on CPU and GPU systems [9.62558654513992]
  We present a comprehensive parallelization solution for the Q$2$Chemistry software package.<n>Our optimizations significantly enhance the simulation speed compared to unoptimized baselines.<n>These benchmarks highlight the capability of Q$2$Chemistry to effectively handle large-scale quantum simulations.
  arXiv  Detail & Related papers  (2025-09-05T09:20:11Z)
• Quantum Annealing for Combinatorial Optimization: A Benchmarking Study [39.125366249242646]
  We show that a state-of-the-art quantum solver has higher accuracy (0.013%) and a significantly faster problem-solving time (6,561x) than the best classical solver.<n>Our results highlight the advantages of leveraging QA over classical counterparts, particularly in hybrid configurations.
  arXiv  Detail & Related papers  (2025-04-08T16:43:24Z)
• Evaluating the performance of quantum processing units at large width and depth [0.40964539027092917]
  We introduce a benchmarking protocol based on the linear ramp quantum approximate optimization algorithm (LR-QAOA)<n>LR-QAOA quantifies a QPU's ability to preserve a coherent signal as circuit depth increases, identifying when performance becomes statistically indistinguishable from random sampling.<n>We apply this protocol to 24 quantum processors from six vendors, testing problems with up to 156 qubits and 10,000 layers across 1D-chains, native layouts, and fully connected topologies.
  arXiv  Detail & Related papers  (2025-02-10T13:50:50Z)
• Bias-Field Digitized Counterdiabatic Quantum Algorithm for Higher-Order Binary Optimization [35.18016233072556]
  Combinatorial optimization plays a crucial role in many industrial applications.<n>We present an enhanced bias-field digitized counterdiabatic quantum optimization (BF-DCQO) algorithm to address higher-order unconstrained binary optimization (HUBO)<n>Our results show that BF-DCQO offers an effective path for solving large-scale HUBO problems on current and near-term quantum processors.
  arXiv  Detail & Related papers  (2024-09-05T17:38:59Z)
• Parallel Quantum Computing Simulations via Quantum Accelerator Platform Virtualization [44.99833362998488]
  We present a model for parallelizing simulation of quantum circuit executions. The model can take advantage of its backend-agnostic features, enabling parallel quantum circuit execution over any target backend.
  arXiv  Detail & Related papers  (2024-06-05T17:16:07Z)
• Accelerating variational quantum algorithms with multiple quantum processors [78.36566711543476]
  Variational quantum algorithms (VQAs) have the potential of utilizing near-term quantum machines to gain certain computational advantages. Modern VQAs suffer from cumbersome computational overhead, hampered by the tradition of employing a solitary quantum processor to handle large data. Here we devise an efficient distributed optimization scheme, called QUDIO, to address this issue.
  arXiv  Detail & Related papers  (2021-06-24T08:18:42Z)
• Benchmarking quantum co-processors in an application-centric, hardware-agnostic and scalable way [0.0]
  We introduce a new benchmark, dubbed Atos Q-score (TM) The Q-score measures the maximum number of qubits that can be used effectively to solve the MaxCut optimization problem. We provide an open-source implementation of Q-score that makes it easy to compute the Q-score of any quantum hardware.
  arXiv  Detail & Related papers  (2021-02-25T16:26:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.