link to homepage

Institute for Advanced Simulation (IAS)

Navigation and service

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:

  1. 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)