Speedup of iterated quantum search by parallel performance

Abstract

Given a sequence $f_1(x_1),f_2(x_1,x_2),...,f_k(x_1,...,x_k)$ of Boolean functions, each of which $f_i$ takes the value 1 in a single point of the form $x_1^0,x_2^0,...,x_i^0,i=1,2,...,k$. A length of all $x_i^0$ is $n,N=2^n$. It is shown how to find $x_k^0(k\ge 2)$ using \frac{kπ\sqrt{N}}{4\sqrt{2}}$simultaneousevaluationsoffunctionsoftheform$f_i, f_{i+1}$withanerrorprobabilityoforder$k/\sqrt{N}$whichis$\sqrt{2}$timesasfastasbythe$k$sequentialapplicationsofGroveralgorithmforthequantumsearch.Evolutionsofamplitudesinparallelquantumcomputationsareapproximatedbysystemsoflineardifferentialequations.Someadvantageofsimultaneousevaluationsofall$f_1 ,... f_k$ are discussed.

Latex, 21 pages, no figures, simplification of the proof