Southwest Quantum Information and Technology

Quantum approximate optimization algorithm on a one-dimensional model

Presenting Author: Zhihui Wang, NASA Ames Research Center (QuAIL)
Contributing Author(s): Zhang Jiang, Stuart Hadfield, and Eleanor Rieffel

A recently proposed class of quantum algorithm, the Quantum Approximate Optimization Algorithm (QAOA), holds great potential in tackling challenging combinatorial optimization problems on a gate model quantum computer. In QAOA, the problem Hamiltonian and a non-commuting driving Hamiltonian are applied alternatively. With an optimized time sequence for each piece, the optimal output of the problem Hamiltonian is approximated. We study QAOA on the model of a ring of disagreement. We provide analysis of QAOA for any level. Through transformation to the Fermionic representation, the evolution of the system under QAOA translates into quantum optimal control of a noisy spin ensemble. We show that the optimal controls lie within a defined subspace as a result of the symmetry in the system and hence the search effort can be focused on a lower-dimensional space. A well-known result of quantum control is that the control landscape admits only global optima. That result relies on the controllability of the system, i.e., given time, the set of provided controls can drive the system between any two states. In QAOA, however, at a finite level, the structure of the controls is constrained and does not guarantee full control over the system. We show that, nevertheless, the search space is still trap-free. While this is a study of a simple model, it may reveal underlying structure of the algorithm and inspire more efficient variants of QAOA.

(Session 5 : Thursday from 5:00pm - 7:00pm)