作者: Peter Shor , David Gosset , Edward Farhi , Jeffrey Goldston , Harvey B. Meyer
关键词: Mathematics 、 Quantum algorithm 、 Path (graph theory) 、 Imaginary time 、 Quantum Monte Carlo 、 Adiabatic quantum computation 、 Quantum annealing 、 Algorithm 、 Adiabatic process 、 Quantum
摘要: 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.