Low-depth gradient measurements can improve convergence in variational hybrid quantum-classical algorithms

Abstract

A broad class of hybrid quantum-classical algorithms known as "variational algorithms" have been proposed in the context of quantum simulation, machine learning, and combinatorial optimization as a means of potentially achieving a quantum speedup on a near-term quantum device for a problem of practical interest. Such algorithms use the quantum device only to prepare parameterized quantum states and make simple measurements. A classical controller uses the measurement results to perform an optimization of a classical function induced by a quantum observable which defines the problem. While most prior works have considered optimization strategies based on estimating the objective function and doing a derivative-free or finite-difference-based optimization, some recent proposals involve directly measuring observables corresponding to the gradient of the objective function. The measurement procedure needed requires coherence time barely longer than that needed to prepare a trial state. We prove that strategies based on such gradient measurements can admit substantially faster rates of convergence to the optimum in some contexts. We first introduce a natural black-box setting for variational algorithms which we prove our results with respect to. We define a simple class of problems for which a variational algorithm based on low-depth gradient measurements and stochastic gradient descent converges to the optimum substantially faster than any possible strategy based on estimating the objective function itself, and show that stochastic gradient descent is essentially optimal for this problem. Importing known results from the stochastic optimization literature, we also derive rigorous upper bounds on the cost of variational optimization in a convex region when using gradient measurements in conjunction with certain stochastic gradient descent or stochastic mirror descent algorithms.

arXiv comment45 pages

References in corpus (35)

• Adam: A Method for Stochastic Optimization
• Quantum Computing in the NISQ era and beyond
• A variational eigenvalue solver on a quantum processor
• Hardware-efficient Variational Quantum Eigensolver for Small Molecules and Quantum Magnets
• Supervised learning with quantum enhanced feature spaces
• Barren plateaus in quantum neural network training landscapes
• The theory of variational hybrid quantum-classical algorithms
• A Quantum Approximate Optimization Algorithm
• Quantum machine learning in feature Hilbert spaces
• Quantum Circuit Learning
• Evaluating analytic gradients on quantum hardware
• Circuit-centric quantum classifiers
• Towards Practical Quantum Variational Algorithms
• Efficient variational quantum simulator incorporating active error minimisation
• Variational ansatz-based quantum simulation of imaginary time evolution
• Quantum Generative Adversarial Networks for Learning and Loading Random Distributions
• Quantum Natural Gradient
• Direct estimations of linear and non-linear functionals of a quantum state
• Universal Quantum Estimator
• Quantum-assisted quantum compiling
• A random compiler for fast Hamiltonian simulation
• Differentiable Learning of Quantum Circuit Born Machine
• Hybrid Quantum-Classical Approach to Quantum Optimal Control
• PennyLane: Automatic differentiation of hybrid quantum-classical computations
• Stochastic gradient descent for hybrid quantum-classical optimization
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• Optimizing Variational Quantum Algorithms using Pontryagin's Minimum Principle
• Variational Quantum Eigensolver with Fewer Qubits
• Quantum Adversarial Machine Learning
• An Adaptive Optimizer for Measurement-Frugal Variational Algorithms
• Fast quantum algorithm for numerical gradient estimation
• Optimizing quantum optimization algorithms via faster quantum gradient computation
• Practical optimization for hybrid quantum-classical algorithms
• On the Complexity of Bandit and Derivative-Free Stochastic Convex Optimization
• Adversarial quantum circuit learning for pure state approximation

Cited by in corpus (58)

• Variational Quantum Algorithms
• The effect of data encoding on the expressive power of variational quantum machine learning models
• Quantum Natural Gradient
• Variational Fast Forwarding for Quantum Simulation Beyond the Coherence Time
• Variational Quantum Linear Solver
• Differentiable Quantum Architecture Search
• Fermionic partial tomography via classical shadows
• Large gradients via correlation in random parameterized quantum circuits
• Equivalence of quantum barren plateaus to cost concentration and narrow gorges
• Variational Quantum State Eigensolver
• Scaling of the quantum approximate optimization algorithm on superconducting qubit based hardware
• QNLP in Practice: Running Compositional Models of Meaning on a Quantum Computer
• Approximate amplitude encoding in shallow parameterized quantum circuits and its application to financial market indicator
• Quantum Machine Learning for Particle Physics using a Variational Quantum Classifier
• Near-Term Quantum Computing Techniques: Variational Quantum Algorithms, Error Mitigation, Circuit Compilation, Benchmarking and Classical Simulation
• A comprehensive review of Quantum Machine Learning: from NISQ to Fault Tolerance
• Empirical performance bounds for quantum approximate optimization
• Quantum Hamiltonian-Based Models and the Variational Quantum Thermalizer Algorithm
• Analytic gradients in variational quantum algorithms: Algebraic extensions of the parameter-shift rule to general unitary transformations
• Generalized quantum circuit differentiation rules
• Realizing a quantum generative adversarial network using a programmable superconducting processor
• Challenges of variational quantum optimization with measurement shot noise
• Quantum Architecture Search with Meta-learning
• Universal Adversarial Examples and Perturbations for Quantum Classifiers
• Non-trivial symmetries in quantum landscapes and their resilience to quantum noise
• Stochastic Gradient Line Bayesian Optimization for Efficient Noise-Robust Optimization of Parameterized Quantum Circuits
• Cost function embedding and dataset encoding for machine learning with parameterized quantum circuits
• Operator Sampling for Shot-frugal Optimization in Variational Algorithms
• Benchmarking variational quantum eigensolvers for the square-octagon-lattice Kitaev model
• Quantum hardware calculations of periodic systems with partition-measurement symmetry verification: simplified models of hydrogen chain and iron crystals
• Efficient calculation of gradients in classical simulations of variational quantum algorithms
• Reduction of finite sampling noise in quantum neural networks
• Limitations of optimization algorithms on noisy quantum devices
• Here comes the SU(N): multivariate quantum gates and gradients
• Estimating Quantum Mutual Information Through a Quantum Neural Network
• Scalable Quantum Simulations of Scattering in Scalar Field Theory on 120 Qubits
• Optimizing the information extracted by a single qubit measurement
• Thermal variational quantum simulation on a superconducting quantum processor
• Quantum computing through the lens of control: A tutorial introduction
• Numerical hardware-efficient variational quantum simulation of a soliton solution
• Beyond MP2 initialization for unitary coupled cluster quantum circuits
• Small quantum computers and large classical data sets
• Bayesian Learning of Parameterised Quantum Circuits
• Density Matrix Emulation of Quantum Recurrent Neural Networks for Multivariate Time Series Prediction
• Qsun: an open-source platform towards practical quantum machine learning applications
• The dilemma of quantum neural networks
• Adaptive shot allocation for fast convergence in variational quantum algorithms
• Image Compression and Classification Using Qubits and Quantum Deep Learning
• Information flow in parameterized quantum circuits
• A quantum algorithm to count weighted ground states of classical spin Hamiltonians
• Iteration Complexity of Variational Quantum Algorithms
• QSlack: A slack-variable approach for variational quantum semi-definite programming
• Quantum Approximation of Normalized Schatten Norms and Applications to Learning
• Modeling stochastic eye tracking data: A comparison of quantum generative adversarial networks and Markov models
• On the learning abilities of photonic continuous-variable Born machines
• Efficient Estimation and Sequential Optimization of Cost Functions in Variational Quantum Algorithms
• The Quantum Approximate Optimization Algorithm Can Require Exponential Time to Optimize Linear Functions
• Information content of queries in training Parameterized Quantum Circuits