Quantum search using non-Hermitian adiabatic evolution

We propose a non-Hermitian quantum annealing algorithm which can be useful for solving complex optimization problems. We demonstrate our approach on Grover's problem of finding a marked item inside of an unsorted database. We show that the energy gap between the ground and excited states depends on the relaxation parameters and is not exponentially small. This allows a significant reduction of the searching time, which is proportional to the number of qubits. We discuss the relations between the probabilities of finding the ground state and the survival of a quantum computer in a dissipative environment, and we discuss alternate ways to solve NP-complete problems. © 2012 American Physical Society