Summer 2018

The Short-path Algorithm for Combinatorial Optimization

Thursday, Jun. 14, 2018 9:15 am9:45 am

Add to Calendar

I will discuss a quantum algorithm for exact combinatorial optimization.  This algorithm has a provable super-Grover speedup for MAX-D-LIN-2 (for D=2, this is the Ising model) under some mild assumptions on the density of states of the given instance.  The talk is based on arXiv:1802.10124 as well as some additional unpublished results generalizing the results in that paper.