Solutions: Quantum Computation and Quantum Information by Nielsen and Chuang

Solutions: Quantum Computation and Quantum Information by Nielsen and Chuang

Chapter 3

3.2

Suppose a Turing machine contains following program lines:

$$ \begin{align} 1:\; &\left\langle q_0,\Gamma_0,q_0,\Gamma_0,+1 \right\rangle\\ 2:\; &\left\langle q_0,\Gamma_1,q_1,\Gamma_1,0 \right\rangle , \end{align} $$

where $q_0 = q_s,$ and $q_1=q_H$.

We encode each program line $\left\langle q,x,q’,x’,s \right\rangle$ as follows:

  1. The state $q_i$ is encoded by the letter ‘$D$’ followed by the letter ‘$A$’ repeated $i$ times
  2. The alphabet of symbol $\Gamma_i$ is encoded by the letter ‘$D$’ followed by the letter ‘$C$’ repeated $i$ times
  3. The movements of tape-head (-1, +1, and 0) are encoded by the letter ‘$L$’, ‘$R$’, and ‘$N$’, respectively

Therefore, a program line $\left\langle q_0,\Gamma_0,q_0,\Gamma_0,+1 \right\rangle$ is encoded as

$$ \begin{equation} DDDDR. \end{equation} $$

By separating program lines by semicolons we then can describe the program as

$$ \begin{equation} DDDDR;DDCDADCN. \end{equation} $$

Then we replace each of the symbols as follows:

$$ \begin{align} D\; \rightarrow\; 0 \\ A\; \rightarrow\; 1 \\ C\; \rightarrow\; 2 \\ L\; \rightarrow\; 3 \\ R\; \rightarrow\; 4 \\ N\; \rightarrow\; 5 \\ ;\; \rightarrow\; 6 \end{align} $$

The result is 0-0-0-0-4-6-0-0-2-0-1-0-2-5.

Since every positive integer has a unique prime factors

$$ \begin{equation} p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}, \end{equation} $$

where $p_i$ are distinct prime numbers, and

$$ \begin{equation} a_1,a_2,\cdots ,a_k \end{equation} $$

are non-negative integers, we can use this product as a Turing number for this program. Thus the number is

$$ \begin{equation} 2^0\times 3^0\times 5^0\times 7^0\times 11^4\times 13^6\times 17^0\times 19^0\times 23^2\times 29^0\times 31^1\times 37^0\times 41^2\times 43^5 \end{equation} $$

3.3

Suppose we have a two-tape Turing machine which takes as input binary numbers on the first tape and blanks on the remainder of both tapes, except the endpoint marker $\triangleright$. The machine contains following program lines can outputs the bits of $x$ in reverse order on the second tape.

$$ \begin{align} 1&: \left\langle q_s,\triangleright ,\triangleright ,q_1,\triangleright ,\triangleright , +1, +1 \right\rangle \\ 2&: \left\langle q_1,0,b,q_1,0,b,+1,0 \right\rangle \\ 3&: \left\langle q_1,1,b,q_1,1,b,+1,0 \right\rangle \\ 4&: \left\langle q_1,b,b,q_2,b,b,-1,0 \right\rangle \\ 5&: \left\langle q_2,0,b,q_2,b,0,-1,+1 \right\rangle \\ 6&: \left\langle q_2,1,b,q_2,b,1,-1,+1 \right\rangle \\ 7&: \left\langle q_2,\triangleright ,b,q_H,\triangleright ,b,0,0 \right\rangle \end{align} $$

3.4

Suppose we have a two-tape Turing machine which takes as input binary numbers on the first tape. The machine contains following program lines can output the bit string which is the answer of modulo-2 addition.

$$ \begin{align} 1&: \left\langle q_s,\triangleright ,\triangleright ,q_1,\triangleright ,\triangleright ,+1,+1 \right\rangle \\ 2&: \left\langle q_1,0,b,q_1,0,0,+1,0 \right\rangle \\ 3&: \left\langle q_1,0,0,q_1,0,0,+1,0 \right\rangle \\ 4&: \left\langle q_1,0,1,q_1,0,0,+1,0 \right\rangle \\ 5&: \left\langle q_1,1,b,q_1,1,1,+1,0 \right\rangle \\ 6&: \left\langle q_1,1,0,q_1,1,1,+1,0 \right\rangle \\ 7&: \left\langle q_1,1,1,q_1,1,1,+1,0 \right\rangle \\ 8&: \left\langle q_1,b,0,q_2,b,0,+1,0 \right\rangle \\ 9&: \left\langle q_1,b,1,q_2,b,1,+1,0 \right\rangle \\ 10&: \left\langle q_2,0,0,q_2,0,0,+1,0 \right\rangle \\ 11&: \left\langle q_2,0,1,q_2,0,1,+1,0 \right\rangle \\ 12&: \left\langle q_2,1,0,q_2,1,0,+1,0 \right\rangle \\ 13&: \left\langle q_2,1,1,q_2,1,1,+1,0 \right\rangle \\ 14&: \left\langle q_2,b,0,q_3,b,0,-1,0 \right\rangle \\ 15&: \left\langle q_2,b,1,q_3,b,1,-1,0 \right\rangle \\ 16&: \left\langle q_3,0,0,q_H,0,0,0,0 \right\rangle \\ 17&: \left\langle q_3,0,1,q_H,0,1,0,0 \right\rangle \\ 18&: \left\langle q_3,1,0,q_H,0,1,0,0 \right\rangle \\ 19&: \left\langle q_3,1,1,q_H,1,0,0,0 \right\rangle \\ \end{align} $$

3.5

Define $A(x)$ as the program that outputs “YES” if an arbitrary program $M$ halts, and outputs “NO” if it doesn’t. That is,

$$ \begin{equation} A(M) = \begin{cases} \mathrm{YES} & \mathrm{if\; program\;} M\; \mathrm{halts,} \\ \mathrm{NO} & \mathrm{otherwise.} \end{cases} \end{equation} $$

Define $B(M)$ as the program that never halts if $A(M)=\mathrm{YES}$, and halts if $A(M)=\mathrm{NO}$. It follows from the definition of $B(M)$ that exactly one of the following two cases must be hold:

  • $A(M)=\mathrm{YES}$ and so $B(M)$ never halts. In this case $B(B(M))$ halts.
  • $A(M)=\mathrm{NO}$ and so $B(M)$ halts. In this case $B(B(M))$ never halts.

In either cases there is a conflict. Therefore, there is no algorithm to determine whether $M$ halts with no inputs.


3.8

NOT:
NOT

AND:
AND

XOR:

(i)

$$ \begin{align} \mathrm{XOR} &= \left(\bar{x}\land y\right) \lor \left( x\land\bar{y}\right) = \left(\bar{x}\land y\right) \lor \left( x\land\bar{y}\right) \lor \left( x\land\bar{x}\right) \lor \left( y\land\bar{y}\right) \\ &= \left( x\land\left(\bar{x}\lor\bar{y}\right)\right) \lor \left( y\land\left(\bar{x}\lor\bar{y}\right)\right) \\ &= \left( x\land\left(\overline{x\land y}\right)\right) \lor \left( y\land\left(\overline{x\land y}\right)\right) \\ &= \overline{\left(\overline{x\land\left(\overline{x\land y}\right)}\right) \land \left(\overline{y\land\left(\overline{x\land y}\right)}\right)} \end{align} $$

XOR

(ii)

$$ \begin{align} \mathrm{XOR} = \left(\bar{x}\land y\right) \lor \left(x\land\bar{y}\right) = \overline{\overline{\bar{x}y} \land \overline{x\bar{y}}} \end{align} $$

3.9

If $g(n)$ is $\Omega(f(n))$,

$$ \begin{equation} cf\left( n\right) \le g\left( n\right) \Leftrightarrow f\left( n\right) \le \frac{1}{c}g\left( n\right) \;\;\; (\mathrm{\;for\;positive}\;c) \end{equation} $$

This means $f(n)$ is $O(g(n))$.

If $f(n)$ is $O(g(n))$,

$$ \begin{equation} f\left( n\right) \le c\left( g\left( n\right)\right) \Leftrightarrow \frac{1}{c} f\left( n\right) \le g\left( n\right) \;\;\; (\mathrm{\;for\;positive}\;c) \end{equation} $$

This means $g(n)$ is $\Omega (f(n))$. So, $f(n)$ is $O(g(n))$ if and only if $g(n)$ is $\Omega(f(n))$.

If $g(n)$ is $\Theta (f(n))$, $g(n)$ is both $O(f(n))$ and $\Omega (f(n))$. As we have done above, this implies that $f(n)$ is both $O(g(n))$ and $\Omega(g(n))$, that is, $f(n)$ is $\Theta (f(n))$.
If $f(n)$ is $\Theta (g(n))$, $f(n)$ is both $O(g(n))$ and $\Omega (g(n))$. As we have done above, this implies that $g(n)$ is both $O(f(n))$ and $\Omega(f(n))$, that is, $g(n)$ is $\Theta (g(n))$.

So, $f(n)$ is $\Theta(g(n))$ if and only if $g(n)$ is $\Theta(f(n))$.


3.10

Obviously, $g(n)$ is $O(n^k)$. So, $g(n)$ is $O(n^l)$ for any $l\le k$.


3.11

When n=1,

$$ \begin{equation} \log n = 0,\;\;\; n^k = 1. \end{equation} $$

The first derivative of $\log n$ and $n^k$

$$ \begin{align} \frac{\mathrm{d}}{\mathrm{d}n} \log n &= \frac{n^{-1}}{\ln 2},\\ \frac{\mathrm{d}}{\mathrm{d}n} n^k &= kn^{k-1}. \end{align} $$

So, there always exist a constant c that makes the first derivative of $cn^k$ larger than that of $\log n$. Therefore, $\log n$ is $O(n^k)$ for any $k\gt 0$.


3.12

$n^k$ intersects with $n^{n\log n}$ only at $n_0=2^k$. The slopes of $n^k$ and $n^{n\log n}$ at $n_0$ are

$$ \begin{align} \left. \frac{\mathrm{d}}{\mathrm{d}n} n^k \right| _{n_0} &= k2^{k(k-1)},\\ \left. \frac{\mathrm{d}}{\mathrm{d}n} n^{n\log n} \right| _{n_0} &= 2k2^{k(k-1)}. \end{align} $$

Therefore, $n^k$ is $O(n^{n\log n})$.


3.15

Every time we perform compare-and-swap, 2 of the possible initial orderings will be sorted into the correct order. So, after $k$ of the operations, at most $2^k$ initial orderings will be sorted. The number of operations needed to sort all possible initial orderings into the correct order k_0 is,

$$ \begin{align} 2^{k_0} &= n! \\ \longrightarrow k_0 &\approx n\log n - n = O(n\log n). \end{align} $$