Quantum optimization for combinatorial searches
C A Trugenberger · New Journal of Physics · 2002
I propose a `quantum annealing' heuristic for the problem of a combinatorial search among a frustrated set of states characterized by a cost function to be minimized. The algorithm is probabilistic, with post-selection of the measurement result. A unique parameter playing the role of an effective temperature governs the computational load and the overall quality of the optimization. Any level of accuracy can be reached with a computational load independent of the dimension N of the search set by choosing the effective temperature correspondingly low. This is much better than classical search heuristics, which typically involve computation times growing as powers of log( N ).