An Introduction to Quantum Computing - Exercise 6.4.1

The Exercise 6.4.1 from Kaye et al. is as follows

Prove that $$\bigg({|0\rangle +(-1)^{x_1}|1\rangle \over\sqrt{2}}\bigg)\cdot\bigg({|0\rangle +(-1)^{x_2}|1\rangle \over\sqrt{2}}\bigg)\cdots\bigg({|0\rangle +(-1)^{x_n}|1\rangle \over\sqrt{2}}\bigg)$$ $$={1\over\sqrt{2^n}}\sum_{z_1z_2...z_n\in\{0,1\}^n} (-1)^{x_1z_1+x_2z_2+...+x_nz_n}|z_1\rangle|z_2\rangle...|z_n \rangle\tag{1}$$

Can anyone help me understand the math to solve the problem above? I am not sure how to achieve the final state that the problem is asking for. So far, I have done the following:

$$\bigg({|0\rangle +(-1)^{x_1}|1\rangle \over\sqrt{2}}\bigg)\cdot\bigg({|0\rangle +(-1)^{x_2}|1\rangle \over\sqrt{2}}\bigg)\cdots\bigg({|0\rangle +(-1)^{x_n}|1\rangle \over\sqrt{2}}\bigg)$$ $$={1\over\sqrt{2^n}}({|0\rangle +(-1)^{x_1}|1\rangle})\cdot({|0\rangle +(-1)^{x_2}|1\rangle})\cdots({|0\rangle +(-1)^{x_n}|1\rangle})\tag{2}$$ From here, I am aware that this needs to turn into a summation such that:

$$={1\over\sqrt{2^n}}\sum_{z_1z_2...z_n\in\{0,1\}^n} \cdots\cdots\cdots\tag{3}$$

However, I am not sure what actually goes inside the summation.

• This looks like a calculation that is usually done as part of the Deutsch–Jozsa algorithm. Some proof details are given here en.wikipedia.org/wiki/Deutsch%E2%80%93Jozsa_algorithm. Do you need more details than that? Mar 25 at 18:38
• @NickMertes Yes I need an in depth explanation on how the math works here since I am unsure on what goes in the summation and why. Mar 25 at 22:21

2 Answers

The proof of this would be quite empirical in nature. You can rewrite your state in terms of product as follows: $$\frac{1}{\sqrt{2^n}} \prod_{i=1}^n (|0\rangle + (-1)^{x_i}|1\rangle)$$ We can write the inner term $$|0\rangle + (-1)^{x}|1\rangle$$ as a summation $$\sum_{z=0}^1 (-1)^{x\cdot z}|z\rangle$$ where both $$x, z$$ belong to the binary field and the operation $$x\cdot z$$ is the AND operation. You can now write the original term as: $$\frac{1}{\sqrt{2^n}} \prod_{i=1}^n \sum_{z=0}^1 (-1)^{x_i\cdot z}|z\rangle$$

Combine the sum and the product by considering a cartesian product and indexing the inner $$z$$ as $$z_1,\dots z_n$$

$$\frac{1}{\sqrt{2^n}} \sum_{z_1,\dots z_n=0}^1 (-1)^{x_1 \cdot z_1} \cdots(-1)^{x_n \cdot z_n} |z_1\rangle \cdots |z_n\rangle$$

It does not take much effort to convert it the final format you have written from the above state.

A way to see how this identity comes about is to simply work out the first few terms from your Eq.(2) upon expanding the terms inside brackets. You will notice that qubit $$k$$ will contribute with a factor of $$(-1)^{x_{k}}$$ whenever it is on state $$|1 \rangle$$, and with a factor of $$1$$ when it is on $$|0\rangle$$.

This can be written more formally as, a qubit $$k$$, in a state $$|z_{k}\rangle$$ with $$z_{k}=0,1$$, will contribute with a factor $$(-1)^{x_{k}z_{k}}$$. If you choose either value of $$z_{k}$$, you will retrieve the statement above. Using this observation, you can combine the contribution from all the qubits and see that it indeed can be written as a sum of all possible combinations of $$z_{k}$$ with $$k=1,\dots,n$$, given that all qubits are in superposition, and an overall factor of $$(-1)^{x_{1}z_{1} + x_{2}z_{2} + \dots + x_{n}z_{n}}$$.

• I appreciate the help but this doesn't really answer my question, I am looking for a mathematical proof. Mar 26 at 11:02
• @afarouz I am not sure what do you mean by a mathematical proof, given that my comment above does not require any non-quantitative steps. The answer from Zee above also explains it but being more mathematically explicit, if that helps. Mar 27 at 0:59