On the universality of the quantum approximate optimization algorithm

M. E.S. Morales, J. D. Biamonte, Z. Zimborás

Research output: Contribution to journalArticlepeer-review

28 Citations (Scopus)


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.

Original languageEnglish
Article number291
JournalQuantum Information Processing
Issue number9
Publication statusPublished - 1 Aug 2020


  • Quantum computation
  • Quantum control
  • Universal quantum gate sets
  • Variational quantum algorithms


Dive into the research topics of 'On the universality of the quantum approximate optimization algorithm'. Together they form a unique fingerprint.

Cite this