Stochastic gradient descent for hybrid quantum-classical optimization

Abstract

Within the context of hybrid quantum-classical optimization, gradient descent based optimizers typically require the evaluation of expectation values with respect to the outcome of parameterized quantum circuits. In this work, we explore the consequences of the prior observation that estimation of these quantities on quantum hardware results in a form of stochastic gradient descent optimization. We formalize this notion, which allows us to show that in many relevant cases, including VQE, QAOA and certain quantum classifiers, estimating expectation values with $k$ measurement outcomes results in optimization algorithms whose convergence properties can be rigorously well understood, for any value of $k$. In fact, even using single measurement outcomes for the estimation of expectation values is sufficient. Moreover, in many settings the required gradients can be expressed as linear combinations of expectation values -- originating, e.g., from a sum over local terms of a Hamiltonian, a parameter shift rule, or a sum over data-set instances -- and we show that in these cases $k$-shot expectation value estimation can be combined with sampling over terms of the linear combination, to obtain "doubly stochastic" gradient descent optimizers. For all algorithms we prove convergence guarantees, providing a framework for the derivation of rigorous optimization results in the context of near-term quantum devices. Additionally, we explore numerically these methods on benchmark VQE, QAOA and quantum-enhanced machine learning tasks and show that treating the stochastic settings as hyper-parameters allows for state-of-the-art results with significantly fewer circuit executions and measurements.

arXiv commentSignificantly revised version - accepted in Quantum. Includes reference and discussion of earlier related work by Harrow and Napp (arXiv:1901.05374)

References in corpus (27)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A variational eigenvalue solver on a quantum processor
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Probing many-body dynamics on a 51-atom quantum simulator
• Supervised learning with quantum enhanced feature spaces
• The theory of variational hybrid quantum-classical algorithms
• Quantum Circuit Learning
• Parameterized quantum circuits as machine learning models
• Observation of a Many-Body Dynamical Phase Transition with a 53-Qubit Quantum Simulator
• Evaluating analytic gradients on quantum hardware
• Circuit-centric quantum classifiers
• Quantum Approximate Optimization Algorithm: Performance, Mechanism, and Implementation on Near-Term Devices
• Self-Verifying Variational Quantum Simulation of the Lattice Schwinger Model
• A blueprint for demonstrating quantum supremacy with superconducting qubits
• Entropy scaling and simulability by Matrix Product States
• A random compiler for fast Hamiltonian simulation
• Average-case complexity versus approximate simulation of commuting quantum computations
• PennyLane: Automatic differentiation of hybrid quantum-classical computations
• Training of Quantum Circuits on a Hybrid Quantum Computer
• An Adaptive Optimizer for Measurement-Frugal Variational Algorithms
• Optimizing quantum optimization algorithms via faster quantum gradient computation
• Architectures for quantum simulation showing a quantum speedup
• Quantum Supremacy for Simulating A Translation-Invariant Ising Spin Model
• Minimizing State Preparations in Variational Quantum Eigensolver by Partitioning into Commuting Families
• Quantum-circuit design for efficient simulations of many-body quantum dynamics
• On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes

Cited by in corpus (91)

• Variational Quantum Algorithms
• Noisy intermediate-scale quantum (NISQ) algorithms
• The power of quantum neural networks
• Challenges and Opportunities in Quantum Machine Learning
• A Review on Quantum Approximate Optimization Algorithm and its Variants
• General parameter-shift rules for quantum gradients
• Experimental Quantum Generative Adversarial Networks for Image Generation
• Effect of barren plateaus on gradient-free optimization
• Variational Quantum Linear Solver
• Solving nonlinear differential equations with differentiable quantum circuits
• Quantum circuit architecture search for variational quantum algorithms
• Fermionic partial tomography via classical shadows
• Estimating the gradient and higher-order derivatives on quantum hardware
• Large gradients via correlation in random parameterized quantum circuits
• Equivalence of quantum barren plateaus to cost concentration and narrow gorges
• Variational Quantum State Eigensolver
• Filtering variational quantum algorithms for combinatorial optimization
• Efficient measure for the expressivity of variational quantum algorithms
• Low-depth gradient measurements can improve convergence in variational hybrid quantum-classical algorithms
• An Adaptive Optimizer for Measurement-Frugal Variational Algorithms
• A variational toolbox for quantum multi-parameter estimation
• Hybrid Quantum-Classical Generative Adversarial Network for High Resolution Image Generation
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• Variational-State Quantum Metrology
• Measuring Analytic Gradients of General Quantum Evolution with the Stochastic Parameter Shift Rule
• Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation
• Recent advances for quantum classifiers
• A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance
• Minimizing estimation runtime on noisy quantum computers
• Learning temporal data with variational quantum recurrent neural network
• Quantum Analytic Descent
• Graph neural network initialisation of quantum approximate optimisation
• Quantum natural gradient generalised to noisy and non-unitary circuits
• Noise-Resilient Variational Hybrid Quantum-Classical Optimization
• Robust resource-efficient quantum variational ansatz through evolutionary algorithm
• Trainability barriers and opportunities in quantum generative modeling
• Trainability Enhancement of Parameterized Quantum Circuits via Reduced-Domain Parameter Initialization
• Optimal quantum control with poor statistics
• Non-trivial symmetries in quantum landscapes and their resilience to quantum noise
• Tree tensor network classifiers for machine learning: from quantum-inspired to quantum-assisted
• Towards Quantum Belief Propagation for LDPC Decoding in Wireless Networks
• Stochastic Gradient Line Bayesian Optimization for Efficient Noise-Robust Optimization of Parameterized Quantum Circuits
• Training variational quantum circuits with CoVaR: covariance root finding with classical shadows
• Quantum State Discrimination Using Noisy Quantum Neural Networks
• Surrogate-based optimization for variational quantum algorithms
• Quantum Fourier analysis for multivariate functions and applications to a class of Schrödinger-type partial differential equations
• Towards Cosmological Simulations of Dark Matter on Quantum Computers
• Stochastic noise can be helpful for variational quantum algorithms
• Inference-Based Quantum Sensing
• Here comes the SU(N): multivariate quantum gates and gradients
• Robustness of quantum algorithms against coherent control errors
• Post-Hartree-Fock method in Quantum Chemistry for Quantum Computer
• Networked Quantum Services
• Improved variational quantum eigensolver via quasi-dynamical evolution
• Focusing on the Hybrid Quantum Computing -- Tabu Search Algorithm: new results on the Asymmetric Salesman Problem
• Quantum Continual Learning Overcoming Catastrophic Forgetting
• Quantum computing through the lens of control: A tutorial introduction
• Automatic Depth Optimization for Quantum Approximate Optimization Algorithm
• Hardware-Tailored Diagonalization Circuits
• Single-component gradient rules for variational quantum algorithms
• Demonstration of a bosonic quantum classifier with data re-uploading
• Fermionic Simulators for Enhanced Scalability of Variational Quantum Simulation
• Resource frugal optimizer for quantum machine learning
• Faster variational quantum algorithms with quantum kernel-based surrogate models
• Implementable Hybrid Quantum Ant Colony Optimization Algorithm
• Bayesian Learning of Parameterised Quantum Circuits
• Random coordinate descent: a simple alternative for optimizing parameterized quantum circuits
• Towards Optimizations of Quantum Circuit Simulation for Solving Max-Cut Problems with QAOA
• Prog-QAOA: Framework for resource-efficient quantum optimization through classical programs
• Information flow in parameterized quantum circuits
• Finite-depth scaling of infinite quantum circuits for quantum critical points
• Decoherence Effects in a Three-Level System under Gaussian Process
• Quantum optimal control in quantum technologies. Strategic report on current status, visions and goals for research in Europe
• Universal noise-precision relations in variational quantum algorithms
• Resource-efficient utilization of quantum computers
• Backpropagation scaling in parameterised quantum circuits
• Learning to learn with an evolutionary strategy applied to variational quantum algorithms
• Stabilizer configuration interaction: Finding molecular subspaces with error detection properties
• Revisiting semiconductor bulk hamiltonians using quantum computers
• Error Analysis of the Variational Quantum Eigensolver Algorithm
• The Accuracy vs. Sampling Overhead Trade-off in Quantum Error Mitigation Using Monte Carlo-Based Channel Inversion
• Policy Gradients using Variational Quantum Circuits
• Variational quantum algorithm based on Lagrange polynomial encoding to solve differential equations
• On the learning abilities of photonic continuous-variable Born machines
• Global optimization in variational quantum algorithms via dynamic tunneling method
• Quantum natural gradient with thermal-state initialization
• Generative flow-based warm start of the variational quantum eigensolver
• Extended parameter shift rules with minimal derivative variance for parameterized quantum circuits
• Unbiased observable estimation with approximate channels in fault-tolerant quantum computation
• Interpolation-based coordinate descent method for parameterized quantum circuits
• Clustering and enhanced classification using a hybrid quantum autoencoder