Introductory Tutorial for SPSA and the Quantum Approximation Optimization Algorithm

• URL: http://arxiv.org/abs/2106.01578v1
• Date: Thu, 3 Jun 2021 03:54:24 GMT
• Title: Introductory Tutorial for SPSA and the Quantum Approximation Optimization Algorithm
• Authors: Salonik Resch
• Abstract summary: This tutorial provides an introduction to the Quantum Approximation Optimization Algorithm (QAOA) Specifically, how to use QAOA with the Simultaneous Perturbation Approximation (SPSA) algorithm to solve the Max-Cut problem. All steps of the algorithm are explicitly shown and no theory or complex mathematics are used.
• Score: 0.1827510863075184
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This short tutorial provides an introduction to the Quantum Approximation Optimization Algorithm (QAOA). Specifically, how to use QAOA with the Simultaneous Perturbation Stochastic Approximation (SPSA) algorithm to solve the Max-Cut problem. All steps of the algorithm are explicitly shown and no theory or complex mathematics are used. The focus is entirely on setting up a practical implementation. Fully functional examples in both R and python (using Qiskit) are provided, both using roughly 100 lines of code.

Related papers

• BGLS: A Python Package for the Gate-by-Gate Sampling Algorithm to Simulate Quantum Circuits [0.0]
  bgls is a Python package which implements gate-by-gate sampling algorithm. We show how to install and use bgls, discuss optimizations in the algorithm, and demonstrate its utility on several problems.
  arXiv  Detail & Related papers  (2023-11-20T14:12:39Z)
• Self-concordant Smoothing for Large-Scale Convex Composite Optimization [0.0]
  We introduce a notion of self-concordant smoothing for minimizing the sum of two convex functions, one of which is smooth and the other may be nonsmooth. We prove the convergence of two resulting algorithms: Prox-N-SCORE, a proximal Newton algorithm and Prox-GGN-SCORE, a proximal generalized Gauss-Newton algorithm.
  arXiv  Detail & Related papers  (2023-09-04T19:47:04Z)
• A One-Sample Decentralized Proximal Algorithm for Non-Convex Stochastic Composite Optimization [10.762749887051546]
  We propose two-time scale algorithms: ProxDAS-A and Proxcal$DASA-GT. Unlike prior work, our algorithms achieve comparable complexity without requiring large batch sizes, more complex per-it operations, or stronger assumptions.
  arXiv  Detail & Related papers  (2023-02-20T05:16:18Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Graph neural network initialisation of quantum approximate optimisation [2.064612766965483]
  We focus on the quantum approximate optimisation algorithm (QAOA) for solving the Max-Cut problem. We address two problems in the QAOA, how to select initial parameters, and how to subsequently train the parameters to find an optimal solution.
  arXiv  Detail & Related papers  (2021-11-04T17:19:08Z)
• Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
  Bilevel optimization has been widely applied in many important machine learning applications. We propose two new algorithms for bilevel optimization. We show that both algorithms achieve the complexity of $mathcalO(epsilon-1.5)$, which outperforms all existing algorithms by the order of magnitude.
  arXiv  Detail & Related papers  (2021-06-08T21:05:30Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  We propose a new algorithm for the min-player against smooth algorithms deployed by an adversary. Our algorithm is guaranteed to make monotonic progress having no limit cycles, and to find an appropriate number of gradient ascents.
  arXiv  Detail & Related papers  (2021-06-02T22:03:36Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  In many real world problems, we want to infer some property of an expensive black-box function f, given a budget of T function evaluations. We present a procedure, InfoBAX, that sequentially chooses queries that maximize mutual information with respect to the algorithm's output. On these problems, InfoBAX uses up to 500 times fewer queries to f than required by the original algorithm.
  arXiv  Detail & Related papers  (2021-04-19T17:22:11Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Improving the Quantum Approximate Optimization Algorithm with postselection [0.0]
  Combinatorial optimization is among the main applications envisioned for near-term and fault-tolerant quantum computers. We consider a well-studied quantum algorithm for optimization: the Quantum Approximate Optimization Algorithm (QAOA) applied to the MaxCut problem on 3-regular graphs. We derive theoretical upper and lower bounds showing that a constant (though small) increase of the fraction of satisfied edges is indeed achievable.
  arXiv  Detail & Related papers  (2020-11-10T22:17:50Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)

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.