Quantum approximate optimization is computationally universal

Understand

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.