guest ::
| Home > Publications database > Solving hard 2-SAT problems on a D-Wave Two system |
| Home > Publications database > Solving hard 2-SAT problems on a D-Wave Two system |
| Conference Presentation (After Call) | FZJ-2016-07417 |
2016
Abstract: Solving a 2-satisfiability (2-SAT) problem amounts to finding whether a collection of two-valued variableswith constraints on pairs of variables can be assigned values satisfying all the constraints. 2-SAT problemscan be solved in polynomial time, in contrast to the general k-SAT problems which are NP-complete. Weconsider computationally hard 2-SAT problems with a unique satisfying assignment, that is with a uniqueground state [1]. Other characteristics of these hard 2-SAT problems are that the energy gap between theground state and the first-excited state is small and that they have a highly degenerate first-excited state.The first makes it hard to solve the problem by quantum annealing as can be seen from the Landau-Zenertransition formula and the latter makes a classical search in terms of simulated annealing hard as thechance of getting trapped in a local minimum is high.We study 2-SAT problems with 8, 12 and 18 variables (or Ising spins in the physics language). For theseproblems we numerically calculate the exact value of the gap between the ground state and the first-excitedstates which gives information about the computational complexity for solving the problems with quantumannealing.We report about a comparison of the frequencies for finding the ground state, as obtained with theD-Wave Two and a digital computer emulating the dynamics of an ideal adiabatic quantum computer bysolving the time-dependent Schrödinger equation for a system of interacting, localized spin-1/2 particles atzero temperature. Our analysis indicates that the D-Wave Two processor does not perform “ideal” quantumannealing and that more research is necessary to investigate the effects of e.g. temperature, imperfectionsetc.
|
The record appears in these collections: |