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!


1 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.

  • $\begingroup$ Your transformation $$\frac1{N} \sum_x \rvert x\rangle \rvert 0 \rangle \to \frac1{N} \sum_x \rvert x\rangle \rvert f(x) \rangle.$$ is not the same as what I see being the standard meaning of ''single query to $f$ in superposition" which is given as, $$ \frac{1}{\sqrt{2^n} } \sum_{x \in \{ 0,1\}^n} |x\rangle \to \frac{1}{\sqrt{2^n} } \sum_{x \in \{ 0,1\}^n} f(x) |x\rangle$$ $\endgroup$
    – user6818
    Commented Aug 10, 2015 at 21:17
  • $\begingroup$ They can be equivalent. Assume f(x) is binary (e.g. when the oracle is yes/no, as in search algorithms). Then one definition is $$|x\rangle|y\rangle \to |x\rangle|y\oplus f(x)\rangle.$$ But let $|y\rangle=(|0\rangle-|1\rangle)/\sqrt2$ and see the magic: if $f(x)=0$ nothing happens, but if $f(x)=1$, the outputs is now $(|1\rangle-|0\rangle)/\sqrt2=-|y\rangle$, and you get that the oracle is equivalent to $$|x\rangle|y\rangle \to (-1)^{f(x)}|x\rangle|y\rangle.$$ See also Nielsen and Chuang, Chap 6. $\endgroup$
    – Ran G.
    Commented Aug 10, 2015 at 22:47
  • $\begingroup$ I am not sure you are getting the issue here. The two transformations that I wrote in the first comment are possible in two non-isomorphic vector spaces. Even if $f$ is Boolean valued, the first one is a transformation in a space of dimension $2^{n+1}$ but the later is a transformation in a vector space of dimension $2^n$. An operator which can effect the first can't effect the second. The two can't be "equal" definitions of what a "single quantum query to $f$" means. $\endgroup$
    – user6818
    Commented Aug 11, 2015 at 3:18
  • $\begingroup$ (Given a system of $n$ qubits I would believe that there exists an universal definition of what is the operator that effects a "single quantum query to $f$") $\endgroup$
    – user6818
    Commented Aug 11, 2015 at 3:21
  • $\begingroup$ I believe you give to much credit to a notion of "single quantum query". It is not set in stone. It is whatever people use and whatever makes sense. I don't see the problem you are trying to state in your comment - if you ignore the second subsystem (the "y" part) the two transformations are equivalent (not equal, but equivalent). In my understanding (which may be wrong), when the funciton acts onto the same space I'd call it a gate (e.g., the Fourier gate). To me, a query is of the form I have in my answer. Again, these are conventions rather than "truth". We can continue in the Computer Science Chat. $\endgroup$
    – Ran G.
    Commented Aug 11, 2015 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.