patternMinor
What can a quantum query to a function do?
Viewed 0 times
canwhatqueryfunctionquantum
Problem
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 `
But I can't see the transformation in the question as a any combination of $O_f(x)$ kind of operators!
$$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!
Solution
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.
$$\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.
Context
StackExchange Computer Science Q#45129, answer score: 5
Revisions (0)
No revisions yet.