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


2 Answers 2


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

  • 1
    $\begingroup$ 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{+}$? $\endgroup$
    – Freeman
    Commented Feb 22, 2013 at 14:45
  • $\begingroup$ 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$. $\endgroup$ Commented Feb 22, 2013 at 14:50
  • $\begingroup$ 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? $\endgroup$
    – Freeman
    Commented Feb 22, 2013 at 14:53
  • $\begingroup$ 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. $\endgroup$ Commented Feb 22, 2013 at 15:39
  • $\begingroup$ $\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{+}$? $\endgroup$
    – Freeman
    Commented Feb 22, 2013 at 15:48

Let me try to explain the last part in a simple way:

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


$ |s_{1} s_{2} s_{3} \rangle \otimes |- \rangle$

where each $s_i$ is either $|+ \rangle$ or $|- \rangle$, depending on whether $a_{i}$ is $0$ or $1$.

Hence, you can read each bit of $a$ by measuring the $|s_{1} s_{2} s_{3} \rangle$ in the Hadamard basis.


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.