Bulletin of the American Physical Society
2006 APS March Meeting
Monday–Friday, March 13–17, 2006; Baltimore, MD
Session W40: Quantum Communication, Cryptography and Computation
2:30 PM–5:30 PM,
Thursday, March 16, 2006
Baltimore Convention Center Room: 343
Sponsoring Units: TGQI DAMOP
Chair: Steven H. Simon, Bell Labs, Lucent Technologies
Abstract ID: BAPS.2006.MAR.W40.11
Abstract: W40.00011 : Quantum Phase Transitions and Typical Case, Polynomial Time Solution of Randomly Generated NP-Complete Problems via Adiabatic Quantum Computation*
4:30 PM–4:42 PM
Preview Abstract Abstract
We argue theoretically that adiabatic quantum computation using only polynomial resources can solve almost all members of a nontrivial randomly generated set of NP-complete problem instances, namely the problem of finding the ground states of spin glasses on 3D cubic lattices having independent, identically Gaussian-distributed couplings. The argument uses the droplet model of quantum spin glasses, particularly its prediction that the paramagnet-spin glass transition is unstable to even infinitesimal longitudinal fields. We then review the ongoing debate as to how well the droplet model describes 3D spin glasses and note that those inclined to view the intractability of NP-complete problems as a guiding physical intuition could take the results presented here as justifying greater suspicion toward the droplet model. Finally, due to this uncertainty as well as uncertainty in regard to the typical case classical complexity of this random NP-complete problem, we outline work using rigorous mean-field methods on a NP-complete problem whose typical-case classical complexity on random instances is better established, namely MAX CLIQUE on random graphs.
*This work is supported in part by ARDA and DoD under the AFOSR DURINT Program. WMK gratefully acknowledges fellowship support from the Fannie and John Hertz Foundation.
To cite this abstract, use the following reference: http://meetings.aps.org/link/BAPS.2006.MAR.W40.11
The American Physical Society (APS) is a non-profit membership organization working to advance the knowledge of physics.
1 Physics Ellipse, College Park, MD 20740-3844
Editorial Office 1 Research Road, Ridge, NY 11961-2701 (631) 591-4000
Office of Public Affairs 529 14th St NW, Suite 1050, Washington, D.C. 20045-2001 (202) 662-8700