Quantum Computers Can Search Rapidly by Using Almost Any Transformation

Abstract

A quantum computer has a clear advantage over a classical computer for exhaustive search. The quantum mechanical algorithm for exhaustive search was originally derived by using subtle properties of a particular quantum mechanical operation called the Walsh-Hadamard (W-H) transform. This paper shows that this algorithm can be implemented by replacing the W-H transform by almost any quantum mechanical operation. This leads to several new applications where it improves the number of steps by a square root. It also broadens the scope for implementation since it demonstrates quantum mechanical algorithms that can adapt to available technology.