000014076 001__ 14076
000014076 005__ 20230217124408.0
000014076 0247_ $$2DOI$$a10.1103/PhysRevA.83.012309
000014076 0247_ $$2WOS$$aWOS:000286738100007
000014076 0247_ $$2Handle$$a2128/11169
000014076 037__ $$aPreJuSER-14076
000014076 041__ $$aeng
000014076 082__ $$a530
000014076 084__ $$2WoS$$aOptics
000014076 084__ $$2WoS$$aPhysics, Atomic, Molecular & Chemical
000014076 1001_ $$0P:(DE-Juel1)132210$$aNeuhaus, T.$$b0$$uFZJ
000014076 245__ $$aClassical and quantum annealing in the median of three-satisfiability
000014076 260__ $$aCollege Park, Md.$$bAPS$$c2011
000014076 264_1 $$2Crossref$$3online$$bAmerican Physical Society (APS)$$c2011-01-18
000014076 264_1 $$2Crossref$$3print$$bAmerican Physical Society (APS)$$c2011-01-01
000014076 300__ $$a012309
000014076 3367_ $$0PUB:(DE-HGF)16$$2PUB:(DE-HGF)$$aJournal Article
000014076 3367_ $$2DataCite$$aOutput Types/Journal article
000014076 3367_ $$00$$2EndNote$$aJournal Article
000014076 3367_ $$2BibTeX$$aARTICLE
000014076 3367_ $$2ORCID$$aJOURNAL_ARTICLE
000014076 3367_ $$2DRIVER$$aarticle
000014076 440_0 $$04918$$aPhysical Review A$$v83$$x0556-2791$$y1
000014076 500__ $$aT.N. thanks the Theory Department at Bielefeld University for extended hospitality. Calculations were performed on the JUMP and JUROPA supercomputers at JSC and on the NICOLE workstation cluster of NIC (VSR Grant No. JJSC02). This work is partially supported by NCF, the Netherlands.
000014076 520__ $$aWe determine the classical and quantum complexities of a specific ensemble of three-satisfiability problems with a unique satisfying assignment for up to N = 100 and 80 variables, respectively. In the classical limit, we employ generalized ensemble techniques and measure the time that a Markovian Monte Carlo process spends in searching classical ground states. In the quantum limit, we determine the maximum finite correlation length along a quantum adiabatic trajectory determined by the linear sweep of the adiabatic control parameter in the Hamiltonian composed of the problem Hamiltonian and the constant transverse field Hamiltonian. In the median of our ensemble, both complexities diverge exponentially with the number of variables. Hence, standard, conventional adiabatic quantum computation fails to reduce the computational complexity to polynomial. Moreover, the growth-rate constant in the quantum limit is 3.8 times as large as the one in the classical limit, making classical fluctuations more beneficial than quantum fluctuations in ground-state searches.
000014076 536__ $$0G:(DE-Juel1)FUEK411$$2G:(DE-HGF)$$aScientific Computing (FUEK411)$$cFUEK411$$x0
000014076 536__ $$0G:(DE-HGF)POF2-411$$a411 - Computational Science and Mathematical Methods (POF2-411)$$cPOF2-411$$fPOF II$$x1
000014076 542__ $$2Crossref$$i2011-01-18$$uhttp://link.aps.org/licenses/aps-default-license
000014076 588__ $$aDataset connected to Web of Science
000014076 650_7 $$2WoSType$$aJ
000014076 7001_ $$0P:(DE-Juel1)VDB96938$$aPeschina, M.$$b1$$uFZJ
000014076 7001_ $$0P:(DE-Juel1)138295$$aMichielsen, K.$$b2$$uFZJ
000014076 7001_ $$0P:(DE-HGF)0$$aDe Raedt, H.$$b3
000014076 77318 $$2Crossref$$3journal-article$$a10.1103/physreva.83.012309$$bAmerican Physical Society (APS)$$d2011-01-18$$n1$$p012309$$tPhysical Review A$$v83$$x1050-2947$$y2011
000014076 773__ $$0PERI:(DE-600)2844156-4$$a10.1103/PhysRevA.83.012309$$gVol. 83, p. 012309$$n1$$p012309$$q83<012309$$tPhysical review / A$$v83$$x1050-2947$$y2011
000014076 8567_ $$uhttp://dx.doi.org/10.1103/PhysRevA.83.012309
000014076 8564_ $$uhttps://juser.fz-juelich.de/record/14076/files/PhysRevA.83.012309.pdf$$yOpenAccess
000014076 8564_ $$uhttps://juser.fz-juelich.de/record/14076/files/PhysRevA.83.012309.gif?subformat=icon$$xicon$$yOpenAccess
000014076 8564_ $$uhttps://juser.fz-juelich.de/record/14076/files/PhysRevA.83.012309.jpg?subformat=icon-180$$xicon-180$$yOpenAccess
000014076 8564_ $$uhttps://juser.fz-juelich.de/record/14076/files/PhysRevA.83.012309.jpg?subformat=icon-700$$xicon-700$$yOpenAccess
000014076 909CO $$ooai:juser.fz-juelich.de:14076$$pdnbdelivery$$pVDB$$pdriver$$popen_access$$popenaire
000014076 9141_ $$y2011
000014076 915__ $$0LIC:(DE-HGF)APS-112012$$2HGFVOC$$aAmerican Physical Society Transfer of Copyright Agreement
000014076 915__ $$0StatID:(DE-HGF)0510$$2StatID$$aOpenAccess
000014076 915__ $$0StatID:(DE-HGF)0010$$aJCR/ISI refereed
000014076 9132_ $$0G:(DE-HGF)POF3-511$$1G:(DE-HGF)POF3-510$$2G:(DE-HGF)POF3-500$$aDE-HGF$$bKey Technologies$$lSupercomputing & Big Data$$vComputational Science and Mathematical Methods$$x0
000014076 9131_ $$0G:(DE-HGF)POF2-411$$1G:(DE-HGF)POF2-410$$2G:(DE-HGF)POF2-400$$3G:(DE-HGF)POF2$$4G:(DE-HGF)POF$$aDE-HGF$$bSchlüsseltechnologien$$lSupercomputing$$vComputational Science and Mathematical Methods$$x2
000014076 9201_ $$0I:(DE-Juel1)JSC-20090406$$gJSC$$kJSC$$lJülich Supercomputing Centre$$x0
000014076 970__ $$aVDB:(DE-Juel1)125929
000014076 980__ $$aVDB
000014076 980__ $$aConvertedRecord
000014076 980__ $$ajournal
000014076 980__ $$aI:(DE-Juel1)JSC-20090406
000014076 980__ $$aUNRESTRICTED
000014076 9801_ $$aFullTexts
000014076 999C5 $$1S. A. Cook$$2Crossref$$oS. A. Cook Proceedings of the Third Annual ACM Symposium on the Theory of Computing 1971$$tProceedings of the Third Annual ACM Symposium on the Theory of Computing$$y1971
000014076 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1119/1.1359518
000014076 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1103/PhysRevE.58.5355
000014076 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1126/science.1057726
000014076 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1103/PhysRevLett.68.9
000014076 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1103/PhysRevLett.86.2050
000014076 999C5 $$1L. D. Landau$$2Crossref$$oL. D. Landau 1932$$y1932
000014076 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1098/rspa.1932.0165
000014076 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1103/PhysRevA.74.060304
000014076 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1103/PhysRevA.80.062326
000014076 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1103/PhysRevLett.104.207206
000014076 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1073/pnas.1002116107
000014076 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1103/PhysRevLett.101.170503
000014076 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1103/PhysRevLett.104.020502
000014076 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1038/22055
000014076 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1103/PhysRevA.71.062305
000014076 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1103/PhysRevA.25.1699
000014076 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1143/PTP.58.1377
000014076 999C5 $$2Crossref$$9-- missing cx lookup --$$a10.1039/b509983h
000014076 999C5 $$1W. van Dam$$2Crossref$$oW. van Dam Proceedings of the 42nd Annual Symposium on Foundations of Computer Science 2001$$tProceedings of the 42nd Annual Symposium on Foundations of Computer Science$$y2001
000014076 999C5 $$1S. Coleman$$2Crossref$$oS. Coleman Proceedings of the International School of Subnuclear Physics, Erice, 1977 1977$$tProceedings of the International School of Subnuclear Physics, Erice, 1977$$y1977