Student AIM Seminar Seminar

This talk introduces NP-hard problems, some of their properties, and their formulation as an Ising or QUBO (quadratic unconstrained binary optimization) problem needed to implement them on the so-called D-Wave annealer, an emerging (maybe quantum or maybe not) technology to solve such problems. The talk presents a short study on the performance of D-Wave for a classical NP-complete problem (where the comparison was with respect to classical solvers).

This presentation is actually part of a series of 5 talks on NP-complete problems and D-Wave. The following two talks will focus again on a technical aspect -- What to do when the problems we want to solve do not fit onto the limited connectivity structure of around 2000 qubits offered by the device? As a solution, we look at how to divide up an NP-complete problem into two parts in such a way that (a) both parts are strictly smaller than the original input problem, and (b) solving both smaller problems to optimality allows us to construct the optimal solution of the full problem in polynomial time. Recursively applying such a method allows us to divide up an NP-complete problem until any desired size is reached, in particular until we can implement it on the D-Wave machine. The third talk is on how to peer into the annealing process of D-Wave with the aim to observe how a solution evolves during annealing. The fourth talk is theoretical again, though it focuses on a very practical problem: Suppose we get a good D-Wave solution, can we quantify how good it is? That is, how far away is it from optimality? That is a hard question, though it is possible to bound the distance of any D-Wave solution from the optimal one, which can be used as a measure of accuracy. Speaker(s): Georg Hahn (Harvard University)