Evaluation of QAOA based on the approximation ratio of individual samples

• URL: http://arxiv.org/abs/2006.04831v2
• Date: Mon, 7 Dec 2020 20:03:38 GMT
• Title: Evaluation of QAOA based on the approximation ratio of individual samples
• Authors: Jason Larkin, Mat\'ias Jonsson, Daniel Justice, and Gian Giacomo Guerreschi
• Abstract summary: We simulate the performance of QAOA applied to the Max-Cut problem and compare it with some of the best classical alternatives. Because of the evolving QAOA computational complexity-theoretic guidance, we utilize a framework for the search for quantum advantage.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Quantum Approximate Optimization Algorithm (QAOA) is a hybrid quantum-classical algorithm to solve binary-variable optimization problems. Due to the short circuit depth and its expected robustness to systematic errors, it is one of the promising candidates likely to run on near-term quantum devices. We simulate the performance of QAOA applied to the Max-Cut problem and compare it with some of the best classical alternatives, for exact, approximate and heuristic solution. When comparing solvers, their performance is characterized by the computational time taken to achieve a given quality of solution. Since QAOA is based on sampling, we utilize performance metrics based on the probability of observing a sample above a certain quality. In addition, we show that the QAOA performance varies significantly with the graph type. By selecting a suitable optimizer for the variational parameters and reducing the number of function evaluations, QAOA performance improves by up to 2 orders of magnitude compared to previous estimates. Especially for 3-regular random graphs, this setting decreases the performance gap with classical alternatives. Because of the evolving QAOA computational complexity-theoretic guidance, we utilize a framework for the search for quantum advantage which incorporates a large number of problem instances and all three classical solver modalities: exact, approximate, and heuristic.

Related papers

• Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA [0.0]
  In this work, an implementation of the QAOA2 method for the scalable solution of the MaxCut problem is presented. The limits of the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA are investigated. Results from large-scale simulations of up to 33 qubits are presented, showing the advantage of QAOA in certain cases and the efficiency of the implementation.
  arXiv  Detail & Related papers  (2024-06-25T09:02:31Z)
• A hybrid quantum-classical approach to warm-starting optimization [0.0]
  We compare the performance of standard QAOA with that of warm-start QAOA in the context of portfolio optimization. We show that the results can be reproduced or even surpassed by a purely classical preprocessing of the original problem followed by standard QAOA.
  arXiv  Detail & Related papers  (2023-09-25T08:53:54Z)
• 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)
• The QAOA with Few Measurements [4.713817702376467]
  The Approximate Quantum Optimization Algorithm (QAOA) was originally developed to solve optimization problems. Fully descriptive benchmarking techniques are often expensive for large numbers of qubits. Some experimental quantum computing platforms such as neutral atom quantum computers have slow repetition rates.
  arXiv  Detail & Related papers  (2022-05-13T18:42:20Z)
• Twisted hybrid algorithms for combinatorial optimization [68.8204255655161]
  Proposed hybrid algorithms encode a cost function into a problem Hamiltonian and optimize its energy by varying over a set of states with low circuit complexity. We show that for levels $p=2,ldots, 6$, the level $p$ can be reduced by one while roughly maintaining the expected approximation ratio.
  arXiv  Detail & Related papers  (2022-03-01T19:47:16Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity. We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
  arXiv  Detail & Related papers  (2022-01-06T21:02:30Z)
• Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm [0.0]
  We propose a strategy to give high approximation ratio on average, even at large circuit depths, by initializing QAOA with the optimal parameters obtained from the previous depths. We test our strategy on the Max-cut problem of certain classes of graphs such as the 3-regular graphs and the Erd"os-R'enyi graphs.
  arXiv  Detail & Related papers  (2021-08-11T15:44:16Z)
• Quantum Approximate Optimization Algorithm Based Maximum Likelihood Detection [80.28858481461418]
  Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices. Recent advances in quantum technologies pave the way for noisy intermediate-scale quantum (NISQ) devices.
  arXiv  Detail & Related papers  (2021-07-11T10:56:24Z)
• Empirical performance bounds for quantum approximate optimization [0.27998963147546135]
  Quantifying performance bounds provides insight into when QAOA may be viable for solving real-world applications. We find QAOA exceeds the Goemans-Williamson approximation ratio bound for most graphs. The resulting data set is presented as a benchmark for establishing empirical bounds on QAOA performance.
  arXiv  Detail & Related papers  (2021-02-12T23:12:09Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  We prove the $mathcaltilde O(t-1/4)$ rate of convergence for the norm of the gradient of Moreau envelope. Our analysis works with mini-batch size of $1$, constant first and second order moment parameters, and possibly smooth optimization domains.
  arXiv  Detail & Related papers  (2020-06-11T17:43:19Z)
• 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.