Performance Benchmarking of Quantum Algorithms for Hard Combinatorial Optimization Problems: A Comparative Study of non-FTQC Approaches

• URL: http://arxiv.org/abs/2410.22810v1
• Date: Wed, 30 Oct 2024 08:41:29 GMT
• Title: Performance Benchmarking of Quantum Algorithms for Hard Combinatorial Optimization Problems: A Comparative Study of non-FTQC Approaches
• Authors: Santaro Kikuura, Ryoya Igata, Yuta Shingu, Shohei Watabe,
• Abstract summary: This study systematically benchmarks several non-fault-tolerant quantum computing algorithms across four distinct optimization problems. Our benchmark includes noisy intermediate-scale quantum (NISQ) algorithms, such as the variational quantum eigensolver. Our findings reveal that no single non-FTQC algorithm performs optimally across all problem types, underscoring the need for tailored algorithmic strategies.
• Score: 0.0
• License:
• Abstract: This study systematically benchmarks several non-fault-tolerant quantum computing algorithms across four distinct optimization problems: max-cut, number partitioning, knapsack, and quantum spin glass. Our benchmark includes noisy intermediate-scale quantum (NISQ) algorithms, such as the variational quantum eigensolver, quantum approximate optimization algorithm, quantum imaginary time evolution, and imaginary time quantum annealing, with both ansatz-based and ansatz-free implementations, alongside tensor network methods and direct simulations of the imaginary-time Schr\"odinger equation. For comparative analysis, we also utilize classical simulated annealing and quantum annealing on D-Wave devices. Employing default configurations, our findings reveal that no single non-FTQC algorithm performs optimally across all problem types, underscoring the need for tailored algorithmic strategies. This work provides an objective performance baseline and serves as a critical reference point for advancing NISQ algorithms and quantum annealing platforms.

Related papers

• Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice [0.0]
  Variational quantum algorithms and, in particular, variants of the varational quantum eigensolver have been proposed to address optimization (CO) problems. We numerically investigate what this scaling result means in practice for solving CO problems using Max-Cut as a benchmark.
  arXiv  Detail & Related papers  (2024-08-06T09:57:34Z)
• Quantum Subroutine for Variance Estimation: Algorithmic Design and Applications [80.04533958880862]
  Quantum computing sets the foundation for new ways of designing algorithms. New challenges arise concerning which field quantum speedup can be achieved. Looking for the design of quantum subroutines that are more efficient than their classical counterpart poses solid pillars to new powerful quantum algorithms.
  arXiv  Detail & Related papers  (2024-02-26T09:32:07Z)
• Variational Quantum Approximate Spectral Clustering for Binary Clustering Problems [0.7550566004119158]
  We introduce the Variational Quantum Approximate Spectral Clustering (VQASC) algorithm. VQASC requires optimization of fewer parameters than the system size, N, traditionally required in classical problems. We present numerical results from both synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2023-09-08T17:54:42Z)
• A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
  The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising variational quantum algorithm that aims to solve intractable optimization problems. This comprehensive review offers an overview of the current state of QAOA, encompassing its performance analysis in diverse scenarios. We conduct a comparative study of selected QAOA extensions and variants, while exploring future prospects and directions for the algorithm.
  arXiv  Detail & Related papers  (2023-06-15T15:28:12Z)
• Effectiveness of quantum annealing for continuous-variable optimization [0.0]
  We test the performance of quantum annealing applied to a one-dimensional continuous-variable function with a rugged energy landscape. We conclude that the hardware realization of quantum annealing has the potential to significantly outperform the best classical algorithms.
  arXiv  Detail & Related papers  (2023-05-11T07:59:19Z)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• Optimization Applications as Quantum Performance Benchmarks [0.0]
  Combinatorial optimization is anticipated to be one of the primary use cases for quantum computation in the coming years. Inspired by existing methods to characterize classical optimization algorithms, we analyze the solution quality obtained by solving Max-Cut problems. This is used to guide the development of an advanced benchmarking framework for quantum computers.
  arXiv  Detail & Related papers  (2023-02-05T01:56:06Z)
• Quantum algorithm for stochastic optimal stopping problems with applications in finance [60.54699116238087]
  The famous least squares Monte Carlo (LSM) algorithm combines linear least square regression with Monte Carlo simulation to approximately solve problems in optimal stopping theory. We propose a quantum LSM based on quantum access to a process, on quantum circuits for computing the optimal stopping times, and on quantum techniques for Monte Carlo.
  arXiv  Detail & Related papers  (2021-11-30T12:21:41Z)
• 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)
• An optimal quantum sampling regression algorithm for variational eigensolving in the low qubit number regime [0.0]
  We introduce Quantum Sampling Regression (QSR), an alternative hybrid quantum-classical algorithm. We analyze some of its use cases based on time complexity in the low qubit number regime. We demonstrate the efficacy of our algorithm for a benchmark problem.
  arXiv  Detail & Related papers  (2020-12-04T00:01:15Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17: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.