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!
Best Answer
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$.