Solving MAXCUT with Quantum Imaginary Time Evolution

ORAL

Abstract

We introduce a method to solve the MaxCut problem efficiently based on quantum imaginary time evolution (QITE). We employ a linear Ansatz for unitary updates and an initial state involving no entanglement, as well as an imaginary-time-dependent Hamiltonian interpolating between a given graph and a subgraph with two edges excised. We apply the method to thousands of randomly selected graphs with up to fifty vertices. We show that our algorithm exhibits a 93% and above performance converging to the maximum solution of the MaxCut problem for all considered graphs, to be compared with the worst-case 87.8% performance of the Goemans-Williamson algorithm.

*This work was supported by DARPA ONISQ program under award W911NF-20-2-0051; Air Force Office of Scientific Research award, AF-FA9550-19-1-0147; the Army ResearchOffice award W911NF-19-1-039; the National Science Foundation grant DGE-2152168.

–

Publication: R. Alam, G. Siopsis, R. Herrman, J. Ostrowski, P. Lotshaw, T. Humble, Solving MaxCut with Quantum Imaginary Time Evolution, in preparation, arXiv:2201.12221

Presenters

  • Rizwanul Alam

    • University of Tennessee

Authors

  • Rizwanul Alam

    • University of Tennessee

  • George Siopsis

    • University of Tennessee

  • Rebekah Herrman

    • University of Tennessee

  • James Ostrowski

    • University of Tennessee
    • University of Tennessee, Knoxville

  • Phillip C Lotshaw

    • Oak Ridge National Lab

  • Travis S Humble

    • Oak Ridge National Lab
    • Oak Ridge National Laboratory