Take the 2-minute tour ×
Physics Stack Exchange is a question and answer site for active researchers, academics and students of physics. It's 100% free, no registration required.

This question is regarding the quantum circuit in the picture below.

Suppose we have the set up below, where U performs the operation $U:\mid x \rangle \mid y \rangle \rightarrow \mid x \rangle\mid y \oplus f(x) \rangle$.

We define the function $f(x)$ on the 3-bit string $\mid x \rangle= \mid x_1 x_2 x_3 \rangle$ with $f(x)=a\cdot x=a_1 x_1 \oplus a_2 x_2 \oplus a_3 x_3$, where $\oplus$ is addition modulo 2 and $a$ is the fixed three bit string $\mid a \rangle=\mid a_1 a_2 a_3 \rangle$.

The objective is to show how this circuit finds $a$.

So far I have that the 3 zero qubits pass through 3 Hadamard gates, putting them in the bell state $\beta_{00}=\frac{1}{\sqrt2}(\mid 0 \rangle +\mid 1 \rangle)$. So at point 1 on the circuit the system has state:

$$\frac14(\mid 0 \rangle +\mid 1 \rangle)(\mid 0 \rangle +\mid 1 \rangle)(\mid 0 \rangle +\mid 1 \rangle)(\mid 0 \rangle -\mid 1 \rangle)=\frac14 \sum_{x\in\{0,1\}^3} \mid x \rangle(\mid 0 \rangle -\mid 1 \rangle$$

Where we have found the RHS by expanding out and summing over all the possible 3 but qubits.

So next we consider what happens when the system passes through the $U$ gate, we find:

$$\frac14 \sum_{x\in\{0,1\}^3} \mid x \rangle(\mid f(x) \rangle -\mid 1 \oplus f(x) \rangle )$$

Here we notice that is $f(x)$ is $0$ nothing changes, but if it is $1$ it acts as a factor of $-1$, therefore the system is:

$$\frac14 \sum_{x\in\{0,1\}^3} (-1)^{f(x)}\mid x \rangle(\mid 0 \rangle -\mid 1 \rangle )$$

Now $f(x)$ outputs sums of the elements of $a$ depending on the value of $x$, for example for $\mid x \rangle = \mid 110 \rangle$, $f(x)=f(110)=a_1 \oplus a_2$. Would anyone be able to help me understand how this helps us find the three values for $a$ at our measured gates? The main issue i'm finding is finding a useful of writing an expression for the system after it has passed through the last three Hadamard gates, one which we can use to find $a$, any help would be greatly appreciated!

Figure 1

share|improve this question

1 Answer 1

You're missing the action of the second set of Hadamards.

Your state at stage 2 is, as you say, $$\newcommand{\ket}[1]{|#1\rangle}\ket{\psi_2}=\frac1{2^{n/2}}\sum_x (-1)^{f(x)}\ket{x}\ket{-}.$$ Applying the Hadamards will take this to $$\ket{\psi_3}=\frac1{2^{n/2}}\sum_x (-1)^{f(x)}H^{\otimes n}\ket{x}\ket{-} =\frac1{2^{n/2}}\sum_x (-1)^{f(x)}\ket{(-)^{x_1}}\cdots\ket{(-)^{x_n}}\ket{-},$$ i.e. $$\ket{\psi_3}=\frac1{2^{n}}\sum_x (-1)^{f(x)}\sum_y(-1)^{x\cdot y}\ket{y}\ket{-}.$$

The probability amplitude of measuring the state $\ket{y}$ is then $$a(y)=\frac1{2^{n}}\sum_x (-1)^{f(x)}(-1)^{x\cdot y}=\frac{1}{2^n}\prod_{j=1}^n\left(1+(-1)^{a_j\oplus y_j}\right),$$ which vanishes unless $y=a$.

Thus for linear $f$, the complicated wave created by its unitary $U$ will be made by the Hadamards to re-interfere into a product state that allows a direct read-out of $f$.

share|improve this answer
Thank you for this, it is great, just working out exactly what you mean. What do you mean by $N$ & $H^{\otimes N}$, we are applying $H\otimes H\otimes H\otimes 1$ to the system correct? So can we just write $N=3$? Also some of the elements of $x$ are $0$ which will be taken to $\ket{+}$? –  Freeman Feb 22 '13 at 14:45
Yes, $N=3$. The tensor power notation is right. Under $H$, $|0\rangle$ goes to $|+\rangle$ and $|1\rangle$ goes to $|-\rangle$, so $|x_j\rangle$ goes to $|(-1)^{x_j}\rangle$. –  Emilio Pisanty Feb 22 '13 at 14:50
Ok, great, so I guess your description was a general one. So wrt to your second statement, wouldn't $|(-1)^{x_j}\rangle=\ket{0}$ or $\ket{-1}$ not $\ket{+}$ or $\ket{-}$?, so our three string vector $\ket{x}=\ket{x_1 x_2 x_3}$ would go to a product of some combination of $\ket{+}$ and $\ket{-}$ under the Hadamard gate? –  Freeman Feb 22 '13 at 14:53
No. $(-)^0=+$ and $(-)^1=-$. And yes, $|x\rangle$ goes to a combination of $|+\rangle$ and $|-\rangle$'s as shown. You then decompose this into the computational basis $\{|y\rangle\}$ to get the final measurement amplitudes. You need to spend (far) more time going through the derivation in detail. –  Emilio Pisanty Feb 22 '13 at 15:39
$\ket{-}=\frac{1}{\sqrt2}(\ket{0}-\ket{1}) \Rightarrow (\ket{-})^0=(\frac{1}{\sqrt2}(\ket{0}-\ket{1}))^0$, I don't see how this equals $\ket{+}=\frac{1}{\sqrt2}(\ket{0}+\ket{1})$? Wouldn't it be $\Big(\begin{matrix} 1 \\ 1 \end{matrix} \Big)=\sqrt2 \ket{+}$? –  Freeman Feb 22 '13 at 15:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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