What can a quantum query to a function do? The $n$-qubit Hadamard gate acts as,
$$H (\otimes^n \vert 0 \rangle ) = \otimes ^n ( H | 0 \rangle ) = \otimes ^n ( \frac { |0\rangle + |1\rangle }{\sqrt{2} } ) = \frac{1}{\sqrt{2^n} } \sum_{x \in \{ 0,1\}^n} |x\rangle $$
So it is capable of producing the uniform superposition state over an exponential number of states in what is to be seen as a ``single&quot; step.

Now if one is given a boolean function $f$ then how is it that the above uniform superposition state can be converted into   $\frac{1}{\sqrt{2^n} } \sum_{x \in \{ 0,1\}^n} f(x) |x\rangle$ by a ``single query to $f$ in superposition&quot; ?
Can someone give a mathematical or a gate picture of this ''single query to $f$ in superposition&quot; ? What is the unitary operator which corresponds to this ''single query to $f$ in superposition&quot;  ?



A part of this confusion arises because I am under the impression that if kets are indexed by elements of $\{0,1\}^n$ then a ''single&quot; quantum query to a Boolean valued function $f$ is ``by definition&quot; a transformation of the form  $\vert x \rangle \vert y \rangle \rightarrow \vert x \rangle \vert y \oplus f(x) \rangle$ or which is often thought of as the operator $O_f(x)$ acting as $O_f(x) \vert y \rangle =  \vert y \oplus f(x) \rangle$
But I can't see the transformation in the question as a any combination of $O_f(x)$ kind of operators!
the gate $f$ performs the transformation 
$$\rvert x\rangle \rvert0\rangle \to \rvert x\rangle \rvert 0\oplus f(x)\rangle, $$

but $0$ is idempotent for $\oplus$ so you simply get $\rvert x\rangle \rvert f(x)\rangle$.
Now, by linearity, if you input a superposition instead of a basis states, you'll get a superposition of the "answers", e.g.,

$$\frac1{\sqrt2}(\rvert 0\rangle \rvert0\rangle+\rvert1\rangle |0\rangle) \to \frac1{\sqrt2}(\rvert 0\rangle \rvert f(0)\rangle+\rvert 1\rangle \rvert f(1)\rangle)$$

Then, if you start with a Hadamard, and get an equal superposition of all basis states, you end up with a superposition of all possible "answers".
$$\frac1{N} \sum_x \rvert x\rangle \rvert 0 \rangle \to \frac1{N} \sum_x \rvert x\rangle \rvert f(x) \rangle.$$

The fact that $x$ or $0$ are in fact a "string" over $\{0,1\}$ doesn't make any difference - treat them as a single quantum system of higher dimension (or treat each qubit as a separate function $f_i$ where $f_1()f_2()\cdots f_n()=f()$ are the bit-wise functions.