Quantum Annealing for Combinatorial Optimization: A Benchmarking Study

• URL: http://arxiv.org/abs/2504.06201v1
• Date: Tue, 08 Apr 2025 16:43:24 GMT
• Title: Quantum Annealing for Combinatorial Optimization: A Benchmarking Study
• Authors: Seongmin Kim, Sang-Woo Ahn, In-Saeng Suh, Alexander W. Dowling, Eungkyu Lee, Tengfei Luo,
• Abstract summary: 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.
• Score: 39.125366249242646
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Quantum annealing (QA) has the potential to significantly improve solution quality and reduce time complexity in solving combinatorial optimization problems compared to classical optimization methods. However, due to the limited number of qubits and their connectivity, the QA hardware did not show such an advantage over classical methods in past benchmarking studies. Recent advancements in QA with more than 5,000 qubits, enhanced qubit connectivity, and the hybrid architecture promise to realize the quantum advantage. Here, we use a quantum annealer with state-of-the-art techniques and benchmark its performance against classical solvers. To compare their performance, we solve over 50 optimization problem instances represented by large and dense Hamiltonian matrices using quantum and classical solvers. The results demonstrate 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. Our results highlight the advantages of leveraging QA over classical counterparts, particularly in hybrid configurations, for achieving high accuracy and substantially reduced problem solving time in large-scale real-world optimization problems.

Related papers

• Learning to Learn with Quantum Optimization via Quantum Neural Networks [1.7819574476785418]
  We introduce a quantum meta-learning framework that combines quantum neural networks, specifically Quantum Long Short-Term Memory (QLSTM) Our approach rapidly generalizes to larger, more complex problems, substantially reducing the number of iterations required for convergence.
  arXiv  Detail & Related papers  (2025-05-01T14:39:26Z)
• Quantum Optimization Benchmark Library -- The Intractable Decathlon [27.362963067036087]
  We present ten optimization problem classes that are difficult for existing classical algorithms.<n>The individual properties of the problem classes vary in terms of objective and variable type, coefficient ranges, and density.<n>We introduce the Quantum Optimization Benchmark Library (QOBLIB) where the problem instances and solution track records can be found.
  arXiv  Detail & Related papers  (2025-04-04T18:00:00Z)
• Hybrid Quantum-Classical Optimisation of Traveling Salesperson Problem [0.0]
  The Traveling Salesperson Problem (TSP) is a fundamental NP-hard optimisation challenge.<n>We present a hybrid quantum-classical approach that integrates quantum optimisation techniques with classical machine learning methods.
  arXiv  Detail & Related papers  (2025-02-28T22:07:28Z)
• Optimization by Decoded Quantum Interferometry [43.55132675053983]
  We introduce a quantum algorithm called Decoded Quantum Interferometry (DQI)<n>For approximating optimal fits to data over finite fields, DQI achieves a better approximation ratio than any time known to us.<n>We demonstrate this by benchmarking on an instance with over 30,000 variables.
  arXiv  Detail & Related papers  (2024-08-15T17:47:42Z)
• 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)
• Guess What Quantum Computing Can Do for Test Case Optimization [43.89456212504871]
  In the near term, quantum approximate optimization algorithms (QAOAs) hold great potential to solve optimization problems. We present the first effort to formulate a software test case optimization problem as a QAOA problem and solve it on quantum computer simulators. To solve bigger test optimization problems that require many qubits, which are unavailable these days, we integrate a problem decomposition strategy with the QAOA.
  arXiv  Detail & Related papers  (2023-12-24T21:25:31Z)
• Variational Quantum Multi-Objective Optimization [5.381539115778766]
  We present a variational quantum optimization algorithm to solve discrete multi-objective optimization problems on quantum computers. We show the effectiveness of the proposed algorithm on several benchmark problems with up to five objectives.
  arXiv  Detail & Related papers  (2023-12-21T18:59:21Z)
• Randomized Benchmarking of Local Zeroth-Order Optimizers for Variational Quantum Systems [65.268245109828]
  We compare the performance of classicals across a series of partially-randomized tasks. We focus on local zeroth-orders due to their generally favorable performance and query-efficiency on quantum systems.
  arXiv  Detail & Related papers  (2023-10-14T02:13:26Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• 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)
• Cross Entropy Hyperparameter Optimization for Constrained Problem Hamiltonians Applied to QAOA [68.11912614360878]
  Hybrid quantum-classical algorithms such as Quantum Approximate Optimization Algorithm (QAOA) are considered as one of the most encouraging approaches for taking advantage of near-term quantum computers in practical applications. Such algorithms are usually implemented in a variational form, combining a classical optimization method with a quantum machine to find good solutions to an optimization problem. In this study we apply a Cross-Entropy method to shape this landscape, which allows the classical parameter to find better parameters more easily and hence results in an improved performance.
  arXiv  Detail & Related papers  (2020-03-11T13:52:41Z)

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.