Quantum adiabatic algorithms, small gaps, and different paths

作者: Peter Shor , David Gosset , Edward Farhi , Jeffrey Goldston , Harvey B. Meyer

DOI: 10.5555/2011395.2011396

关键词: MathematicsQuantum algorithmPath (graph theory)Imaginary timeQuantum Monte CarloAdiabatic quantum computationQuantum annealingAlgorithmAdiabatic processQuantum

摘要: We construct a set of instances 3SAT which are not solved efficiently using the simplestquantum adiabatic algorithm. These obtained by picking randomclauses all consistent with two disparate planted solutions and then penalizing one ofthem single additional clause. argue that randomly modifying beginningHamiltonian, obtains (with substantial probability) an path thatremoves this difficulty. This suggests quantum algorithm should ingeneral be run on each instance many different random paths leading to problemHamiltonian. do know whether trick will help for of3SAT (as opposed from particular we consider), especially if theinstance has exponential number assignments violate few clauses.We use continuous imaginary time Quantum Monte Carlo in novel way tonumerically investigate ground state as well first excited our system.Our arguments supplemented data simulations withup 150 spins.

参考文章(18)
Michael Sipser, Jeffrey Goldstone, Sam Gutmann, Edward Farhi, Quantum Computation by Adiabatic Evolution arXiv: Quantum Physics. ,(2000)
Jeffrey Goldstone, Sam Gutmann, Edward Farhi, Quantum Adiabatic Evolution Algorithms with Different Paths arXiv: Quantum Physics. ,(2002)
Boris Altshuler, Hari Krovi, Jérémie Roland, Adiabatic quantum optimization fails for random instances of NP-complete problems arXiv: Quantum Physics. ,(2009)
EDWARD FARHI, JEFFREY GOLDSTONE, SAM GUTMANN, DANIEL NAGAJ, HOW TO MAKE THE QUANTUM ADIABATIC ALGORITHM FAIL International Journal of Quantum Information. ,vol. 06, pp. 503- 516 ,(2008) , 10.1142/S021974990800358X
Daniel S. Fisher, A. P. Young, DISTRIBUTIONS OF GAPS AND END-TO-END CORRELATIONS IN RANDOM TRANSVERSE-FIELD ISING SPIN CHAINS Physical Review B. ,vol. 58, pp. 9131- 9141 ,(1998) , 10.1103/PHYSREVB.58.9131
Yoshiki Matsuda, Hidetoshi Nishimori, Helmut G Katzgraber, Ground-state statistics from annealing algorithms: quantum versus classical approaches New Journal of Physics. ,vol. 11, pp. 073021- ,(2009) , 10.1088/1367-2630/11/7/073021
Tad Hogg, Adiabatic Quantum Computing for Random Satisfiability Problems Physical Review A. ,vol. 67, pp. 022314- ,(2003) , 10.1103/PHYSREVA.67.022314
Ben W. Reichardt, The quantum adiabatic optimization algorithm and local minima symposium on the theory of computing. pp. 502- 510 ,(2004) , 10.1145/1007352.1007428
Daniel S. Fisher, Critical behavior of random transverse-field Ising spin chains. Physical Review B. ,vol. 51, pp. 6411- 6461 ,(1995) , 10.1103/PHYSREVB.51.6411