Solving MaxCut with quantum imaginary time evolution

Rizwanul Alam; George Siopsis; Rebekah Herrman; James Ostrowski; Phillip C. Lotshaw; Travis S. Humble

doi:10.1007/s11128-023-04045-7

Solving MaxCut with quantum imaginary time evolution

Rizwanul Alam, George Siopsis, Rebekah Herrman, James Ostrowski, Phillip C. Lotshaw, Travis S. Humble

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

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. Our results compare favorably with the performance of classical algorithms, such as the greedy and Goemans–Williamson algorithms. We also discuss the overlap of the final state of the QITE algorithm with the ground state as a performance metric, which is a quantum feature not shared by other classical algorithms.

Original language	English
Article number	281
Journal	Quantum Information Processing
Volume	22
Issue number	7
DOIs	https://doi.org/10.1007/s11128-023-04045-7
State	Published - Jul 2023

Funding

This work was supported by the DARPA ONISQ program under award W911NF-20-2-0051. J. Ostrowski acknowledges the Air Force Office of Scientific Research award, AF-FA9550-19-1-0147. G. Siopsis acknowledges the Army Research Office award W911NF-19-1-0397 and the National Science Foundation award DGE-2152168. J. Ostrowski and G. Siopsis acknowledge the National Science Foundation award OMA-1937008. This manuscript has been authored by UT-Battelle, LLC under Contract No. DE-AC05-00OR22725 with the U.S. Department of Energy. The United States Government retains and the publisher, by accepting the article for publication, acknowledges that the United States Government retains a non-exclusive, paid-up, irrevocable, world-wide license to publish or reproduce the published form of this manuscript, or allow others to do so, for United States Government purposes.

Keywords

MaxCut
Quantum computing
Quantum imaginary time evolution (QITE)
Quantum optimization

Access to Document

10.1007/s11128-023-04045-7

Cite this

@article{900c63715b5143de947adcfce57d1b50,

title = "Solving MaxCut with quantum imaginary time evolution",

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. Our results compare favorably with the performance of classical algorithms, such as the greedy and Goemans–Williamson algorithms. We also discuss the overlap of the final state of the QITE algorithm with the ground state as a performance metric, which is a quantum feature not shared by other classical algorithms.",

keywords = "MaxCut, Quantum computing, Quantum imaginary time evolution (QITE), Quantum optimization",

author = "Rizwanul Alam and George Siopsis and Rebekah Herrman and James Ostrowski and Lotshaw, \{Phillip C.\} and Humble, \{Travis S.\}",

note = "Publisher Copyright: {\textcopyright} 2023, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.",

year = "2023",

month = jul,

doi = "10.1007/s11128-023-04045-7",

language = "English",

volume = "22",

journal = "Quantum Information Processing",

issn = "1570-0755",

publisher = "Springer",

number = "7",

}

TY - JOUR

T1 - Solving MaxCut with quantum imaginary time evolution

AU - Alam, Rizwanul

AU - Siopsis, George

AU - Herrman, Rebekah

AU - Ostrowski, James

AU - Lotshaw, Phillip C.

AU - Humble, Travis S.

PY - 2023/7

Y1 - 2023/7

N2 - 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. Our results compare favorably with the performance of classical algorithms, such as the greedy and Goemans–Williamson algorithms. We also discuss the overlap of the final state of the QITE algorithm with the ground state as a performance metric, which is a quantum feature not shared by other classical algorithms.

AB - 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. Our results compare favorably with the performance of classical algorithms, such as the greedy and Goemans–Williamson algorithms. We also discuss the overlap of the final state of the QITE algorithm with the ground state as a performance metric, which is a quantum feature not shared by other classical algorithms.

KW - MaxCut

KW - Quantum computing

KW - Quantum imaginary time evolution (QITE)

KW - Quantum optimization

UR - https://www.scopus.com/pages/publications/85165220194

U2 - 10.1007/s11128-023-04045-7

DO - 10.1007/s11128-023-04045-7

M3 - Article

AN - SCOPUS:85165220194

SN - 1570-0755

VL - 22

JO - Quantum Information Processing

JF - Quantum Information Processing

IS - 7

M1 - 281

ER -

Solving MaxCut with quantum imaginary time evolution

Abstract

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this