An Improved Approximation Algorithm for Quantum Max-Cut

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

• Robbie King, California Institute of Technology
• Thursday 10 November 2022, 16:00-17:00
• Zoom.

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: https://maths-cam-ac-uk.zoom.us/j/92731536549?pwd=SkhEQThwVFdDY0h1RUJkV2JPMWZSUT09

This talk is part of the CQIF Seminar series.

This talk is included in these lists:

• All CMS events
• CMS Events
• CQIF Seminar
• DAMTP info aggregator
• Hanchen DaDaDash
• Interested Talks
• Zoom
• Zoom: https://maths-cam-ac-uk.zoom.us/j/92731536549?pwd=SkhEQThwVFdDY0h1RUJkV2JPMWZSUT09
• bld31

Note that ex-directory lists are not shown.