AQC 2016 - Max-k-SAT, Multi-Body Frustration, & Multi-Body Sampling on a Two Local Ising System
4A Google TechTalk, June 29, 2016, presented by Nicholas Chancellor (Durham University)
ABSTRACT: For some time it has been known how to encode satisfiability (SAT) problems and the physics analogue of finding the ground state of a frustrated spin system onto a two local Ising spin model. These previous constructions however do not necessarily yield the statement which satisfies the maximum number of clauses as the ground state (max-SAT), in the language of physics, they did not support frustration of the multi-body terms. Furthermore, the inability to accurately describe frustration means that these methods cannot be used for thermal sampling.
We propose a new method of encoding problems which does support max-SAT, frustration, and sampling. I will describe this method in detail, and show how a recent coupling proposal by a different group for unfrustrated Ising couplings is also compatible with frustration and can be made compatible with sampling applications. I will than discuss applications of our method including, direct embedding of max-SAT problems on a chimera graph, optimization with non-linear constraints, and particle simulation.
Stefan Zohren, Oxford University, Paul Warburton, UCL, Simon Benjamin, Oxford University, Stephen Roberts, Oxford University
Presented at the Adiabatic Quantum Computing Conference, June 26-29, 2016, at Google's Los Angeles office.