}(i)\in G$ with probability $|a_{i,f}|^2$. As shown in [@Hei01], Lemma 1, for each algorithm $A$ with $k$ measurements there is an algorithm ${\widetilde }{A}$ with one measurement such that $A(f)={\widetilde }{A}(f)$ for all $f\in F$ and ${\widetilde }{A}$ uses just twice the number of queries of $A$.

For $\theta\ge 0$ and a quantum algorithm $A$ we define the (probabilistic) error at $f\in F$ as follows. Let $\zeta$ be a random variable with distribution $A(f)$. Then $$e(S,A,f,\theta)=\inf\left\{\varepsilon\ge0\,\,|\,\,{{\mathbb P}}\{\|S(f)-\zeta\|>\varepsilon\}\le\theta
\right\}$$ (observe that this infimum is always attained). Let $$e(S,A,F,\theta)=\sup_{f\in F} e(S,A,f,\theta)$$ (this quantity can take the value $+\infty$). Furthermore, we set $$\begin{aligned}
\lefteqn{e_n^{{\rm q }}(S,F,\theta)}\\
&=&\inf\{e(S,A,F,\theta)\,\,|\,\,A\,\,
\mbox{is any quantum algorithm with}\,\, n_q(A)\le n\}.\end{aligned}$$ We denote $$e(S,A,f)=e(S,A,f,1/4)$$ and similarly, $$e(S,A,F)=e(S,A,F,1/4),\quad e_n^{{\rm q }}(S,F)=e_n^{{\rm q }}(S,F,1/4).$$ The quantity $e_n^{{\rm q }}(S,F)$ is the $n$-th minimal query error, that is, the smallest error which can be reached using at most $n$ queries. Note that it essentially suffices to study $e_n^{{\rm q }}(S,F)$ instead of $e_n^{{\rm q }}(S,F,\theta)$, since with $\mathcal{O}(\nu)$ repetitions, the error probability can be reduced to $2^{-\nu}$ (see Lemmas 3, 4 and Corollary 1 of [@Hei04a]).

The quantum query complexity is defined for $\varepsilon > 0$ by $$\begin{aligned}
\lefteqn{\mbox{comp}_\varepsilon^{{\rm q }}(S,F)=}\\
&&\min\{n_q(A)\,\,|\,\, A\,\,\mbox{is 