A new algorithm for directed quantum search
Tathagat Tulsi, Lov K. Grover, Apoorva D. Patel · 2005
Quantum searching requires precise knowledge of problem parameters (such as the fraction of target states) for efficient operation. Recently an algorithm has been discovered, referred to as the Phase-$\\pi/3$ search algorithm, which gets around this limitation. This algorithm can search a database with the fraction of target states equal to $1-\\epsilon$ so that in $q$ queries it produces a probability of error equal to $\\epsilon^{2q+1}$ which has since been proved to be optimal. This paper gives a different algorithm which has the same worst-case behavior as the Phase-$\\pi/3$ search algorithm but much better average-case behavior. Furthermore the new algorithm gives $\\epsilon^{2q+1}$ convergence for all integral $q$, the Phase-$\\pi/3$ search algorithm, requires $q$ to be $(3^{n}-1)/2$, with $n$ a positive integer. In the new algorithm, the operations are controlled in a special way by two ancilla qubits, and fixed point behavior is achieved by irreversible measurement operations.