\documentclass[11pt]{amsproc}
\usepackage{amssymb}
%\baselineskip 16pt
\usepackage{graphicx}
\setlength{\oddsidemargin}{-0.15in}
\setlength{\evensidemargin}{-0.15in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{9in}
\setlength{\textwidth}{6.5in}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{definition}[theorem]{Definition}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{example}[theorem]{Example}
\newtheorem{remark}[theorem]{Remark}
\def\qed{\hfill $\Box$\medskip}
\def\diag{{\rm diag}\,}
\def\la{{\langle}}
\def\ra{{\rangle}}
\def\tr{{\rm Tr}}
\def\pt{{\rm pt}}
\def\IR{{\mathbb R}}
\def\IC{{\mathbb C}}
\def\IF{{\mathbb F}}
\def\II{{\mathbb I}}
\def\IN{{\mathbb N}}
\def\IQ{{\mathbb Q}}
\def\IZ{{\mathbb Z}}
\def\cH{{\cal H}}

\def\ph{h\mkern-10mu\mathchar'26}

\pagestyle{empty}

\begin{document}
\openup 1.3\jot

\noindent
{\bf Math 410 Final Examination} 
{\hfill\bf Due: 11:59 p.m., 17 December, 2018}

\bigskip
{\bf If you have time and interest, try 2(c), 3(c), 8(d) for extra credits.
\ Good Luck!}

\bigskip
\begin{itemize}
\item[1.] Suppose $A \in M_m$ and $B \in M_n$ have eigenvalues 
$a_1, \dots, a_m$ and $b_1, \dots, b_n$, respectively. 
\begin{itemize}
\item[(a)] 
Show that $A\otimes B$ has eigenvalues $a_ib_j$ with $1 \le i \le m, 1 \le j \le n$.
\item[(b)] Determine the eigenvalues and their multiplicities 
of each of the following matrices
$\sigma_z \otimes \cdots \otimes \sigma_z$ ($n$ times), \quad
$\sigma_x \otimes \cdots \otimes \sigma_x$ ($n$ times), \quad
$H \otimes \cdots \otimes H$ ($n$ times),

where $H\in M_2$ is the Hadamard gate.

\end{itemize}

  
\medskip
\item[2.] Let $\rho = p |0\ra \la 0| + (1-p) |1\ra \la 1|$ and 
$\sigma = \begin{pmatrix}a_{11} & a_{12} \cr \bar a_{12} & a_{22}\cr
\end{pmatrix} \in M_2$ be
density matrices.
Suppose $\lambda_1, \lambda_2$
are the eigenvalues of $\rho^{1/2} \sigma \rho^{1/2}$.

\begin{itemize}
\item[(a)] Show that  
$\lambda_1 + \lambda_2
= p a_{11} + (1-p)a_{22}$ and 
$\lambda_1\lambda_2 = p(1-p)\det(\sigma)$.

\item[(b)] Recall that the fidelity of $\rho, \sigma$ is
$F(\rho,\sigma) = \tr\sqrt{\rho^{1/2} \sigma \rho^{1/2}} 
= \lambda_1^{1/2}+\lambda_2^{1/2},$ 
Show that
$$F(\rho, \sigma)^2 \ge pa_{11} + (1-p)a_{22} \ge \min \{p,1-p\}.$$

\item[(c)] (Extra 5 points) 
Determine ALL the density matrices $\sigma \in M_2$ such that 
the fidelity $F(\rho,\sigma) = \sqrt{p}$ if $p \le 1/2$. 
{\hfill [Hint: Consider 2 cases: $p \ne 1/2$, $p = 1/2$.]}

\end{itemize}


\medskip\item[3.] (See \S 9.1 and \S 9.2) Let 
$F_1,\dots, F_r$ be $m\times n$ complex matrices.
Define $\Phi: M_n \rightarrow M_m$ by
$$\Phi(A) = F_1 A F_1^\dag + \cdots + F_r A F_r^\dag.$$




\begin{itemize}
\item[(a)] Show that if $A$ is positive semidefinite, then 
$\Phi(A)$ is positive semidefinite.
That is,

\qquad
show that if $\la v| A | v\ra \ge 0$ for all $|v\ra \in \IC^n$,
then $\la u|\Phi(A)|u\ra \ge 0$ for all $|u\ra \in \IC^m$.

{\hfill 
[Hint: Show that $\la u|F_jAF_j^\dag|u\ra \ge 0$ for every $j$.]
}
\item
[(b)] Show that if  
$F_1^\dag F_1 + \cdots + F_r^\dag F_r = I_n$, 
then $\tr(A) = \tr(\Phi(A))$ for all $A \in M_n$.


{\hfill 
[Hint: Note that $\tr(F_jAF_j^\dag) = \tr(A F_j^\dag F_j)$ for every $j$.]
}

\item[(c)] (Extra 5 points) Show that if 
$\tr(A) = \tr(\Phi(A))$ for all density matrices
$A \in M_n$, then 
$F_1^\dag F_1 + \cdots + F_r^\dag F_r = I_n$.

\end{itemize}


\medskip\item[4.] 
Determine the change of the Bloch sphere under the
following quantum operation:
$${\mathcal E}(\rho) = (1-2p) \rho + p (\sigma_x \rho \sigma_x + \sigma_z \rho \sigma_z),
\qquad p \in (0,1/2).$$


\medskip\item[5.] 
In the nine-qubit code (\S 10.3), determine the error and the 
correction
operation in each of the following.

\begin{itemize}
\item[(a)] $(A_i,B_i) = (0,0)$ for $i = 1,2,3$ and $(A_4,B_4) = (1,0)$.

\item[(b)] $(A_i,B_i) = (0,0)$ for $i = 1,2$, and $(A_j,B_j) = (0,1)$ for $j = 3,4$.


\end{itemize}


\medskip
\item[6.] For the five-qubit QECC
described in \S 10.5.2, show that 
if $|\Psi\ra$ is changed to $Y_0|\Psi\ra$,
then 
$$M_0|\Psi\ra = |\Psi\ra \quad \hbox{ and } \quad
M_i|\Psi\ra = -|\Psi\ra \quad \hbox{ for } i = 1,2,3.$$

\noindent
Remark.
The point of this problem is to verify the seventh column of Table 10.70.

\noindent
Using the table to 
``prove'' the result is not acceptable.

\item[7.]
 Consider the following encoding / decoding circuit for the 
three qubit bit-flip quantum error correction scheme:
\begin{center}
{\includegraphics[height=1.2cm,width=6cm]{bit-flip.jpg}}
\end{center}

\noindent
Suppose $|\psi\ra = a|0\ra + b|1\ra$ goes through the circuit.
Determine the final three qubit sate if

(a)  an error occurs in the first qubibit,

(b)  an error occurs in the second qubit,

(c)  an error occurs in the third qubit.

\item[8.] 
Suppose one can encode 2-qubit states as $n$-qubit states 
so that $2$-bit general errors can be corrected, 
i.e., up to  2-bit errors caused by $X,Y,Z$ can be corrected.
In particular, $|00\ra, |01\ra, |10\ra, |11\ra$
are encoded as the logical
$n$-qubit states: $|00\ra_L, |01\ra_L, |10\ra_L, |11\ra_L$.


(a) Show that there should be $1+3n+3^2n(n-1)/2$ 
states in $\{|x_1 \cdots x_n\ra: x_j \in \{0,1\}\}$

\qquad decoded as  $|00\ra_L$.

(b) Show that $4(1+3n+9n(n-1)/2) \le 2^n$.

(c) Find the smallest $n\in \IN$ satisfying the condition in (b).

(d) (Extra 20 points)
 Prove or disprove that 
one can construct an $n$-qubit 
QECC for 

\qquad
general errors with the minimum $n$ found in the above
problem.


\end{itemize}


\end{document}

