Adiabatic Quantum Computing

We use statistical methods in the Euclidean time formulation as well as real time problem solvers to find the solution of NP-complete problems. In the figure below we display a free energy landscape as a function of physical parameters for a particular problem realization in 3-SAT. If interpreted correctly the presented data allow a classification of the complexity of the particular problem.

Satisfiability (SAT) problems involve determining whether a given Boolean expression has a satisfying truth assignment. In the case of 3-SAT the Boolean expression is a conjunction of clauses C1 AND C2 AND ... AND Cm where each clause Cj , j = 1, ..., m is a disjunction of three literals l1 OR l2 OR l3. A literal is either a variable xi or its negation -xi, where i = 1, ..., n.

Read more:

T. Neuhaus, M. Peschina, K. Michielsen, and H. De Raedt, Classical and quantum annealing in the median of three-satisfiability, Phys. Rev. A 83, 012309 (2011), DOI:10.1103/PhysRevA.83.012309