You are an expert at summarizing long articles. Proceed to summarize the following text: 
the quantum summation ( * qs * ) algorithm ( also known as the amplitude estimation algorithm ) of brassard , hyer , mosca and tapp , see @xcite , computes an approximation to the arithmetic mean of all values of a boolean function defined on a set of @xmath12 elements . information regarding the boolean function is supplied by quantum queries . the quantum queries play a role similar to the use of function values in the worst case and randomized settings . suppose that we use @xmath1 quantum queries . obviously , the only case of interest is when @xmath6 is much smaller than @xmath0 . it was proven in @xcite that the error of the * qs * algorithm is at most @xmath13    nayak and wu , see @xcite , showed that for any @xmath14 $ ] the error of any quantum algorithm that uses no more than @xmath1 quantum queries must be proportional to @xmath11 with probability @xmath15 . therefore , the * qs * algorithm enjoys the smallest possible error modulo a factor multiplying @xmath11 . the minimal error estimate of order @xmath11 in the quantum setting should be compared to the minimal error estimates in the worst case and randomized settings of algorithms using @xmath1 function values . it is known , see @xcite , that in the worst case setting , the error bound is roughly @xmath16 . this means that as long as @xmath6 is much less than @xmath0 the error is almost @xmath17 , and is therefore of order @xmath6 times larger than in the quantum setting . in the randomized setting , the classical monte carlo is almost optimal , and the error bound is roughly @xmath18 , see again @xcite . hence , it is of order @xmath19 larger than in the quantum setting . the * qs * algorithm has many applications . in particular , it can be used for approximation of the arithmetic mean of a real function , which is the basic step for approximation of many continuous problems such as multivariate integration , multivariate approximation and path integration , see @xcite . since the * qs * algorithm has so many applications , it seems reasonable to check whether the estimate ( [ 111 ] ) is sharp and how the error decreases if we lower the probability @xmath20 to @xmath21 . it also seems reasonable to study the error of the * qs * algorithm in various settings . the estimate ( [ 111 ] ) corresponds to the worst - probabilistic setting , which is most frequently used in the quantum setting . the essence of this setting is that it holds for all boolean functions . it is also interesting to study the average performance of the * qs * algorithm with respect to some measure on boolean functions . this is the average - probabilistic setting . in the worst - average and average - average settings , we study the worst or average performance with respect to boolean functions and the average performance with respect to all outcomes of a quantum algorithm . we add in passing that the worst - average setting is usually used for the study of the classical monte carlo algorithm . sharp error bounds in the worst- and average - probabilistic settings are addressed in this paper whereas the worst- and average - average settings will be studied in a future paper . we study error bounds with probabilities @xmath22 $ ] . if we want to obtain error bounds with higher probability , it is known that it is enough to run the * qs * algorithm several times and take the median as the final result , see e.g. , @xcite .    in the worst - probabilistic setting , we show that ( [ 111 ] ) can be slightly improved . namely , the error of the * qs * algorithm is at most @xmath23    furthermore , for large @xmath6 and @xmath24 we prove that the last estimate is sharp . more generally , for @xmath25 $ ] we prove that the error of the * qs * algorithm is at most @xmath26 where @xmath27 is the inverse of the function @xmath28 . we prove that the last estimate is sharp for large @xmath6 and @xmath24 . we have @xmath29 $ ] and it is well approximated by @xmath30 . in particular , for the most commonly used values of @xmath15 we have @xmath31    in the average - probabilistic setting , we consider two measures on the set of boolean functions . the first measure is uniform on boolean functions , while the second measure is uniform on arithmetic means of boolean functions . the results for these two measures are quite different . the mean element of the arithmetic means is @xmath17 for both measures . however , the first moment is of order @xmath32 for the first measure , and about @xmath33 for the second . the first moment is exactly equal to the error of the constant algorithm that always outputs @xmath17 . this explains why we can obtain the error of order @xmath32 without any quantum queries for the first measure . this provides the motivation for us to check whether the error of the * qs * algorithm enjoys a similar property . it turns out that this is indeed the case iff @xmath6 is divisible by @xmath9 . that is , for @xmath6 divisible by @xmath9 , the average - probabilistic error of the * qs * algorithm is of order @xmath34 , and if @xmath6 is not divisible by @xmath9 , then the error is of order @xmath11 . for the second measure , since the first moment is not small , the average - probabilistic error of the * qs * algorithm is of order @xmath11 for all @xmath6 . for both measures , the upper bounds presented in this paper match lower bounds that were recently obtained by papageorgiou , see  @xcite . hence , the * qs * algorithm enjoys minimal error bounds also in the average - probabilistic setting if we choose @xmath6 divisible by @xmath9 for the first measure and with no restriction on @xmath6 for the second measure . the quantum setting , and in particular the * qs * algorithm , is relatively new and probably not well known , especially for people interested in continuous complexity . hence we present all details of this algorithm , emphasizing its quantum parts . since we wanted also to find sharp error bounds , we needed a very detailed analysis of the outcome probabilities of the * qs * algorithm . we outline the contents of this paper . in section [ sec : quantsummalgo ] we define the * qs * algorithm . section [ sec : perfanalys ] deals with the performance analysis of the * qs * algorithm in the worst - probabilistic setting , see section [ sec : wcp ] , and in the average - probabilistic setting , see section  [ sec : acp ] . we consider the most basic form of the summation problem , i.e. , the summation of boolean functions . let @xmath35 denote the set of boolean functions @xmath36 . let @xmath37 denote the arithmetic mean of all values of @xmath38 . clearly , @xmath39 $ ] . * problem : * for @xmath40 , compute an @xmath41-approximation @xmath42 of the sum @xmath43 such that @xmath44    we are interested in the minimal number of evaluations of the function @xmath38 that are needed to compute @xmath42 satisfying  . it is known that in the worst case setting , we need roughly @xmath45 evaluations of the function @xmath38 . in the randomized setting , we assume that @xmath42 is a random variable and require that holds for the expected value of @xmath46 for any function  @xmath38 . it is known , see e.g. , @xcite , that in the randomized setting we need roughly @xmath47 function evaluations . in the quantum setting , we want to compute a random variable @xmath42 such that holds with a high probability ( greater than @xmath17 ) either for _ all _ boolean functions or on the average with respect to a probability measure defined on the set @xmath35 . these two error criteria in the quantum setting will be precisely defined in section  [ sec : perfanalys ] .    in this section we describe the quantum summation algorithm , which is also called the quantum amplitude estimation algorithm . this algorithm was discovered by brassard , hyer , mosca and tapp @xcite , and uses grover s iterate operator as its basic component , see @xcite . we use standard notation of quantum computation , see e.g. , @xcite .    for simplicity we assume that @xmath12 . let @xmath48 denote the tensor product @xmath49 of @xmath50 copies of @xmath51 , with @xmath51 the 2-dimensional complex vector space . unit vectors from @xmath51 are called _ one qubit _ quantum states ( or _ qubits _ ) . let @xmath52 and @xmath53 be an orthonormal basis of @xmath51 . then any qubit  @xmath54 can be represented as @xmath55 for @xmath56 , we have @xmath57 , with @xmath58 . let @xmath59 the set @xmath60 forms an orthonormal basis of @xmath48 and any unit vector @xmath61 can be represented as @xmath62 unit vectors from @xmath48 are called @xmath50 qubit quantum states ( or quantum states or just states , whenever @xmath50 is clear from the context ) . the only transforms that can be performed on quantum states are defined by certain unitary operators on @xmath48 . we now define the six unitary operators that are basic components of the summation algorithm . since unitary operators are linear , it is enough to define them on the basis states  @xmath63 .    1 .   let @xmath64 denote the _ inversion about zero transform _ @xmath65 where @xmath66 is the kronecker delta . hence , @xmath67 and @xmath68 for all @xmath69 . this corresponds to the diagonal matrix with one element equal to @xmath70 , and the rest equal to @xmath71 . the operator @xmath72 can be also written as the householder operator @xmath73 here , for a state @xmath54 , we let @xmath74 denote the projection onto the space @xmath75 given by @xmath76 where @xmath77 is the inner product in @xmath48 , @xmath78 . the matrix form of the projector @xmath74 in the basis @xmath79 is @xmath80 . one can also view the matrix form of the projector @xmath74 as the matrix product of the @xmath81 column vector @xmath54 and the @xmath81 row vector @xmath82 , which is the hermitian conjugate of @xmath54 , @xmath83 . for any @xmath84 we have @xmath85 hence @xmath86 , as claimed . 2 .   let @xmath87 denote the _ walsh - hadamard transform _ @xmath88 that is , the walsh - hadamard transform corresponds to the matrix with entries @xmath89 the matrix @xmath90 is symmetric . furthermore , @xmath91 thus , @xmath92 and @xmath93 is orthogonal . this means that the operator @xmath94 is symmetric and unitary . 3 .   for @xmath95 , let @xmath96 denote the _ quantum fourier transform _ @xmath97 hence , @xmath98 corresponds to the unitary block - diagonal matrix @xmath99,\ ] ] where @xmath100 is the matrix of the inverse quantum fourier transform . for @xmath101 we have @xmath102 the coefficients of @xmath103 in the basis @xmath79 are the inverse quantum fourier transforms of the coefficients of the state  @xmath54 . note that @xmath94 and @xmath104 coincide for the state @xmath52 , i.e. , @xmath105 4 . let @xmath106 denote the _ quantum query _ operator @xmath107 this again corresponds to the diagonal matrix with elements @xmath108 depending on the values of the boolean function @xmath38 . this operator is the only one that provides information about the boolean function @xmath38 . this is analogous to the concept of an _ oracle _ or a _ black - box _ which is used in classical computation and which supplies information about the function @xmath38 through its values . + the standard definition of the quantum query @xmath109 is @xmath110 where @xmath111 means addition modulo 2 . we can simulate @xmath112 by @xmath109 if we use an auxiliary qubit @xmath113 , namely , @xmath114 5 . let @xmath115 denote the _ grover operator _ @xmath116 this is the basic component of grover s search algorithm , see @xcite . as we shall see , @xmath117 also plays the major role for the summation algorithm . the eigenvectors and eigenvalues of @xmath117 will be useful in further considerations . let @xmath118 and @xmath119 , @xmath120 denote the orthogonal projections of @xmath54 onto the subspaces @xmath121 and @xmath122 , respectively . that is , @xmath123 then @xmath124 and @xmath125 . furthermore , @xmath126 , for @xmath127 , so that @xmath128 and @xmath129 , where @xmath130 is the sum we want to approximate . + from  @xcite , we know that @xmath131 + for the sake of completeness , we provide a short proof of . by the definition of the operator @xmath112 we have @xmath132 and @xmath133 since @xmath134 , we obtain for @xmath127 , @xmath135 from this we calculate for @xmath127 , @xmath136 which is equivalent to . + thus , the space @xmath137 is an invariant space of @xmath117 and its eigenvectors and corresponding eigenvalues can be computed by solving the eigenproblem for the @xmath138 matrix @xmath139\,.\ ] ] for @xmath140 , the eigenvectors and the corresponding orthonormalized eigenvalues of @xmath117 are @xmath141 where @xmath142 . moreover , it is easy to check that @xmath143 for @xmath144 , we have @xmath145 and @xmath54 is the eigenvector of @xmath117 with eigenvalues @xmath108 , respectively . for @xmath144 , we define @xmath146 then it is easy to check that ( [ eq : represent ] ) is valid , and @xmath147 is an eigenvalue of @xmath117 for all @xmath148 $ ] . 6 .   the next unitary transform , called the _ grover iterate operator _ , is defined on the tensor product of @xmath149 and uses @xmath150 qubits . the first space @xmath151 and @xmath152 qubits will be related to the accuracy of the quantum summation algorithm . grover iterate _ operator @xmath153 is defined by @xmath154 hence , the power of @xmath117 applied to the second component depends on the first one . note that @xmath155 may vary from 0 to @xmath156 . therefore @xmath157 may use the powers of @xmath117 up to the @xmath158st . we need one more concept of quantum computation , that of _ suppose @xmath159 is a positive integer and consider the space @xmath160 . given the state @xmath161 we can not , in general , recover all the coefficients @xmath162 . we can only measure the state @xmath54 with respect to a finite collection of linear operators @xmath163 , where the @xmath164 satisfy the completeness relation @xmath165 after performing the measurement , we obtain the outcome @xmath155 and the state @xmath54 collapses into the state @xmath166 both these events occur with probability @xmath167 . note that for @xmath168 the outcome @xmath155 can not happen with positive probability . hence , with probability @xmath71 the outcome @xmath155 corresponds to @xmath169 for @xmath170 . the most important example of such a collection of operators is @xmath171 . then , the measurement of the state @xmath54 with respect to this collection of operators gives us the outcome  @xmath155 and the collapse into the state @xmath172 with probability @xmath173 , @xmath174 . another example is a variation of the previous example and will be used in the quantum summation algorithm . we now let @xmath175 , as for the grover iterate operator , and define @xmath176 by @xmath177 for @xmath178 , with @xmath179 denoting the identity operator on @xmath48 . that is , @xmath180 for @xmath181 and @xmath182 . since @xmath183 for all basis states @xmath184 of @xmath151 and @xmath185 of @xmath48 , the completeness relation is satisfied . consider now the probability of the outcome @xmath155 for a special state @xmath54 of the form @xmath186 with @xmath187 , @xmath188 and @xmath189 for @xmath190 . since @xmath191 is self - adjoint , the outcome @xmath155 and the collapse of the state @xmath54 to the state @xmath192 occur with probability @xmath193 . hence , this collection of operators measures the components of the so - called first register @xmath120 of the quantum state @xmath54 . following @xcite , we are ready to describe the quantum summation ( * qs * ) algorithm for solving our problem . the * qs * algorithm depends on a boolean function @xmath38 and on an integer parameter @xmath6 that controls the number of quantum queries of @xmath38 used by the algorithm . we perform computations in the space @xmath149 , with @xmath194 , so we use @xmath195 qubits . as we will see later , the accuracy of the algorithm is related to the dimension of the space @xmath151 . * algorithm qs*(@xmath38 , @xmath6 )    input state : : :    @xmath196    with @xmath194 and    @xmath197 . computation : : :    1 . @xmath198 ,    2 . @xmath199 ,    3 . measurement : : :    perform the measurement of the state @xmath201    with respect to the collection    @xmath202 .    denote the outcome by @xmath155 . output : : :    @xmath203 . we briefly comment on the * qs * algorithm . the input state is always the same and does not depend on @xmath38 . step 1 computes @xmath204 , which is the equally weighted superposition of the basis states . step 2 computes @xmath205 by using the grover iterate operator . during this step we use the successive powers of the grover operator @xmath117 , and this is the only step where information about the boolean function @xmath38 is used . we shall see that the * qs * algorithm uses @xmath206 quantum queries . step  3 computes @xmath201 by performing the inverse quantum fourier transform on the first @xmath152 qubits , and prepares the system for measurement . after step 3 , we perform the measurement , obtain the outcome @xmath155 and compute the output @xmath207 on a classical computer . we stress that the distribution of the outcomes @xmath155 depends on the boolean function @xmath38 , and this is the only dependence of the output @xmath207 on  @xmath38 . in this section we analyze the error of the * qs * algorithm . as we have seen in section  [ sec : quantsummalgo ] , the output @xmath207 of the * qs * algorithm is a random value chosen according to a certain distribution dependent on the input function @xmath38 . in this way , the * qs * algorithm is a randomized algorithm . various ways of measuring the performance of randomized algorithms are commonly used in the analysis of algorithms and computational complexity . they correspond to various error criteria . in this paper we consider two error criteria : worst - probabilistic and average - probabilistic . in a future paper we consider other two error criteria : worst - average and average - average , which correspond to the worst or average performance with respect to boolean functions and the average performance with respect to all outcomes . we start with the error criterion that is used in most papers dealing with quantum computations . we are interested in the worst case error of the * qs * algorithm that holds with a given probability @xmath15 . here @xmath208 $ ] and @xmath209 measures the probability of * qs * algorithm s failure and usually @xmath15 is set to be @xmath210 . in our analysis , however , we will allow an arbitrary @xmath211 $ ] . the choice of the upper bound @xmath212 will be clear from the analysis of the * qs * algorithm . the * qs * algorithm outputs @xmath207 with probability @xmath213 for @xmath214 , see theorem [ thm : perfanalys ] where the @xmath215 s are given . its worst - probabilistic error is formally defined as the smallest error bound that holds for all boolean function with probability at least @xmath15 , i.e. , @xmath216 it is easy to see that @xmath217 can be rewritten as follows . let @xmath218 . for @xmath219 define the measure of @xmath220 as @xmath221 then    @xmath222      the worst - probabilistic error @xmath217 of the * qs * algorithm is defined by the worst performance with respect to boolean functions . it is also natural to consider the average performance of the * qs * algorithm with respect to boolean functions . let @xmath223 be a probability measure on the set @xmath35 . that is , any boolean function @xmath40 occurs with probability @xmath224 . obviously , @xmath225 and @xmath226 . the average - probabilistic error is defined by replacing the first max in by the expectation , i.e. , @xmath227 hence , we are interested in the average error that holds with a certain fixed probability . we begin by citing a theorem from  @xcite for which we will propose a number of improvements . [ thm : brass&co ] @xcite for any boolean function @xmath40 , the * qs * algorithm uses exactly @xmath1 quantum queries and outputs @xmath228 that approximates @xmath130 such that @xmath229 with probability at least @xmath230 . hence , @xmath231 and , therefore , @xmath232    using proof ideas of theorem [ thm : brass&co ] from @xcite we present the following theorem and the subsequent corollaries . [ thm : perfanalys ] for any boolean function @xmath233 , denote @xmath234.\ ] ]    1 . the * qs * algorithm uses exactly @xmath1 quantum queries , and @xmath235 qubits . 2 .   for @xmath236 , the outcome @xmath155 of the * qs * algorithm occurs with probability @xmath237 ( if @xmath238 we need to apply the limiting value of the formula above . ) for @xmath239 , the outcome @xmath155 occurs with probability @xmath240 . 3 .   if @xmath241 is an integer then the * qs * algorithm outputs the exact value of @xmath43 with probability  @xmath71 . this holds iff @xmath242 for some integer @xmath243 $ ] . in particular , this holds for @xmath244 , for @xmath245 and even @xmath6 , and for @xmath246 and @xmath6 divisible by @xmath9 . 4 .   let @xmath247 and @xmath248 . if @xmath241 is not an integer then the * qs * algorithm outputs the same value @xmath249 for the outcomes @xmath250 and @xmath251 such that @xmath252 with probability @xmath253 and outputs the same value @xmath254 for the outcomes @xmath255 and @xmath256such that @xmath257 with probability @xmath258    as before , let @xmath259 and @xmath260 for arbitrary @xmath261 . note that @xmath262 the steps 13 of the * qs * algorithm are equivalent to the application of the operator @xmath263 to the state @xmath264 . then @xmath265 can be written as @xmath266 , and @xmath267 is given by . hence @xmath268 applying @xmath157 in step 2 and remembering that @xmath269 , we obtain @xmath270    since @xmath271 , the largest power of @xmath117 is @xmath1 . hence , we use exactly @xmath1 quantum queries to compute @xmath205 . the remaining steps of the * qs * algorithm do not use quantum queries . this means that the total number of quantum queries used by the algorithm is @xmath1 , and obviously we are using @xmath195 qubits . this proves the first part of theorem [ thm : perfanalys ] . step 3 yields the state @xmath272 we are ready to analyze the probability of the outcome @xmath155 of the * qs * algorithm . observe that @xmath273 and therefore @xmath274 observe that for @xmath140 , we have @xmath275 , whereas for @xmath144 , we have @xmath276 and @xmath277 . for @xmath278 we have @xmath279 if @xmath280 is an integer then the last sum is clearly @xmath6 , and the whole expression is @xmath71 . if @xmath280 is not an integer then @xmath281 which holds for all @xmath282 if we take @xmath283 as @xmath71 . therefore @xmath284 hence @xmath285 which holds for all @xmath282 if we take @xmath283 as @xmath71 . applying this we conclude that @xmath286    the outcome @xmath155 occurs after the measurement and the state @xmath201 collapses to the state @xmath287 , where @xmath288 . for @xmath214 , we have @xmath289 whereas @xmath290 for @xmath291 . since @xmath292 and @xmath293 are orthogonal we have @xmath294 hence , the outcome @xmath155 , @xmath236 , occurs with probability @xmath295 indeed , for @xmath140 , we have @xmath296 and ( [ 158 ] ) follows from the form of @xmath297 . for @xmath144 , we have @xmath298 and @xmath277 . since the two terms in ( [ 158 ] ) are now the same , the formula for @xmath299 again yields ( [ 158 ] ) . since @xmath300 , the last formula is equivalent to ( [ eq : pj ] ) . obviously for @xmath301 , the probability of the outcome @xmath155 is zero . this proves the second part of theorem  [ thm : perfanalys ] . assume now that @xmath302 . if @xmath303 or @xmath304 ( if @xmath6 is even ) then the probability @xmath305 of the outcome @xmath306 is @xmath71 . for @xmath303 we have @xmath307 and the output is @xmath308 . for @xmath304 we have @xmath309 and the output is @xmath310 . hence , in both cases the * qs * algorithm outputs the exact value with probability @xmath71 . if @xmath311 and @xmath312 then the probability of the distinct outcomes @xmath306 and @xmath313 is @xmath17 . these two values of the outcomes yield the same output @xmath314 hence , the * qs * algorithm outputs the exact value with probability @xmath71 . this proves the third part of theorem  [ thm : perfanalys ] . we now turn to the case when @xmath315 . it is easy to check that the third part of theorem  [ thm : perfanalys ] holds for @xmath316 . assume then that @xmath317 which implies that @xmath318 . since @xmath306 is not an integer , we have @xmath319 , @xmath320 and @xmath321 . this means that both @xmath250 and @xmath251 may be the outcomes of the * qs * algorithm . obviously , these two outcomes are different iff @xmath322 . similarly , both @xmath255 and @xmath323 may be also the outcomes . they are different iff @xmath324 . we show that the outputs for the outcomes @xmath250 and @xmath255 satisfy and with probabilities and , respectively . we focus on the output for the outcome @xmath250 and its probability . the proof for the outcome @xmath255 is similar . we estimate the error of the * qs * algorithm for the output @xmath325 . recall that @xmath326 . we have @xmath327 since @xmath328 and @xmath329 , this proves the estimate of the error of the * qs * algorithm in the fourth part of theorem [ thm : perfanalys ] . we find the probability of the output @xmath228 . since @xmath330 is injective for @xmath331 $ ] , the output @xmath228 occurs only for the outcomes @xmath250 and @xmath251 . if @xmath332 then these two outcomes are the same and @xmath228 occurs with probability @xmath333 . due to ( [ 158 ] ) @xmath334 which agrees with the claim in theorem [ thm : perfanalys ] . if @xmath335 then @xmath336 and @xmath228 occurs for exactly two distinct outcomes . the probability of @xmath228 is now equal to the sum of the probabilities @xmath337 with @xmath338 s given by ( [ 158 ] ) . since both terms are equal , the probability of @xmath228 is @xmath339 which also agrees with the claim in theorem [ thm : perfanalys ] . since @xmath340 we have @xmath341 we finish proving using the standard expansion of the sine . this completes the proof . based on theorem [ thm : perfanalys ] we present simplified estimates of the error of the * qs * algorithm and of the corresponding probability . [ maxcor ] the * qs * algorithm outputs @xmath228 such that @xmath342 with probability at least @xmath343    it is enough to prove corollary [ maxcor ] if @xmath306 is not an integer . the estimate of the error of the * qs * algorithm by the maximum of the estimates and holds with probability that is the sum of the probabilities and  . moreover , @xmath344 . it now suffices to observe that the function @xmath345 is a lower bound of the left hand side of with @xmath346 , and attains the minimum @xmath3 on the interval @xmath347 $ ] for @xmath348 , see also @xcite . corollary [ maxcor ] guarantees high probability of the estimate . unfortunately this estimate does not preserve the continuity of the estimates and with respect to @xmath349 and @xmath350 . the continuity of the estimates will be present in the next corollary at the expense of the probability of the outcome . this corollary will also play an essential role in the study of the average - probabilistic error of the * qs * algorithm . [ mincor ] the * qs * algorithm outputs @xmath228 such that @xmath351 with probability at least @xmath352    we may again assume that @xmath306 is not an integer . let us define @xmath353.\ ] ]    then @xmath354 is the probability of   and @xmath355 is the probability of  . for @xmath356 $ ] , note that @xmath357 is decreasing , and @xmath358 is increasing . therefore @xmath359.\ ] ]    let @xmath360 . then @xmath361 . in this case is equivalent to and holds with probability at least @xmath362 , which corresponds to . analogously , if @xmath363 then @xmath364 . in this case is equivalent to and holds with probability at least @xmath365 , which also corresponds to . finally , note that @xmath366 is minimal for @xmath367 and is equal to @xmath368    unfortunately for @xmath369 close to @xmath17 the probability of the estimate is too small . however , in this case we may use corollary [ maxcor ] , which yields the estimate with high probability . we now turn to global error estimates , that is , estimates independent of @xmath370 . theorem  [ thm : brass&co ] of @xcite states , in particular , that @xmath371 with probability at least @xmath3 . we now improve this estimate by combining the estimates and . [ improvedcor ] the * qs * algorithm outputs @xmath228 such that @xmath372 with probability at least @xmath3 . that is , @xmath373    let us define @xmath374 clearly , @xmath375 is a lower bound of the @xmath376 and therefore @xmath377 is a lower bound of the probability of the output satisfying ( [ eq : mincorerr ] ) . we consider two cases . assume first that @xmath378 \cup [ \tfrac{3}{4},1]$ ] . it is easy to see that then @xmath379 and the estimate   yields @xmath380 with probability at least @xmath3 . assume now that @xmath381 . then we can use the estimate  , which holds unconditionally with probability at least @xmath3 . in this case , we have @xmath382 these two estimates combined together yield . the obvious consequence of corollary [ improvedcor ] is that for @xmath6 large enough we can compute the value of @xmath370 exactly by rounding the output . assume that @xmath383 then the rounding of the * qs * algorithm output to the nearest number of the form @xmath384 yields the exact value of the sum @xmath370 with probability at least @xmath3 . the proof of corollary [ improvedcor ] may suggest that the constant @xmath210 in can be decreased . furthermore one may want to decrease the constant @xmath210 at the expense of decreasing the probability @xmath3 . these points are addressed in the next corollary . we shall see that the constant @xmath210 may be lowered only by decreasing the probability . [ globalcor ] define @xmath385 and @xmath386.\ ] ] then @xmath387 , \\ m/\pi & \text{for } \quad p \in ( 8/ \pi^2 , 1 ] . \\ \end{cases}\ ] ] moreover , @xmath388 $ ] and @xmath389.\ ] ]    for @xmath390 , corollary [ globalcor ] is a consequence of corollary [ mincor ] . for @xmath391 $ ] , corollary  [ globalcor ] trivially holds since @xmath392 . for the remaining @xmath15 s we use a proof technique similar to that of corollary [ improvedcor ] .    let @xmath393 $ ] . it is easy to check that @xmath394 is decreasing and , therefore , @xmath395 is well defined and @xmath396 $ ] . we have to show that the estimate @xmath397 holds with probability at least @xmath15 . we consider two cases . assume first that @xmath398 \cup [ 1-v^{-1}(p),1]$ ] . observe that the function  @xmath399 defined in can be rewritten as @xmath400 it is easy to see that in this case , @xmath401 and the estimate yields @xmath402 with probability at least @xmath15 . assume now that @xmath403 . then we can use the estimate  , which holds unconditionally with probability at least @xmath404 . in this case , we have @xmath405 this proves . we found the estimate   by numerical computations . for @xmath406 $ ] ]    from figure [ fig : cp ] we see that the estimate is almost linear on the interval @xmath407 $ ] , which explains why the right hand side of the estimate is small .     on @xmath408 $ ] . the two horizontal lines show @xmath409 and @xmath3 levels . the part of the graph between the arrows shows that @xmath394 is almost linear . ] we now find a sharp bound on the worst - probabilistic error of the * qs * algorithm . we show that for large @xmath6 and @xmath24 the bound obtained in corollary [ globalcor ] is optimal for @xmath25 $ ] . [ thm : asympp ] for large @xmath6 and @xmath24 , the worst - probabilistic error of the * qs * algorithm is given by @xmath410.\ ] ] here , @xmath394 is as in corollary [ globalcor ] , and @xmath411 by ( [ eq : linearestim ] ) .    from corollary [ globalcor ] , it is enough to show a lower bound on the error . define @xmath412 for large @xmath6 , we have @xmath413 there exist two boolean functions @xmath414 and @xmath415 with sums @xmath416 and @xmath417 such that @xmath418 since @xmath419 and the derivative of @xmath306 for @xmath420 is @xmath421 , we have @xmath422 obviously , @xmath423 for some integers @xmath424 with @xmath425 . consider @xmath426 for @xmath427 . then @xmath426 varies from @xmath428 for @xmath429 to @xmath430 for @xmath431 . since @xmath432 , for a positive and small @xmath433 ( we finally let @xmath433 go to zero ) , we can choose @xmath434 such that for @xmath435 we have @xmath436 for large @xmath24 , we then have @xmath437 let @xmath438 denote the output for the outcome @xmath439 , and @xmath440 for @xmath441 . due to ( [ eq : perfanalyserr1 ] ) and ( [ eq : perfanalyserr2 ] ) of theorem [ thm : perfanalys ] we have @xmath442 let us write @xmath443 for @xmath444 . the probability of @xmath440 is given by ( [ eq : perfanalyspr2 ] ) and is now equal to @xmath445 since @xmath446 , the probability of @xmath447 is @xmath448 since @xmath449 for @xmath450 $ ] , we see that the probability of @xmath447 is slightly less than  @xmath15 for small @xmath433 . we are ready to find a lower bound on the worst - probabilistic error @xmath451 of the * qs * algorithm . take the function @xmath38 that corresponds to @xmath452 . we claimed that the error is minimized if @xmath453 . indeed , @xmath441 must belong to @xmath220 since otherwise @xmath454 for @xmath21 . the probability of @xmath441 is slightly less than @xmath15 , and so the set @xmath220 must also contain some other outcome @xmath155 . if @xmath455 then the error bound is roughly @xmath456 , and the sum of the probabilities of the outputs for the outcome @xmath441 and @xmath439 is always at least @xmath457 . on the other hand , if @xmath439 does not belong to the set @xmath220 then any other outcome @xmath155 yields the output @xmath458 . since @xmath459 , the distribution of the outcomes around @xmath17 is a mesh with step size roughly @xmath460 . hence , if @xmath461 , the error is at least roughly @xmath462 . thus the choice @xmath455 minimizes the error and for @xmath433 tending to zero , the error is roughly @xmath463 . this completes the proof .    from these results , it is obvious how to guarantee that the error of the * qs * algorithm is at most @xmath41 with probability at least @xmath15 . since @xmath464 holds with probability @xmath15 , it is enough to take @xmath465 . due to theorem [ thm : asympp ] this bound is sharp for small @xmath41 and large @xmath466 . we have    [ epsiloncor ] for @xmath25 $ ] , the algorithm * qs*(@xmath38 , @xmath467 ) computes @xmath228 with the error @xmath41 and probability at least @xmath15 with @xmath468 quantum queries . for small @xmath41 and large @xmath466 , the estimate of the number of quantum queries is sharp .      in this section we study the average performance of the * qs * algorithm with respect to some measure on the set @xmath35 of all boolean functions defined on the set @xmath469 . we consider two such measures . the first measure @xmath470 is uniformly distributed on the set  @xmath35 , i.e. , @xmath471 the second measure @xmath472 is uniformly distributed on the set of results , i.e. , @xmath473 for the average - probabilistic error we want to estimate @xmath474    for the measures @xmath475 , the mean of the random variable @xmath43 is clearly @xmath17 . however , their first ( central ) moments are very different . as we shall see , the moment for the measure @xmath470 is small since it is of order @xmath32 whereas the moment for measure @xmath472 is roughly @xmath33 . since the first moments are the same as the error of the constant algorithm @xmath476 , we can achieve small error of order @xmath32 for the measure @xmath470 without any quantum queries , while this property is not true for the measure @xmath472 . we now consider the measure @xmath470 . it is interesting to ask if the * qs * algorithm has the same property as the constant algorithm . we shall prove that this is indeed the case iff @xmath6 is divisible by 4 . we compute the first moment or the error of the constant algorithm , which is @xmath477 we do it only for odd @xmath0 since the case of even @xmath0 is analogous . we have @xmath478 thus @xmath479 by stirling s formula @xmath480 $ } , \ ] ] we estimate the both binomial quantities in ( [ eq : zero_err ] ) by @xmath481 proving that @xmath482    we are ready to analyze the average - probabilistic error of the * qs * algorithm . [ thm : wa4 ] assume that @xmath6 is divisible by @xmath9 and let @xmath483 $ ] . then the average - probabilistic error of the * qs * algorithms with respect to the measure @xmath470 satisfies @xmath484    the estimate @xmath485 is obvious and , applying corollary  [ improvedcor ] , we get @xmath486    as before denote @xmath487 . let @xmath488 . we are interested in the behavior of @xmath489 for @xmath490 . clearly @xmath491 . let @xmath492 , by taylor s theorem , we have @xmath493 and @xmath494 . assume additionally that @xmath495 which is equivalent to assuming that @xmath496 since @xmath6 is divisible by @xmath9 then @xmath497 for @xmath498 , and @xmath499 for @xmath500 . this yields @xmath501 observe that @xmath502 \cup [ \tfrac{3}{4},1].\ ] ] indeed , for @xmath503 we have @xmath504,\ ] ] and for @xmath505 we have @xmath506=[\tfrac{3}{4},1],\ ] ] as claimed . let @xmath507 . by the proof of corollary [ improvedcor ] , the error of the * qs * algorithm satisfies @xmath508 and by ( [ eq : min_estim ] ) , we have @xmath509    we split the sum that defines @xmath510 into two sums . the first sum is for @xmath219 for which @xmath511 with @xmath512 and the second sum is for @xmath38 for which @xmath513 with @xmath514 . for the first sum we estimate the error of the * qs * algorithm by @xmath515 and for the second sum , by the worst - case error @xmath516 . hence we have @xmath517 since @xmath518 for some integer @xmath519 $ ] , @xmath520 since @xmath521 , the first sum can be estimated as @xmath522 the second sum can be estimated by @xmath523 adding the estimates of these two sums we obtain @xmath524 the last sum is given by ( [ eq : zero_err ] ) and estimated by ( [ needed ] ) . hence @xmath525 which completes the proof .    in the next theorem we consider the case when @xmath6 is not divisible by 4 . assume that @xmath526 is not divisible by @xmath9 , and let @xmath527 $ ] . then the average - probabilistic error of the * qs * algorithm with respect to the measure @xmath470 satisfies @xmath528    let @xmath529 for @xmath530 . let , as before , @xmath531 . as in the proof of theorem [ thm : wa4 ] , for @xmath532 we have @xmath533 and @xmath494 . assume additionally that @xmath534 which is equivalent to assuming that @xmath535 thus for @xmath536 satisfying ( [ eq : xestim ] ) we have @xmath537,\ ] ] and @xmath538 and @xmath539 .    from the proof of corollary [ maxcor ] we have @xmath540 . since @xmath541 then either @xmath542 or @xmath543 . we then estimate @xmath544    we now estimate the error of the * qs * algorithm for  @xmath545 such that @xmath546 for  @xmath536 satisfying  ( [ eq : xestim ] ) and the outcome @xmath547 or @xmath548 . denote the outcome by @xmath549 for @xmath550 . by taylor s theorem we have @xmath551$}.\end{gathered}\ ] ] since @xmath552 for @xmath553 $ ] , we have @xmath554 . consider the error for the outcome @xmath549 and @xmath536 satisfying  ( [ eq : xestim ] ) . then @xmath555 and the error can be estimated by @xmath556 clearly , @xmath557 and @xmath558 $ ] . then @xmath559 . hence , for @xmath38 such that @xmath561 with @xmath536 satisfying ( [ eq : xestim ] ) we have @xmath562    we are now ready to estimate @xmath563 . first , by ( [ eq : eap_estim ] ) , we have @xmath564 this , ( [ eq:123 ] ) and the bernstein inequality , @xmath565 yields @xmath566 which completes the proof . obviously , in the average - probabilistic setting , we should use the * qs * algorithm with @xmath6 divisible by @xmath9 . then theorem [ thm : wa4 ] states that the error is of order @xmath34 . recently , papageorgiou @xcite proved that for any quantum algorithm that uses @xmath6 quantum queries the error is bounded from below by of @xmath567 with probability @xmath25 $ ] . here , @xmath568 is a positive number independent of @xmath6 and @xmath0 . hence , the * qs * algorithm enjoys an optimality property also in the average - probabilistic setting for the measure @xmath470 as long as we use it with @xmath6 divisible by @xmath9 . we now turn to the measure @xmath472 . clearly , the average - probabilistic error of the * qs * algorithm is bounded by its worst - probabilistic error , which is of order @xmath11 with probability @xmath483 $ ] . it turns out , again due to a recent result of papageorgiou @xcite that this bound is the best possible , since any quantum algorithm that uses @xmath6 quantum queries must have an error proportional at least to @xmath11 . hence , the factor @xmath32 that is present for the measure @xmath470 does not appear for the measure @xmath472 , and the behavior of the * qs * algorithm is roughly the same in the worst- and average - probabilistic settings . we are grateful for many valuable comments on this paper from j. creutzig , a. papageorgiou , j. f. traub , and a.g . werschulz . l. grover , a fast quantum mechanical algorithm for database search , proceedings of the 28th annual acm symposium on the theory of computing ( stoc ) , 212 - 219 , 1996 , http://arxiv.org/quant-ph/9605043 , 1996 . a. nayak and f. wu , the quantum query complexity of approximating the median and related statistics , proceedings of the 31th annual acm symposium on the theory of computing ( stoc ) , 384 - 393 , 1999 , http://arxiv.org/quant-ph/9804066 , 1998 .
we study the quantum summation ( * qs * ) algorithm of brassard , hyer , mosca and tapp , see @xcite , that approximates the arithmetic mean of a boolean function defined on @xmath0 elements . 
 we improve error bounds presented in @xcite in the worst - probabilistic setting , and present new error bounds in the average - probabilistic setting .    in particular , in the worst - probabilistic setting , we prove that the error of the * qs * algorithm using @xmath1 quantum queries is @xmath2 with probability @xmath3 , which improves the error bound @xmath4 of @xcite . 
 we also present error bounds with probabilities @xmath5 $ ] , and show that they are sharp for large @xmath6 and @xmath7 .    in the average - probabilistic setting , we prove that the * qs * algorithm has error of order @xmath8 iff @xmath6 is divisible by @xmath9 . 
 this bound is optimal , as recently shown in @xcite . for @xmath6 
 not divisible by @xmath9 , the * qs * algorithm is far from being optimal if @xmath10 since its error is proportional to @xmath11 .