The Analysis on the Running Time of the Generalized Quantum Search Hamiltonian : $O(N^{1/4})$ and O(1) Time Resources

Abstract

Farhi et al. suggested the analogue quantum search Hamiltonian and Fenner also proposed the intuitive quantum search Hamiltonian. Recently the generalized quantum search Hamiltonian containning hamiltonians of Farhi et al. and Fenner was presented in quant-ph/0110020. In this letter, we analyze the running time of the generalized quantum search Hamiltonian. Our analysis displays two surprising results. The first is the exponential speedup(T = O(N 1/4)), and the next O(1) time resource. In 1996, Farhi et al. suggested the analogue quantum search algorithm based on Hamiltonian evolution.[1] The Hamiltonian to solve the search problem is Haf = Ed(|w〉〈w|+|ψ〉〈ψ|). In the Hamiltonian Haf, |w 〉 is the target state that we have to find, |ψ 〉 is the initial state that is a superposition of N states, E is a constant in unit of energy, and d is a constant. Fenner [2] also proposed the quantum search Hamiltonian Hif = −2iEx(|w〉〈ψ | − |ψ〉〈w|), where x = 〈w|ψ 〉 ≈ 1 √. The Hamiltonian Hif is called the intuitive quantum search Hamil-N tonian. Recently, the generalized quantum search Hamiltonian including hamiltonians of Farhi et al. and Fenner was presented.[3] The Hamiltonian is as follows: Hyj = E[d(|w〉〈w | + |ψ〉〈ψ|) + r(e iφ |w〉〈ψ | + e −iφ |ψ〉〈w|)] (1) where, r is a constant, and φ is a phase. The initial state can be written as |ψ 〉 = x|w 〉 + √ 1 − x 2 |β〉, where |β 〉 is the orthogonal complement of the state |w〉. If the phase is given by φ = nπ(n is an integer), then the Hamiltonian finds the target state with probability one, but if not, the probability to find the target becomes 1 − O(x 2) ≈ 1 − O(1/N).