Quantum search using non-Hermitian adiabatic evolution
Alexander I. Nesterov, G. P. Berman · Physical Review A · 2012
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 [L. K. Grover, Phys. Rev. Lett. 79, 325 (1997)] 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.