# Quantum Circuit, example of the Bernstein-Vazirani problem

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!

-

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

-
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