Generalized quantum search with parallelism
Authors:
- 19 April 2000
- journal article
- research article
- Published by American Physical Society (APS) in Physical Review A
- Vol. 61 (5) , 052313
Abstract
We generalize Grover’s unstructured quantum search algorithm to enable it to work with arbitrary starting superpositions and arbitrary unitary operators. We show that the generalized quantum search algorithm, when cast in a special orthonormal basis, can be understood as performing an exact rotation of a starting superposition into a target superposition. We derive a formula for the success probability of the generalized quantum search algorithm after n rounds of amplitude amplification. We then use this formula to determine 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 not dramatic but it illustrates that a hybrid use of quantum computing and classical computing techniques can yield a performance that is better than either alone. In addition, we show that a punctuated quantum algorithm that takes the same average computation time 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 analytic formula that connects the degree of parallelism with the expected computation time for k-parallel quantum search. The resulting parallel speedup scales as while the minimum number of agents needed to ensure success, k, decreases as the inverse of the square of the achievable coherence time. This result has practical significance for the design of rudimentary quantum computers that are likely to have a limited coherence time.
Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Nuclear magnetic resonance spectroscopy: An experimentally accessible paradigm for quantum computingPhysica D: Nonlinear Phenomena, 1998
- Tight Bounds on Quantum SearchingFortschritte der Physik, 1998
- Correlated input-port, matter-wave interferometer: Quantum-noise limits to the atom-laser gyroscopePhysical Review A, 1998
- Quantum Computers Can Search Rapidly by Using Almost Any TransformationPhysical Review Letters, 1998
- Bulk quantum computation with nuclear magnetic resonance: theory and experimentProceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 1998
- Strengths and Weaknesses of Quantum ComputingSIAM Journal on Computing, 1997
- Bulk Spin-Resonance Quantum ComputationScience, 1997
- Quantum Bit RegenerationPhysical Review Letters, 1996
- Simple quantum computerPhysical Review A, 1995
- Rapid solution of problems by quantum computationProceedings of the Royal Society of London. Series A: Mathematical and Physical Sciences, 1992