University of Cambridge > > CQIF Seminar > An Improved Approximation Algorithm for Quantum Max-Cut

An Improved Approximation Algorithm for Quantum Max-Cut

Add to your list(s) Download to your calendar using vCal

  • UserRobbie King, California Institute of Technology
  • ClockThursday 10 November 2022, 16:00-17:00
  • HouseZoom.

If you have a question about this talk, please contact Sergii Strelchuk.

We give an approximation algorithm for Quantum Max-Cut which works by rounding an SDP relaxation to an entangled quantum state. The SDP is used to choose the parameters of a variational quantum circuit. The entangled state is then represented as the quantum circuit applied to a product state. It achieves an approximation ratio of 0.582, significantly improving on the algorithms of Anshu, Gosset, Morenz, 0.531, and Parekh, Thompson, 0.533. In addition, we also study the EPR Hamiltonian, which we argue is a natural intermediate problem which isolates some key quantum features of local Hamiltonian problems. For the EPR Hamiltonian, we give an approximation algorithm with approximation ratio 1/sqrt(2).

Zoom link:

This talk is part of the CQIF Seminar series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


© 2006-2023, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity