
\documentclass[11pt]{article}
\usepackage{amsmath, amssymb, amsfonts}
\usepackage{graphicx}
\setlength{\oddsidemargin}{-0.15 true in}
\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{problem}[theorem]{Problem}
\newtheorem{remark}[theorem]{Remark}
\renewcommand{\theequation}{\thesection.\arabic{equation}}
%\baselineskip 16pt
\def\qed{\hfill $\Box$\medskip}
\def\diag{{\rm diag}\,}
\def\la{{\langle}}
\def\ra{{\rangle}}
\def\IC{{\mathbb{C}}}
\def\IR{{\mathbb{R}}}
\def\ZZ{{\mathbb{Z}}}
\def\IZ{{\ZZ}}
\def\IN{{\mathbb{N}}}
\def\IQ{{\mathbb{Q}}}
\def\LL{{\mathbb{L}}}
\def\HH{{\mathbb{H}}}
\def\DD{{\mathbb{D}}}
\def\TT{{\mathbb{T}}}
\def\tr{{\rm tr}\,}
\pagestyle{empty}
\begin{document}
\openup 1 \jot


\noindent
\bf\noindent
Lecture notes on Quantum Computing 

\medskip\noindent
Chapter 1 Mathematical Background
\rm
{\hfill Basic notation: $\IN \subseteq \IZ \subseteq \IQ \subseteq \IR \subseteq \IC$.}

\medskip\noindent
{\bf \S 1.1 Vector spaces}

\begin{itemize}
\item $\IC^n$ is the set of complex $n\times 1$ column vectors.
\item $\IC^n$ is a vector space under scalar multiplication and addition.
\item We use the Dirac notation, bra-vector $\la x|$ and ket-vector $|x\ra$.
\end{itemize}

\noindent{\bf 
Terminology} zero vector, (additive) inverse of a vector, complex and real 
vector spaces.

\newpage
\medskip\noindent
{\bf \S 1.2 Linear independent vectors and basis}

\begin{itemize} 
\item 
A set of vectors $\{|u_1\ra, \dots, |u_m\ra\}\subseteq \IC^n$ 
is linearly dependent if there are $a_1, \dots, a_m \in \IC$ not all zero such that
$a_1 |u_1\ra + \cdots + a_m |u_m\ra = |0\ra$. Else, the set is linear independent.
(How to check?)

\item A set of vectors
A set of vectors $\{|u_1\ra, \dots, |u_m\ra\}\subseteq \IC^n$ 
is generating if for every $|v\ra \in \IC^n$ 
there are $a_1, \dots, a_m \in \IC$ not all zero such that
$|v\ra = a_1 |u_1\ra + \cdots + a_m |u_m\ra$. (How to check?)


\item A linearly independent generating set for $\IC^n$ is a basis. The number of vectors in 
it must be $n$, known as the dimension of $\IC^n$.

\end{itemize}

\newpage
\medskip\noindent
{\bf \S 1.3 Linear functions and dual vector spaces}

\begin{itemize}
\item A function $f: \IC^n \rightarrow \IC$ is a linear functional if 
$f(|u\ra + |v\ra) = f(|u\ra) + f(|v\ra)$ and $f(a|u\ra) = af(|u\ra)$ for all $a \in IC, 
|u\ra, |v\ra \in \IC^n$.

\item The set of functional on $\IC^n$ form a vector space ${\IC^n}^*$, 
known as the dual space of
$\IC^n$. 

\item Each linear functional can be defined by $f(|u\ra)= \la v | u\ra$
for some $|v\ra \in \IC^n$. Thus, ${\IC^n}^*$ can be viewed as the space of 
complex row vectors.
\end{itemize}

\newpage

\noindent
{\bf Inner product and length of vectors} 

\begin{itemize}
\item Define the inner product of $|u\ra, |v\ra \in \IC^n$  by
$\la u| v\ra = \bar u_1 v_1 + \cdots + \bar u_n v_n = u_1^*v_1 + \cdots + u_n^* v_n \in \IC$.

\item Then $\la u|v \ra = \la v| u \ra^*$, 
$\la u|c_1 v + c_2w\ra = c_1 \la u|v \ra + c_2 \la u| w \ra$ for any
$c_1, c_2 \in \IC$, $|u\ra,
|v\ra, |w\ra \in \IC^n$.

\item Also,  $\la u, u\ra = \sum_{j=1}^n |u_j|^2 \ge 0$, where the equality holds if and only if 
$|u\ra = |0\ra$. 

\item Define $\|u\| = \sqrt{\la u|u\ra}$ as the length or norm of $|u\ra$.

\item 
Two vectors $|u\ra, |v\ra \in \IC^n$ are orthogonal if $\la u, v\ra = 0$.
\end{itemize}

\newpage
\medskip\noindent
{\bf \S 1.4 Orthonormal basis and the Gram-Schmidt process}

\begin{itemize}
\item 
Express a vector as a linear combination of orthonormal basis $\{|e_1\ra, \dots, |e_n\ra\}$.
\item The set $\{P_j = |e_j\ra \la e_j|: j = 1, \dots, n\}$ form a complete set of 
projection operators/matrices.
\item Gram-Schmidt orthogonalization/orthonormalization.
\end{itemize}

\newpage
\medskip\noindent
{\bf \S 1.5 Linear operators and Matrices}

\begin{itemize}
\item A function $T: \IC^n\rightarrow \IC^n$ is linear if $T(|u\ra + |v\ra) = 
T(|u\ra) + T(|v\ra)$ and $T(c|u\ra)= cT(|u\ra)$ for all $c \in \IC, |u\ra, |v\ra \in \IC^n$.
 
\item Every linear function on $\IC^n$ has the form $T(|v\ra) = A|v\ra$
for an $n\times n$ matrix $A=(A_{ij})$.

\item Let $A$ be a matrix. We can define the transpose $A^t$, the conjugate
$A^*$ or sometimes $\bar A$, and the Hermitian conjugate $A^{\dag} = (\bar A)^t$.

\item A square matrix $A$ is Hermitian if $A = A^{\dag}$; $A$ is unitary if $A^\dag A = I_n$; 
$A$ is normal if $A^\dag A = AA^\dag$.  


\end{itemize}


\newpage
\noindent
{\bf \S 1.7 Pauli matrices}
$\sigma_x  = \begin{pmatrix} 0 & 1 \cr 1 & 0 \cr\end{pmatrix}$,
$\sigma_y  = \begin{pmatrix} 0 & -i \cr i & 0 \cr\end{pmatrix}$, 
$\sigma_z = \begin{pmatrix} 1 & 0 \cr 0 & -1\cr\end{pmatrix}$ and their properties

\begin{itemize}
\item The Jordan product $\{\sigma_u,\sigma_v\} = 
\sigma_u \sigma_v + \sigma_v \sigma_u = 2\delta_{uv} I_2$, where 
$\delta_{uv}$ is the Kronecker symbol.

\item The Lie product $[\sigma_u,\sigma_v] = \sigma_u\sigma_v - \sigma_v\sigma_u
= 2i\xi_{uv}\sigma_w$ where $\xi_{uv} = 1$ if $(u,v) = (x,y), (y,z), (z,x)$
and $\xi_{uv} = -1$ if $(u,v) = (y,x), (z,y), (x,z)$.
\end{itemize}

\newpage
\
~
\vskip -.7in
\noindent
{\bf \S 1.6 \& 1.8 Eigenvalues}

Let $A$ be an $n\times n$ complex matrix. Then $\lambda\in \IC$ is an eigenvalue 
of $A$ if there is a nonzero eigenvector $|\lambda\ra$ such that
$A |\lambda \ra = \lambda |\lambda\ra$.

\begin{itemize}
\item The matrix $A$ always has complex eigenvalues because $\det(tI - A) = 0$ always
has a solution $\lambda$ so that $(\lambda I-A)|\lambda\ra = |0\ra$ has non-trivial solution.

\item There is a unitary matrix $U$ such that $U^\dag AU = T$ is in upper triangular form.
Moreover, $\det(tI - A) = \det(tI - T) = (t-T_{11}) \cdots (t-T_{nn})$.

\item The matrix $A$ is normal if and only if $T$ is diagonal; the matrix $A$ is 
unitary if and only if $T$ is a diagonal matrix so that the diagonal entries have moduli 1;
the matrix $A$ is Hermitian if and only if $T$ is a real diagonal matrices.
\end{itemize}  

\it Proof of the Schur Triangularization Lemma. \rm
Suppose $A \in M_n$. We show that there a unitary $U \in M_n$ such that 
$U^\dag A U = T$ is in upper triangular form.
We prove the result by induction on $n$. If $n =1$, the result is trivial.
Suppose the result holds for matrices in $M_{n-1}$. Let $A \in M_n$.
Solve $\det(tI - A) = 0$ to get a solution $\lambda$.There is a nonzero
vector $|\lambda\ra$ such that $A|\lambda\ra = \lambda |\lambda\ra$.
We may replace $|\lambda\ra$ by $|\lambda\ra/ \|\lambda\ra\|$ and assume that
$|\lambda\ra$ has unit length,
and we can let $U_1 \in M_n$ be unitary with
$|\lambda\ra$ as the first column. Then 
$AU_1 = [A |x_1\ra  \cdots  A|x_n\ra] = [\lambda |x_1\ra A |x_2\ra \cdots 
 A|x_n\ra]$ if $U_1$ has columns 
$|x_1\ra = |\lambda\ra, |x_2\ra, \dots, |x_n\ra$.
Because
$\la x_1|A|x_1\ra = \lambda$,
and  $\la x_j | A | x_1 \ra = 0$ for $j = 2, \dots, n$, we see that
$U^\dag A U = \begin{pmatrix}\lambda_1 & * \cr 0 & A_1\cr\end{pmatrix}$.
By induction assumption there is a unitary $U_2 \in M_{n-1}$ such that 
$U_2^\dag A_1 U_2 = T_1$ in upper triangular form.
Let $U = U_1 \begin{pmatrix} 1 & 0 \cr 0 & U_2\cr\end{pmatrix}\in M_n$. 
Then $U^\dag U = I_n$ so that $U$ is unitary, and 
$U^\dag A U = \begin{pmatrix} 1 & 0 \cr 0 & U_2^\dag\cr \end{pmatrix}
\begin{pmatrix}\lambda_1 & * \cr 0 & A_1\cr\end{pmatrix}
 \begin{pmatrix} 1 & 0 \cr 0 & U_2\cr \end{pmatrix} = \begin{pmatrix}
 \lambda & * \cr 0 & T_1\cr\end{pmatrix}$ is upper triangular form. \qed
 
 \it Proof of the consequences for normal, unitary, Hermitian matrices.
 \rm Let $U^\dag A U = T$.
 Suppose $A$ is normal, i.e., $A^\dag A  = A A^\dag$. Then 
 $$T^\dag T = (U^\dag AU)^\dag (U^\dag A U) = 
 (U^\dag A^\dag U)  (U^\dag A U) = U^\dag A^\dag A U 
 = U^\dag A A^\dag U = TT^\dag.$$
Now, the $(1,1)$ entry of $T^\dag T$ is $|T_{11}|^2$
and the $(1,1)$ entry of $TT^\dag$ is $|T_{11}|^2 + \cdots + |T_{1n}|^2$.
So, $T_{12} = \dots = T_{1n} = 0$. Now, consider the $(2,2), \dots, (n,n)$ 
entries,
we see that only the diagonal entries of $T$ can be nonzero.
So, $T$ is a diagonal matrix.
Conversely, if $U^\dag A U = T$ is in diagonal form, then 
$A = UTU^\dag$ so that $A^\dag A = U^\dag T^\dag U U^\dag T U = U^\dag T^\dag T U$
and $AA^t = U^\dag TT^\dag U$.
Note that for a diagonal matrix $T$, we have 
$TT^\dag = T^\dag T$ is a diagonal matrix 
with diagonal entries $|T_{11}|^2, \dots, |T_{nn}|^2$. So, $A^\dag A = A A^\dag$.

Now, if $A$ is unitary, then $A$ is normal and $T = U^\dag  A U$ is diagonal,
and is unitary. So, $T^\dag T = I_n$ implies $|T_{jj}|^2 = 1$ for all $j$.
Conversely, if $A = U^\dag T U$ such that $T$ is diagonal with all diagonal 
entries satisfying $|T_{jj}| = 1$, then $A^\dag A = UT^\dag U^\dag U T U^\dag
= U T^\dag T U^\dag = UU^\dag = I_n$.

Finally, suppose $A$ is Hermitian, then $A = A^\dag$ so that the 
diagonal matrix $T$ satisfies 
$T^\dag = U A^\dag U^\dag = UAU^\dag = T$ So, $T$ is Hermitian and 
all the diagonal entries of $T$ are real.
Conversely, if $T$ is a real diagonal matrix, then 
$T = T^\dag$ so that $A^\dag = U^\dag T^\dag U = U^\dag T U = A$. \qed 
 

\newpage
\noindent
{\bf \S 1.9  Spectral decomposition}

\begin{itemize}
\item Suppose $A$ is normal and $A = UDU^\dag$, where $D$ has diagonal entries $\lambda_1, \dots, 
\lambda_n$ and $U$ has orthonormal columns $|\lambda_1\ra, \dots, |\lambda_n\ra$.
Then 
$A = \lambda_1 |\lambda_1\ra \la \lambda_1| + \cdots + \lambda_n |\lambda_n\ra\la \lambda_n|$
so that 
$$A^k = \sum_{j=1}^n\lambda_j^k |\lambda_j\ra \la \lambda_j|
\qquad \hbox{ and } \qquad e^{A} = \sum_{k=0}^\infty \frac{1}{k!} A^k 
= \sum_{j=1}^n e^{\lambda_j} |\lambda_j\ra \la \lambda_j|.$$
\item Also, $A = \sum_{\alpha} \alpha P_\alpha$, where 
$P_\alpha = \sum_{\lambda_j = \alpha} |\lambda_j\ra \la \lambda_j|$.
Then $A^k = \sum_{\alpha} \alpha^k P_\alpha$ and $e^A = \sum_{\alpha} e^{\alpha} P_\alpha$.
\end{itemize}

\it Proof. \rm  Because $A|\lambda_j\ra = \lambda_j |\lambda_j\ra$
for $j = 1, \dots, n$, we have $AU = U D$ so that 
$$A = UDU^\dag = \sum_{j=1}^n \lambda_j
|\lambda_j\ra \la \lambda_j |.$$
Now, 
$$A^k = \underbrace{UDU^\dag \cdots UDU^\dag}_k 
= UD^k U^\dag = \sum_{j=1}^n \lambda_j^k |\lambda_j\ra
\la \lambda_j|,$$ 
and
$$e^{A} = \sum_{k = 0}^\infty \frac{1}{k!} A^k = \sum_{k=0}^\infty \frac{1}{k!} 
\sum_{j=1}^n\lambda_j^k
|\lambda_j \ra \la \lambda_j| = \sum_{j=1}^n e^{\lambda_j}|\lambda_j \ra \la \lambda_j|.$$
\newpage
\noindent
{\bf \S  1.9 Singular value decomposition (SVD)}

\medskip
\noindent
{\bf Theorem}  \it Every square matrix $A$ can be written as $A = UDV^\dag$, where 
$U, V$ are unitary and $D = \diag(s_1, \dots, s_n)$ with $s_1 \ge \cdots \ge s_n \ge 0$.
\rm

\it Proof. \rm Proof by induction on the size of $A$. Clearly, the result holds for $n = 1$.
Assume that the result is true for matrices of size less than $n$ with $n \ge 2$.
Choose unitary $U, V$ such that $S = U_1^\dag A V_1$ has largest $(1,1)$ entry with largest
real part $S_{11}$. First, we have $S_{11} \ge 0$, else replace $V$ by $e^{it}V$
for some suitable $e^{it}$. Next, we 
claim that $S_{1j} = 0$ for $j = 2, \dots, n$. If not, we can replace
$V_1$ by $V_1R$ where $R$ is obtained from $I_n$ by changing the $2\times 2$ submatrix
in rows and columns $1, j$ by
$\frac{1}{\sqrt{S_{11}^2 + |S_{1j}|^2}} 
{\footnotesize \begin{pmatrix} S_{11} & S_{1j}\cr  \bar S_{1j} & -S_{11}\cr\end{pmatrix}}$.
Then $U_1^\dag A V_2R$ has $(1,1)$ entry equal to $\sqrt{ S_{11}^2 + |S_{1j}|^2} > S_{11}$,
which is a contradiction. Similarly, we can show that $S_{j1} = 0$ for all $j = 2, \dots, n$.
Thus,  $S = {\footnotesize \begin{pmatrix} 1 & 0 \cr 0 & \hat S \cr\end{pmatrix}}$.
By induction assumption, there are unitary $U_2, V_2$ such that $U_2^\dag \hat S V_2 = 
\diag(s_2, \dots, s_n)$. 

Let 
$V = V_1 {\footnotesize\begin{pmatrix} 1 & \cr &  V_2  \cr \end{pmatrix}}$
and $U = U_1 {\footnotesize \begin{pmatrix} 1 & \cr & U_2 \cr\end{pmatrix}}$. Then
$U^\dag A V = \diag(s_1, \dots,s_n)$. \qed


\medskip\noindent
{\bf Note} $s_1, \dots, s_n$ are the singular values of $A$ and equal the nonnegative square
roots of the eigenvalues of $A^\dag A$ or  / and $A A^\dag$. 

The matrix $A$ has rank $k$ if and only if it has $k$ nonzero singular values.

In practice, write $A^\dag A = V D^2 V^\dag$ so that the columns of the unitary matrix $V$,
$|v_1\ra, \dots, |v_n\ra$, are
the right singular vectors. Then $AV=UD$ for some unitary $U$ such that $A= UDV^\dag$.
In particular, if $s_j \ne 0$ then 
$|u_j\ra = A|v_j\ra/s_j$; if $A$ has rank $k$ so that $s_k > 0 = s_{k+1} = \cdots = s_n$ 
then $|u_{k+1}\ra, \dots, |u_n\ra$ are chosen so that 
$\{|u_1\ra, \dots, |u_n\ra\}$ is an orthonormal basis.

In Matlab, we use the command $[U,D,V] = {\rm svd}(A)$.

\newpage
\noindent
{\bf \S 1.10 Tensor product (Kronecker product)}

\begin{itemize}
\item $A \otimes B = (A_{ij}B)$ satisfies 

(a) $(A\otimes B)(C\otimes D) = (AC)\otimes (BD)$,

(b) $A\otimes (B+C) = A\otimes B + A\otimes C$, $(A\otimes B)^\dag = A^\dag \otimes B^\dag$,
$(A\otimes B)^{-1} = A^{-1} \otimes B^{-1}$.

(c) $\tr(A\otimes B) = (\tr A)(\tr B)$ and 
$\det(A\otimes B) = \det(A)^n\det(B)^m$ if $A \in M_m, B \in M_n$.
\end{itemize}

\it Proof. \rm
(a) Let $A$ be $m\times n$, $B$ be $r\times s$, $C$ be $n\times p$, $D$ be $s\times q$.
Then $A\otimes B = (A_{ij}B)$ is $mr\times ns$, and 
$C\otimes D = (C_{ij}D)$ is $ns \times pq$. Now 
$$(A\otimes B)(C\otimes D) = (A_{ij}B)(C_{ij}D) = (f_{rs} BD),$$ where
$f_{rs} = \sum_{\ell = 1}^n A_{r\ell}C_{\ell s} = (AC)_{rs}$.
So, $(f_{rs} BD) = AC \otimes BD$.

\medskip
(b) $A\otimes (B+C) = (A_{ij}(B+C)) = (A_{ij}B) + (A_{ij}C) = A\otimes B + A \otimes C$.

\medskip
$(A\otimes B)^\dag 
= \overline{A\otimes B)^t = \overline(A^t \otimes B^t)} = A^\dag \otimes B^\dag$.

\medskip
$(A^{-1}\otimes B^{-1})(A\otimes B) = (A^{-1}A) \otimes (B^{-1}B) = I_m \otimes I_n
= I_{mn} \ \Longrightarrow \
A^{-1} \otimes B^{-1} = (A\otimes B)^{-1}$.

\medskip
(c) Note that $\tr(AB) = \sum_{i=1}^n \sum_{j=1}^n A_{ij}B_{ji} = \tr(BA)$.
Assume that $A$ is $m\times m$ and $B$ is $n\times n$.
Let $U, V$ be unitary and $S, T$ be triangular such that 
$A = USU^\dag$ and $B = VTV^\dag$. Then $\tr A = \tr S, \tr B = \tr T$,
$$\tr(A\otimes B) = \tr((U\otimes V)(S\otimes T)(U\otimes V)^\dag) = 
\tr(S\otimes T) 
$$
$$= \sum_{i=1}^m {S_{ii}} \sum_{j=1}^n T_{jj} 
 (\sum_{i=1}^m S_{ii})(\sum_{j=1}^n T_{jj})
= (\tr S)(\tr T) = (\tr A)(\tr B).$$
Also,
$$\det(A\otimes B) = \det((U\otimes V)(S\otimes T)(U\otimes V)^\dag) = 
\det(S\otimes T) 
$$
$$= \prod_{i=1}^m {S_{ii}}^n \det(T) = 
(\det S)^n (\det T)^m = (\det A)^n(\det B)^m.$$

\end{document}

 