Source-linked AI summary
Quantum approximate optimization is computationally universal
Seth Lloyd
TL;DR
The paper asks whether QAOA’s alternating Hamiltonian dynamics can perform more than ground-state preparation. It shows that programmed Hamiltonian application times yield computationally universal dynamics, including on one-dimensional qubit architectures with simple interactions.
Problem
QAOA was originally intended to drive a quantum system close to a Hamiltonian ground state, leaving its computational universality as the central question.
Method
The paper uses alternating QAOA Hamiltonians with programmable application times to implement a computationally universal broadcast quantum cellular automaton.
Results
QAOA dynamics are computationally universal, including with fixed-Z IQP dynamics and simple one-dimensional nearest-neighbor architectures.
Takeaways & Limitations
QAOA provides a framework for universal quantum computation and may support near-term quantum information-processing devices.
Takeaways & Limitations
The paper leaves architectural questions about one-dimensional nearest-neighbor systems and the number of wire or interaction types required for universal computation.
Abstract
from arXiv · showhide
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.