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

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

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

• I'm asking about how Fourier sampling solves the parity problem @glS – Sanchayan Dutta Mar 17 '18 at 11:05
• You can clarify that in the question. Also, I don't fully understand the relevance of the Hadamard transform with the rest of the question – glS Mar 17 '18 at 11:07
• @glS They're using the Hadamard transform in the final gate they're building (see last image). I just wrote down whatever was in the video so that people don't have to refer to the video again and again. – Sanchayan Dutta Mar 17 '18 at 11:09

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

• Note: I've just realised I'm not sure on the best way to word "You then rotate each qubit in this superposition state using an operation equivalent to XOR (in this new basis)" – Mithrandir24601 Mar 17 '18 at 11:39
• I couldn't understand the step $\left(-1\right)^{x.\left(u\oplus y\right)} = 0$. $-1$ raised to any real number power, does not equal $0$. Did you mean something else? That step isn't clear to me. – Sanchayan Dutta Apr 15 '18 at 7:11
• Indeed it doesn't - it's when summing over $x$ that it gives $0$ - for $u\oplus y\neq 0$, there are an equal number of odd terms and even terms in $\sum_xx\cdot \left(u\oplus y\right)$ (there's that implicit $\mod 2$). That is, it's a balanced function and everything boils down to $\left(-1\right)+1 = 0$. I'll fix that typo now – Mithrandir24601 Apr 15 '18 at 8:56