% IMPORTANT: The following is UTF-8 encoded.  This means that in the presence
% of non-ASCII characters, it will not work with BibTeX 0.99 or older.
% Instead, you should use an up-to-date BibTeX implementation like “bibtex8” or
% “biber”.

@INPROCEEDINGS{Michielsen:824916,
      author       = {Michielsen, Kristel},
      title        = {{S}olving hard 2-{SAT} problems on a {D}-{W}ave {T}wo
                      system},
      reportid     = {FZJ-2016-07417},
      year         = {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.},
      month         = {Dec},
      date          = {2016-12-05},
      organization  = {IAS Symposium 2016, Juelich (Germany),
                       5 Dec 2016 - 6 Dec 2016},
      subtyp        = {After Call},
      cin          = {JSC},
      cid          = {I:(DE-Juel1)JSC-20090406},
      pnm          = {511 - Computational Science and Mathematical Methods
                      (POF3-511)},
      pid          = {G:(DE-HGF)POF3-511},
      typ          = {PUB:(DE-HGF)6},
      url          = {https://juser.fz-juelich.de/record/824916},
}