Quantum approximate optimization is computationally universal

Abstract

The quantum approximate optimization algorithm (QAOA) applies two Hamiltonians to a quantum system in alternation. The original goal of the algorithm was to drive the system close to the ground state of one of the Hamiltonians. This paper shows that the same alternating procedure can be used to perform universal quantum computation: the times for which the Hamiltonians are applied can be programmed to give a computationally universal dynamics. The Hamiltonians required can be as simple as homogeneous sums of single-qubit Pauli X's and two-local ZZ Hamiltonians on a one-dimensional line of qubits.

6 pages, plain TeX

References in corpus (5)

• Dynamical Decoupling of Open Quantum Systems
• Dynamical suppression of decoherence in two-state quantum systems
• Quantum Supremacy through the Quantum Approximate Optimization Algorithm
• A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem
• Schemes for Parallel Quantum Computation Without Local Control of Qubits

Cited by in corpus (41)

• Noisy intermediate-scale quantum (NISQ) algorithms
• From the Quantum Approximate Optimization Algorithm to a Quantum Alternating Operator Ansatz
• General parameter-shift rules for quantum gradients
• Quantum Approximate Optimization of the Long-Range Ising Model with a Trapped-Ion Quantum Simulator
• Diagnosing Barren Plateaus with Tools from Quantum Optimal Control
• Variational Quantum Linear Solver
• Large gradients via correlation in random parameterized quantum circuits
• Optimal Protocols in Quantum Annealing and QAOA Problems
• Parameter Concentration in Quantum Approximate Optimization
• Universal Variational Quantum Computation
• Learning quantum data with the quantum Earth Mover's distance
• Error mitigation for variational quantum algorithms through mid-circuit measurements
• 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
• Quantum Embedding Search for Quantum Machine Learning
• Prospects and challenges of quantum finance
• NP-hard but no longer hard to solve? Using quantum computing to tackle optimization problems
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation
• Learning Unitaries by Gradient Descent
• Parameters Fixing Strategy for Quantum Approximate Optimization Algorithm
• Policy Gradient based Quantum Approximate Optimization Algorithm
• End-to-End Quantum Machine Learning Implemented with Controlled Quantum Dynamics
• Performance and limitations of the QAOA at constant levels on large sparse hypergraphs and spin glass models
• Analytical Framework for Quantum Alternating Operator Ansätze
• Networked Quantum Services
• Optimizing QAOA: Success Probability and Runtime Dependence on Circuit Depth
• Progress towards analytically optimal angles in quantum approximate optimisation
• Emergence of noise-induced barren plateaus in arbitrary layered noise models
• Robust Control Optimization for Quantum Approximate Optimization Algorithm
• The dilemma of quantum neural networks
• Space-efficient binary optimization for variational computing
• Experimental pairwise entanglement estimation for an N-qubit system :A machine learning approach for programming quantum hardware
• Trade-off between Gradient Measurement Efficiency and Expressivity in Deep Quantum Neural Networks
• Robust universal Hamiltonian quantum computing using two-body interactions
• Hamiltonian Switching Control of Noisy Bipartite Qubit Systems
• Policy Gradient Approach to Compilation of Variational Quantum Circuits
• Hamiltonian singular value transformation and inverse block encoding
• Low overhead universality and quantum supremacy using only $Z$-control
• Quantum Alternating Operator Ansatz for the Preparation and Detection of Long-Lived Singlet States in NMR
• An upper bound on the Universality of the Quantum Approximate Optimization Algorithm