Solutions: Quantum Computation and Quantum Information by Nielsen and Chuang

Solutions: Quantum Computation and Quantum Information by Nielsen and Chuang

Chapter 5

5.1

$$ \begin{align} \left\langle m\middle| j\right\rangle \longrightarrow &\frac{1}{N}\sum_{k,n=0}^{N-1}\mathrm{e}^{-2\pi imn/N}\mathrm{e}^{2\pi ijk/N}\left\langle n\middle|k\right\rangle \\ &= \frac{1}{N}\sum_{k,n=0}^{N-1}\mathrm{e}^{-2\pi imn/N}\mathrm{e}^{2\pi ijk/N}\delta_{n,k} \\ &= \frac{1}{N}\sum_{k=0}^{N-1}\mathrm{e}^{2\pi i\left(j-m\right)k/N} = \delta_{j,m} \end{align} $$

So, this transformation is unitary since it preserves the inner product.


5.2

For $n$ qubit state, $N=2^n$. Then,

$$ \begin{align} \left|00\cdots 0\right\rangle \longrightarrow &\frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1}\mathrm{e}^{2\pi ik\cdot 0/2^n}\left|k\right\rangle \\ &= \frac{1}{\sqrt{2^n}}\sum_{k=0}^{2^n-1}\left|k\right\rangle. \end{align} $$

5.3

Each term in eq. 5.1 requires the evaluation of exponential, multiplication with $x_j$, and 2^n additions. We need to perform that for $2^n$ coefficients ($y_1,y_2,\cdots,y_{2^n}$). So, in total, eq. 5.1 requires $\Theta(2^{2n})$ operations.


5.4

Recall that any unitary operation can be decomposed as

$$ \begin{align} U = \mathrm{e}^{i\alpha}R_z\left(\beta\right)R_y\left(\gamma\right)R_z\left(\delta\right) = \begin{pmatrix} \mathrm{e}^{i\left(\alpha-\beta/2-\delta/2\right)}\cos\frac{\gamma}{2} & -\mathrm{e}^{i\left(\alpha-\beta/2+\delta/2\right)}\sin\frac{\gamma}{2} \\ \mathrm{e}^{i\left(\alpha+\beta/2-\delta/2\right)}\sin\frac{\gamma}{2} & \mathrm{e}^{i\left(\alpha+\beta/2+\delta/2\right)}\cos\frac{\gamma}{2} \end{pmatrix}. \end{align} $$

When $\alpha=2\pi/2^{k+1},\ \beta=0,\ \gamma=0,\ \delta=2\pi/2^k$, it creates $R_k$

$$ \begin{align} &\mathrm{e}^{\frac{2\pi i}{2^{k+1}}}R_z\left(0\right)R_y\left(0\right)R_z\left(\frac{2\pi}{2^k}\right) \\ &= \mathrm{e}^{\frac{2\pi i}{2^{k+1}}} \begin{pmatrix} \mathrm{e}^{-\frac{2\pi i}{2^{k+1}}} & 0 \\ 0 & \mathrm{e}^{\frac{2\pi i}{2^{k+1}}} \end{pmatrix} = \begin{pmatrix} 1 & 0 \\ 0 & \mathrm{e}^{\frac{2\pi i}{2^k}} \end{pmatrix} = R_k. \end{align} $$

Using corollary 4.2, it is transformed as

$$ \begin{align} R_k &= \mathrm{e}^{\frac{2\pi i}{2^{k+1}}}R_z\left(0\right)R_y\left(0\right)XR_y\left(0\right)R_z\left(-\frac{2\pi}{2^{k+1}}\right)XR_z\left(\frac{2\pi}{2^{k+1}}\right) \\ &= \mathrm{e}^{\frac{2\pi i}{2^{k+1}}}XR_z\left(-\frac{2\pi}{2^{k+1}}\right)XR_z\left(\frac{2\pi}{2^{k+1}}\right). \end{align} $$

circuit_5_4


5.5

The inverse discrete Fourier transform:

$$ \begin{align} x_j = \frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\mathrm{e}^{-\frac{2\pi ikj}{N}}y_k \end{align} $$

Then,

$$ \begin{align} \left|x\right\rangle &= \sum_{j=0}^{N-1}x_j\left|j\right\rangle \\ &= \sum_{j=0}^{N-1}\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\mathrm{e}^{-\frac{2\pi ikj}{N}}y_k \left|j\right\rangle\\ &= \sum_{k=0}^{N-1}y_k\left(\sum_{j=0}^{N-1}\frac{1}{\sqrt{N}}\mathrm{e}^{-\frac{2\pi ikj}{N}}\left|j\right\rangle\right). \end{align} $$

Thus, the inverse quantum Fourier transform is given as the following action:

$$ \begin{align} \left|k\right\rangle \longrightarrow &\sum_{j=0}^{N-1}\frac{1}{\sqrt{N}}\mathrm{e}^{-\frac{2\pi ikj}{N}}\left|j\right\rangle \\ &= \frac{\left(\left|0\right\rangle+\mathrm{e}^{-2\pi i0.k_n}\left|1\right\rangle\right)\otimes\left(\left|0\right\rangle+\mathrm{e}^{-2\pi i0.k_{n-1}k_n}\left|1\right\rangle\right)\otimes\cdots\otimes\left(\left|0\right\rangle+\mathrm{e}^{-2\pi i0.k_1k_2\cdots k_n}\left|1\right\rangle\right)}{2^{n/2}} \end{align} $$

Applying the Hadamard gate to the bit $\left|k_1\right\rangle$ produce the state

$$ \begin{align} \frac{\left|0\right\rangle+\mathrm{e}^{2\pi i0.k_1}\left|1\right\rangle}{\sqrt{2}} = \frac{\left|0\right\rangle+\mathrm{e}^{-2\pi i0.k_1}\left|1\right\rangle}{\sqrt{2}}. \end{align} $$

Therefore, replacing the $R_i$ gates in figure 5.1 with $R_i^{\dagger}$ gives the quantum circuit to perform the inverse quantum Fourier transform.


5.6

$$ \begin{align} E\left(U,V\right) &= E\left(H_1R_2^1R_3^1\cdots R_n^1\cdots H_{n-1}R_2^{n-1}H_n,\ \ H_1R_2^{'1}R_3^{'1}\cdots R_n^{'1}\cdots H_{n-1}R_2^{'n-1}H_n\right) \\ &\le E\left(H_1,H_1\right)+E\left(R_2^1,R_2^{'1}\right)+E\left(R_3^1,R_3^{'1}\right)+\cdots+E\left(R_2^{n-1},R_2^{'n-1}\right)+E\left(H_n,H_n\right) \\ &= E\left(R_2^1,R_2^{'1}\right)+E\left(R_3^1,R_3^{'1}\right)+\cdots+E\left(R_2^{n-1},R_2^{'n-1}\right) \\ &= \Delta+\Delta+\cdots+\Delta \end{align} $$

where $R_i^{‘j}$ denotes the $\mathrm{controlled-}R_i$ gate with an error $\Delta=1/p(n)$ which takes the $i$th gate as a controll bit and $j$th gate as a target bit.

Since the number of $R_i^j$ gates is $n(n+1)/2$, $E(U,V)$ scales as $\Theta(n^2/p(n))$.


5.7

Using the binary representation, $j=j_1j_2\cdots j_n$.

circuit_5_7

Then, applying the circuit above transforms $\left|j\right\rangle\left|u\right\rangle$ into

$$ \begin{align} \left|j\right\rangle\left|u\right\rangle \longrightarrow &\left|j\right\rangle U^{j_n2^0}\cdots U^{j_32^{n-3}}U^{j_22^{n-2}}U^{j_12^{n-1}}\left|u\right\rangle \\ &= \left|j\right\rangle U^{j_12^{n-1}}U^{j_22^{n-2}}U^{j_32^{n-3}}\cdots U^{j_n2^0}\left|u\right\rangle \\ &= \left|j\right\rangle U^{j_1j_2j_3\cdots j_n}\left|u\right\rangle = \left|j\right\rangle U^{j}\left|u\right\rangle. \end{align} $$

5.8

The probability of getting the state $\left|u\right\rangle$ measured is $\left|c_u\right|^2$, and the measurement succeeds with probability $1-\varepsilon$. Therefore, $\left|c_u\right|^2\left(1-\varepsilon\right)$.


5.9

Let $\left|-1\right\rangle$ and $\left|+1\right\rangle$ be the eigenstates of $U$ with eigenvalues $-1$ and $+1$, respectively. After applying following operations, $\left|0\right\rangle\left|\psi\right\rangle=\sum_{j=-1,+1}c_i\left|0\right\rangle\left|j\right\rangle$ becomes

circuit_5_9


$$ \begin{align} \left|\psi_0\right\rangle &= \sum_{j=-1,+1}c_i\left|0\right\rangle\left|j\right\rangle \\ \left|\psi_1\right\rangle &= \sum_{j=-1,+1}c_i\frac{1}{\sqrt{2}}\sum_{k=0,1}\left|k\right\rangle\left|j\right\rangle \\ \left|\psi_2\right\rangle &= \sum_{j=-1,+1}c_i\frac{1}{\sqrt{2}}\left(\left|0\right\rangle+\mathrm{e}^{2\pi i\varphi_i}\left|1\right\rangle\right)\left|j\right\rangle \\ \left|\psi_3\right\rangle &= \sum_{j=-1,+1}c_i\left|\varphi_i\right\rangle\left|j\right\rangle \end{align} $$

So, by measuring the first qubit, the second qubit collapses into one of the eigenstates of $U$, which is $\left|-1\right\rangle$ or $\left|+1\right\rangle$. When the measuring result is 0, the final state of the second qubit is $\left|+1\right\rangle$ and vice versa. This is exactly the same thing that is done by exercise 4.34. It’s easy to convince oneself that the phase estimation circuit with one bit register is exactly the same as the circuit in exercise 4.34, since $FT=FT^{\dagger}=H$.


5.10

$$ \begin{align} 5^1 &= 5\ \left(\mathrm{mod}\ 21\right) \\ 5^2 &= 4\ \left(\mathrm{mod}\ 21\right) \\ 5^3 &= 19\ \left(\mathrm{mod}\ 21\right) \\ 5^4 &= 5\ \left(\mathrm{mod}\ 21\right) \\ 5^5 &= 17\ \left(\mathrm{mod}\ 21\right) \\ 5^6 &= 1\ \left(\mathrm{mod}\ 21\right) \end{align} $$

5.11

By Euler’s theorem,

$$ \begin{align} x^{\varphi(N)} \equiv 1\ \left(\mathrm{mod}\ N\right) \end{align} $$

where $\varphi(N)$ is a Euler’s totient function. Obviously, $\varphi(N)\le N$. So, $r\le N$.


5.12

$U$ is a $2^L-1\times2^L-1$ matrix. It’s easy to notice that the unitary matrix is identity for $N\le y\le 2^L-1$ since $U\left|y\right\rangle=\left|y\right\rangle$. For $0\le y\le N-1$,

$$ \begin{equation} \left\langle y'\middle|U^{\dagger}U\middle|y\right\rangle = \left\langle xy'\ \left(\mathrm{mod}\ N\right)\middle| xy\ \left(\mathrm{mod}\ N\right)\right\rangle. \end{equation} $$

Since $x$ is co-prime to $N$, it has an inverse $x^{-1}$. Then,

$$ \begin{align} \left\langle xy'\middle| xy\right\rangle = \left\langle y'\middle| y\right\rangle=\delta_{y',y} \end{align} $$

Therefore, $U$ is a unitary matrix.


5.13

$$ \begin{align} \frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}\mathrm{e}^{2\pi isk/r}\left|u_s\right\rangle &= \frac{1}{r}\sum_{s=0}^{r-1}\sum_{k'=0}^{r-1}\mathrm{e}^{2\pi is\left(k-k'\right)/r}\left|x^{k'}\ \left(\mathrm{mod}\ N\right)\right\rangle \\ &= \sum_{k'=0}^{r-1}\delta_{k,k'}\left|x^{k'}\ \left(\mathrm{mod}\ N\right)\right\rangle \\ &= \left|x^k\ \left(\mathrm{mod}\ N\right)\right\rangle \end{align} $$

5.14

$$ \begin{align} V\left|j\right\rangle\left|0\right\rangle = \left|j\right\rangle\left|0+x^j\ \left(\mathrm{mod}\ N\right)\right\rangle = \left|j\right\rangle\left|x^j\ \left(\mathrm{mod}\ N\right)\right\rangle \end{align} $$

The operation that calculate $2^jk_j$ costs $O(L^3)$ and additions can be performed at a cost of $O(L)$. Then, V can be expressed in a quantum circuit using $O(L^3)$ gates.


5.16

$$ \begin{align} \int_{x}^{x+1}\frac{1}{y^2}dy &= \left[-\frac{1}{y^2}\right]^{x+1}_x \\ &= \frac{1}{x}-\frac{1}{x+1} = \frac{1}{x\left(x+1\right)} \end{align} $$

Define $f(x)=1/x(x+1)-2/3x^2$. Then,

$$ \begin{align} f(2) &= 1/6-1/6 = 0, f'(x) &= -\frac{2x+1}{x^2\left(x+1\right)^2}+\frac{2}{3x} \\ &= \frac{-6x-3+2x\left(x+1\right)^2}{3x^2\left(x+1\right)^2}. \end{align} $$

Since $f’(x)$ is positive for all $x\ge2,\ \int_{x}^{x+1}1/y^2dy\ge 2/3^2$ for all $x\ge2$.

Let $q(i)$ denote the $i$th prime number. If we put a rectangle of height $1/q^2(i)$ over the interval $[q(i),q(i+1)]$ for each $i$, then the union of rectangles is the upper Riemann sum for $\int_{2}^{\infty}1/y^2dy$, and the interval $q(i+1)-q(i)$ is $\ge 2$ except $i=1$. Thus,

$$ \begin{align} \sum_{q}\frac{1}{q^2}\le\frac{2}{3}\int_{2}^{\infty}\frac{1}{y^2}dy=3/4. \\ \longrightarrow 1-\sum_q p\left(q\middle|s'_1\right)p\left(q\middle|s'_2\right)\ge 1-\sum_q \frac{1}{q^2}\ge 1-\frac{3}{4}=\frac{1}{4}. \end{align} $$

5.17

Something in the problem setting seems to be wrong. For $N=1\ \left(\mathrm{then}\ L=1\right)$, $a=1$ and any $b$ satisfies $N=a^b$. In any case $b\ \left(\ge 2\right) \ge L$.


5.18

$$ \begin{align} 4^1 &= 4\ \left(\mathrm{mod}\ 91\right) \\ 4^2 &= 16\ \left(\mathrm{mod}\ 91\right) \\ 4^3 &= 64\ \left(\mathrm{mod}\ 91\right) \\ 4^4 &= 74\ \left(\mathrm{mod}\ 91\right) \\ 4^5 &= 23\ \left(\mathrm{mod}\ 91\right) \\ 4^6 &= 1\ \left(\mathrm{mod}\ 91\right) \end{align} $$
`

Thus, the order $r=6$, which is even number, and $4^{r/2}=4^3\ne -1\ \left(\mathrm{mod}\ 91\right)$.


5.19

We only need to consider about $9$, which is a composite number and not even under $15$. Since $9=3^2$, $15$ is the smallest number for which order-finding subroutine is required.


5.20

$$ \begin{align} \hat{f}\left(l\right) &\equiv \frac{1}{\sqrt{N}}\sum_{x=0}^{N-1}\mathrm{e}^{-2\pi ilx/N}f\left(x\right) \\ &= \frac{1}{\sqrt{N}}\sum_{k\in\left\{0,r,\cdots,N-r\right\}}\mathrm{e}^{-2\pi ilk/N}f\left(0\right) \\ &+ \frac{1}{\sqrt{N}}\sum_{k\in\left\{1,r+1,\cdots,N-r+1\right\}}\mathrm{e}^{-2\pi ilk/N}f\left(1\right) \\ &\vdots \\ &+ \frac{1}{\sqrt{N}}\sum_{k\in\left\{r-1,2r-1,\cdots,N-1\right\}}\mathrm{e}^{-2\pi ilk/N}f\left(r-1\right) \\ &= \frac{1}{\sqrt{N}}\sum_{k\in\left\{0,r,\cdots,N-r\right\}}\mathrm{e}^{-2\pi ilk/N}\left[\mathrm{e}^{-2\pi il\cdot 0/N}f\left(0\right)+\mathrm{e}^{-2\pi il\cdot 1/N}f\left(1\right)+\cdots +\mathrm{e}^{-2\pi il\left(r-1\right)/N}f\left(r-1\right)\right] \\ &= \frac{\sqrt{N}}{r}\sum_{x=0}^{r-1}\mathrm{e}^{-2\pi ilx/N}f\left(x\right). \end{align} $$

5.21

(1)

$$ \begin{align} U_y\left|f\left(l\right)\right\rangle &= \frac{1}{\sqrt{r}}\sum_{x=0}^{r-1}\mathrm{e}^{-2\pi ilx/N}U_y\left|f\left(x\right)\right\rangle \\ &= \frac{1}{\sqrt{r}}\sum_{x=0}^{r-1}\mathrm{e}^{-2\pi ilx/N}\left|f\left(x+y\right)\right\rangle \\ &= \frac{1}{\sqrt{r}}\sum_{x'=y}^{r+y-1}\mathrm{e}^{-2\pi il\left(x'-y\right)/N}\left|f\left(x'\right)\right\rangle \\ &= \mathrm{e}^{2\pi ily/N}\frac{1}{\sqrt{r}}\sum_{x'=y}^{r+y-1}\mathrm{e}^{-2\pi ilx'/N}\left|f\left(x'\right)\right\rangle \\ &= \mathrm{e}^{2\pi ily/N}\frac{1}{\sqrt{r}}\sum_{x'=0}^{r-1}\mathrm{e}^{-2\pi ilx'/N}\left|f\left(x'\right)\right\rangle\ \ \ \ \ \left(\because\ \mathrm{e}^{-2\pi ilx'/N}\left|f\left(x'\right)\right\rangle\ \mathrm{is\ periodic}\right) \\ &= \mathrm{e}^{2\pi ily/N}\left|f\left(l\right)\right\rangle \end{align} $$

So, $\left|f(l)\right\rangle$ is the eigenstate of $U_y$ with the eigenvalue $\mathrm{e}^{2\pi ily/N}$.

(2)

$$ \begin{align} U_y\left|f\left(x_0\right)\right\rangle &= \frac{1}{\sqrt{r}}\sum_{l=0}^{r-1}\mathrm{e}^{2\pi ilx_0/r}U_y\left|f\left(l\right)\right\rangle \\ &= \frac{\mathrm{e}^{2\pi ily/N}}{\sqrt{r}}\sum_{l=0}^{r-1}\mathrm{e}^{2\pi ilx_0/N}\left|f\left(l\right)\right\rangle \end{align} $$

So, after step 4, we get

$$ \begin{equation} \frac{1}{\sqrt{r}}\sum_{l=0}^{r-1}\mathrm{e}^{2\pi ily/N}\left|\widetilde{l/r}\right\rangle\left|f\left(l\right)\right\rangle. \end{equation} $$

Here, the factor $\mathrm{e}^{2\pi ily/N}$ doesn’t affect the measurement result. Then, $U_y$ can be used to realize the black box.


5.22

Eq. (5.70) should be

$$ \begin{equation} \left|\hat{f}\left(l_1,l_2\right)\right\rangle = \sum_{j=0}^{r-1}\mathrm{e}^{-2\pi il_2j/r}\left|f\left(0,j\right)\right\rangle. \end{equation} $$

Solution:

$$ \begin{align} \left|\hat{f}\left(l_1,l_2\right)\right\rangle &= \frac{1}{r}\sum_{x_1=0}^{r-1}\sum_{x_2=0}^{r-1}\mathrm{e}^{-2\pi i\left(l_1x_1+l_2x_2\right)/r}\left|f\left(x_1,x_2\right)\right\rangle \\ &= \frac{1}{r}\sum_{x_1=0}^{r-1}\sum_{x_2=0}^{r-1}\mathrm{e}^{-2\pi i\left(l_1x_1+l_2x_2\right)/r}\left|f\left(0,x_2+sx_1\right)\right\rangle \\ &= \frac{1}{r}\sum_{x_1=0}^{r-1}\sum_{j=sx_1}^{r-1+sx_1}\mathrm{e}^{-2\pi i\left(l_1x_1+l_2j-l_2sx_1\right)/r}\left|f\left(0,j\right)\right\rangle \\ &= \frac{1}{r}\sum_{x_1=0}^{r-1}\mathrm{e}^{-2\pi i sx_1\left(l_1/s-l_2\right)/r}\sum_{j=0}^{r-1}\mathrm{e}^{-2\pi il_2j/r}\left|f\left(0,j\right)\right\rangle\ \ \ \ \ \left(\because\ \mathrm{e}^{-2\pi il_2j/N}\left|f\left(0,j\right)\right\rangle\ \mathrm{is\ periodic}\right) \\ &= \sum_{j=0}^{r-1}\mathrm{e}^{-2\pi il_2j/r}\left|f\left(0,j\right)\right\rangle \end{align} $$

5.23

$$ \begin{align} \frac{1}{r}\sum_{l_1=0}^{r-1}\sum_{l_2=0}^{r-1}\mathrm{e}^{2\pi i\left(l_1x_1+l_2x_2\right)/r}\left|\hat{f}\left(l_1,l_2\right)\right\rangle &= \frac{1}{r}\sum_{l_1=0}^{r-1}\sum_{l_2=0}^{r-1}\sum_{j=0}^{r-1}\mathrm{e}^{2\pi i\left(l_1x_1+l_2x_2-l_2j\right)/r}\left|f\left(0,j\right)\right\rangle \\ \mathrm{Since}\ l_1/s-l_2\ \mathrm{is\ an\ integer\ multiple\ of}\ &r,\ l_1=smr+sl_2,\ \mathrm{where}\ m\ \mathrm{is\ an\ integer}.\ \mathrm{Then,} \\ &= \frac{1}{r}\sum_{l_2=0}^{r-1}\sum_{j=0}^{r-1}\mathrm{e}^{2\pi i\left(smrx_1+sl_2x_1+l_2x_2-l_2j\right)/r}\left|f\left(0,j\right)\right\rangle \\ &= \frac{1}{r}\sum_{l_2=0}^{r-1}\sum_{j=0}^{r-1}\mathrm{e}^{2\pi il_2\left(sx_1+x_2-j\right)/r}\left|f\left(0,j\right)\right\rangle \\ &= \delta_{sx_1+x_2-j,0}\sum_{j=0}^{r-1}\left|f\left(0,j\right)\right\rangle \\ &= \left|f\left(0,sx_1+x_2\right)\right\rangle \\ &= \left|f\left(x_1,x_2\right)\right\rangle \end{align} $$