title: Ultrafast adiabatic quantum algorithm for the NP-complete exact cover problem.
abstract: An adiabatic quantum algorithm may lose quantumness such as quantum coherence entirely in its long runtime, and consequently the expected quantum speedup of the algorithm does not show up. Here we present a general ultrafast adiabatic quantum algorithm. We show that by applying a sequence of fast random or regular signals during evolution, the runtime can be reduced substantially, whereas advantages of the adiabatic algorithm remain intact. We also propose a randomized Trotter formula and show that the driving Hamiltonian and the proposed sequence of fast signals can be implemented simultaneously. We illustrate the algorithm by solving the NP-complete 3-bit exact cover problem (EC3), where NP stands for nondeterministic polynomial time, and put forward an approach to implementing the problem with trapped ions.
authors.affiliation: Department of Applied Physics, Xi'an Jiaotong University, Xi'an 710049, China.|Key Laboratory of Quantum Information and Quantum Optoelectronic Devices, Shaanxi Province, China.
authors.forename: Hefeng
authors.initials: H
authors.lastname: Wang
authors.affiliation: Department of Theoretical Physics and History of Science, The Basque Country University (EHU/UPV), P. O. Box 644, 48080 Bilbao, Spain.|IKERBASQUE, Basque Foundation for Science, 48011 Bilbao, Spain.
authors.forename: Lian-Ao
authors.initials: LA
authors.lastname: Wu