How does Fourier sampling actually work (and solve the parity problem)?

Question

I'm writing with respect to part I and part II of the Fourier sampling video lectures by Professor Umesh Vazirani.

In part I they start with:

In the Hadamard Transform:

$$|0...0\rangle \to \sum_{\{0,1\}^n}\frac{1}{2^{n/2}}|x\rangle$$ $$|u\rangle =|u_1...u_n\rangle \to \sum_{\{0,1\}^n}\frac{(-1)^{u.x}}{2^{n/2}}|x\rangle \quad \text{(where $u.x=u_1x_1+u_2x_2+...+u_nx_n$)}$$

In Fourier Sampling:

$$|\psi\rangle=\sum_{\{0,1\}}^{n}\alpha_x|x\rangle \to \sum_{x}\hat{\alpha_x}|x\rangle=|\hat{\psi}\rangle$$

When $|\hat{\psi}\rangle$ is measured we see $x$ with probability $|\hat{\alpha_x}|^2$.

In part II:

The Parity Problem:

We are given a function $f:\{0,1\}^n\to\{0,1\}$ as a black box. We know that $f(x)=u.x$ (i.e. $u_1x_1+u_2x_2+...+u_nx_n (\text{mod 2})$) for some hidden $u\in\{0,1\}^{n}$. How do we figure out $u$ with as few queries to $f$ as possible?

They say that we need to follow a two step procedure for figuring out $u$ in minimum possible number of steps.

• Set up a superposition $\frac{1}{2^{n/2}}\sum_{x}(-1)^{f(x)}|x\rangle$

• Fourier sample to obtain $u$.

This is where I got lost. I don't understand what exactly they mean by "set up a superposition...". Why should we do it? And how does Fourier sampling (as described) help to determine $u$ ?

They further build a quantum gate like this:

Even this doesn't make sense to me. They're performing Hadamard transforms on a set of n-qubits having state $|0\rangle$ and then bit flip and again Hadamard transform. So we get back to where we were initially. How does an extra $|-\rangle$ state input help by outputting $- \oplus f(0...0)$? I'm not even sure what operation $\oplus$ stand for, here.

Answer 1

Starting from the beginning (a very good place to start, after all), the state $\left| 0\right\rangle^{\otimes n}\left| -\right\rangle$ is input into $H^{\otimes n}\otimes I$ (here, called the 'Fourier sample'). This generates the state $$\left(\sum_{x=\{0,1\}^n}\frac{1}{2^{n/2}}|x\rangle\right)\left|-\right\rangle = \frac{1}{2^{n/2}}\left(\left|0\right\rangle + \left|1\right\rangle\right)^{\otimes n}\left|-\right\rangle.$$ Now, we apply the operation $U_f$ (in this case, the bit oracle) to give $$U_f\left(\sum_{x=\{0,1\}^n}\frac{1}{2^{n/2}}|x\rangle\right)\left|-\right\rangle = \sum_{x=\{0,1\}^n}\frac{1}{2^{n/2}}|x\rangle\left|-\oplus f\left(x\right)\right\rangle.$$

The first point to note is that $\oplus$ is the classical XOR operation. What this gives is actually the phase oracle, so that we get $$\left(\sum_{x=\{0,1\}^n}\frac{1}{2^{n/2}}\left(-1\right)^{f\left(x\right)}\left|x\right\rangle\right)\left|-\right\rangle.$$ This is because $U_f\left|x\right\rangle\left(\left|0\right\rangle - \left|1\right\rangle\right) = \left|x\right\rangle\left|f\left(x\right)\right\rangle - \left|x\right\rangle\left|1\oplus f\left(x\right)\right\rangle = \left(-1\right)^{f\left(x\right)}\left|x\right\rangle\left(\left|0\right\rangle - \left|1\right\rangle\right)$. This is the 'set up a superposition...' point - all this means is to perform the operations required to set the qubits in the above state, which is a superposition of all possible states (with phase factors, in this case). In this case, this is just Hadamard, followed by a phase oracle.

Now, $x$ is just a classical bit string: $x = \prod_ix_i$, so $$H\left|x_i\right\rangle = \frac{1}{\sqrt{2}}\left(\left|0\right\rangle + \left(-1\right)^{x_i}\left|1\right\rangle\right) = \frac{1}{\sqrt{2}}\sum_{y=\left\lbrace0, 1\right\rbrace}\left(-1\right)^{x_i.y}\left|y\right\rangle.$$

This gives the property $$H^{\otimes n}\left| x\right\rangle = \frac{1}{2^{n/2}}\sum_{y\in\left\lbrace0, 1\right\rbrace^n}\left(-1\right)^{x.y}\left|y\right\rangle.$$

This gives the final state as $$\frac{1}{2^n}\left(\sum_{x, y=\{0,1\}^n}\left(-1\right)^{f\left(x\right) \oplus x.y}\left|y\right\rangle\right)\left|-\right\rangle.$$

We know that $f\left(x\right) = u.x = x.u$, giving $\left(-1\right)^{f\left(x\right) \oplus x.y} = \left(-1\right)^{x.\left(u\oplus y\right)}$. Summing over the $x$ terms gives that $\sum_x\left(-1\right)^{x.\left(u\oplus y\right)} = 0,\, \forall\, u\oplus y \neq 0$. This means that we're left with the term for $u\oplus y = 0$, which means that $u=y$, giving the output as $\left|u\right\rangle\left|-\right\rangle$, which is measured to obtain $u$.

As for why we want to set up a superposition: This is where the power of quantum computing comes into play - In less mathematical terms, applying the Hadamard transformation is performing a rotation on the qubit states to get into the state $\left|+\right\rangle^{\otimes n}$. You then rotate each qubit in this superposition state using an operation equivalent to XOR (in this new basis), so that when performing the Hadamard transformation again, you're now just rotating back onto the state $\left|u\right\rangle$. Another way of looking at this is to consider it as a reflection or inversion that achieves the same result.

The point is that, using superposition, we can do this to all the qubits at the same time, instead of having to individually check each qubit as in the classical case.