On the universality of the quantum approximate optimization algorithm
- PDF / 558,338 Bytes
- 26 Pages / 439.37 x 666.142 pts Page_size
- 78 Downloads / 197 Views
On the universality of the quantum approximate optimization algorithm M. E. S. Morales1 · J. D. Biamonte1 · Z. Zimborás2,3,4 Received: 20 September 2019 / Accepted: 4 July 2020 © The Author(s) 2020
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 (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.
B
Z. Zimborás [email protected] M. E. S. Morales [email protected] http://quantum.skoltech.ru J. D. Biamonte [email protected] http://quantum.skoltech.ru
1
Deep Quantum Laboratory, Skolkovo Institute of Science and Technology, 3 Nobel Street, Moscow, Russia 121205
2
Wigner Research Centre for Physics of the Hungarian Academy of Sciences, Budapest, Hungary
3
MTA-BME Lendület Quantum Information Theory Research Group, Budapest, Hungary
4
Mathematical Institute, Budapest University of Technology and Economics, Budapest, Hungary 0123456789().: V,-vol
123
291
Page 2 of 26
M. E. S. Morales et al.
Keywords Quantum computation · Variational quantum algorithms · Universal quantum gate sets · Quantum control
1 Introduction A question in the field of quantum information processing is whether contemporary quantum processors will in the near future be able to solve problems more efficiently than classical computers. Combinatorial optimization problems are of special interest, for which a class of algorithms under the name of quantum approximate optimization algorithm (QAOA) have been proposed [1]. QAOA consists of a bang-bang protocol [2] that is expected to solve hard problems approximately. This procedure involves the unitary evolution under a Hamiltonian encoding the objective function of the combinatorial optimization problem and a second non-commuting mixer Hamiltonian. Since its proposal, QAOA has been extensively studied to understand its performance [3–5], for establishing quantum supremacy results [6] and for solving several optimization problems [7–9]. This algorithm together with others such
Data Loading...
