$e_{j_0}\otimes\dots\otimes e_{j_{m-1}}$ with $i=\sum_{k=0}^{m-1}j_k2^{m-1-k}$. Let $\mathcal{U}(H_m)$ denote the set of unitary operators on $H_m$.

A quantum query on $F$ is given by a tuple $$Q=(m,m',m'',Z,\tau,\beta),$$ where $m,m',m''\in {{\mathbb N}}, m'+m''\le m, Z\subseteq {{\mathbb Z}}[0,2^{m'})$ is a nonempty subset, and $$\tau:Z\to \Lambda$$ $$\beta:K\to{{\mathbb Z}}[0,2^{m''})$$ are arbitrary mappings. Let $m(Q):=m$ denote the number of qubits of $Q$.

Given a query $Q$, we define for each $f\in F$ the unitary operator $Q_f\in\mathcal{U}(H_m)$ by setting for $\lg i\rs\lg x\rs\lg y\rs\in \mathcal{C}_m
=\mathcal{C}_{m'}\otimes\mathcal{C}_{m''}\otimes\mathcal{C}_{m-m'-m''}$: $$Q_f\lg i\rs\lg x\rs\lg y\rs=
\left\{\begin{array}{ll}
\lg i\rs\lg x\oplus\beta(f(\tau(i)))\rs\lg y\rs &\quad \mbox {if} \quad i\in Z\\
\lg i\rs\lg x\rs\lg y\rs & \quad\mbox{otherwise,} 
 \end{array}
\right.$$ where $\oplus$ means addition modulo $2^{m''}$.

A quantum algorithm on $F$ with no measurement is a tuple $$A=(Q,(U_j)_{j=0}^n),$$ where $Q$ is a quantum query on $F$, $n\in{{\mathbb N}}_0$ and $U_{j}\in \mathcal{U}(H_m)\,(j=0,\dots,n)$, with $m=m(Q)$. Given $f\in F$, we define $A_f\in \mathcal{U}(H_m)$ as $$A_f = U_n Q_f U_{n-1}\dots U_1 Q_f U_0.$$ We denote by $n_q(A):=n$ the number of queries and by $m(A)=m=m(Q)$ the number of qubits of $A$. Let $(A_f(x,y))_{x,y\in {{\mathbb Z}}[0,2^m)}$ be the matrix of the transformation $A_f$ in the canonical basis $\mathcal{C}_{m}$.

A quantum algorithm from $F$ to $G$ with $k$ measurements is a tuple $$A=((A_l)_{l=0}^{k-1},(b_l)_{l=0}^{k-1},\varphi),$$ where $k\in{{\mathbb N}}$, 