Solutions: Quantum Computation and Quantum Information by Nielsen and Chuang

Solutions: Quantum Computation and Quantum Information by Nielsen and Chuang

Chapter 6

6.1

$$ \begin{align} 2\left|0\right\rangle\left\langle0\right|-I &= 2\left|0\right\rangle\left\langle0\right|-\sum_{j=0}^{2^n-1}\left|j\right\rangle\left\langle j\right| \\ &= \left|0\right\rangle\left\langle0\right| - \sum_{j=1}^{2^n-1}\left|j\right\rangle\left\langle j\right| \\ &= \begin{pmatrix} 1 & & & & 0 \\ & -1 & & & \\ & & -1 & & & \\ & & & \ddots & \\ 0 & & & & -1 \end{pmatrix} \end{align} $$

6.2

$$ \begin{align} \left(2\left|\psi\right\rangle\left\langle\psi\right|-I\right)\sum_k \alpha_k\left|k\right\rangle &= \left(\frac{2}{N}\sum_{x,y=0}^{N-1}\left|x\right\rangle\left\langle y\right|-I\right)\sum_k\alpha_k\left|k\right\rangle \\ &= \frac{2}{N}\sum_{x=0}^{N-1}\sum_k\alpha_k\left|x\right\rangle-\sum_k\alpha_k\left|k\right\rangle \\ &= 2\sum_{x=0}^{N-1}\left\langle\alpha\right\rangle\left|x\right\rangle-\sum_k\alpha_k\left|k\right\rangle \\ &= \sum_k \left[-\alpha_k+2\left\langle\alpha\right\rangle\right]\left|k\right\rangle \end{align} $$

6.3

Clearly, $G$ corresponds to the $\theta$-rotation in $\left|\alpha\right\rangle-\left|\beta\right\rangle$ plane because $O$ is the $-\theta$ rotation followed by $2\theta$ rotation. So it’s described as eq. $6.13$.


6.4

The register qubit is transformed into $\left|\beta\right\rangle$, which is the linear combination of the solutions. Then, we need to do the procedure (step 1 - step 4) many times and can determine the solutions from meaurement statistics.


6.5

circuit_6_5


6.6

circuit_6_6

Let $\left|\phi_1\right\rangle=a_1\left|0\right\rangle+b_1\left|1\right\rangle$, $\left|\phi_2\right\rangle=a_2\left|0\right\rangle+b_2\left|1\right\rangle$.

$$ \begin{align} \left|\psi_0\right\rangle &= \left(a_1\left|0\right\rangle+b_1\left|1\right\rangle\right)\left(a_2\left|0\right\rangle+b_2\left|1\right\rangle\right) \\ \left|\psi_1\right\rangle &= \left(b_1\left|0\right\rangle+a_1\left|1\right\rangle\right)\left(b_2\left|0\right\rangle+a_2\left|1\right\rangle\right) \\ \left|\psi_2\right\rangle &= \left(b_1\left|0\right\rangle+a_1\left|1\right\rangle\right)\frac{1}{\sqrt{2}}\left(\left(a_2+b_2\right)\left|0\right\rangle+\left(b_2-a_2\right)\left|1\right\rangle\right) \\ \left|\psi_3\right\rangle &= \frac{b_1}{\sqrt{2}}\left|0\right\rangle\left(\left(a_2+b_2\right)\left|0\right\rangle+\left(b_2-a_2\right)\left|1\right\rangle\right)+\frac{a_1}{\sqrt{2}}\left|1\right\rangle\left(\left(b_2-a_2\right)\left|0\right\rangle+\left(a_2+b_2\right)\left|1\right\rangle\right) \\ \left|\psi_4\right\rangle &= b_1\left|0\right\rangle\left(b_2\left|0\right\rangle+a_2\left|1\right\rangle\right)+a_1\left|1\right\rangle\left(b_2\left|0\right\rangle-a_2\left|1\right\rangle\right) \\ \left|\psi_5\right\rangle &= a_1\left|0\right\rangle\left(-a_2\left|0\right\rangle+b_2\left|1\right\rangle\right)+b_1\left|1\right\rangle\left(a_2\left|0\right\rangle+b_2\left|1\right\rangle\right) \\ &= -\left(a_1a_2\left|00\right\rangle-a_1b_2\left|01\right\rangle-b_1a_2\left|10\right\rangle-b_1b_2\left|11\right\rangle\right) \\ &= -\left(2\left|00\right\rangle - I\right)\left|\phi_1\phi_2\right\rangle \end{align} $$

6.7

circuit_6_7_1

$$ \begin{align} \mathrm{e}^{-i\left|x\right\rangle\left\langle x\right|\Delta t} &= \sum_{j=0}^{\infty}\frac{\left(-i\left|x\right\rangle\left\langle x\right|\Delta t\right)^j}{j!} \\ &= I+\left(-i\left|x\right\rangle\left\langle x\right|\Delta t\right)+\frac{\left(-i\left|x\right\rangle\left\langle x\right|\Delta t\right)^2}{2}+\frac{\left(-i\left|x\right\rangle\left\langle x\right|\Delta t\right)^3}{6}+\cdots \\ &= I+\left(-i\Delta t\right)\left|x\right\rangle\left\langle x\right|+\frac{\left(-i\Delta t\right)^2}{2}\left|x\right\rangle\left\langle x\right|+\frac{\left(-i\Delta t\right)^3}{6}\left|x\right\rangle\left\langle x\right|+\cdots \\ &= I+\left[\sum_{j=1}^{\infty}\frac{\left(-i\Delta t\right)^j}{j!}\right]\left|x\right\rangle\left\langle x\right| \\ &= I-\left(-i\Delta t\right)^0\left|x\right\rangle\left\langle x\right|+\left[\sum_{j=0}^{\infty}\frac{\left(-i\Delta t\right)^j}{j!}\right]\left|x\right\rangle\left\langle x\right| \\ &= I-\left|x\right\rangle\left\langle x\right|+\mathrm{e}^{-i\Delta t}\left|x\right\rangle\left\langle x\right| \\ &= \left|y\right\rangle\left\langle y\right|+\mathrm{e}^{-i\Delta t}\left|x\right\rangle\left\langle x\right|. \end{align} $$

Now we calculate the effect of the above circuit on $\left|y\right\rangle\left|0\right\rangle$.

$$ \begin{align} \left|\psi_0\right\rangle &= \left|y\right\rangle\left|0\right\rangle \\ &= I\left|y\right\rangle\left|0\right\rangle \\ &= \left(\left|x\right\rangle\left\langle x\right| + \left|y\right\rangle\left\langle y\right|\right)\left|y\right\rangle\left|0\right\rangle \\ &= \left\langle x\middle|y\right\rangle\left|x\right\rangle\left|0\right\rangle + \left\langle y\middle|y\right\rangle\left|y\right\rangle\left|0\right\rangle \\ \left|\psi_1\right\rangle &= \left\langle x\middle|y\right\rangle\left|x\right\rangle\left|1\right\rangle + \left\langle y\middle|y\right\rangle\left|y\right\rangle\left|0\right\rangle \\ \left|\psi_2\right\rangle &= \mathrm{e}^{-i\Delta t}\left\langle x\middle|y\right\rangle \left|x\right\rangle\left|1\right\rangle + \left\langle y\middle|y\right\rangle\left|y\right\rangle\left|0\right\rangle \\ \left|\psi_3\right\rangle &= \mathrm{e}^{-i\Delta t}\left\langle x\middle|y\right\rangle \left|x\right\rangle\left|0\right\rangle + \left\langle y\middle|y\right\rangle\left|y\right\rangle\left|0\right\rangle \\ &= \left(\mathrm{e}^{-i\Delta t}\left|x\right\rangle\left\langle x\right|+\left|y\right\rangle\left\langle y\right|\right)\left|y\right\rangle\left|0\right\rangle \end{align} $$

So, this circuit implements $\mathrm{e}^{-i\left|x\right\rangle\left\langle x\right|\Delta t}$.



circuit_6_7_2

$$ \begin{align} \mathrm{e}^{-i\left|\psi\right\rangle\left\langle\psi\right|\Delta t} &= \sum_{j=0}^{\infty}\frac{\left(-i\left|\psi\right\rangle\left\langle\psi\right|\Delta t\right)^j}{j!} \\ &= I+\left(-i\Delta t\right)\left|\psi\right\rangle\left\langle\psi\right| + \frac{\left(-i\Delta t\right)^2}{2}\left|\psi\right\rangle\left\langle\psi\right|+\frac{\left(-i\Delta t\right)^3}{6}\left|\psi\right\rangle\left\langle\psi\right|+\cdots \\ &= I-\left|\psi\right\rangle\left\langle\psi\right|+\mathrm{e}^{-i\Delta t}\left|\psi\right\rangle\left\langle\psi\right\rangle \end{align} $$

After applying the circuit above, we get

$$ \begin{align} \left|\psi_0\right\rangle &= \left|y\right\rangle\left|0\right\rangle \\ &= I\left|y\right\rangle\left|0\right\rangle \\ &= \left(\sum_{j=0}^{N-1}\left|j\right\rangle\left\langle j\right|\right)\left|y\right\rangle\left|0\right\rangle \\ &= \sum_{j=0}^{N-1}\left\langle j\middle|y\right\rangle\left|j\right\rangle\left|0\right\rangle \\ \left|\psi_1\right\rangle &= \sum_{j=0}^{N-1}\left\langle j\middle|y\right\rangle H^{\otimes n}\left|j\right\rangle\left|0\right\rangle \\ &= \left(\sum_{j=0}^{N-1}\left\langle j\middle|y\right\rangle H^{\otimes n}\left|j\right\rangle-\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\left\langle j\middle|y\right\rangle\left|0\right\rangle\right)\left|0\right\rangle+\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\left\langle j\middle|y\right\rangle\left|0\right\rangle\left|0\right\rangle \\ \left|\psi_2\right\rangle &= \left(\sum_{j=0}^{N-1}\left\langle j\middle|y\right\rangle H^{\otimes n}\left|j\right\rangle-\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\left\langle j\middle|y\right\rangle\left|0\right\rangle\right)\left|0\right\rangle+\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\left\langle j\middle|y\right\rangle\left|0\right\rangle\left|1\right\rangle \\ \left|\psi_3\right\rangle &= \left(\sum_{j=0}^{N-1}\left\langle j\middle|y\right\rangle H^{\otimes n}\left|j\right\rangle-\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\left\langle j\middle|y\right\rangle\left|0\right\rangle\right)\left|0\right\rangle+\mathrm{e}^{-i\Delta t}\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\left\langle j\middle|y\right\rangle\left|0\right\rangle\left|1\right\rangle \\ \left|\psi_4\right\rangle &= \left(\sum_{j=0}^{N-1}\left\langle j\middle|y\right\rangle H^{\otimes n}\left|j\right\rangle-\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\left\langle j\middle|y\right\rangle\left|0\right\rangle\right)\left|0\right\rangle+\mathrm{e}^{-i\Delta t}\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\left\langle j\middle|y\right\rangle\left|0\right\rangle\left|0\right\rangle \\ \left|\psi_5\right\rangle &= \left(\sum_{j=0}^{N-1}\left\langle j\middle|y\right\rangle\left|j\right\rangle-\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\left\langle j\middle|y\right\rangle\sum_{k=0}^{N-1}\left|k\right\rangle\right)\left|0\right\rangle+\frac{\mathrm{e}^{-i\Delta t}}{\sqrt{N}}\sum_{j=0}^{N-1}\left\langle j\middle|y\right\rangle\sum_{k=0}^{N-1}\left|k\right\rangle\left|0\right\rangle \\ &= \left(\sum_{j=0}^{N-1}\left|j\right\rangle\left\langle j\right|-\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\left|k\right\rangle\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\left\langle j\right|\right)\left|y\right\rangle\left|0\right\rangle+\frac{\mathrm{e}^{-i\Delta t}}{\sqrt{N}}\sum_{k=0}^{N-1}\left|k\right\rangle\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\left\langle j\right|\left|y\right\rangle\left|0\right\rangle \\ &= \left(I-\left|\psi\right\rangle\left\langle\psi\right|+\mathrm{e}^{-i\Delta t}\left|\psi\right\rangle\left\langle\psi\right|\right)\left|y\right\rangle\left|0\right\rangle \end{align} $$

Thus, the circuit implements $\mathrm{e}^{-i\left|\psi\right\rangle\left\langle\psi\right|\Delta t}$.


6.11

$$ \begin{equation} H = \sum_x \left|x\right\rangle\left\langle x\right| + \left|\psi\right\rangle\left\langle\psi\right| \end{equation} $$

I haven’t checked if it really works though.