On the universality of the quantum approximate optimization algorithm
Open Access
- 24 August 2020
- journal article
- research article
- Published by Springer Nature in Quantum Information Processing
- Vol. 19 (9) , 1-26
Abstract
The quantum approximate optimization algorithm (QAOA) is considered to be one of the most promising approaches towards using near-term quantum computers for practical application. In its original form, the algorithm applies two different Hamiltonians, called the mixer and the cost Hamiltonian, in alternation with the goal being to approach the ground state of the cost Hamiltonian. Recently, it has been suggested that one might use such a set-up as a parametric quantum circuit with possibly some other goal than reaching ground states. From this perspective, a recent work (Lloyd, arXiv:1812.11075) argued that for one-dimensional local cost Hamiltonians, composed of nearest neighbour ZZ terms, this set-up is quantum computationally universal and provides a universal gate set, i.e. all unitaries can be reached up to arbitrary precision. In the present paper, we complement this work by giving a complete proof and the precise conditions under which such a one-dimensional QAOA might produce a universal gate set. We further generalize this type of gate-set universality for certain cost Hamiltonians with ZZ and ZZZ terms arranged according to the adjacency structure of certain graphs and hypergraphs.Keywords
Funding Information
- Hungarian Scientific Research Fund (K124351)
This publication has 31 references indexed in Scilit:
- Classical and quantum bounded depth approximation algorithmsQuantum Information & Computation, 2019
- From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator AnsatzAlgorithms, 2019
- A quantum walk-assisted approximate algorithm for bounded NP optimisation problemsQuantum Information Processing, 2019
- Barren plateaus in quantum neural network training landscapesNature Communications, 2018
- Optimizing Variational Quantum Algorithms Using Pontryagin’s Minimum PrinciplePhysical Review X, 2017
- The theory of variational hybrid quantum-classical algorithmsNew Journal of Physics, 2016
- A variational eigenvalue solver on a photonic quantum processorNature Communications, 2014
- Quantum Computation and Quantum Information2012
- Classical and Quantum Computation2002
- Control systems on Lie groupsJournal of Differential Equations, 1972