IQI Weekly Seminar

Abstract:

We describe the Quantum Alternating Operator Anzatz (QAOA), a reworking of the acronym and generalization of Farhi, Goldstone, and Gutmann Quantum Approximate Optimization Algorithm [1]. We then discuss our work demonstrating that the QAOA is powerful enough to obtain the O(\sqrt N) query complexity on Grover's problem, and inspiring a novel quantum algorithm for this problem, the first within the QAOA framework to show a quantum advantage for a number of iterations  p of the alternating operators, in the intermediate range between p = 1 and p < 1 [2]; a novel temporal planning approach for compiling QAOA circuits to realistic hardware[3]; an analysis of the parameter landscape for the simple problem of MaxCut on a ring [4]; and a framework for designing QAOA circuits for a variety of optimization problems with both soft and hard constraints, including examples for a variety of challenging combinatorial optimization problems [5]. We conclude with a discussion of future research directions.

[1] A Quantum Approximate Optimization Algorithm.

    Edward Farhi, Jeffrey Goldstone, and Sam Gutmann.

    arXiv:1411.4028

[2] Near-optimal quantum circuit for Grover's unstructured search using a transverse field

    Zhang Jiang, Eleanor G. Rieffel, Zhihui Wang, Phys. Rev. A 95, 062317 (2017)

    arXiv:1702.02577

[3] Compiling Quantum Circuits to Realistic Hardware Architectures using Temporal Planners

    Davide Venturelli, Minh Do, Eleanor Rieffel, Jeremy Frank, Proceedings of IJCAI 2017, and ICAPS SPARK Workshop 2017

    arXiv:1705.08927

[4] The Quantum Approximation Optimization Algorithm for MaxCut: A Fermionic View

    Zhihui Wang, Stuart Hadfield, Zhang Jiang, Eleanor G. Rieffel,

    arXiv:1706.02998

[5] Quantum approximate optimization with hard and soft constraints.

    Stuart Hadfield, ZhihuiWang, Eleanor Rieffel, Bryan O'Gorman, Davide Venturelli, Rupak Biswas.

    In preparation.