000824916 001__ 824916
000824916 005__ 20210129225143.0
000824916 037__ $$aFZJ-2016-07417
000824916 1001_ $$0P:(DE-Juel1)138295$$aMichielsen, Kristel$$b0$$eCorresponding author$$ufzj
000824916 1112_ $$aIAS Symposium 2016$$cJuelich$$d2016-12-05 - 2016-12-06$$wGermany
000824916 245__ $$aSolving hard 2-SAT problems on a D-Wave Two system
000824916 260__ $$c2016
000824916 3367_ $$033$$2EndNote$$aConference Paper
000824916 3367_ $$2DataCite$$aOther
000824916 3367_ $$2BibTeX$$aINPROCEEDINGS
000824916 3367_ $$2DRIVER$$aconferenceObject
000824916 3367_ $$2ORCID$$aLECTURE_SPEECH
000824916 3367_ $$0PUB:(DE-HGF)6$$2PUB:(DE-HGF)$$aConference Presentation$$bconf$$mconf$$s1481807464_2006$$xAfter Call
000824916 520__ $$aSolving 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.
000824916 536__ $$0G:(DE-HGF)POF3-511$$a511 - Computational Science and Mathematical Methods (POF3-511)$$cPOF3-511$$fPOF III$$x0
000824916 909CO $$ooai:juser.fz-juelich.de:824916$$pVDB
000824916 9101_ $$0I:(DE-588b)5008462-8$$6P:(DE-Juel1)138295$$aForschungszentrum Jülich$$b0$$kFZJ
000824916 9131_ $$0G:(DE-HGF)POF3-511$$1G:(DE-HGF)POF3-510$$2G:(DE-HGF)POF3-500$$3G:(DE-HGF)POF3$$4G:(DE-HGF)POF$$aDE-HGF$$bKey Technologies$$lSupercomputing & Big Data$$vComputational Science and Mathematical Methods$$x0
000824916 9141_ $$y2016
000824916 915__ $$0StatID:(DE-HGF)0550$$2StatID$$aNo Authors Fulltext
000824916 9201_ $$0I:(DE-Juel1)JSC-20090406$$kJSC$$lJülich Supercomputing Center$$x0
000824916 980__ $$aconf
000824916 980__ $$aVDB
000824916 980__ $$aUNRESTRICTED
000824916 980__ $$aI:(DE-Juel1)JSC-20090406