Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice

• URL: http://arxiv.org/abs/2408.03073v1
• Date: Tue, 6 Aug 2024 09:57:34 GMT
• Title: Benchmarking Variational Quantum Algorithms for Combinatorial Optimization in Practice
• Authors: Tim Schwägerl, Yahui Chai, Tobias Hartung, Karl Jansen, Stefan Kühn,
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Variational quantum algorithms and, in particular, variants of the varational quantum eigensolver have been proposed to address combinatorial optimization (CO) problems. Using only shallow ansatz circuits, these approaches are deemed suitable for current noisy intermediate-scale quantum hardware. However, the resources required for training shallow variational quantum circuits often scale superpolynomially in problem size. In this study we numerically investigate what this scaling result means in practice for solving CO problems using Max-Cut as a benchmark. For fixed resources, we compare the average performance of training a shallow variational quantum circuit, sampling with replacement, and a greedy algorithm starting from the same initial point as the quantum algorithm. We identify a minimum problem size for which the quantum algorithm can consistently outperform sampling and, for each problem size, characterize the separation between the quantum algorithm and the greedy algorithm. Furthermore, we extend the average case analysis by investigating the correlation between the performance of the algorithms by instance. Our results provide a step towards meaningful benchmarks of variational quantum algorithms for CO problems for a realistic set of resources.

Related papers

• Performance Benchmarking of Quantum Algorithms for Hard Combinatorial Optimization Problems: A Comparative Study of non-FTQC Approaches [0.0]
  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.
  arXiv  Detail & Related papers  (2024-10-30T08:41:29Z)
• Solving non-native combinatorial optimization problems using hybrid quantum-classical algorithms [0.0]
  Combinatorial optimization is a challenging problem applicable in a wide range of fields from logistics to finance. Quantum computing has been used to attempt to solve these problems using a range of algorithms. This work presents a framework to overcome these challenges by integrating quantum and classical resources with a hybrid approach.
  arXiv  Detail & Related papers  (2024-03-05T17:46:04Z)
• 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)
• Iterative Quantum Algorithms for Maximum Independent Set: A Tale of Low-Depth Quantum Algorithms [0.0]
  We study a new class of hybrid approaches to quantum optimization, termed Iterative Maximum Quantum Algorithms. We show that for QAOA with depth $p=1$, this algorithm performs exactly the same operations and selections as the classical greedy algorithm for MIS.
  arXiv  Detail & Related papers  (2023-09-22T18:00:03Z)
• 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)
• Parallel circuit implementation of variational quantum algorithms [0.0]
  We present a method to split quantum circuits of variational quantum algorithms (VQAs) to allow for parallel training and execution. We apply this specifically to optimization problems, where inherent structures from the problem can be identified. We show that not only can our method address larger problems, but that it is also possible to run full VQA models while training parameters using only one slice.
  arXiv  Detail & Related papers  (2023-04-06T12:52:29Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  We study the problem of designing worst-case to average-case reductions for quantum algorithms. We provide an explicit and efficient transformation of quantum algorithms that are only correct on a small fraction of their inputs into ones that are correct on all inputs.
  arXiv  Detail & Related papers  (2022-12-06T22:01:49Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  We provide a complete quantum circuit-level description of the algorithm from problem input to problem output. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
  arXiv  Detail & Related papers  (2022-11-22T18:54:48Z)
• 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 Algorithms for Euclidean Discrepancy and Covariate-Balancing [0.0]
  Algorithmic discrepancy theory seeks efficient algorithms to find those two-colorings of a set that minimize a given measure of coloring imbalance in the set. We frame these problems as quantum Ising models, for which variational quantum algorithms (VQA) are particularly useful.
  arXiv  Detail & Related papers  (2021-03-16T14:13:29Z)
• 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.