![[Search]](/static/images/search.gif){kind=small}
![[A-Z Index]](/static/images/az.gif){kind=small}
![[Contact]](/static/images/contact.gif){kind=small}
![[University of Cambridge]](/static/images/identifier2.gif){kind=small}
![[Talks.cam]](/static/images/talkslogosmall.gif)
Robbie King, California Institute of Technology
Thursday 10 November 2022, 16:00-17:00
An Improved Approximation Algorithm for Quantum Max-Cut
- đ¤ Speaker: Robbie King, California Institute of Technology
- đ Date & Time: Thursday 10 November 2022, 16:00 - 17:00
- đ Venue: Zoom
Abstract
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
Series This talk is part of the CQIF Seminar series.
Included in Lists
- All CMS events
- bld31
- CMS Events
- CQIF Seminar
- DAMTP info aggregator
- Hanchen DaDaDash
- Interested Talks
- Zoom
- Zoom: https://maths-cam-ac-uk.zoom.us/j/92731536549?pwd=SkhEQThwVFdDY0h1RUJkV2JPMWZSUT09
Note: Ex-directory lists are not shown.