Experimental Workflows for Combinatorial Optimization: Towards Quantum Advantage

• URL: http://arxiv.org/abs/2604.25162v2
• Date: Wed, 29 Apr 2026 21:38:07 GMT
• Title: Experimental Workflows for Combinatorial Optimization: Towards Quantum Advantage
• Abstract summary: This paper presents a sandbox platform for experimenting with hybrid quantum-classical graph optimization.<n>We transform intractable graph problems into unconstrained problems and solve the resulting instances with QAOA on IBM platforms.<n>We evaluate the approach on synthetic graphs, benchmark instances, and real-world networks, and report hardware experiments on IBM Quantum System One at PINQ2 in Bromont, Quebec.
• Score: 0.08620335948752805
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Demonstrating quantum advantage for combinatorial optimization requires more than standalone algorithmic results; it calls for end-to-end case studies that integrate problem modelling, quantum execution, and classical refinement into practical workflows. This paper presents a sandbox platform for experimenting with hybrid quantum-classical workflows in graph optimization, enabling the systematic study of end-to-end optimization pipelines. Using our platform, we investigate three classically intractable and mutually reducible graph problems -- Minimum Vertex Cover, Maximum Independent Set, and Maximum Clique -- by transforming them into an unconstrained problem and solving the resulting instances with QAOA on IBM platforms. Our workflow combines classical pre-processing to reduce instance size, quantum optimization on the reduced problem, and classical postprocessing to map quantum outputs to high-quality feasible solutions, thereby avoiding direct constraint encoding in the quantum circuit. We evaluate the approach on synthetic graphs, benchmark instances, and real-world networks, and report hardware experiments on IBM Quantum System One at PINQ2 in Bromont, Quebec, powered by IBM's 156-qubit Heron r2 processor on graphs up to 128 vertices, with circuits involving up to 128 qubits and 13,555 two-qubit gates. The results illustrate how sandbox-style end-to-end experimentation can expose bottlenecks, clarify the role of classical-quantum workload partitioning, and provide domain experts and practitioners with a practical guide for interpreting quantum optimization outputs and assessing quantum utility on the road to quantum advantage in combinatorial optimization.

Related papers

• Quantum Annealing for Combinatorial Optimization: Foundations, Architectures, Benchmarks, and Emerging Directions [0.0]
  Critical decision-making issues in science, engineering, and industry are based on optimization.<n>We develop a unified framework, relating adiabatic quantum dynamics, Ising and QUBO models, stoquastic and non-stoquastic Hamiltonians, and diabatic transitions to modern flux-qubit annealers.<n>We find that overhead in embedding and encoding is the largest of the scalability and performance.
  arXiv  Detail & Related papers  (2026-02-03T04:51:26Z)
• Quantum Approximate Optimization Algorithm for MIMO with Quantized b-bit Beamforming [47.98440449939344]
  Multiple-input multiple-output (MIMO) is critical for 6G communication, offering improved spectral efficiency and reliability.<n>This paper explores the use of the Quantum Approximate Optimization Algorithm (QAOA) and alternating optimization to address the problem of b-bit quantized phase shifters both at the transmitter and the receiver.<n>We demonstrate that the structure of this quantized beamforming problem aligns naturally with hybrid-classical methods like QAOA, as the phase shifts used in beamforming can be directly mapped to rotation gates in a quantum circuit.
  arXiv  Detail & Related papers  (2025-10-07T17:53:02Z)
• Quantum Portfolio Optimization: An Extensive Benchmark [0.0]
  We provide a computational study, comparing quantum approaches against state-of-the-art classical methods on a meaningful, real-world instance set.<n>We consider a variant of portfolio optimization which we show to be particular difficult for classical solvers in practice.<n>The results show that all instances can be solved to proven optimality by mixed-integer programming in the order of seconds.
  arXiv  Detail & Related papers  (2025-09-22T15:13:31Z)
• Combinatorial optimization enhanced by shallow quantum circuits with 104 superconducting qubits [14.569660066740758]
  optimization problems have attracted tremendous attention due to their broad applicability and natural fitness to Ising Hamiltonians.<n>Here we propose a quantum sampling strategy, based on which we design an algorithm for accelerating solving the ground states of Ising model.<n>Using up to 104 superconducting qubits, we demonstrate that this algorithm outputs favorable solutions against even a highly-optimized classical simulated subroutine (SA) algorithm.
  arXiv  Detail & Related papers  (2025-09-15T02:58:38Z)
• 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)
• Quantum optimization using a 127-qubit gate-model IBM quantum computer can outperform quantum annealers for nontrivial binary optimization problems [0.0]
  We introduce a comprehensive quantum solver for binary optimization problems on gate-model quantum computers. It consistently delivers correct solutions for problems with up to 127 qubits. We benchmark this solver on IBM quantum computers for several classically nontrivial unconstrained binary optimization problems.
  arXiv  Detail & Related papers  (2024-06-03T19:08:01Z)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems. In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems. We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
  arXiv  Detail & Related papers  (2024-04-17T11:00:12Z)
• Performance analysis of a filtering variational quantum algorithm [0.0]
  Filtering Variational Quantum Eigensolver (F-VQE) is a variational hybrid quantum algorithm designed to solve optimization problems on existing quantum computers.<n>We employ Instantaneous Quantum Polynomial circuits as our parameterized quantum circuits.<n>Despite some observed positive signs, we conclude that significant development is necessary for a practical advantage with F-VQE.
  arXiv  Detail & Related papers  (2024-04-13T08:50:44Z)
• Synergy Between Quantum Circuits and Tensor Networks: Short-cutting the Race to Practical Quantum Advantage [43.3054117987806]
  We introduce a scalable procedure for harnessing classical computing resources to provide pre-optimized initializations for quantum circuits. We show this method significantly improves the trainability and performance of PQCs on a variety of problems. By demonstrating a means of boosting limited quantum resources using classical computers, our approach illustrates the promise of this synergy between quantum and quantum-inspired models in quantum computing.
  arXiv  Detail & Related papers  (2022-08-29T15:24:03Z)
• Realization of arbitrary doubly-controlled quantum phase gates [62.997667081978825]
  We introduce a high-fidelity gate set inspired by a proposal for near-term quantum advantage in optimization problems. By orchestrating coherent, multi-level control over three transmon qutrits, we synthesize a family of deterministic, continuous-angle quantum phase gates acting in the natural three-qubit computational basis.
  arXiv  Detail & Related papers  (2021-08-03T17:49:09Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  We introduce a new variational quantum algorithm that benefits from two innovations: multi-basis graph complexity and nonlinear activation functions. Our results in increased optimization performance, two increase in effective landscapes and a reduction in measurement progress.
  arXiv  Detail & Related papers  (2021-06-24T20:16:02Z)
• 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)
• Quantum circuit architecture search for variational quantum algorithms [88.71725630554758]
  We propose a resource and runtime efficient scheme termed quantum architecture search (QAS) QAS automatically seeks a near-optimal ansatz to balance benefits and side-effects brought by adding more noisy quantum gates. We implement QAS on both the numerical simulator and real quantum hardware, via the IBM cloud, to accomplish data classification and quantum chemistry tasks.
  arXiv  Detail & Related papers  (2020-10-20T12:06:27Z)

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.