[Note] Quantum Computation and Quantum Information - Final exam

期末考詳解，原文書:

Quantum Computation and Quantum Information, Michael A. Nielsen & Isaac L. Chuang

• 班平均：64

Problem 1

Recall that the Bell basis consist of the following states on two qubits:

$$\begin{align*}\vert \beta_{00}\rangle &= \frac{1}{\sqrt 2}(\vert 00\rangle+\vert11\rangle) & \vert \beta_{01}\rangle &= \frac{1}{\sqrt 2}(\vert 00\rangle-\vert11\rangle)\\\vert \beta_{10}\rangle &= \frac{1}{\sqrt 2}(\vert 10\rangle+\vert01\rangle) & \vert \beta_{11}\rangle &= \frac{1}{\sqrt 2}(\vert 10\rangle-\vert01\rangle)\end{align*}$$

Suppose Alice is holding the first two qubits of $\vert +\rangle \otimes \vert \beta_{11}\rangle$ and Bob is holding the third.

(a) If Alice applies $(I\otimes H)\text{CNOT}$ to her two qubits, where the first qubit is the control of the $\text{CNOT}$ and the second qubit is the target, what is the state shared by Alice and Bob now?

(b) After step (a), what is the reduced density matrix of Bob’s state?

(c) After step (a), Alice measures her two qubits in the Bell basis, what are the probabilities of each measurement outcome and Bob’s post-measurement state corresponding to each measurement outcome?

$$\begin{align*}\vert +\rangle\otimes\vert\beta_{11}\rangle &= \frac{1}{\sqrt 2}(\vert 0\rangle + \vert 1\rangle) \otimes \vert \beta_{11}\rangle\\ &= \frac{1}{\sqrt 2}\big(\vert0\rangle\otimes\vert\beta_{11}\rangle+\vert1\rangle\otimes\vert\beta_{11}\rangle\big)\end{align*}$$

(a)

First apply $\text{CNOT}_\text{Alice}$

$$\begin{align*}&\frac{1}{\sqrt 2}\big(\vert0\rangle\otimes\vert\beta_{11}\rangle+\vert1\rangle\otimes\vert\beta_{11}\rangle\big)\\&\qquad\xrightarrow{\text{CNOT}_\text{Alice}} \frac{1}{\sqrt 2}\big(\vert0\rangle\otimes\vert\beta_{11}\rangle+\vert1\rangle\otimes\vert\beta_{01}\rangle\big)\end{align*}$$

Then, apply $(I\otimes H)_\text{Alice}$

$$\begin{align*}&&\frac{1}{\sqrt 2}\big(\vert0\rangle\otimes\vert\beta_{11}\rangle+&\vert1\rangle\otimes\vert\beta_{01}\rangle\big)\\&&\qquad\xrightarrow{(I\otimes H)_\text{Alice}}&\frac{1}{2}(\vert0\rangle\otimes(\vert\beta_{01}\rangle-\vert\beta_{10}\rangle)+\vert1\rangle\otimes(\vert\beta_{00}\rangle+\vert\beta_{11}\rangle))\\&&=&\frac{1}{2}(\vert00\rangle\otimes\vert-\rangle-\vert01\rangle\otimes\vert+\rangle+\vert10\rangle\otimes\vert-\rangle+\vert11\rangle\otimes\vert+\rangle)\\&&=&\frac{1}{2}\big((\vert00\rangle+\vert10\rangle)\vert-\rangle+(\vert11\rangle-\vert01\rangle)\vert+\rangle\big)\end{align*}$$

(b)

Let $\vert\psi\rangle=\displaystyle\frac{1}{2}\big((\vert00\rangle+\vert10\rangle)\vert-\rangle+(\vert11\rangle-\vert01\rangle)\vert+\rangle\big)$. The reduced density matrix of Bob’s state is

$$\begin{align*}\rho_{Bob} &=\text{tr}_\text{Alice}(\vert\psi\rangle\langle\psi\vert)\\ &=\vert-\rangle\langle-\vert+\vert+\rangle\langle+\vert\\ &=\vert0\rangle\langle0\vert+\vert1\rangle\langle1\vert\end{align*}$$

(c)

$$\begin{align*}\begin{cases} Pr(00)=\frac{1}{4} &\Rightarrow \vert \psi_\text{Bob}\rangle=\vert0\rangle\\ Pr(01)=\frac{1}{4} &\Rightarrow \vert \psi_\text{Bob}\rangle=-\vert1\rangle\\ Pr(10)=\frac{1}{4} &\Rightarrow \vert \psi_\text{Bob}\rangle=-\vert1\rangle\\ Pr(11)=\frac{1}{4} &\Rightarrow \vert \psi_\text{Bob}\rangle=\vert0\rangle\\\end{cases}\end{align*}$$

Problem 2

Calculate the output state and measurement distribution of the following circuits.

(a)

(b)

(a)

$$\begin{align*}\vert \psi_1\rangle &= \vert +\rangle\otimes\vert0\rangle\\\vert \psi_2\rangle &= \frac{1}{\sqrt{2}}(\vert00\rangle+\vert11\rangle)\\\vert \psi_3\rangle &= \frac{1}{2}(\vert00\rangle+\vert10\rangle+\vert01\rangle-\vert11\rangle)\end{align*}$$

Output distribution:

$$\begin{cases} Pr(00) = \frac{1}{4}\\ Pr(01) = \frac{1}{4}\\ Pr(10) = \frac{1}{4}\\ Pr(11) = \frac{1}{4}\end{cases}$$

(b)

$$\begin{align*}\vert \psi_1\rangle &= \vert +\rangle \otimes \vert 0\rangle\\\vert \psi_2\rangle &= \frac{1}{\sqrt 2}(\vert 00\rangle + \vert 11\rangle)\\\vert \psi_3\rangle &= \frac{1}{\sqrt 2}(\vert 00\rangle-\vert11\rangle)\\\vert \psi_4\rangle &= \frac{1}{\sqrt 2}(\vert00\rangle-\vert10\rangle)\\ &= \vert -\rangle\otimes \vert 0\rangle\\\vert \psi_5\rangle &= \vert 10\rangle\end{align*}$$

Output distribution:

$$Pr(10)=1$$

Problem 3

Suppose we have a one-bit function $f:\{0,1\}\to\{0,1\}$ and associated phase oracle

$$O_f\vert b\rangle = (-1)^{f(b)}\vert b\rangle~~\text{for}~~ b\in\{0,1\}$$

(a) Suppose we run the one-qubit circuit $HO_fH$ on input $\vert 0\rangle$ then measures in the computational basis, what is the output probability distribution in terms of $f(0)$ and $f(1)$?

(b) Now suppose we implemented quantum gate of $f$ while leaving some “garbage” in the work space, so we have the oracle

$$O'_f\vert b,c\rangle =(-1)^{f(b)}\vert b,c\oplus b\rangle$$

Suppose we run the two qubit quantum circuit $(H\otimes I)O’_f(H\otimes I)$ on the input $\vert 00\rangle$ and measurement the first qubit, what is the output probability distribution?

(a)

Apply $H$

$$\vert 0\rangle \xrightarrow{H}\vert+\rangle$$

Apply oracle $O_f$

$$\vert +\rangle \xrightarrow{O_f} \frac{1}{\sqrt 2}\left((-1)^{f(0)}\vert 0\rangle + (-1)^{f(1)}\vert 1\rangle\right)$$

Apply $H$

$$\begin{align*}&\frac{1}{\sqrt 2}\left((-1)^{f(0)}\vert 0\rangle + (-1)^{f(1)}\vert 1\rangle\right) \\ &\qquad\xrightarrow{H} \frac{1}{2}\left(\left((-1)^{f(0)}+(-1)^{f(1)}\right)\vert 0\rangle + \left((-1)^{f(0)}-(-1)^{f(1)}\right)\vert 1\rangle\right)\end{align*}$$

Output distribution

$$\begin{cases} Pr(0) = \frac{1}{4}\left((-1)^{2f(0)}+(-1)^{2f(1)}+2(-1)^{f(0)+f(1)}\right)\\ Pr(1) = \frac{1}{4}\left((-1)^{2f(0)}+(-1)^{2f(1)}-2(-1)^{f(0)+f(1)}\right)\end{cases}$$

(b)

Apply $(H\otimes I)$

$$\vert 00\rangle \xrightarrow{(H\otimes I)}\vert+\rangle\otimes \vert 0\rangle$$

Apply oracle $O’_f$

$$\vert+\rangle\otimes \vert 0\rangle \xrightarrow{O'_f} \frac{1}{\sqrt 2}\left((-1)^{f(0)}\vert00\rangle+(-1)^{f(1)}\vert11\rangle\right)$$

Apply $(H\otimes I)$

$$\begin{align*}&\frac{1}{\sqrt 2}\left((-1)^{f(0)}\vert00\rangle+(-1)^{f(1)}\vert11\rangle\right)\\&\qquad\xrightarrow{(H\otimes I)}\frac{1}{2}\left((-1)^{f(0)}(\vert00\rangle+\vert10\rangle)+(-1)^{f(1)}(\vert01\rangle-\vert11\rangle)\right)\end{align*}$$

Output distribution

$$\begin{cases} Pr(0)=\frac{1}{4}\left((-1)^{2f(0)}+(-1)^{2f(1)}\right)\\ Pr(1)=\frac{1}{4}\left((-1)^{2f(0)}+(-1)^{2f(1)}\right)\end{cases}$$

Problem 4

In this problem, we walk through Shor’s algorithm with $N=3\times 5$

(a) What is the number of positive integers less than $N$ that is coprime to N?

(b) What is the order $r$ of $x=2$ modulo $N$ (the smallest positive integer $r$ such that $x^r=1(\text{mod}~N)$)? Check that $r$ is even.

(c) Calculate $x^{r/2}+1$ and $x^{r/2}-1$.

(d) Calculate $\text{gcd}(x^{r/2}-1, N)$ and confirm it is a factor of $N$.

(e) Recall the period finding algorithm has the following circuit

where the controlled gate does controlled multiplication: $\vert j,y\rangle\to\vert j,y\cdot x^j(\text{mod}~N)\rangle$, and $QFT_t$ is the quantum fourier transform gate on $t$ qubits, with $QFT_t\vert x\rangle=\frac{1}{\sqrt{2^t}}\exp[2\pi ixy/2^t]\vert y\rangle$ for $x\in\{0,1,\dots,2^t-1\}$. Use $t=5$, write down all intermediate states and the output probability distribution of the period finding algorithm. (Hint: recall $\vert 1\rangle=\frac{1}{\sqrt r}\sum^{r-1}_{s=0}\vert u_s\rangle$, where $\vert u_s\rangle=\frac{1}{\sqrt r}\sum^{r-1}_{k=0}\exp[-2\pi isk/r]\vert x^k\rangle$)

(a) By Euler’s totient function

$$\phi(N)=(p-1)(q-1)=2\times4=8$$

(b)

$$2^r=1(\text{mod}~15)~\Rightarrow~ r=4$$

$r$ is even.

(c)

$$x^{r/2}+1=2^{2}+1=5,\quad x^{r/2}-1=4-1=3$$

(d)

$$\text{gcd}(x^{r/2}-1,N)=\text{gcd}(3,15)=3$$

Yes, $3$ is a factor of $N=15$.

(e)

$$\begin{align*}\vert \psi_1\rangle &=(H^{\otimes5}\vert0\rangle)\otimes\vert1\rangle\\ &=\frac{1}{\sqrt{32}}\sum^{31}_{j=0}\vert j\rangle\otimes\vert 1\rangle\\\vert \psi_2\rangle &=\frac{1}{\sqrt{32}}\sum^{31}_{j=0}\vert j\rangle\otimes \vert x^j\rangle\end{align*}$$

Recall (from Hint)

$$\vert 1\rangle=\frac{1}{\sqrt r}\sum^{r-1}_{s=0}\vert u_s\rangle,\quad \vert u_s\rangle=\frac{1}{\sqrt r}\sum^{r-1}_{k=0}e^{-2\pi i\frac{sk}{r}}\vert x^k\rangle$$

$r=4~\Rightarrow$

$$\begin{align*}\Rightarrow&&\vert 1\rangle&=\frac{1}{2}\sum^{3}_{s=0}\vert u_s\rangle, \quad \vert u_s\rangle=\frac{1}{2}\sum^{3}_{k=0}e^{-2\pi i\frac{sk}{4}}\vert x^k\rangle\\&&\vert u_s\cdot x^j\rangle &= \frac{1}{2}\sum^{3}_{k=0}e^{-2\pi i\frac{sk}{4}}\vert x^{j+k}\rangle\\ &&&= \frac{1}{2}\sum^{3}_{k=0}e^{-2\pi i\frac{s(k'-j)}{4}}\vert x^{k'}\rangle\\ &&&= e^{2\pi i\frac{sj}{4}}\vert u_s\rangle\\\Rightarrow &&\vert \psi_1\rangle &= \frac{1}{\sqrt{32}}\sum^{31}_{j=0}\vert j\rangle \otimes \frac{1}{2}\sum^3_{s=0}\vert u_s\rangle\\\Rightarrow &&\vert \psi_2\rangle &=\frac{1}{2\sqrt{32}}\sum^{31}_{j=0}\sum^3_{s=0}\vert j\rangle\otimes e^{2\pi i\frac{sj}{4}}\vert u_s\rangle\\&&QFT_5\vert k\rangle &=\frac{1}{\sqrt{32}}\sum^{31}_{j=0}e^{2\pi i\frac{kj}{32}}\vert j\rangle,\quad e^{2\pi i\frac{sj}{4}}=e^{2\pi i\frac{(8s)j}{32}}\\&&\Rightarrow~~&\frac{1}{\sqrt{32}}\sum^{31}_{j=0}e^{2\pi i\frac{sj}{4}}\vert j\rangle =\frac{1}{\sqrt{32}}\sum^{31}_{j=0}e^{2\pi i\frac{(8s)j}{32}}\vert j\rangle=QFT_5\vert 8s\rangle\\\Rightarrow&&\vert \psi_3\rangle&=QFT^{-1}_5\vert \psi_2\rangle=\frac{1}{2}\sum^4_{s=0}\vert 8s\rangle\otimes \vert u_s\rangle\end{align*}$$

Output distribution:

$$\{0, 8,16,24\}\sim\text{Uniform}$$

Problem 5

Suppose we have an input of $N$ numbers $x_1,x_2,\dots,x_N$. Give a rough sketch of a quantum algorithm that determines whether all inputs are different in $O(N)$ time. (You can use Grover’s algorithm that searches from any number of marked items as a subroutine.)

Reduce to Element distinctness problem

1. Divide the inputs into $\sqrt N$ blocks of size $\sqrt N$
2. Outer Grover search through each block $s$ and query all elements in it (check collision inside)
3. Inner Grover search between pair ($x\in s,y\in s$)
4. If $s$ contains an element of the collision, we found it $\Rightarrow Pr=\frac{1}{\sqrt N}$

Complexity:

• Inner Grover: $\sqrt{N}$
• Outer Grover: $\sqrt{\sqrt N}$
• Total: $\sqrt{\sqrt N}\cdot \sqrt{N}=O(N^{3/4})\le O(N)$