Characterization of exact one-query quantum algorithms

The quantum query model is one of the most important models in quantum computing. Several well-known quantum algorithms are captured by this model, including the Deutsch-Jozsa algorithm, the Simon algorithm, the Grover algorithm, and others. In this paper, we characterize the computational power of exact one-query quantum algorithms. It is proved that a total Boolean function $f:{\{0,1\}}^n\to \{0,1\}$ can be exactly computed by a one-query quantum algorithm if and only if $f\left(x\right)=x_{i_1}$ or $x_{i_1}\oplus x_{i_2}$ (up to isomorphism). Note that, unlike most work in the literature based on the polynomial method, our proof does not resort to any knowledge about the polynomial degree of $f$.

Figure 1

Classical oracle.

Figure 2

A decision tree $T$ for computing $f\left(x\right)=x_1\wedge (x_2\vee x_3)$.

Figure 3

Quantum oracle.

Figure 4

$T$-query quantum algorithm.

Figure 5

One-query quantum algorithm.