Generalized quantum search with parallelism - art. no. 052313

We generalize Grover's unstructured quantum search algorithm to enable it t o work with arbitrary starting superpositions and arbitrary unitary operato rs. We show that the generalized quantum search algorithm, when cast in a s pecial orthonormal basis, can be understood as performing an exact rotation of a starting superposition into a target superposition. We derive a formu la for the success probability of the generalized quantum search algorithm after n rounds of amplitude amplification. We then use this formula to dete rmine the optimal strategy for a punctuated quantum search algorithm, i.e., one in which the amplitude amplified state is observed before the point of maximum success probability. On average, the optimal strategy is about 12% better than the naive use of Grover's algorithm. The speedup obtained is n ot dramatic but it illustrates that a hybrid use of quantum computing and c lassical computing techniques can yield a performance that is better than e ither alone. In addition, we show that a punctuated quantum algorithm that takes the same average computation lime as Grover's standard algorithm only requires half the coherence time. We then extend the analysis to the case of a society of k quantum searches acting in parallel. We derive an analyti c formula that connects the degree of parallelism with the expected computa tion time for k-parallel quantum search. The resulting parallel speedup sca les as O(root k), while the minimum number of agents needed to ensure succe ss, k, decreases as the inverse of the square of the achievable coherence t ime. This result has practical significance for the design of rudimentary q uantum computers that are likely to have a limited coherence time.