You will be presented with the full text of a science research paper. Please write an abstract for this paper. Your response should include the abstract and no additional text.

Paper text:
we are given a subroutine which for every one of @xmath0 possible inputs gives us a @xmath1 or a @xmath2 as output .
the subroutine is in a `` black box '' , so we are not allowed to see what algorithm it uses .
the problem is to find an input for which the subroutine gives @xmath2 ( a `` marked '' input or `` element '' ) or to say that there is no such input .
classically there is no other way than to try out many inputs on the subroutine . on the other hand ,
if the subroutine also works for superpositions of inputs    @xmath3    we can use grover s quantum searching algorithm @xcite to find a `` marked element '' ( an input that yields @xmath2 ) which gives us a quadratic speedup relative to the classical method .
in particular when we know the number @xmath4 of marked elements , grover s algorithm will find one of these elements with high probability using only about @xmath5 queries to the subroutine .
a slight modification of this algorithm can actually increase the success probability to @xmath2 while using at most one more query ( see below ) .
all this also works when we are only told that the number of marked elements is either @xmath4 or @xmath1 .
on the other hand , when we do nt know the number of marked elements , grover s algorithm does nt perform that well . in particular to get a certainly correct answer any algorithm will use on the order of @xmath0 queries as for the classical case @xcite .
if we allow for some error probability , a grover type quantum search still helps . note that when the quantum algorithm outputs a candidate marked element
, we can check it with just one more query .
thus the only error that can happen , is that the algorithm wrongly says that there are no marked elements .
thus the error is so - called one sided and we have not only a quantum monte carlo algorithm ( bqp ) but actually a quantum - rp algorithm .
so the problem now is : given @xmath0 and some upper bound on the error probability @xmath6 , find an algorithm that uses as few queries to the black box as possible .
note that by error probability we mean the error probability for the worst case , which here in particular means the number of marked elements for which the algorithm performs worst .
a simple , but not optimal , solution to this problem is to run grover s algorithm many times for some random number of iterations (= number of queries ) between @xmath1 and @xmath7 , which is about the optimum for just one marked element .
we choose the number of iterations of each run uniformly at random from the given range . from the evolution of the state vector ( of the qc ) in grover
s algorithm ( see below ) it is easy to see that in each such run and for any number of marked elements ( except @xmath1 ) the probability of finding a marked element is about @xmath8 .
actually a careful analysis ( see below ) shows that for the worst - case number of marked elements @xmath4 , it s about @xmath9 . by repeating this
many times we get asymptotically at most about the following number of queries :    @xmath10      the proposed algorithm again basically consists of many runs of grover s algorithm , each for some numbers of iterations ( = number of queries ) .
it consists of 2 parts plus possibly a third one to improve it a bit .
the first part checks for all numbers of marked elements from @xmath2 to some maximum @xmath11 , each time running grover s algorithm for the appropriate number of iterations , which is about @xmath5 for @xmath4 marked elements .
if the maximal error probability @xmath6 which we allow is below about @xmath12 we have to use the exact version of grover which is guaranteed to work for a given known number of marked elements .
the total number of queries of this first step is about :    @xmath13    which i ve obtained by approximating the sum with an integral .
the second part consists of a number of grover runs for a random number of iterations smaller than the last grover run of the first part .
thus we choose the number of iterations uniformly at random from the range @xmath14 .
this i propose to do @xmath15 times .
thus the second part consists of at most the following number of queries :    @xmath16    it turns out that this choice of the number of grover runs in the second part which gives equal number of queries for the first and second parts is optimal .    in the second part we have probability about @xmath8 to find a marked element in every run ,
provided the number of marked elements is larger than @xmath11 .
say the actual ( worst case ) probability is some @xmath17 ( which is a bit smaller than 1/2 and which we will determine below ) , then @xmath18 and we get the following number of queries for the total algorithm as a function of @xmath0 and @xmath6 :    @xmath19    note the ( admittedly small ) improvement relative to the simpler algorithm described above .
note also that @xmath6 as a function of @xmath20 for a fixed @xmath0 goes as    @xmath21    which is of course better than the exponential we could achieve by just running the same probabilistic algorithm over and over .
it turns out that the worst case detection probability @xmath17 actually occurs for a number of marked elements @xmath4 close to @xmath0 .
so if we want we can add a third part to the algorithm where we take care of this worst case by just classically checking a number of random inputs to the black box . to achieve the maximum allowed error probability @xmath6
this only takes a number of queries that is of a smaller order than the number of queries used in the first two parts , thus we can neglect the cost of this third part .    in the remainder of the paper
i will determine the maximal error probability @xmath17 for a grover run with a random number of iterations and i will also give a simple argument that an exact version of grover s algorithm can be constructed for a known number @xmath4 of marked elements , which has been known before ( i think it s by peter hoyer , but ca nt find a reference ) .
first we have to review grover s algorithm :      each iteration of grover s algorithm consists of the following four steps :    @xmath22    the initial state is the uniform amplitude superposition of all possible @xmath0 inputs to the black box .
the first step involves querying the oracle , while the second and fourth steps involve hadamard transforming each of the @xmath23 qubits ( thus here we have @xmath24 ) .
we can write the initial state as    @xmath25    where @xmath26 is the set of marked elements while @xmath27 and @xmath28 .
it turns out ( and is easy to see ) that after any number of applications of the 4 steps of grover s algorithm the state remains of the above form , thus a superposition with real coefficients of the uniform amplitude superposition of all unmarked ( basis- ) states and of the uniform amplitude superposition of all marked states .
the actual calculation consists simply of applying the 4 above steps to each of these 2 states . in every iteration
the state vector gets rotated by some angle @xmath29 , so after @xmath30 iterations we have :    @xmath31    where @xmath29 is given by    @xmath32    it is easy to check that @xmath33 which will facilitate the subsequent calculations .
the probability of finding a marked element after @xmath30 steps is @xmath34 . if we choose the number of iterations uniformly at random from the range @xmath35 we get the success probability    @xmath36    where the summation is easily accomplished because we can write the trigonometric functions in terms of exponentials @xmath37 which gives us geometric series .
also we used @xmath33 . note that , as stated above , @xmath38 .
now we have to look for the minimum of @xmath17 ( = worst case ) over the range @xmath39 of marked elements .
the lower end of this range corresponds to @xmath40 .
the following plot shows @xmath17 as a function of @xmath29 ( here for @xmath41 )
. note that @xmath42 while @xmath43 .
the point @xmath44 is where @xmath45 first reaches @xmath8 .
significant for us is the next local minimum @xmath46 and the last local minimum @xmath47 , where i have taken the limit @xmath48 to get these values .
these two values are the absolute minimum ( in our range ) and the next larger local minimum . if we include the third part of the algorithm ( classical checking ) we do nt have to worry about @xmath49 , thus @xmath50 . then asymptotically the number of queries becomes ( from equation [ res ] ) :
@xmath51    the second graph above shows how the success probability evolves in grover s algorithm for 3 cases of interest .
the range shown in the plot is the range which we use in the second part of the algorithm , thus from 0 to about @xmath52 iterations .
the thick solid line is for @xmath11 marked elements , for which the average probability over this range is @xmath8 .
the dashed graph corresponds to the first local minimum in the first plot , whereas the dotted graph gives the last local minimum which occurs for only few unmarked elements .
here i give a simple argument why grover s algorithm can easily be modified to give a correct answer for a known number @xmath4 of marked elements . the problem with standard
grover is that @xmath53 never exactly becomes @xmath2 .
our task now is to modify the 4 steps in grover s algorithm so that we get a smaller rotation angle @xmath54 .
imagine we apply these ( modified ) 4 steps to the initial ( uniform amplitude ) state .
usually in the 1 .
step we change the phase of the marked states by @xmath55 which allows us to increase the amplitude of the marked states to @xmath56 . if we do nt change the phase it is easy to see that the 4 steps of grover s algorithm do nt change the initial state at all , thus the amplitude of the marked states remains @xmath57 . by continuity
it is now clear that we can adjust the absolute value of the amplitude of the marked states to any value between these extremes . to get the amplitude back to real and positive
we then call the black box once more to rotate the phase of the marked elements by the right amount
.    actually one can avoid this last ( additional ) call to the black box by also choosing a different phase change in step 3 , but this is not so easy to explain .
of course there are also various other ways to make grover s algorithm exact .
the algorithm we have constructed is clearly not optimal .
it s order _ is _ optimal , as stated in corollary 3 on page 6 of @xcite , but the performance can obviously still be improved by a multiplicative constant .
my guess is that the number of queries can be reduced by at least a factor of @xmath58 , but probably by a factor of @xmath59 or more .
unfortunately no bound on the multiplicative constant is specified in @xcite .    in the second part of the algorithm we choose the number of iterations of grover at random .
this is not very elegant and certainly not optimal , but it makes the algorithm and the assessment of its performance easy .
a general observation is that zero error algorithms are a rather academic and unphysical concept .
any computer has some failure probability , this is especially true for quantum computers .
fortunately fault tolerant techniques allow us to greatly increase the reliability .
essentially the error probability can be reduced exponentially in the resources we invest into fault tolerance which allows us to attain a reliability that is good enough for all practical purposes .
so what about my use of the exact variant of grover s algorithm ?
actually we do nt really need the exact version , we merely need to be able to greatly reduce the error without using many more queries . in a fault
tolerant implementation we actually anyways ca nt really apply phase rotations by any amount because we only can use a finite `` universal '' set of gates .
the better we want to approximate a given phase rotation the more such gates we have to use .
fortunately the number of gates necessary typically only increases as the logarithm of the precision of the approximation .
we want to find a marked element out of a black box containing @xmath0 elements . 
 when the number of marked elements is known this can be done elegantly with grover s algorithm , a variant of which even gives a correct result with certainty . on the other hand , when the number of marked elements is not known the problem becomes more difficult . 
 for every prescribed success probability i give an algorithm consisting of several runs of grover s algorithm that matches a recent bound @xcite on the order of the number of queries to the black box . 
 the improvement in the order over a previously known algorithm is small and the number of queries can clearly still be reduced by a constant factor .