[Note] Quantum Computation and Quantum Information - Midterm exam

期中考詳解，原文書:

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

• 班平均：57.7
• 標準差：13.9

Problam 1

Defien the following states

$$\begin{align*}\vert y_+\rangle = \left(\begin{matrix}1/\sqrt 2\\i/\sqrt2\end{matrix}\right) \quad \vert y_-\rangle = \left(\begin{matrix}1/\sqrt 2\\-i/\sqrt2\end{matrix}\right)\end{align*}$$

Calculate the following expressions and write out the answer in matrix notations.

(a) $\vert 0\rangle\langle y_-\vert$

(b) $\vert 1\rangle\langle+\vert y_+\rangle$

(c) $\vert y_+\rangle\otimes\vert +\rangle$

(d) $\langle 1\vert \otimes \langle -\vert$

(e) $(H\otimes X)(\vert 0\rangle\otimes \vert y_-\rangle)$

(f) $(\langle-\vert\otimes \langle1\vert)(H\otimes Z)(\vert 0\rangle\otimes\vert y_+\rangle)$

(a)

$$\vert 0\rangle\langle y_-\vert = \left(\begin{matrix}1\\0\end{matrix}\right)\left(\begin{matrix}1/\sqrt2 & -i/\sqrt2\end{matrix}\right) = \left(\begin{matrix}1/\sqrt2 & -i/\sqrt2 \\ 0 & 0\end{matrix}\right)$$

(b)

$$\vert 1\rangle\langle+\vert y_+\rangle = \left(\begin{matrix}0\\1\end{matrix}\right)\left(\begin{matrix}1/\sqrt2 & 1/\sqrt2\end{matrix}\right)\left(\begin{matrix}1/\sqrt2\\i/\sqrt2\end{matrix}\right)=\left(\begin{matrix}0 \\(1+i)/2 \end{matrix}\right)$$

(c)

$$\vert y_+\rangle\otimes \vert +\rangle = \left(\begin{matrix}1/\sqrt2\\i/\sqrt2\end{matrix}\right) \otimes \left(\begin{matrix}1/\sqrt2\\1/\sqrt2\end{matrix}\right)=\left(\begin{matrix}1/2\\1/2\\i/2\\i/2\end{matrix}\right)$$

(d)

$$\langle 1\vert \otimes \langle -\vert = \left(\begin{matrix} 0 & 1\end{matrix}\right)\otimes \left(\begin{matrix}1/\sqrt2 & -1/\sqrt2\end{matrix}\right) = \left(\begin{matrix}0&0&1/\sqrt2&-1/\sqrt2\end{matrix}\right)$$

(e)

$$(H\otimes X)(\vert 0\rangle \otimes \vert y_-\rangle) = H\vert 0\rangle\otimes X\vert y_-\rangle = \left(\begin{matrix}1/\sqrt2\\1/\sqrt2\end{matrix}\right) \otimes \left(\begin{matrix}-i/\sqrt2\\1/\sqrt2\end{matrix}\right)=\left(\begin{matrix}-i/2\\1/2\\-i/2\\1/2\end{matrix}\right)$$

(f)

$$(\langle-\vert\otimes \langle1\vert)(H\otimes Z)(\vert 0\rangle\otimes\vert y_+\rangle) = \langle -\vert H\vert 0\rangle\langle 1\vert Z\vert y_+\rangle=0$$

Problem 2

Calculate the outcome probabilities and corresponding post measurement states of the following measurement settings.

(a) The state $\vert +\rangle$ in computational basis

(b) The state $\frac{1}{\sqrt2}(\vert 0\rangle\otimes\vert +\rangle+\vert 1\rangle\otimes \vert -\rangle)$ in computational basis

(c) The state is $\vert +\rangle$, measurement $\{M_1, M_2\}$ with $M_1=\displaystyle\frac{1}{2}\left(\begin{matrix}1 & -i\\i & 1\end{matrix}\right)$, $M_2=I-M_1$

(a)

$$\begin{align*}\begin{cases} Pr(0)= 1/2&\Rightarrow \vert \psi\rangle=\vert 0\rangle\\ Pr(1)= 1/2&\Rightarrow \vert \psi\rangle=\vert 1\rangle\\\end{cases}\end{align*}$$

(b)

$$\frac{1}{\sqrt2}(\vert 0\rangle\otimes\vert +\rangle+\vert 1\rangle\otimes \vert -\rangle) = \left(\begin{matrix}1/2\\1/2\\1/2\\-1/2\end{matrix}\right)$$ $$\begin{align*}\begin{cases} Pr(00)= 1/4&\Rightarrow \vert \psi\rangle=\vert 00\rangle\\ Pr(01)= 1/4&\Rightarrow \vert \psi\rangle=\vert 01\rangle\\ Pr(10)= 1/4&\Rightarrow \vert \psi\rangle=\vert 10\rangle\\ Pr(11)= 1/4&\Rightarrow \vert \psi\rangle=\vert 11\rangle\end{cases}\end{align*}$$

(c)

$$\begin{align*}\begin{cases} Pr(1)= \langle+\vert M_1^\dagger M_1\vert +\rangle = 1/2 &\Rightarrow \vert \psi\rangle=\displaystyle\frac{1}{2}\left(\begin{matrix}1-i\\1+i\end{matrix}\right)\\ Pr(2)= \langle+\vert M_2^\dagger M_2\vert +\rangle = 1/2 &\Rightarrow \vert \psi\rangle=\displaystyle\frac{1}{2}\left(\begin{matrix}1+i\\1-i\end{matrix}\right)\\\end{cases}\end{align*}$$

Problem 3

Let $\vert \psi\rangle = \frac{1}{\sqrt2}(\vert 0\rangle\otimes\vert 0\rangle+\vert 1\rangle\otimes\vert 1\rangle)$

(a) Calculate $\langle \psi\vert Z\otimes (X+Z)/\sqrt2\vert \psi\rangle$

(b) What are the eigenvalues of $(X+Z)/\sqrt2$ and $Z\otimes (X+Z)/\sqrt2$?

(c) Suppose Alice is holding the first part of $\vert \psi\rangle$ and Bob is holding the second part. If Alice measures $Z$ on her part and Bob measures $(X+Z)/\sqrt2$,what is the probabilities that their measurements have the same outcome?

(a)
Because $(X+Z)/\sqrt2 = H$

$$\begin{align*}\langle \psi\vert Z\otimes H\vert \psi\rangle = \langle \psi\vert \left( \frac{1}{\sqrt2}(\vert 0\rangle \otimes \vert +\rangle -\vert 1\rangle \otimes \vert -\rangle)\right) = \frac{1}{2}(\frac{1}{\sqrt2}+\frac{1}{\sqrt2})=\frac{1}{\sqrt2}\end{align*}$$

(b)

• $(X+Z)/\sqrt2=H \Rightarrow \lambda=\pm 1$
• $Z\otimes H \Rightarrow \lambda=\pm 1$

(c)
Outcome table ($\lambda$)

$Z\otimes I$	$I\otimes (X+Z)/\sqrt2$	$Z\otimes (X+Z)/\sqrt2$
$+1$	$+1$	$+1$
$+1$	$-1$	$-1$
$-1$	$+1$	$-1$
$-1$	$-1$	$+1$

Let $Pr(+)$ and $Pr(-)$ denotes Alice and Bob get the same outcome and different outcomes.

$$\begin{align*}\begin{cases} Pr(+)+Pr(-)=1\\ \langle Z\otimes (X+Z)/\sqrt2\rangle = Pr(+)(+1)+Pr(-)(-1)= \displaystyle\frac{1}{\sqrt2}\end{cases}\end{align*}$$

$\Rightarrow Pr(+)=\displaystyle\frac{1}{2}(1+\frac{1}{\sqrt2})$

Problem 4

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

$$\begin{eqnarray}\vert \beta_{00}\rangle=\frac{1}{\sqrt2}(\vert 00\rangle+\vert 11\rangle) \quad& \vert \beta_{01}\rangle=\frac{1}{\sqrt2}(\vert 00\rangle-\vert 11\rangle)\\\vert \beta_{10}\rangle=\frac{1}{\sqrt2}(\vert 10\rangle+\vert 01\rangle) \quad& \vert \beta_{11}\rangle=\frac{1}{\sqrt2}(\vert 10\rangle-\vert 01\rangle)\end{eqnarray}$$

Consider the quantum state $\vert +\rangle \otimes \vert \beta_{00}\rangle$ on three qubits. Suppose Alice is holding the first two qubits of $\vert +\rangle\otimes \vert \beta_{00}\rangle$ and Bob is holding the third. If 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?

$$\vert +\rangle\otimes \vert \beta_{00}\rangle = \frac{1}{2}(\vert 000\rangle+\vert011\rangle + \vert 100\rangle + \vert 111\rangle)$$ $$\begin{cases}Pr(00)=1/4 &\Rightarrow \vert\psi\rangle = \vert +\rangle\\Pr(01)=1/4 &\Rightarrow \vert \psi\rangle = \vert -\rangle\\Pr(10)=1/4 &\Rightarrow \vert\psi\rangle = \vert +\rangle\\Pr(11)=1/4 &\Rightarrow \vert \psi\rangle=\vert -\rangle\\\end{cases}$$

Problem 5

Show that for any $E$ that is an Hermitian operator on single qubit:

$$\langle \beta_{00}\vert E\otimes I\vert \beta_{00}\rangle=\langle \beta_{01}\vert E\otimes I\vert \beta_{01}\rangle=\langle \beta_{10}\vert E\otimes I\vert \beta_{10}\rangle=\langle \beta_{11}\vert E\otimes I\vert \beta_{11}\rangle$$

$$\begin{align*}\langle \beta_{00}\vert E\otimes I\vert \beta_{00}\rangle &= \frac{1}{2}(\langle 0\vert E\vert 0\rangle+\langle 1\vert E\vert 1\rangle)\\\langle \beta_{01}\vert E\otimes I\vert \beta_{01}\rangle &= \frac{1}{2}(\langle 0\vert E\vert 0\rangle+\langle 1\vert E\vert 1\rangle)\\\langle \beta_{10}\vert E\otimes I\vert \beta_{10}\rangle &= \frac{1}{2}(\langle 0\vert E\vert 0\rangle+\langle 1\vert E\vert 1\rangle)\\\langle \beta_{11}\vert E\otimes I\vert \beta_{11}\rangle &= \frac{1}{2}(\langle 0\vert E\vert 0\rangle+\langle 1\vert E\vert 1\rangle)\\\end{align*}$$

Hence, for any Hermitian operator $E$, the statement holds.

Problem 6

Consider the following ensemble:

$$p_1=2/3, \vert \psi_1\rangle=\vert +\rangle, p_2=1/3, \vert \psi_2\rangle=\vert 0\rangle$$

Calculate the following quantities.

(a) The corresponding density matrix $\rho$.

(b) The expectation value of $Z$ against $\rho$.

(c) The outcome probabilities and post measurement states of computational basis measurement.

(d) The evolved state $\rho’$ obtained after applying $H$ to $\rho$.

(a)

$$\rho=p_1\vert \psi_1\rangle\langle\psi_1\vert + p_2\vert \psi_2\rangle\langle \psi_2\vert = \left(\begin{matrix}2/3 & 1/3\\1/3&1/3\end{matrix}\right)$$

(b)

$$\langle Z\rangle = \sum_ip_i\langle \psi_i\vert Z\vert\psi_i\rangle=\text{tr}(\sum_i p_i\vert\psi_i\rangle\langle \psi_i\vert Z)=\text{tr}(\rho Z)=1/3$$

(c)

$$\begin{cases} Pr(0) = \text{tr}(M_0^\dagger M_0\rho)= 2/3 &\Rightarrow \rho_0= M_0\rho M_0^\dagger/Pr(0) = \vert 0\rangle\langle 0\vert \\ Pr(1) = \text{tr}(M_1^\dagger M_1\rho)=1/3 &\Rightarrow \rho_1= M_1\rho M_1^\dagger/Pr(1) = \vert 1\rangle\langle 1\vert\\\end{cases}$$

(d)

$$\rho'=H\rho H^\dagger = \frac{1}{6}\left(\begin{matrix}5&1\\1&1\end{matrix}\right)$$

Problem 7

Calculate a purification of

$$\rho=\left(\begin{matrix}1/2&1/4\\1/4&1/2\end{matrix}\right)$$

The eigenvalue and eignevector of $\rho$

$$\det(\rho-\lambda I)=0 ~\Rightarrow~ \lambda^2-\lambda+\frac{3}{16} = 0$$ $$\Rightarrow\begin{cases} \lambda_1 = 3/4 &\Rightarrow\vert \lambda_1\rangle = \vert +\rangle\\ \lambda_2 = 1/4 &\Rightarrow\vert \lambda_2\rangle = \vert -\rangle\end{cases}$$

The ensemble of $\rho$ is:

$$\rho=\frac{3}{4}\vert +\rangle\langle+\vert+\frac{1}{4}\vert -\rangle\langle-\vert$$

Then, the purification is

$$\vert \psi\rangle = \frac{\sqrt3}{2}\vert+\rangle\vert0\rangle+\frac{1}{2}\vert-\rangle\vert1\rangle$$

Verify:

$$\begin{align*}\text{tr}_R(\vert \psi\rangle\langle\psi\vert) &= \frac{3}{4}\vert +\rangle\langle+\vert\langle0\vert0\rangle + \frac{1}{4}\vert -\rangle\langle-\vert\langle1\vert1\rangle\\&= \frac{3}{4}\vert +\rangle\langle+\vert+\frac{1}{4}\vert -\rangle\langle-\vert\\&= \rho_A\end{align*}$$

Hence, $\vert \psi\rangle$ is a purification of $\rho$.

Problem 8

Let $\vert \psi\rangle=\frac{1}{\sqrt2}(\vert0\rangle\vert+\rangle+\vert1\rangle\vert-\rangle)$ be a quantum state on two systems $A$ and $B$. Calculate the reduced density matrix of $\vert \psi\rangle$ on system $A$.

$$\begin{align*}\text{tr}_B(\vert \psi\rangle\langle\psi\vert) &= \frac{1}{2}\text{tr}_B\left((\vert0\rangle\vert+\rangle+\vert1\rangle\vert-\rangle)(\langle0\vert\langle+\vert+\langle1\vert\langle-\vert)\right)\\&= \frac{1}{2}(\vert0\rangle\langle0\vert+\vert1\rangle\langle1\vert)\end{align*}$$

Problem 9

Find $k$ such that $n^3+2n^2+\log(n)$ is $\Theta(n^k)$.

Suppose $\exists~c_1, c_2$ such that $c_1 n^k\le n^3+2n^2+\log(n)\le c_2n^k,~\forall~n\ge n_0$.
Assume $k=3$, let

$$\begin{cases} f(n)=n^3+2n^2+\log(n)-c_1 n^3\ge 0\\ f'(n)=3n^2+4n+\frac{1}{n}-3c_1n^2 \ge 0\\\end{cases}$$

The two inequality hold for $c_1=1$, $n_0=1$. Let

$$\begin{cases} g(n)=n^3+2n^2+\log(n)-c_2 n^3\le 0\\ g'(n)=3n^2+4n+\frac{1}{n}-3c_2n^2 \le 0\\\end{cases}$$

The two inequality hold for $c_2=3$, $n_0=1$.

Hence, $n^3+2n^2+\log(n) = \Theta(n^k)$ if $k=3$.

Problem 10

In Simon’s problem, we are given an oracle function $f:\{0,1\}^n\to\{0,1\}^n$ promised that $f(x)=f(y)$ if and only if $x=y\oplus s$ for some $s\ne0^n$. The problem is finding $s$. The Simon’s algorithm generate strings $z_1,z_2,\dots,z_k$ by running the following sub-algorithm.

1. Create uniform superposition in the first register, prepare $\vert0\rangle^n$ in the second register.
2. apply the oracle
3. measure the second register
4. apply Hadamard gates on the first register
5. measure the first register and output as $z_i$

Suppose we are running Simon’s algorithm with $n=3$ and $s=110$. Write down all possible output strings $z_i$.

1. Apply $H^{\otimes n}$ on the first register: $$H^{\otimes n} \vert0\rangle^{\otimes n} \otimes \vert 0\rangle^{\otimes n} = \frac{1}{2^{n/2}}\sum_{x\in\{0,1\}^n}\vert x\rangle \otimes \vert 0\rangle^{\otimes n}$$
2. Apply oracle: $$O_f \frac{1}{2^{n/2}}\sum_{x\in\{0,1\}^n}\vert x\rangle \otimes \vert 0\rangle^{\otimes n} = \frac{1}{2^{n/2}}\sum_{x\in\{0,1\}^n}\vert x\rangle \otimes \vert f(x)\rangle$$
3. Measure the second register: $$\frac{1}{\sqrt2}\left(\vert x\rangle + \vert x\oplus s\rangle\right)$$
4. Apply $H^{\otimes n}$ on the first register: $$\frac{1}{\sqrt2}\frac{1}{2^{n/2}}\sum_{z\in\{0, 1\}^n}\left((-1)^{x\cdot z} + (-1)^{(x\oplus s) \cdot z}\right)\vert z\rangle$$
5. Measure the first register. Only the states with $(-1)^{x\cdot z} + (-1)^{(x\oplus s) \cdot z} \ne 0$ can be measured. Suppose $n=3$, $s=110$:

$x$	$x\oplus s$	Possible $z$
$000$	$110$	$000, 001, 110, 111$
$001$	$111$	$000, 001, 110, 111$
$010$	$100$	$000, 001, 110, 111$
$011$	$101$	$000, 001, 110, 111$

Since $(-1)^{(x\oplus s)\cdot z} = (-1)^{x\cdot z+s\cdot z}$, $z$ must satisfy $s\cdot z ~(\text{mod}~2)=0$.

The possible $z=000, 001, 110, 111$.

Problem 11

Calculate the eigenvalues of $aX+bY+cZ$, where $X,Y,Z$ are the Pauli matrices and $a,b,c$ are real nubmers.

$$\begin{align*}&S = aX+bY+cZ = \left(\begin{matrix} c & a-bi\\a+bi&-c\end{matrix}\right)\\\Rightarrow ~&\det(S-\lambda I)=0\\ \Rightarrow ~&(c-\lambda)(-c-\lambda)-(a-bi)(a+bi)=0\\\Rightarrow ~&\lambda^2-c^2-a^2-b^2=0\\\Rightarrow ~&\lambda=\pm\sqrt{a^2+b^2+c^2}\end{align*}$$

Problem 12

Calculate the output state of the following circuit

1. Apply $H$, $\vert 000\rangle \to \frac{1}{\sqrt2}(\vert 000\rangle+\vert 100\rangle)$.
2. Apply controlled-not, $\frac{1}{\sqrt2}(\vert 000\rangle+\vert 100\rangle) \to \frac{1}{\sqrt2}(\vert 000\rangle+\vert 110\rangle)$.
3. Apply controlled-not, $\frac{1}{\sqrt2}(\vert 000\rangle+\vert 100\rangle) \to \frac{1}{\sqrt2}(\vert 000\rangle+\vert 111\rangle)$.