On the Universality of the Quantum Approximate Optimization Algorithm

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 [S. Lloyd, arXiv:1812.11075] argued that for one-dimensional local cost Hamiltonians, composed of nearest neighbor ZZ terms, this set-up is quantum computationally universal, i.e., all unitaries can be reached up to arbitrary precision. In the present paper, we give the complete proof of this statement and the precise conditions under which such a one-dimensional QAOA might be considered universal. We further generalize this type of universality for certain cost Hamiltonians with ZZ and ZZZ terms arranged according to the adjacency structure of certain graphs and hypergraphs.

arXiv comment18+6 pages, 3 figures

References in corpus (22)

• A variational eigenvalue solver on a quantum processor
• Barren plateaus in quantum neural network training landscapes
• The theory of variational hybrid quantum-classical algorithms
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• Quantum Approximate Optimization Algorithm for MaxCut: A Fermionic View
• Optimizing Variational Quantum Algorithms using Pontryagin's Minimum Principle
• Reachability Deficits in Quantum Approximate Optimization
• Efficient variational simulation of non-trivial quantum states
• Scalable quantum computation via local control of only two qubits
• Local controllability of quantum networks
• Symmetry Principles in Quantum Systems Theory
• Fundamentals of universality in one-way quantum computation
• Zero forcing, linear and quantum controllability for systems evolving on networks
• A quantum walk assisted approximate algorithm for bounded NP optimisation problems
• Clifford algebras and universal sets of quantum gates
• Symmetry criteria for quantum simulability of effective interactions
• Logic circuits from zero forcing
• A Dynamic Systems Approach to Fermions and Their Relation to Spins
• Ultrafast Variational Simulation of Non-trivial Quantum States with Long Range Interactions
• Universal extensions of restricted classes of quantum operations
• Criteria for universality of quantum gates
• Fungible dynamics: there are only two types of entangling multiple-qubit interactions

Cited by in corpus (57)

• Variational Quantum Algorithms
• General parameter-shift rules for quantum gradients
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• Avoiding local minima in variational quantum eigensolvers with the natural gradient optimizer
• Parameter Concentration in Quantum Approximate Optimization
• From pulses to circuits and back again: A quantum optimal control perspective on variational quantum algorithms
• Universal Variational Quantum Computation
• Error mitigation for variational quantum algorithms through mid-circuit measurements
• Speeding up Learning Quantum States through Group Equivariant Convolutional Quantum Ansätze
• Noise-Resilient Variational Hybrid Quantum-Classical Optimization
• Training Saturation in Layerwise Quantum Approximate Optimisation
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach
• Abrupt Transitions in Variational Quantum Circuit Training
• Quantum optimization via four-body Rydberg gates
• Modeling and mitigation of cross-talk effects in readout noise with applications to the Quantum Approximate Optimization Algorithm
• NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems
• Quantum Architecture Search with Meta-learning
• Lyapunov control-inspired strategies for quantum combinatorial optimization
• Two-dimensional ${\mathbb{Z}}_2$ lattice gauge theory on a near-term quantum simulator: variational quantum optimization, confinement, and topological order
• Variational Quantum Classifiers Through the Lens of the Hessian
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Entanglement entropy production in Quantum Neural Networks
• Analytical Framework for Quantum Alternating Operator Ansätze
• Reachability Deficits in Quantum Approximate Optimization of Graph Problems
• On Circuit Depth Scaling For Quantum Approximate Optimization
• Shortcuts to Quantum Approximate Optimization Algorithm
• Variational Simulation of Schwinger's Hamiltonian with Polarisation Qubits
• Quantum Optimization for Training Quantum Neural Networks
• Mitigated barren plateaus in the time-nonlocal optimization of analog quantum-algorithm protocols
• Convergence of Digitized-Counterdiabatic QAOA: circuit depth versus free parameters
• Robustness of Variational Quantum Algorithms against stochastic parameter perturbation
• Progress towards analytically optimal angles in quantum approximate optimisation
• Characterization of variational quantum algorithms using free fermions
• Emergence of noise-induced barren plateaus in arbitrary layered noise models
• Problem-Size Independent Angles for a Grover-Driven Quantum Approximate Optimization Algorithm
• Implementing Jastrow--Gutzwiller operators on a quantum computer using the cascaded variational quantum eigensolver algorithm
• Ion native variational ansatz for quantum approximate optimization
• Analyzing the quantum approximate optimization algorithm: ansätze, symmetries, and Lie algebras
• A variational quantum algorithm for tackling multi-dimensional Poisson equations with inhomogeneous boundary conditions
• Mitigating Quantum Gate Errors for Variational Eigensolvers Using Hardware-Inspired Zero-Noise Extrapolation
• Efficient Quantum Circuits based on the Quantum Natural Gradient
• Trade-off between Gradient Measurement Efficiency and Expressivity in Deep Quantum Neural Networks
• Hamiltonian Switching Control of Noisy Bipartite Qubit Systems
• Deep-Circuit QAOA
• Evaluating the Practicality of Quantum Optimization Algorithms for Prototypical Industrial Applications
• Depth scaling of unstructured search via quantum approximate optimization
• Out of the Loop: Structural Approximation of Optimisation Landscapes and non-Iterative Quantum Optimisation
• Policy Gradient Approach to Compilation of Variational Quantum Circuits
• Path Matters: Industrial Data Meet Quantum Optimization
• On the Differential Topology of Expressivity of Parameterized Quantum Circuits
• Expressiveness of Commutative Quantum Circuits: A Probabilistic Approach
• Computational Phase Transitions: Benchmarking Ising Machines and Quantum Optimisers
• Low overhead universality and quantum supremacy using only $Z$-control
• Performance Guarantees for Quantum Neural Estimation of Entropies
• Role of overparametrization in quantum approximate optimization
• Quantum Alternating Operator Ansatz for the Preparation and Detection of Long-Lived Singlet States in NMR
• Probabilistic Representation of Commutative Quantum Circuit Models