What can a quantum query to a function do?

Question

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" 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" ?

  Can someone give a mathematical or a gate picture of this ''single query to $f$ in superposition" ? What is the unitary operator which corresponds to this ''single query to $f$ in superposition" ?

---

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" quantum query to a Boolean valued function $f$ is ``by definition" 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!

Answer 1

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.