Solving MaxCut with quantum imaginary time evolution

DOI10.1007/S11128-023-04045-7MaRDI QIDQ6171442zbMATH OpenOpenAlexFDO

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

Publication date 11 August 2023

Published in Quantum Information Processing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2201.12221

zbMATH Keywords

quantum computingquantum optimizationMaxCutquantum imaginary time evolution (QITE)

Mathematics Subject Classification ID

Quantum computation (81P68)

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. This metric can be improved by introducing higher-order Ansaetze and entangled initial states.

Recommendations

• A universal quantum algorithm for weighted maximum cut and Ising problems
• Faster exact solution of sparse maxcut and QUBO problems
• scientific article; zbMATH DE number 7651034
• Recursive QAOA outperforms the original QAOA for the MAX-CUT problem on complete graphs
• Impact of graph structures for QAOA on maxcut

Cites work

• scientific article; zbMATH DE number 5899272 (Why is no real title available?)
• scientific article; zbMATH DE number 5764850 (Why is no real title available?)
• .878-approximation algorithms for MAX CUT and MAX 2SAT
• Classical symmetries and the quantum approximate optimization algorithm
• From the quantum approximate optimization algorithm to a quantum alternating operator ansatz
• Lower bounds on circuit depth of the quantum approximate optimization algorithm
• Quantum approximate optimization of the long-range Ising model with a trapped-ion quantum simulator
• Randomized heuristics for the Max-Cut problem

Cited in

(1)

• A universal quantum algorithm for weighted maximum cut and Ising problems

This page was built for publication: Solving MaxCut with quantum imaginary time evolution

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6171442)