%% LyX 1.4.4 created this file.  For more info, see http://www.lyx.org/.
%% Do not edit unless you really know what you are doing.
\documentclass[english]{article}
\usepackage[T1]{fontenc}
\usepackage[latin1]{inputenc}
\usepackage{geometry}
\geometry{verbose,letterpaper,tmargin=1in,bmargin=1in,lmargin=1in,rmargin=1in}
\setlength{\parskip}{\medskipamount}
\setlength{\parindent}{0pt}
\usepackage{amsmath}
\usepackage{amssymb}

\makeatletter

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
%% Because html converters don't know tabularnewline
\providecommand{\tabularnewline}{\\}

\usepackage{babel}
\makeatother
\begin{document}
COMSW4281 Lecture Notes

Professor Anargyros Papageorgiou

Spring 2007


\section*{Lecture 1 (17 January)}


\subsection*{Course Information}

Course email: cs4281@columbia.edu (to contact TA, submit homeworks)\\
Professor email: ap@cs\\
Textbook: Nielsen \& Chuang\\
Courseworks\\
Grading: Homework 30\%, Midterm 30\%, Final 40\%\\
Matlab recommended for programming\\
Quizzes might be given, averaged into midterm/final grades\\
Office Hours: Tues 1-2, Wed 12-1


\subsection*{Why Quantum Computing}

1. Moore's Law - Density of transistors increases every 18 months,
which means within 10-20 years quantum effects will become a barrier

2. Quantum Algorithms - Factoring, Search Algorithms\\
 \\
Best Classical Factoring Algorithm: Number Field\\
Performance: log $2^{C(\log N)^{1/2}}\left(\log\log N\right)^{2/3}$\\
Quantum Algorithm Discovered 1994 by Peter Shor\\
Performance: $\left(\log N\right)^{3}$ w/ probability O(1) (or $>\frac{1}{2}$)\\
In general, quantum algorithms do not give results with certainty,
but if probablity is greater than one half, they can be repeated to
get sufficient certainty\\
\\
Discrete Logarithm Problem: given numbers $a$ and $b=a^{s}$, find
s.\\
Quantum solution: 1 query $O\left(\left(\log s\right)^{2}\right)$\\
When looking at quantum performance, have to look at the number of
queries as well as number of operations.\\
\\
Search Algorithm\\
Given binary string length N (for some huge N), find position of subtring\\
Classical Lower Bound O(N), even for randomized algorithms, no success
guarantee\\
Quantum Algorithm O($\sqrt{N}$)\\
Quantum Algorithm only has polynomial advantage over classical, not
exponential as in factoring\\
Grover's Algorithm\\
\\
Boolean mean, Numerical integration - related to search, same polynomial
speedup

3. Quantum cryptography for key distribution\\
Can replace PKI, which assumes that factoring is hard. Private key
distribution over a quantum channel can't be eavesdropped upon without
detection. Earliest successes and applications of quantum computing
are in this area.

4. Study of Quantum Mechanics as a model of computation\\
Church-Turing Thesis - any algorithmic computation can be simulated
(efficiently) by a turing machine (which is probabalistic).\\
(efficiently) - part of strong version of thesis, weaker one leaves
it out\\
(Thesis) - means conjecture or belief, not a provable theorem. \\
(which is probalistic) - fix for thesis added in 1970s. Solovay Strassev
came up with a randomized algorithm for primality testing which can
give arbitrary levels of certainty at vastly improved efficiency over
deterministic algorithm\\
\\
Deutsch 1985\\
Came up with quantum model of computation in order to produce more
solid version of CT thesis. Conjectured a Universal Quantum Computer
that can simulate any physical process. It isn't known if this is
really possible. (His paper is in courseworks, first 3-4 pages are
philosophical and accessible, rest is more technical)\\
\\
5. Study of Entanglement. 2 qubit system that can't be seperated...
EPR state... Quantum Teleportation... More later in the course.


\subsection*{Quantum Systems}

Size of quantum system is $C^{N}$where N is number of particles,
C is number of coordinates, set of complex numbers used to represent
a state.

Quantum states can be expressed as vectors\\
 $x=\left(\begin{array}{c}
x_{1}\\
x_{1}\\
\vdots\\
x_{n}\end{array}\right)\in\mathbb{C}^{N}$

Dirac notation is used in many cases instead of standard linear algebra
notation. Dirac {}``captures the transpose of a matrix'' ($X^{H}$
- hermetian transpose of X)

For quantum states, $\left\Vert x\right\Vert =1$. ($\left\Vert x\right\Vert $
- euclidean norm of X, square root of sum of squares)

States are transformed by unitary matrices $U_{x}$. Unitary means
preserves length, that $UU^{H}=I$, or $U^{-1}=U^{H}$. Examples of
unitary matrices: identity matrix, any rotation matrix, and the Hausholder
matrix\\
 ($P=I-2UU^{H}$, $\left\Vert U\right\Vert =1$). Hausholder matrix
has something to do with mirrors/reflection.


\subsection*{Quantum Computing Nutshell}

$X_{0}$ - initial states\\
$Y=V_{T}=U_{3}U_{2}U_{1}X_{0}$ - result is unitary matrices applied
to input

Complexity is $n\cdot T$, where $T$ is number of matrices, n=log
N=number of qubits, and N=length of quantum register


\section*{Lecture 2 (22 January)}


\subsection*{Quantum Computation}

Start with $X_{0}$, initial quantum state which is a vector. Apply
unitary operations, $U_{1}\ldots U_{t}$ (Unitary meaning $U_{j}^{H}U_{j}=I$).
Cost can be measured in terms of number of qubits n, and number of
operations t.


\subsection*{Qubits}

Classical computation uses bits with states 0 and 1\\
Quantum computation uses qubits whose states are superpositions of
states $\left|0\right\rangle $ and $\left|1\right\rangle $. (pronounced
$\texttt{"}$ket zero$\texttt{"}$ and $\texttt{"}$ket one.$\texttt{"}$)

Superposition states of qubits occur in a variety of physical systems.
Simplest example is an electron that can be in a ground state 0 and
excited state 1. You can shine light to put electron in excited state
and reduce light to put it into ground state, or you can increase
and decrease light repeatedly to put electron into superposition state.
Other examples of superposition states occur in polarizations of photons,
and intermediate angle spins of electrons traveling through magnetic
fields

Mathematical description of qubits. Formally, a qubit is an element
of a two dimensional hilbert space $\mathcal{H}$.

A hilbert space is \_\_\_. (couldn't make out word)

Qubit states can be represented as two complex numbers a and b, in
a vector like\\
$\left(\begin{array}{c}
a\\
b\end{array}\right)\in\mathbb{C}^{2}$\\
$\left|0\right\rangle =\left(\begin{array}{c}
1\\
0\end{array}\right)$, $\left|1\right\rangle =\left(\begin{array}{c}
0\\
1\end{array}\right)$\\
Euclidean norms are 1 ($\left\Vert \left|0\right\rangle \right\Vert =1$,
$\left\Vert \left|1\right\rangle \right\Vert =1$)\\
$\left|0\right\rangle $ and $\left|1\right\rangle $ are orthonormal
($\left|0\right\rangle \cdot\left|1\right\rangle =0$)


\subsubsection*{Dirac Notation}

$\left|x\right\rangle $ called {}``ket'', denotes coordinate vector
$\left(\begin{array}{c}
x_{1}\\
x_{2}\\
\vdots\\
x_{n}\end{array}\right)$

$\left\langle x\right|$ called {}``bra'' denotes $\left(\begin{array}{cccc}
\overline{x_{1}} & \overline{x_{2}} & \cdots & \overline{x_{n}}\end{array}\right)$\\
 (where $\bar{n}$ is complex conjugate of $n$)

$\left\langle x|y\right\rangle $ called {}``braket'' denotes inner
product, magnitude of projection of y on to x.\\
$\left\langle x|y\right\rangle =\left\langle x\right|\cdot\left|y\right\rangle =\left(\begin{array}{cccc}
\overline{x_{1}} & \overline{x_{2}} & \cdots & \overline{x_{n}}\end{array}\right)\left(\begin{array}{c}
y_{1}\\
y_{2}\\
\vdots\\
y_{n}\end{array}\right)=\sum_{j=1}^{n}\bar{x_{j}}y_{j}$\\
$\left\langle x|x\right\rangle =\left\Vert \left|x\right\rangle \right\Vert ^{2}$

A qubit is a unitary vector in hilbert space.\\
$\left|y\right\rangle =a\left|0\right\rangle +b\left|1\right\rangle $
where $a,b\in\mathbb{C}$ and $\left|a\right|^{2}+\left|b\right|^{2}=1$

A qubit is a linear combination of ket 0 and ket 1.\\
$\left|y\right\rangle =a\left(\begin{array}{c}
1\\
0\end{array}\right)+b\left(\begin{array}{c}
0\\
1\end{array}\right)=\left(\begin{array}{c}
a\\
b\end{array}\right)$

Showing qubit y is unitary.\\
$\left\Vert \left|y\right\rangle \right\Vert ^{2}=\left(\begin{array}{cc}
\bar{a} & \bar{b}\end{array}\right)\left(\begin{array}{c}
a\\
b\end{array}\right)=\bar{a}a+\bar{b}b=\left|a\right|^{2}+\left|b\right|^{2}=1$

Showing qubit y is unitary in dirac notation.\begin{eqnarray*}
\left\Vert \left|y\right\rangle \right\Vert ^{2} & = & \left\langle y|y\right\rangle =\left\langle y\right|\cdot\left|y\right\rangle \\
 & = & \left(\bar{a}\left\langle 0\right|+\bar{b}\left\langle 1\right|\right)\cdot\left(a\left|0\right\rangle +b\left|1\right\rangle \right)\\
 & = & \bar{a}a\left\langle 0|0\right\rangle +\bar{a}b\left\langle 0|1\right\rangle +\bar{b}a\left\langle 1|0\right\rangle +\bar{b}b\left\langle 1|1\right\rangle \\
 & = & \bar{a}a+\bar{b}b=\left|a\right|^{2}+\left|b\right|^{2}=1\end{eqnarray*}
One feature of dirac notation demonstrated here is that you can treat
matrix multiplication as regular multiplication


\subsection*{Bloch Sphere representation of Qubits}

Bloch sphere lets you represent qubits in a picture\\
$\left|\psi\right\rangle =\alpha\left|0\right\rangle +\beta\left|1\right\rangle $\\
 Substitute $\alpha=\left|\alpha\right|e^{i\varphi_{\alpha}}$, $\beta=\left|\beta\right|e^{i\varphi_{\beta}}$
\\
$\left|\psi\right\rangle =\left|\alpha\right|e^{i\varphi_{\alpha}}\left|0\right\rangle +\left|\beta\right|e^{i\varphi_{\beta}}\left|1\right\rangle $\\
$\left|\psi\right\rangle =e^{i\varphi_{\alpha}}\left(\left|\alpha\right|\left|0\right\rangle +\left|\beta\right|e^{i\left(\varphi_{\beta}-\varphi_{\alpha}\right)}\left|1\right\rangle \right)$\\
 Substitute $\varphi=\varphi_{\beta}-\varphi_{\alpha}$, $\gamma=\varphi_{\alpha}$
for $\varphi\in\left[0,2\pi\right]$\\
$\left|\psi\right\rangle =e^{i\gamma}\left(\left|\alpha\right|\left|0\right\rangle +\left|\beta\right|e^{i\varphi}\left|1\right\rangle \right)$\\
 Substitute $\left|\alpha\right|=\cos\vartheta$, $\left|\beta\right|=\sin\vartheta$,
for $\vartheta\in\left[0,\frac{\pi}{2}\right]$

$\left|\psi\right\rangle =e^{i\gamma}\left(\cos\vartheta\left|0\right\rangle +\sin\vartheta e^{i\varphi}\left|1\right\rangle \right)$\\
 Substitute $\left|\alpha\right|=\cos\frac{\vartheta}{2}$, $\left|\beta\right|=\sin\frac{\vartheta}{2}$,
for $\vartheta\in\left[0,\pi\right]$\\
$\left|\psi\right\rangle =e^{i\gamma}\left(\cos\frac{\vartheta}{2}\left|0\right\rangle +\sin\frac{\vartheta}{2}e^{i\varphi}\left|1\right\rangle \right)$\\
Any qubit can be expressed this way, in terms of $\gamma$, $\vartheta$,
and $\varphi$. And if you disregard $\gamma$, (global phase which
it turns out to be impossible to physically measure anyway), you can
take angles $\vartheta$ and $\varphi$ and use them to plot points
on a unit sphere.

(Drawing bloch spheres\\
 - z axis up, y axis right, x axis out\\
 - $\vartheta$ = angle between point and z axis (latitude, but starting
at north pole and extending down)\\
 - $\varphi$= angle between projection of point at z=0 and x axis
(longitude)

Textbook Figure 1.3, page 15)


\subsection*{Measuring Qubits}

Attempting to measure a qubit in a superposition state, $\left|y\right\rangle =a\left|0\right\rangle +b\left|1\right\rangle $,
will give you state $\left|0\right\rangle $ with probability $\left|a\right|^{2}$,
and $\left|1\right\rangle $ with probability $\left|b\right|^{2}$.
After measuring the state, the qubit collapses, it ceases to be a
superposition, and it changes to whatever state the measurement gave,
either $\left|0\right\rangle $ or $\left|1\right\rangle $.

Collapse is a non-unitary transformation. It can be considered a projection
and renormalization.

Using standard linear algebra notation, you can express measurement
of some state $u$ (where $u\in\mathbb{C}^{N}$) from a superposition
state $x$ as being a projection of $x$ onto $u$, followed by the
normalization. To compute the result of the projection, you can multiply
$x$ by a matrix $M$ where $M=u\cdot u^{H}$. $M$ is called a projection
matrix and $Mx$ will be the result of projecting $x$ onto $u$.
You don't actually need to form the matrix, however, since $Mx=uu^{H}x$,
and $u^{H}x$ can be computed as a simple dot product.

Using dirac notation, and taking a measurement of $\left|0\right\rangle $
as an example:\begin{eqnarray*}
M\left|x\right\rangle  & = & \left|0\right\rangle \left\langle 0\right|\left|x\right\rangle \\
 & = & \left|0\right\rangle \left\langle 0\right|\left(a\left|0\right\rangle +b\left|1\right\rangle \right)\\
 & = & a\left|0\right\rangle \left\langle 0\right|\left|0\right\rangle +b\left|0\right\rangle \left\langle 0\right|\left|1\right\rangle \\
 & = & a\left|0\right\rangle \end{eqnarray*}
After normalizing, final state is $\frac{a}{\left|a\right|}\left|0\right\rangle $.
Same process can be used for a measurement of $\left|1\right\rangle $
to express final state as $\frac{b}{\left|b\right|}\left|1\right\rangle $


\section*{Lecture 3 (24 January)}


\subsection*{Course Information}

Midterm - Wednesday, 7 March\\
Midterm Review - Monday before


\subsection*{Lecture 2 Review}

$\left|y\right\rangle =a\left|0\right\rangle +b\left|1\right\rangle =e^{i\gamma}\left(\cos\frac{\vartheta}{2}\left|0\right\rangle +e^{i\varphi}\sin\frac{\vartheta}{2}\left|0\right\rangle \right)$\\
Collapse probability\\
 $\left|0\right\rangle $, $p=\left|a\right|^{2}$\\
 $\left|1\right\rangle $, $p=\left|b\right|^{2}$


\subsection*{Alternate Basis}

\begin{eqnarray*}
\left|+\right\rangle  & = & \frac{1}{\sqrt{2}}\left(\left|0\right\rangle +\left|1\right\rangle \right)=\cos\left(\frac{\pi}{4}\right)\left|0\right\rangle +e^{i0}\sin\left(\frac{\pi}{4}\right)\left|1\right\rangle \\
\left|-\right\rangle  & = & \frac{1}{\sqrt{2}}\left(\left|0\right\rangle -\left|1\right\rangle \right)=\cos\left(\frac{\pi}{4}\right)\left|0\right\rangle +e^{i\pi}\sin\left(\frac{\pi}{4}\right)\left|1\right\rangle \end{eqnarray*}
Bloch sphere representations\\
$\left|+\right\rangle $, $\vartheta=\pi/2$, $\varphi=0$, on equator
at front of sphere\\
$\left|-\right\rangle $, $\vartheta=\pi/2$, $\varphi=\pi$, on equator
at back of sphere

Proving orthogonality of $\left|+\right\rangle $ and $\left|-\right\rangle $:\begin{eqnarray*}
\left\langle +|-\right\rangle  & = & \left(\frac{1}{\sqrt{2}}\left(\left\langle 0\right|+\left\langle 1\right|\right)\right)\cdot\left(\frac{1}{\sqrt{2}}\left(\left|0\right\rangle -\left|1\right\rangle \right)\right)\\
 & = & \frac{1}{2}\left(\left\langle 0|0\right\rangle -\left\langle 0|1\right\rangle +\left\langle 1|0\right\rangle -\left\langle 1|1\right\rangle \right)\\
 & = & \frac{1}{2}\left(1-0+0-1\right)=0\end{eqnarray*}


Proving $\left|+\right\rangle $ is unit vector (proof is similar
for $\left|-\right\rangle $ ):\begin{eqnarray*}
\left\langle +|+\right\rangle  & = & \left(\frac{1}{\sqrt{2}}\left(\left\langle 0\right|+\left\langle 1\right|\right)\right)\cdot\left(\frac{1}{\sqrt{2}}\left(\left|0\right\rangle +\left|1\right\rangle \right)\right)\\
 & = & \frac{1}{2}\left(\left\langle 0|0\right\rangle +\left\langle 0|1\right\rangle +\left\langle 1|0\right\rangle +\left\langle 1|1\right\rangle \right)\\
 & = & \frac{1}{2}\left(1+0+0+1\right)=1\end{eqnarray*}


Equivalences, change of base\begin{eqnarray*}
\left|0\right\rangle  & = & \frac{1}{\sqrt{2}}\left(\left|+\right\rangle +\left|-\right\rangle \right)\\
\left|1\right\rangle  & = & \frac{1}{\sqrt{2}}\left(\left|+\right\rangle -\left|-\right\rangle \right)\end{eqnarray*}



\subsection*{Hadamard Gate}

Hadamard matrix maps $\left|0\right\rangle $ to$\left|+\right\rangle $,
$\left|1\right\rangle $ to $\left|-\right\rangle $ \[
H=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}
1 & 1\\
1 & -1\end{array}\right)\]
You can see it by looking at columns. In general when looking at a
transformation matrix, the first column shows what first basis vector
($\left|0\right\rangle $) is transformed to, second column shows
second basis vector ($\left|1\right\rangle $), and so on.

Hadamard mapping for general state $\left|y\right\rangle =a\left|0\right\rangle +b\left|1\right\rangle $\begin{eqnarray*}
H\left|y\right\rangle  & = & \frac{1}{\sqrt{2}}\left(\left(a+b\right)\left|0\right\rangle +\left(a-b\right)\left|1\right\rangle \right)\\
 & = & \frac{1}{\sqrt{2}}\left(a\left(\left|0\right\rangle +\left|1\right\rangle \right)+b\left(\left|0\right\rangle -\left|1\right\rangle \right)\right)\\
 & = & a\left|+\right\rangle +b\left|-\right\rangle \end{eqnarray*}


Hadamard transform is unitary and is it's own inverse.

Example:\begin{eqnarray*}
H\left|0\right\rangle  & = & \frac{1}{\sqrt{2}}\left(\left|0\right\rangle +\left|1\right\rangle \right)\\
HH\left|0\right\rangle  & = & \frac{1}{\sqrt{2}}\left(H\left|0\right\rangle +H\left|1\right\rangle \right)=\frac{1}{2}\left(\left|0\right\rangle +\left|1\right\rangle +\left|0\right\rangle -\left|1\right\rangle \right)=\left|0\right\rangle \end{eqnarray*}
The two half-$\left|0\right\rangle $ kets adding up is called constructive
interference. The two half-$\left|1\right\rangle $ kets cancelling
out is called destructive interference.


\subsection*{Other Gates}

Pauli Matrix: \[
X=\left(\begin{array}{cc}
0 & 1\\
1 & 0\end{array}\right)\]


X is analogous to NOT gate:\begin{eqnarray*}
X\left|0\right\rangle  & = & \left|1\right\rangle \\
X\left|1\right\rangle  & = & \left|0\right\rangle \\
X\left|y\right\rangle  & = & a\left|1\right\rangle +b\left|0\right\rangle \end{eqnarray*}
in Dirac notation:\begin{eqnarray*}
X & = & \left|1\right\rangle \left\langle 0\right|+\left|0\right\rangle \left\langle 1\right|\\
 & = & \left(\begin{array}{c}
0\\
1\end{array}\right)\left(\begin{array}{cc}
1 & 0\end{array}\right)+\left(\begin{array}{c}
1\\
0\end{array}\right)\left(\begin{array}{cc}
0 & 1\end{array}\right)\\
 & = & \left(\begin{array}{cc}
0 & 0\\
1 & 0\end{array}\right)+\left(\begin{array}{cc}
0 & 1\\
0 & 0\end{array}\right)=\left(\begin{array}{cc}
0 & 1\\
1 & 0\end{array}\right)\end{eqnarray*}


In general, when you have a unitary operation U and you know how it
transforms basis states:\\
$U\left|0\right\rangle =\left|s\right\rangle $, $U\left|1\right\rangle =\left|t\right\rangle $,
you can express U as:\[
U=\left|s\right\rangle \left\langle 0\right|+\left|t\right\rangle \left\langle 1\right|\]
Verification:\begin{eqnarray*}
U\left|0\right\rangle  & = & \left|s\right\rangle \left\langle 0|0\right\rangle +\left|t\right\rangle \left\langle 1|0\right\rangle =\left|s\right\rangle \\
U\left|1\right\rangle  & = & \left|s\right\rangle \left\langle 0|1\right\rangle +\left|t\right\rangle \left\langle 1|1\right\rangle =\left|t\right\rangle \end{eqnarray*}



\subsection*{Linear Algebra Review}

Given U is unitary matrix, $\left\langle y|y\right\rangle =1$,$U\left|y\right\rangle =\lambda\left|y\right\rangle $.
Eigenvalues $\lambda\in\mathbb{C}$ can be expressed as $\lambda=e^{it}$,
$t\in\mathbb{R}$.

Show unitary matrix has eigenvalues of unit length:\begin{eqnarray*}
\left\langle y\right|U^{H} & = & \bar{\lambda}\left\langle y\right|\\
\left\langle y|U^{H}U|y\right\rangle  & = & \bar{\lambda}\lambda\left\langle y|y\right\rangle \\
1 & = & \left|\lambda\right|^{2}\end{eqnarray*}
Because they have unit length, eigenvalues can be written in the form
$\lambda=e^{it}.$

Show a hermitian matrix $A^{H}=A$ has eigenvalues that are real numbers:\begin{eqnarray*}
A\left|y\right\rangle  & = & \lambda\left|y\right\rangle \\
\left\langle y\right|A\left|y\right\rangle  & = & \lambda\left\langle y|y\right\rangle =\lambda\\
\left\langle y\right|A^{H} & = & \bar{\lambda}\left\langle y\right|\\
\left\langle y\right|A^{H}\left|y\right\rangle  & = & \bar{\lambda}\left\langle y|y\right\rangle =\bar{\lambda}\end{eqnarray*}
$A=A^{H}$ therefore $\lambda=\bar{\lambda}$ therefore $\lambda\in\mathbb{R}$


\subsubsection*{Spectral Theorem}

Unitary matrix U can be diagnalized as $U=V\Lambda V^{H}$ where\[
\Lambda=\left(\begin{array}{cccc}
\lambda_{1} & 0 & 0 & 0\\
0 & \lambda_{1} & 0 & 0\\
0 & 0 & \ddots & 0\\
0 & 0 & 0 & \lambda_{n}\end{array}\right)\]
and $V=\left(\begin{array}{cccc}
Y_{1} & Y_{2} & \cdots & Y_{n}\end{array}\right)$, columns $Y_{i}$ are eigenvectors.

The spectral theorem applies more generally to any Normal matrix.
Normal matrices commute with their transpose, $UU^{H}=U^{H}U$.

(Matrix types\\
 Normal - $U^{H}U=UU^{H}$\\
 Unitary - $U^{H}U=UU^{H}=I$, type of normal matrix\\
 Hermetian - $U^{H}=U$, type of normal matrix)


\subsection*{Pauli Matrices}

\[
X=\left(\begin{array}{cc}
0 & 1\\
1 & 0\end{array}\right)\]


Eigenvalues are $\lambda_{1}=1$, $\lambda_{2}=-1$. Eigenvectors:\begin{eqnarray*}
\left|+\right\rangle  & = & \frac{1}{\sqrt{2}}\left(\left|0\right\rangle +\left|1\right\rangle \right)=\frac{1}{\sqrt{2}}\left(\begin{array}{c}
1\\
1\end{array}\right)\\
\left|-\right\rangle  & = & \frac{1}{\sqrt{2}}\left(\left|0\right\rangle -\left|1\right\rangle \right)=\frac{1}{\sqrt{2}}\left(\begin{array}{c}
1\\
-1\end{array}\right)\end{eqnarray*}
Called X matrix because on Bloch Sphere, eigenvectors are aligned
with X axis.

\begin{eqnarray*}
Y & = & \left(\begin{array}{cc}
0 & -i\\
i & 0\end{array}\right)\\
Y\left|0\right\rangle  & = & i\left|1\right\rangle \\
Y\left|1\right\rangle  & = & -i\left|0\right\rangle \\
Y\left|y\right\rangle  & = & ia\left|1\right\rangle -ib\left|0\right\rangle \end{eqnarray*}
Eigenvectors are

$|\otimes\rangle=\frac{1}{\sqrt{2}}\left(\begin{array}{c}
1\\
i\end{array}\right)=\frac{1}{\sqrt{2}}\left(\left|0\right\rangle +i\left|1\right\rangle \right)$$ $, $\vartheta=\frac{\pi}{2}$, $\varphi=\frac{\pi}{2}$

$|\oplus\rangle=\frac{1}{\sqrt{2}}\left(\begin{array}{c}
1\\
-i\end{array}\right)=\frac{1}{\sqrt{2}}\left(\left|0\right\rangle -i\left|1\right\rangle \right)$, $\vartheta=\frac{\pi}{2}$, $\varphi=\frac{3\pi}{2}$

\begin{eqnarray*}
Z & = & \left(\begin{array}{cc}
1 & 0\\
0 & -1\end{array}\right)\\
Z\left|y\right\rangle  & = & a\left|0\right\rangle -b\left|1\right\rangle =a\left|0\right\rangle -e^{i\pi}b\left|1\right\rangle \end{eqnarray*}



\section*{Lecture 4 (29 Janary)}


\subsection*{Lecture 3 Review}

Hadamard matrix\[
H=\frac{1}{\sqrt{2}}\left(\begin{array}{cc}
1 & 1\\
1 & -1\end{array}\right)\]
Pauli Matrices\begin{eqnarray*}
X & = & \left(\begin{array}{cc}
0 & 1\\
1 & 0\end{array}\right)\\
Y & = & \left(\begin{array}{cc}
0 & -i\\
i & 0\end{array}\right)\\
Z & = & \left(\begin{array}{cc}
1 & 0\\
0 & -1\end{array}\right)=\left(\begin{array}{cc}
1 & 0\\
0 & e^{i\pi}\end{array}\right)\end{eqnarray*}
First column of each matrix tells you where $\left|0\right\rangle $
maps, second column tells you where $\left|1\right\rangle $ maps.


\subsection*{New Gates}

Phase gate\begin{eqnarray*}
S & = & \left(\begin{array}{cc}
1 & 0\\
0 & i\end{array}\right)=\left(\begin{array}{cc}
1 & 0\\
0 & e^{i\frac{\pi}{2}}\end{array}\right)\\
S^{2} & = & X\end{eqnarray*}


Pi over 8 gate\[
T=\left(\begin{array}{cc}
1 & 0\\
0 & e^{i\frac{\pi}{4}}\end{array}\right)=e^{i\frac{\pi}{8}}\left(\begin{array}{cc}
e^{-i\frac{\pi}{8}} & 0\\
0 & e^{i\frac{\pi}{8}}\end{array}\right)\]


Homework tip: We are allowed to cite eigenvalues from class. We can
also guess and verify other eigenvalues without going through characteristic
equations. Also, for diagonal matrices, eigenvalues can be read off
the diagonal and a eigenvectors are $\left|0\right\rangle $ and $\left|1\right\rangle $.


\subsection*{Multiple Qubit Systems}

Starting with 2 qubits. 2 qubits mean 4 base states:$\left|00\right\rangle $,
$\left|01\right\rangle $, $\left|10\right\rangle $, $\left|11\right\rangle $
or, equivalently $\left|0\right\rangle \left|0\right\rangle $, $\left|0\right\rangle \left|1\right\rangle $,
$\left|1\right\rangle \left|0\right\rangle $, $\left|1\right\rangle \left|1\right\rangle $.

An arbitrary state is a superposition\[
\left|y\right\rangle =a_{00}\left|00\right\rangle +a_{01}\left|01\right\rangle +a_{10}\left|10\right\rangle +a_{11}\left|11\right\rangle \]
constrained by $\sum_{j,k}\left|a_{jk}\right|^{2}=1$, $a_{jk}\in\mathbb{C}$

Measurement of any outcome j occurs with probability $\left|a_{j}\right|^{2}$.
Following measurement $\left|y\right\rangle $ collapses to $\left|j\right\rangle $.
It is also possible to make partial measurements, measuring some qubits
but not others, taking sums as you would expect. (The probabilty of
making the partial measurement is just the sum of probabilities of
the full measurements containing the partial measurement. Following
measurement, base states that aren't compatible with the measurement
have their coefficients set to 0 and the rest are renormalized.)

Combining qubit states\begin{eqnarray*}
\left|y_{1}\right\rangle  & = & a_{1}\left|0\right\rangle +b_{1}\left|1\right\rangle \\
\left|y_{2}\right\rangle  & = & a_{2}\left|0\right\rangle +b_{2}\left|1\right\rangle \end{eqnarray*}
You can combine two independent qubit states to get a state describing
the probability of each joint outcome\begin{eqnarray*}
\left|y_{1}y_{2}\right\rangle  & = & \left|y_{1}\right\rangle \left|y_{2}\right\rangle =\left(a_{1}\left|0\right\rangle +b_{1}\left|1\right\rangle \right)\left(a_{2}\left|0\right\rangle +b_{2}\left|1\right\rangle \right)\\
 & = & a_{1}\left|0\right\rangle a_{2}\left|0\right\rangle +a_{1}\left|0\right\rangle b_{2}\left|1\right\rangle +b_{1}\left|1\right\rangle a_{2}\left|0\right\rangle +b_{1}\left|1\right\rangle b_{2}\left|1\right\rangle \\
 & = & a_{1}a_{2}\left|00\right\rangle +a_{1}b_{2}\left|01\right\rangle +b_{1}a_{2}\left|10\right\rangle +b_{1}b_{2}\left|11\right\rangle \end{eqnarray*}
(Note: all the products in the above equations are really tensor products,
which are defined below. In previous lecture notes, products inside
dirac expressions implied standard matrix multiplication, which makes
no sense here.)

You cannot generally break a multiple qubit state up into separate
independent states. Example: EPR state $\frac{1}{\sqrt{2}}\left(\left|00\right\rangle +\left|11\right\rangle \right)$.
You can see visually that there are no values for $a_{1}$, $b_{1}$,
$a_{2}$, $b_{2}$ that will let you write the EPR state in above
form.

For an n-qubit system, each basis state can be expressed as a bitstring
$\left|j_{n-1}j_{n-2}\cdots j_{0}\right\rangle $ for $j_{m}\in\left\{ 0,1\right\} $.
Or, for convenience, it can just be written as a normal number$\left|j\right\rangle $
where $j=\sum_{m=0}^{n-1}2^{m}j_{m}$

Now that we have a notion for multiple qubit states, have to answer
3 questions:\\
Q1: What is the coordinate representation of a state $\left|j\right\rangle $
?\\
Q2: How can you decompose and recompose states? For example, how do
you compute $\left|y\right\rangle =\left|y_{1}\right\rangle \left|y_{2}\right\rangle $
where $\left|y_{1}\right\rangle $ and $\left|y_{2}\right\rangle $
are multiple qubit states.\\
Q3: How can you compose operations. Given $\left|y_{1}\right\rangle $
and $\left|y_{2}\right\rangle $ which are multiple qubit states and
unitary operators $U_{1}$ and $U_{2}$ which apply to $\left|y_{1}\right\rangle $
and $\left|y_{2}\right\rangle $ , respectively, how can you find
a U matrix that satisfies $U\left|y\right\rangle =U_{1}\left|y_{1}\right\rangle U_{2}\left|y_{2}\right\rangle $

Once you answer these questions you can start looking at algorithms.


\subsection*{Tensor Products}

Tensor products are a new concept.

Given two matrices, A which has size $m\times n$, and B which has
size $p\times q$, the tensor product $A\otimes B$ will be a huge
matrix of size $mp\times nq$: \[
A\otimes B=\left(\begin{array}{cccc}
a_{11}B & a_{12}B & \cdots & a_{1n}B\\
a_{21}B & a_{22}B & \text{ }\cdots & a_{2n}B\\
\vdots & \vdots & \ddots\\
a_{m1}B & a_{m2}B &  & a_{mn}B\end{array}\right)\]


Example:\begin{eqnarray*}
\left(\begin{array}{ccc}
1 & 2 & 3\\
4 & 5 & 6\end{array}\right))\otimes\left(\begin{array}{rr}
10 & 0\\
0 & 20\end{array}\right) & = & \begin{array}{ccc}
1\left(\begin{array}{rr}
10 & 0\\
0 & 20\end{array}\right) & 2\left(\begin{array}{rr}
10 & 0\\
0 & 20\end{array}\right) & 3\left(\begin{array}{rr}
10 & 0\\
0 & 20\end{array}\right)\\
4\left(\begin{array}{rr}
10 & 0\\
0 & 20\end{array}\right) & 5\left(\begin{array}{rr}
10 & 0\\
0 & 20\end{array}\right) & 6\left(\begin{array}{rr}
10 & 0\\
0 & 20\end{array}\right)\end{array}\\
 & = & \left(\begin{array}{rrrrrr}
10 & 0 & 20 & 0 & 30 & 0\\
0 & 20 & 0 & 40 & 0 & 60\\
40 & 0 & 50 & 0 & 60 & 0\\
0 & 80 & 0 & 100 & 0 & 120\end{array}\right)\end{eqnarray*}


Example: (using column vectors):\\
$X=\left(\begin{array}{c}
1\\
2\\
3\end{array}\right)$, $Y=\left(\begin{array}{c}
10\\
100\end{array}\right)$\\
$X\otimes Y=\left(\begin{array}{c}
10\\
100\\
20\\
200\\
30\\
300\end{array}\right)$, $Y\otimes X=\left(\begin{array}{c}
10\\
20\\
30\\
100\\
200\\
300\end{array}\right)$

Example: (using qubits)\\
$X=\left(\begin{array}{c}
1\\
0\end{array}\right)=\left|0\right\rangle $, $Y=\left(\begin{array}{c}
1\\
0\end{array}\right)=\left|0\right\rangle $\\
$X\otimes Y=\left|0\right\rangle \otimes\left|0\right\rangle =\left|0\right\rangle \left|0\right\rangle =\left|00\right\rangle =\left(\begin{array}{c}
1\\
0\\
0\\
0\end{array}\right)$

Similarly, $\left|11\right\rangle =\left(\begin{array}{c}
0\\
0\\
0\\
1\end{array}\right)$\\
And more generally, $\left|j\right\rangle =\left|j_{1}j_{0}\right\rangle $
will be a column vector which is all zeros except for single $1$
entry at position $j+1$ (see {}``Multiple Qubit Systems'' above,
$j=\sum_{m=0}^{n-1}2^{m}j_{m}$).

Example: (using qubits again):\begin{eqnarray*}
H\left|0\right\rangle  & = & \frac{1}{\sqrt{2}}\left(\left|0\right\rangle +\left|1\right\rangle \right)\\
\left(H\left|0\right\rangle \right)\otimes\left(H\left|0\right\rangle \right) & = & \left(\frac{1}{\sqrt{2}}\left(\left(\begin{array}{c}
1\\
0\end{array}\right)+\left(\begin{array}{c}
0\\
1\end{array}\right)\right)\right)\otimes\left(\frac{1}{\sqrt{2}}\left(\left(\begin{array}{c}
1\\
0\end{array}\right)+\left(\begin{array}{c}
0\\
1\end{array}\right)\right)\right)\\
 & = & \frac{1}{\sqrt{2}}\left(\begin{array}{c}
1\\
1\end{array}\right)\otimes\frac{1}{\sqrt{2}}\left(\begin{array}{c}
1\\
1\end{array}\right)=\frac{1}{2}\left(\begin{array}{c}
1\\
1\\
1\\
1\end{array}\right)\end{eqnarray*}


Repeat example using dirac notation:\begin{eqnarray*}
\left(H\left|0\right\rangle \right))\otimes(\left(H\left|0\right\rangle \right)) & = & \frac{1}{2}\left(\left|0\right\rangle +\left|1\right\rangle \right)\left(\left|0\right\rangle +\left|1\right\rangle \right)\\
 & = & \frac{1}{2}\left(|00\rangle+\left|01\right\rangle +\left|10\right\rangle +\left|11\right\rangle \right)\\
 & = & \frac{1}{2}\left(\left(\begin{array}{c}
1\\
0\\
0\\
0\end{array}\right)+\left(\begin{array}{c}
0\\
1\\
0\\
0\end{array}\right)+\left(\begin{array}{c}
0\\
0\\
1\\
0\end{array}\right)+\left(\begin{array}{c}
0\\
0\\
0\\
1\end{array}\right)\right)=\frac{1}{2}\left(\begin{array}{c}
1\\
1\\
1\\
1\end{array}\right)\end{eqnarray*}


Associative property of tensor product:\[
\left|x\right\rangle \otimes\left|y\right\rangle \otimes\left|z\right\rangle =\left|x\right\rangle \otimes\left|yz\right\rangle =\left|xy\right\rangle \otimes\left|z\right\rangle =\left|xyz\right\rangle \]


Notation for tensor exponentiation:\[
\left|\psi\right\rangle ^{\otimes k}=\left|\psi\right\rangle \otimes\left|\psi\right\rangle \cdots\otimes\left|\psi\right\rangle \]



\subsection*{Powers of $H\left|0\right\rangle $}

\[
\left(H\left|0\right\rangle \right)^{\otimes k}=\frac{1}{2^{k/2}}\left(\begin{array}{c}
1\\
1\\
\vdots\\
1\end{array}\right)\]
where length of column vector is $2^{k}$.

The formula is obvious for $k=1$. Proof for rest of cases is by induction,
(base case $k=2$ was shown in previous section.) Inductive case is:
\begin{eqnarray*}
\left(\frac{\left|0\right\rangle +\left|1\right\rangle }{\sqrt{2}}\right)^{\otimes k} & = & \left(\frac{\left|0\right\rangle +\left|1\right\rangle }{\sqrt{2}}\right)^{\otimes k-1}\otimes\left(\frac{\left|0\right\rangle +\left|1\right\rangle }{\sqrt{2}}\right)\\
 & = & \frac{1}{2^{(k-1)/2}}\left(\begin{array}{c}
1\\
1\\
\vdots\\
1\end{array}\right)\otimes\frac{1}{\sqrt{2}}\left(\begin{array}{c}
1\\
1\end{array}\right)=\frac{1}{2^{k/2}}\left(\begin{array}{c}
1\\
1\\
\vdots\\
1\end{array}\right)\end{eqnarray*}



\subsection*{Tensor Products Continued}

{[}DUNNO] I'm not exactly sure what the following equations are supposed
to show. I think I was lost at the time I was taking these notes.\[
\left|j\right\rangle =\left|j_{n-1}j_{n-2}\cdots j_{0}\right\rangle \]


Now make an arbitary split at qubit k. \begin{eqnarray*}
\left|j\right\rangle  & = & \left|j_{n-1}\cdots j_{k}\right\rangle \left|j_{k-1}\cdots j_{0}\right\rangle \\
 & = & \left|j^{(1)}\right\rangle \left|j^{(2)}\right\rangle \end{eqnarray*}


\begin{eqnarray*}
j & = & \sum_{m=0}^{n-1}2^{m}j_{m}\\
j^{(1)} & = & \sum_{m=k}^{n-1}2^{m-k}j_{m}\\
j^{(2)} & = & \sum_{m=0}^{k-1}2^{m}j_{m}\end{eqnarray*}


Known n=1, n=2.\begin{eqnarray*}
\left|j\right\rangle  & = & \left|j^{(1)}\right\rangle \left|j^{(2)}\right\rangle \\
 & = & \left(\begin{array}{c}
0\\
\vdots\\
1\\
\vdots\\
0\end{array}\right)\otimes\left(\begin{array}{c}
0\\
\vdots\\
1\\
\vdots\\
0\end{array}\right)=\left(\begin{array}{c}
0\\
\vdots\\
\vdots\\
1\\
\vdots\\
\vdots\\
0\end{array}\right)\end{eqnarray*}
$\left|j^{(1)}\right\rangle $ has 1 at position $j^{(1)}+1$\\
$\left|j^{(2)}\right\rangle $ has 1 at position $j^{(2)}+1$\\
 $\left|j\right\rangle $ has 1 at position $j+1=j^{(1)}\cdot2^{k}+j^{(2)}+1$


\subsection*{New Course Information}

The class now has a TA: James Li (sp?)


\section*{Lecture 5 (31 January)}


\subsection*{Lecture 4 Review}

In n-dimensional qubit systems, basis vectors are $\left(\begin{array}{c}
0\\
\vdots\\
1\\
\vdots\\
0\end{array}\right)=\left|j\right\rangle $ with the 1 at position $j+1$.

Any state $\left|j\right\rangle $ is a linear combination of j vectors.

Any outcome $\left|j\right\rangle $ has probability $\left|c_{j}\right|^{2}$
for$\left|y\right\rangle =\sum_{j=0}^{2^{n-1}}c_{j}\left|j\right\rangle $

First homework assignment is out today, 3 problems, due 14 Feb.

Showed last time that\[
\left(H\left|0\right\rangle \right)^{\otimes k}=\left(\frac{\left|0\right\rangle +\left|1\right\rangle }{\sqrt{2}}\right)^{\otimes k}=\frac{1}{2^{k/2}}\left(\begin{array}{c}
1\\
\vdots\\
1\end{array}\right)\]
producing column vector of $2^{k}$ rows. Will be generalizing today
for inputs other than $\left|0\right\rangle $.


\subsection*{Properties of Tensor Products}

1. Associative property (see lecture 4)\\
 2. Distributing scalar multiple over tensor product\\
 $a\left(\left|x\right\rangle \otimes\left|y\right\rangle \right)=\left(a\left|x\right\rangle \right)\otimes\left|y\right\rangle =\left|x\right\rangle \otimes\left(a\left|y\right\rangle \right)$\\
 3. Distributing tensor product over addition\\
 $\left|y\right\rangle \otimes\left(\left|x_{1}\right\rangle +\left|x_{2}\right\rangle \right)=\left|y\right\rangle \otimes\left|x_{1}\right\rangle +\left|0y\right\rangle \otimes\left|x_{2}\right\rangle $\\
 4. Applying tensor products of operations individually to vectors.\\
$\left(A\otimes B\right)\left(\left|x\right\rangle \otimes\left|y\right\rangle \right)=\left(A\left|x\right\rangle \right)\otimes\left(B\left|y\right\rangle \right)$

Example:\begin{eqnarray*}
\left(\frac{|0\rangle+|1\rangle}{\sqrt{2}}\right)^{\otimes k} & = & H\left|0\right\rangle \otimes\cdots\otimes H\left|0\right\rangle \\
 & = & \left(H\otimes\cdots\otimes H\right)\left(\left|0\right\rangle \otimes\cdots\otimes\left|0\right\rangle \right)\\
 & = & H^{\otimes k}\left|0\right\rangle ^{\otimes k}\end{eqnarray*}


Example:\[
\left(X\otimes S\right)\left|00\right\rangle =X\left|0\right\rangle \otimes S\left|0\right\rangle \]
(X is NOT gate from lecture 3, S is phase gate from lecture 4)\\
Lets you apply transformations to individual inputs instead of applying
huge combination operations with big matrices.

Example:\[
\left(A\otimes B\right)\left(\sum_{j}a_{j}\left|x_{j}\right\rangle \left|y_{j}\right\rangle \right)=\sum_{j}a_{j}\left(A\left|x_{j}\right\rangle \right)\otimes\left(B\left|y_{j}\right\rangle \right)\]
6. Distributing Hermitian transpose over tensor product\\
$\left(A\otimes B\right)^{H}=A^{H}\otimes B^{H}$\\
7. Applying tensor product of operations to other operations.\\
$\left(A\otimes B\right)\left(C\otimes D\right)=AC\otimes BD$\\
Proof can be stated in terms of property 4, just break down C and
D into individual column vectors $\left|x\right\rangle $ and $\left|y\right\rangle $.
This is a useful technique in general, substituting vectors to figure
out how matrices work.\\
8. If A and B are unitary operations, then $A\otimes B$ is unitary.\\
Proof: $A^{H}A=I$, $B^{H}B=I$\\
$\left(A\otimes B\right)^{H}\left(A\otimes B\right)=\left(A^{H}\otimes B^{H}\right)\left(A\otimes B\right)=\left(A^{H}A\right)\otimes\left(B^{H}B\right)=I\otimes I=I$


\subsection*{Powers of Hadamard Gate}

Result of applying hadamard transforms to each qubit in some base
(non-superposition) state $j$, made of $k$ qubits.\begin{eqnarray*}
H^{\otimes k}\left|j_{k-1}\cdots j_{0}\right\rangle  & = & H\left|j_{k-1}\right\rangle \cdots H\left|j_{0}\right\rangle \\
 & = & \frac{\left|0\right\rangle +\left(-1\right)^{j_{k-1}}\left|1\right\rangle }{\sqrt{2}}\otimes\cdots\otimes\frac{\left|0\right\rangle +\left(-1\right)^{j_{0}}\left|1\right\rangle }{\sqrt{2}}\\
 & = & \bigotimes_{s=k-1}^{0}\frac{\left|0\right\rangle +\left(-1\right)^{j_{s}}\left|1\right\rangle }{\sqrt{2}}\\
 & = & \frac{1}{2^{k/2}}\sum_{m=0}^{2^{k-1}}\left(-1\right)^{j\cdot m}\left|m\right\rangle \end{eqnarray*}
Where $j\cdot m=j_{k-1}m_{k-1}+j_{k-2}m_{k-2}+\cdots+j_{0}m_{0}$.
$j_{i},m_{i}\in\left\{ 0,1\right\} $ are digits of $j$ and $m$
expressed as binary strings. 

(Observe that for some single qubit state, $j_{s}$, $H|j_{s}\rangle=\frac{\left|0\right\rangle +\left(-1\right)^{j_{s}}\left|1\right\rangle }{\sqrt{2}}$
to see the intuition in the last step. At $k=2$,\begin{eqnarray*}
 &  & \frac{\left|0\right\rangle +\left(-1\right)^{j_{1}}\left|1\right\rangle }{\sqrt{2}}\otimes\frac{\left|0\right\rangle +\left(-1\right)^{j_{0}}\left|1\right\rangle }{\sqrt{2}}\\
 &  & =\left|00\right\rangle +\left(-1\right)^{j_{0}}\left|01\right\rangle +\left(-1\right)^{j_{1}}\left|10\right\rangle +\left(-1\right)^{j_{0}+j_{1}}\left|11\right\rangle \end{eqnarray*}


At $k=3$,\begin{eqnarray*}
 &  & \frac{\left|0\right\rangle +\left(-1\right)^{j_{2}}\left|1\right\rangle }{\sqrt{2}}\otimes\frac{\left|0\right\rangle +\left(-1\right)^{j_{1}}\left|1\right\rangle }{\sqrt{2}}\otimes\frac{\left|0\right\rangle +\left(-1\right)^{j_{0}}\left|1\right\rangle }{\sqrt{2}}\\
 &  & =\left|000\right\rangle +\left(-1\right)^{j_{0}}\left|001\right\rangle +\left(-1\right)^{j_{1}}\left|010\right\rangle +\left(-1\right)^{j_{0}+j}\left|011\right\rangle \\
 &  & +\left(-1\right)^{j_{2}}\left|100\right\rangle +\left(-1\right)^{j_{0}+j_{2}}\left|101\right\rangle +\left(-1\right)^{j_{1}+j_{2}}\left|110\right\rangle +\left(-1\right)^{j_{0}+j_{1}+j_{2}}\left|111\right\rangle \end{eqnarray*}
You can see that $\left(-1\right)^{j_{i}}$ coefficients follow the
$\left|1\right\rangle $'s and get included in the expanded terms
where $m_{i}$ is 1 instead of 0.)

For two qubit system, inputs $\left|+\right\rangle $, $\left|+\right\rangle $:\[
\frac{\left|0\right\rangle +\left|1\right\rangle }{\sqrt{2}}\otimes\frac{\left|0\right\rangle +\left|1\right\rangle }{\sqrt{2}}\rightarrow\begin{array}{c}
\left|00\right\rangle \\
\left|01\right\rangle \\
\left|10\right\rangle \\
\left|11\right\rangle \end{array}\]
For $n+1$ qubit system, inputs: $\left|+\right\rangle $, $\left|y\right\rangle $:
$\frac{\left|0\right\rangle +\left|1\right\rangle }{\sqrt{2}}\left|y\right\rangle =\frac{\left|0y\right\rangle +\left|1y\right\rangle }{\sqrt{2}}$
(has $n+1$ qubits if $\left|y\right\rangle $ has $n$ qubits)

Solution is then made up of terms like $\left|m_{k-1}m_{k-2}\cdots m_{0}\right\rangle $\\
if $m_{k-2}=1$ then term has $\left|1\right\rangle $ at second cubit,
but may be + or -\\
if $j_{k-2}=1$ then it's $-\left|1\right\rangle $ else if $j_{k-2}=0$
then $\left|1\right\rangle $ \\
if $m_{k-2}=0$ or $j_{k-2}=0$ then no problem with + or - since
we have 0 at location k-2

Summary: $\left(-1\right)^{j_{k-2}m_{k-2}}\left|?\mbox{(0 or 1)}???\right\rangle $

Repeat for all qubits to get $\left(-1\right)^{j_{k-1}m_{k-1}+\cdots+j_{0}m_{0}}\left|m_{k-1}\cdots m_{0}\right\rangle $

Upshot: $H^{\otimes k}\left|j\right\rangle =\frac{1}{2^{k/2}}\sum_{m=0}^{2^{k-1}}\left(-1\right)^{m\cdot j}\left|m\right\rangle $

Homework hint: This is half of work needed to solve one of the problems.
It tells you columns of the matrix. Homework asks you to find the
whole matrix.


\subsection*{Properties of Tensor Products (continued)}

9. If you have two states $\left|x\right\rangle $ and $\left|y\right\rangle $
which you can decompose with same dimensions.\\
$\left|y\right\rangle =\left|y_{1}\right\rangle \left|y_{2}\right\rangle $
\\
$\left|x\right\rangle =\left|x_{1}\right\rangle \left|x_{2}\right\rangle $
\\
Then $\left\langle x|y\right\rangle =\left\langle x_{1}x_{2}|y_{1}y_{2}\right\rangle =\left\langle x_{1}|y_{1}\right\rangle \left\langle x_{2}|y_{2}\right\rangle $

Example: \\
$\left|d\right\rangle =|011000\rangle$\\
$\left|k\right\rangle =|011010\rangle$\\
 You can tell $\left\langle d|k\right\rangle =0$ based solely on
the fact that the fifth qubit's inner product ($\left\langle 0|1\right\rangle $)
is zero.

Example:\\
$\left\langle z_{1}\right|\left\langle z_{2}\right|X\otimes Y\left|\psi_{1}\right\rangle \left|\psi_{2}\right\rangle =\left\langle z_{1}\right|X\left|\psi_{1}\right\rangle \otimes\left\langle z_{2}\right|Y\left|\psi_{2}\right\rangle $


\subsection*{Completeness Relation}

\[
\left|j\right\rangle \left\langle i\right|=\left(\begin{array}{c}
0\\
\vdots\\
1\\
\vdots\\
0\end{array}\right)\left(\begin{array}{ccccc}
0 & \cdots & 1 & \cdots & 0\end{array}\right)=\left(\begin{array}{ccccc}
0 & \cdots & \cdots & \cdots & 0\\
\vdots & \ddots &  & .\cdot & \vdots\\
\vdots &  & 1 &  & \vdots\\
\vdots & .\cdot &  & \ddots & \vdots\\
0 & \cdots & \cdots & \cdots & 0\end{array}\right)\]


$\left|j\right\rangle $ is column vector with 1 at position j+1\\
 $\left\langle i\right|$ is row vector with 1 at position i+i\\
 $\left|j\right\rangle \left\langle i\right|$ is projection matrix
with 1 at row j+1, col i+i

Completeness relation\[
\sum_{i=o}^{2^{n-1}}\left|i\right\rangle \left\langle i\right|=I\]


Next lecture will show completeness relation holds on any orthonormal
basis, not just $i$.


\section*{Lecture 6 (5 February)}


\subsection*{Lecture 5 Review}

1. $H^{\otimes k}\left|j\right\rangle =\frac{1}{2^{k/2}}\sum_{m=0}^{2^{k-1}}\left(-1\right)^{j\cdot m}\left|m\right\rangle $\\
 2. $\left\langle x_{1}\right|\otimes\left\langle x_{2}\right|\cdot\left|y_{1}\right\rangle \otimes\left|y_{2}\right\rangle =\left\langle x_{1}|y_{1}\right\rangle \otimes\left\langle x_{2}|y_{2}\right\rangle $\\
 Example:\\
$\left\langle 01\right|X\otimes A\left|01\right\rangle =\left\langle 0\right|X\left|0\right\rangle \otimes\left\langle 1\right||A\left|1\right\rangle $\\
3. $I=\sum_{j=0}^{2^{n-1}}\left|j\right\rangle \left\langle j\right|$


\subsection*{Completeness Relation}

A proof of the completeness relation (3 above) was shown last lecture
based on adding up projections to get the diagonal matrix. This is
another proof:

An arbitrary state is a linear combination of basis states:\[
\left|y\right\rangle =\sum_{j}c_{j}\left|x_{j}\right\rangle \]
Each constant is just:\[
c_{j}=\left\langle x_{j}|y\right\rangle \in\mathbb{C}\]
Substituting $c_{j}$ above gives:\[
\left|y\right\rangle =\sum_{j}\left|x_{j}\right\rangle \left\langle x_{j}|y\right\rangle \]
In general\[
\left|y\right\rangle =A\left|y\right\rangle \rightarrow A=I\]
So\[
\sum_{j}\left|x_{j}\right\rangle \left\langle x_{j}\right|=I\]


$A=AI=A\sum_{j}\left|x_{j}\right\rangle \left\langle x_{j}\right|=\sum_{j}\left(A\left|x_{j}\right\rangle \right)\left\langle x_{j}\right|$


\subsection*{More Linear Algebra}

An $n\times n$ matrix has $n$ eigenvalues ($\lambda_{i}\in\mathbb{C}$)
and orthonormal eigenvectors ($\left|x_{j}\right\rangle $ $j=\left\{ 1\ldots n\right\} $)
iff A is normal ($A^{H}A=AA^{H}$).

$V=\left(\begin{array}{ccc}
\left|x_{1}\right\rangle  & \cdots & \left|x_{n}\right\rangle \end{array}\right)$, eigenvector matrix, $V^{H}V=I$\\
 $\Lambda=\left(\begin{array}{cccc}
\lambda_{1} & 0 & 0 & 0\\
0 & \lambda_{2} & 0 & 0\\
0 & 0 & \ddots & 0\\
0 & 0 & 0 & \lambda_{n}\end{array}\right)$, eigenvalue matrix\\
 \begin{eqnarray*}
A & = & V\Lambda V^{H}=\left(\begin{array}{ccc}
\lambda_{1}\left|x_{1}\right\rangle  & \ldots & \lambda_{n}\left|x_{n}\right\rangle \end{array}\right)\left(\begin{array}{c}
\left\langle x_{1}\right|\\
\vdots\\
\left\langle x_{n}\right|\end{array}\right)\\
 & = & \sum_{j=1}^{n}\lambda_{j}\left|x_{j}\right\rangle \left\langle x_{j}\right|\end{eqnarray*}


Eigenvalues and Tensor Products:

If $A$ eigenvalues are $\lambda_{j}$, eigenvectors are $\left|x_{j}\right\rangle $,
for j=1..n, \\
and $B$ eigenvalues are $\lambda_{k}$, eigenvectors are $\left|x_{k}\right\rangle $,
for k=1..n\\
then $A\otimes B$ eigenvalues are $\lambda_{j}$$\lambda_{k}$, eigenvectors
are $\left|x_{j}\right\rangle $$\left|x_{k}\right\rangle $

For any matrix A, you can compute $A^{2}$, $A^{3}$, $A^{4}$\\
If A is nonsingular, you can compute $A^{-1}$, $A^{-2}$\\
What about a general f: D $\rightarrow$ C, like sin(A), $e^{A}$,
f(A)\\
If A is normal and f($\lambda_{j}$) is well defined for all eigenvalues
\begin{eqnarray*}
f(A) & = & \sum_{j}f\left(\lambda_{j}\right)\left|x_{j}\right\rangle \left\langle x_{j}\right|\\
 & = & V\left(\begin{array}{cccc}
f\left(\lambda_{1}\right) & 0 & 0 & 0\\
0 & f\left(\lambda_{2}\right) & 0 & 0\\
0 & 0 & \ddots & 0\\
0 & 0 & 0 & f\left(\lambda_{n}\right)\end{array}\right)V^{H}\end{eqnarray*}


Example:\\
$f(z)=z^{k}$\\
$f(A)=A^{k}=(V\Lambda V^{H})(V\Lambda V^{H})\cdots(V\Lambda V^{H})$
{[}multiplied k times]\\
$=V\Lambda^{k}V^{H}$

If $A\in\mathbb{R}^{n,n}$ and $A=A^{T}$ then $e^{iA}$ is unitary.
Proof:\begin{eqnarray*}
\left(e^{iA}\right)^{H}\left(e^{iA}\right) & = & \left(\sum_{j}e^{i\lambda_{j}}\left|x_{j}\right\rangle \left\langle x_{j}\right|\right)^{H}\left(\sum_{j}e^{i\lambda_{j}}\left|x_{j}\right\rangle \left\langle x_{j}\right|\right)\\
 & = & \left(\sum_{j}e^{-i\lambda_{j}}\left|x_{j}\right\rangle \left\langle x_{j}\right|\right)\left(\sum_{j}e^{\text{i$\lambda$}_{j}}\left|x_{j}\right\rangle \left\langle x_{j}\right|\right)\\
 & = & \sum_{j,k}e^{-i\lambda_{j}}e^{i\lambda_{k}}\left|x_{j}\right\rangle \left\langle x_{j}\right|\left|x_{k}\right\rangle \left\langle x_{k}\right|\\
 & = & \sum_{j}1\left|x_{j}\right\rangle \left\langle x_{j}\right|=I\end{eqnarray*}



\subsection*{Controlled Gates}

Controlled gates have a control input and a normal input. Control
output is always the same as the control input. If control input is
$\left|0\right\rangle $, normal output is the same as the normal
input. If control input $\left|1\right\rangle $, normal output is
some function of the normal input, where the function depends on the
type of controlled gate.


\subsubsection*{Controlled Not Gate}

\begin{eqnarray*}
\left|00\right\rangle  & \rightarrow & \left|00\right\rangle \\
\left|01\right\rangle  & \rightarrow & \left|01\right\rangle \\
\left|10\right\rangle  & \rightarrow & \left|11\right\rangle \\
\left|11\right\rangle  & \rightarrow & \left|10\right\rangle \end{eqnarray*}
\[
Q_{\text{CNOT}}\left|i\right\rangle \left|j\right\rangle =\left|i\right\rangle \left|i\oplus j\right\rangle \]


\[
Q_{\text{CNOT}}=\left(\begin{array}{cccc}
1 & 0 & 0 & 0\\
0 & 1 & 0 & 0\\
0 & 0 & 0 & 1\\
0 & 0 & 1 & 0\end{array}\right)=\left(\begin{array}{cc}
I & 0\\
0 & X\end{array}\right)\]


Each column of matrix is derived directly by writing CNOT mappings
listed above for $\left|00\right\rangle $, $\left|01\right\rangle $,
$\left|10\right\rangle $, and $\left|11\right\rangle $ inputs. Matrix
can be shown to be unitary by multipling with its conjugate transpose
and getting the identity matrix.

CNOT for Hadamard inputs:\begin{eqnarray*}
\left|+\right\rangle \left|+\right\rangle  & \rightarrow & \left|+\right\rangle \left|+\right\rangle \\
\left|-\right\rangle \left|+\right\rangle  & \rightarrow & \left|-\right\rangle \left|+\right\rangle \\
\left|+\right\rangle \left|-\right\rangle  & \rightarrow & \left|-\right\rangle \left|-\right\rangle \\
\left|-\right\rangle \left|-\right\rangle  & \rightarrow & \left|+\right\rangle \left|-\right\rangle \end{eqnarray*}
When dealing with inputs that aren't 0 and 1, calling the same input
the {}``control input'' doesn't neccessarily make sense. When superposition
states are fed to the CNOT, as above, the state of the second qubit
controls a NOT operation on the first.

Formally:\[
Q_{\text{CNOT}}H\left|i\right\rangle H\left|j\right\rangle =H\left|i\oplus j\right\rangle H\left|j\right\rangle \]
for $i,j\in0,1$

Proof:\begin{eqnarray*}
Q_{\text{CNOT}}\left(H|i\rangle H|j\rangle\right) & = & Q_{\text{CNOT}}\left(\left(\frac{\left|0\right\rangle +\left(-1\right)^{i}\left|1\right\rangle }{\sqrt{2}}\right)\left(\frac{\left|0\right\rangle +\left(-1\right)^{j}\left|1\right\rangle }{\sqrt{2}}\right)\right)\\
 & = & Q_{\text{CNOT}}\left(\frac{1}{2}\left(\left|00\right\rangle +\left(-1\right)^{j}\left|01\right\rangle +\left(-1\right)^{i}\left|10\right\rangle +\left(-1\right)^{i+j}\left|11\right\rangle \right)\right)\\
 & = & \frac{1}{2}\left(\left|00\right\rangle +\left(-1\right)^{j}\left|01\right\rangle +\left(-1\right)^{i}\left|11\right\rangle +\left(-1\right)^{i+j}\left|10\right\rangle \right)\\
 & = & \frac{1}{2}\left(\left|00\right\rangle +\left(-1\right)^{j}\left|01\right\rangle +\left(-1\right)^{i+j}\left|10\right\rangle +\left(-1\right)^{i}\left|11\right\rangle \right)\\
 & = & \frac{1}{2}\left(\left|00\right\rangle +\left(-1\right)^{j}\left|01\right\rangle +\left(-1\right)^{i+j}\left|10\right\rangle +\left(-1\right)^{i+j+j}\left|11\right\rangle \right)\\
 & = & \left(\frac{\left|0\right\rangle +\left(-1\right)^{i+j}\left|1\right\rangle }{\sqrt{2}}\right)\left(\frac{\left|0\right\rangle +\left(-1\right)^{j}\left|1\right\rangle }{\sqrt{2}}\right)\\
 & = & H\left|i\oplus j\right\rangle H\left|j\right\rangle \end{eqnarray*}


Example circuit:\[
\left(H\otimes H\right)\left(Q_{\text{CNOT}}\right)\left(H\otimes H\right)\left|i\right\rangle \left|j\right\rangle \]
\[
\left|i\right\rangle \left|j\right\rangle \xrightarrow{H\otimes H}H\left|i\right\rangle H\left|j\right\rangle \xrightarrow{Q_{\text{CNOT}}}H\left|i\oplus j\right\rangle H\left|j\right\rangle \xrightarrow{H\otimes H}H^{\otimes2}\left|i\oplus j\right\rangle H^{\otimes2}\left|j\right\rangle =\left|i\oplus j\right\rangle \left|j\right\rangle \]



\subsubsection*{Controlled-U Gate}

Notation looks like $\left|i\right\rangle \left|j\right\rangle \xrightarrow{Q_{C-U}}\left|i\right\rangle U^{i}\left|j\right\rangle $

\begin{eqnarray*}
\left|00\right\rangle  & \rightarrow & \left|00\right\rangle \\
\left|01\right\rangle  & \rightarrow & \left|01\right\rangle \\
\left|10\right\rangle  & \rightarrow & \left|1\right\rangle Q\left|0\right\rangle \\
\left|11\right\rangle  & \rightarrow & \left|1\right\rangle Q\left|1\right\rangle \end{eqnarray*}


\[
Q_{C-U}=\left(\begin{array}{cc}
I & 0\\
0 & U\end{array}\right)\]



\section*{Lecture 7 (7 February)}


\subsection*{Lecture 6 Review}

\[
\textrm{Circuit: }(\left|A\right\rangle \left|B\right\rangle )=Q_{CNOT}\left|i\right\rangle \left|j\right\rangle \]
If $i$ and $j$ are defined on the computational basis, output is
$\left|i\right\rangle \left|i\oplus j\right\rangle $, but output
in terms of some other set of basis states will be expressed differently.


\subsection*{Controlled Z Gate}

\[
Z=\left(\begin{array}{rr}
1 & 0\\
0 & -1\end{array}\right)\]
\[
Q_{Z}\left|i\right\rangle \left|j\right\rangle =\left|i\right\rangle Z^{i}\left|j\right\rangle \]
\[
\begin{array}{l}
Z\left|0\right\rangle =\left|0\right\rangle \\
Z\left|1\right\rangle =-\left|1\right\rangle \end{array}\Rightarrow Z\left|j\right\rangle =\left(-1\right)^{j}\left|j\right\rangle \]
\[
Q_{Z}\left|i\right\rangle \left|j\right\rangle =\left(-1\right)^{ij}\left|i\right\rangle \left|j\right\rangle \]
The gate with the control reversed, $Z^{j}\left|i\right\rangle \left|j\right\rangle $,
going through the steps above, has the exact same definition, $\left(-1\right)^{ij}\left|i\right\rangle \left|j\right\rangle $.
So for the controlled Z gate, it is reasonable to think of either
input as being the controlling input on the computational basis.


\subsection*{Swap Gate}

\[
\textrm{Circuit: }\left(Q_{CNOT}\right)\left({Q'}_{CNOT}\right)\left(Q_{CNOT}\right)\left|i\right\rangle \left|j\right\rangle \]
where $Q_{CNOT}\left|i\right\rangle \left|j\right\rangle =\left|i\right\rangle X^{i}\left|j\right\rangle $
and ${Q'}_{CNOT}\left|i\right\rangle \left|j\right\rangle =X^{j}\left|i\right\rangle \left|j\right\rangle $)

\[
\left|i\right\rangle \left|j\right\rangle ^{\underrightarrow{Q_{CNOT}}}\left|i\right\rangle \left|i\oplus j\right\rangle {}^{\underrightarrow{{Q'}_{CNOT}}}\left|i\oplus i\oplus j=j\right\rangle \left|i\oplus j\right\rangle {}^{\underrightarrow{Q_{CNOT}}}\left|j\right\rangle \left|i\right\rangle \]



\subsubsection*{For arbitary states:\begin{eqnarray*}
\left|x\right\rangle \left|y\right\rangle  & = & \left(a\left|0\right\rangle +b\left|1\right\rangle \right)\left(c\left|0\right\rangle +d\left|1\right\rangle \right)\protect\\
 & = & ac\left|00\right\rangle +ad\left|01\right\rangle +bc\left|10\right\rangle +bd\left|11\right\rangle \protect\\
Swap\left|x\right\rangle \left|y\right\rangle  & = & ac\left|00\right\rangle +ad\left|10\right\rangle +bc\left|01\right\rangle +bd\left|11\right\rangle \protect\\
 & = & a\left(c\left|0\right\rangle +d\left|1\right\rangle \right)\left|0\right\rangle +b\left(c\left|0\right\rangle +d\left|1\right\rangle \right)\left|1\right\rangle \protect\\
 & = & \left(a\left|0\right\rangle +b\left|1\right\rangle \right)\left(c\left|0\right\rangle +d\left|1\right\rangle \right)\protect\\
 & = & \left|y\right\rangle \left|x\right\rangle \end{eqnarray*}
}


\subsection*{1-Qubit Gates as Rotations}

(See also section 4.2 of the textbook)

\[
X=\left(\begin{array}{rr}
0 & 1\\
1 & 0\end{array}\right),\quad Y=\left(\begin{array}{rr}
0 & -i\\
i & 0\end{array}\right),\quad Z=\left(\begin{array}{rr}
1 & 0\\
0 & -1\end{array}\right)\]
Implementation of all 1-qubit gates can be seen as counterclockwise
rotations by an angle $\vartheta$, of points plotted on the Bloch
sphere around the X, Y, and Z axes.\begin{eqnarray*}
e^{-i\vartheta X/2} & = & R_{X}\left(\vartheta\right)=\cos\left(\frac{\vartheta}{2}\right)I-i\sin\left(\frac{\vartheta}{2}\right)X=\left(\begin{array}{rr}
\cos\left(\frac{\vartheta}{2}\right) & -i\sin\left(\frac{\vartheta}{2}\right)\\
-i\sin\left(\frac{\vartheta}{2}\right) & \cos\left(\frac{\vartheta}{2}\right)\end{array}\right)\\
e^{-i\vartheta Y/2} & = & R_{Y}\left(\vartheta\right)=\cos\left(\frac{\vartheta}{2}\right)I-i\sin\left(\frac{\vartheta}{2}\right)Y=\left(\begin{array}{rr}
\cos\left(\frac{\vartheta}{2}\right) & -\sin\left(\frac{\vartheta}{2}\right)\\
\sin\left(\frac{\vartheta}{2}\right) & \cos\left(\frac{\vartheta}{2}\right)\end{array}\right)\\
e^{-i\vartheta Z/2} & = & R_{Z}\left(\vartheta\right)=\cos\left(\frac{\vartheta}{2}\right)I-i\sin\left(\frac{\vartheta}{2}\right)Z=\left(\begin{array}{lr}
e^{-i\vartheta/2} & 0\\
0 & e^{i\vartheta/2}\end{array}\right)\end{eqnarray*}


Proof of the equations above will be done in two parts. First, by
deriving the matrices from rotations around the axes, and then by
showing that the exponential forms are equivalent.

One general note to make here is that any matrix of the form $\left(\begin{array}{rr}
e^{ia} & 0\\
0 & e^{ib}\end{array}\right)$ can be expressed as a rotation around the Z axis by some angle. Just
observe: \[
\left(\begin{array}{rr}
e^{ia} & 0\\
0 & e^{ib}\end{array}\right)=e^{i\frac{a+b}{2}}\left(\begin{array}{rr}
e^{i\frac{a-b}{2}} & 0\\
0 & e^{i\frac{b-a}{2}}\end{array}\right)\]



\subsubsection*{Rotation around X axis}

Take an arbitrary qubit $\left|y\right\rangle =\cos\frac{\vartheta_{1}}{2}\left|0\right\rangle +e^{i\varphi}\sin\frac{\vartheta_{1}}{2}\left|1\right\rangle $.
Trying to find an expression for this qubit after a rotation about
the X axis is messy. But for the case where $\varphi=\frac{\pi}{2}$,
finding the rotation is easy, and using that case is sufficient for
finding the general rotation matrix. So let \[
\left|\widetilde{y}\right\rangle =\cos\frac{\vartheta_{1}}{2}\left|0\right\rangle +e^{i\pi/2}\sin\frac{\vartheta_{1}}{2}\left|1\right\rangle =\cos\frac{\vartheta_{1}}{2}\left|0\right\rangle +i\sin\frac{\vartheta_{1}}{2}\left|1\right\rangle \]
This is a projection of $\left|y\right\rangle $ onto the YZ plane
(x=0). Rotating this point $\vartheta$ radians counterclockwise around
the X axis is the same thing as subtracting $\vartheta$ from $\vartheta_{1}$.
The rotated point is\[
\left|\widetilde{y}'\right\rangle =\cos\frac{\vartheta_{1}-\vartheta}{2}\left|0\right\rangle +i\sin\frac{\vartheta_{1}-\vartheta}{2}\left|1\right\rangle \]
In terms of a rotation matrix, the mapping from $\left|\widetilde{y}\right\rangle $
to $\left|\widetilde{y}'\right\rangle $ looks like:\[
\left(\begin{array}{rr}
a & b\\
c & d\end{array}\right)\left(\begin{array}{r}
\cos\frac{\vartheta_{1}}{2}\\
i\sin\frac{\vartheta_{1}}{2}\end{array}\right)=\left(\begin{array}{r}
\cos\frac{\vartheta_{1}-\vartheta}{2}\\
i\sin\frac{\vartheta_{1}-\vartheta}{2}\end{array}\right)\]


Using the angle sum identies: \begin{eqnarray*}
\sin\left(x+y\right) & = & \sin x\cos y+\cos x\sin y\\
\cos\left(x+y\right) & = & \cos x\cos y-\sin x\sin y\end{eqnarray*}
on the right hand side, and matrix multiplication on the left hand
side gives:

\[
\left(\begin{array}{r}
a\cos\frac{\vartheta_{1}}{2}+ib\sin\frac{\vartheta_{1}}{2}\\
c\cos\frac{\vartheta_{1}}{2}+id\sin\frac{\vartheta_{1}}{2}\end{array}\right)=\left(\begin{array}{r}
\cos\frac{\vartheta_{1}}{2}\cos\frac{\vartheta}{2}+\sin\frac{\vartheta_{1}}{2}\sin\frac{\vartheta}{2}\\
i\sin\frac{\vartheta_{1}}{2}\cos\frac{\vartheta}{2}-i\cos\frac{\vartheta_{1}}{2}\sin\frac{\vartheta}{2}\end{array}\right)\]


Comparing the two sides of this equation gives you the following solution:\begin{eqnarray*}
a & = & \cos\frac{\vartheta}{2}\\
b & = & -\sin\frac{\vartheta}{2}\\
c & = & -i\sin\frac{\vartheta}{2}\\
d & = & \cos\frac{\vartheta}{2}\end{eqnarray*}
So\[
R_{X}\left(\vartheta\right)=\left(\begin{array}{rr}
a & b\\
c & d\end{array}\right)=\left(\begin{array}{rr}
\cos\left(\frac{\vartheta}{2}\right) & -i\sin\left(\frac{\vartheta}{2}\right)\\
-i\sin\left(\frac{\vartheta}{2}\right) & \cos\left(\frac{\vartheta}{2}\right)\end{array}\right)\]



\subsubsection*{Rotation around Z axis}

Again, start with an arbitrary qubit, $\left|y\right\rangle =\cos\frac{\vartheta}{2}\left|0\right\rangle +e^{i\varphi}\sin\frac{\vartheta}{2}\left|1\right\rangle $.
Taking $\vartheta=\frac{\pi}{2}$ projects $\left|y\right\rangle $
onto the XY plane (on the equator at z=0). \[
\left|\widetilde{y}\right\rangle =\frac{1}{\sqrt{2}}\left|0\right\rangle +e^{i\varphi}\frac{1}{\sqrt{2}}\left|1\right\rangle \]


Rotating that point by $\vartheta$ radians counterclockwise gives:\[
\left|\widetilde{y}'\right\rangle =\frac{1}{\sqrt{2}}\left|0\right\rangle +e^{i(\varphi+\vartheta)}\frac{1}{\sqrt{2}}\left|1\right\rangle \]
Expressed as a rotation matrix:\[
\left(\begin{array}{rr}
a & b\\
c & d\end{array}\right)\left(\begin{array}{r}
\frac{1}{\sqrt{2}}\\
e^{i\varphi}\frac{1}{\sqrt{2}}\end{array}\right)=\left(\begin{array}{r}
\frac{1}{\sqrt{2}}\\
e^{i(\varphi+\vartheta)}\frac{1}{\sqrt{2}}\end{array}\right)\]
Simplifying:\[
\left(\begin{array}{r}
a+be^{i\varphi}\\
c+de^{i\varphi}\end{array}\right)=\left(\begin{array}{r}
1\\
e^{i\varphi_{1}}e^{i\vartheta}\end{array}\right)\]
\[
R_{Z}\left(\vartheta\right)=\left(\begin{array}{rr}
a & b\\
c & d\end{array}\right)=\left(\begin{array}{rr}
1 & 0\\
0 & e^{i\vartheta}\end{array}\right)=e^{i\vartheta/2}\left(\begin{array}{lr}
e^{-i\vartheta/2} & 0\\
0 & e^{i\vartheta/2}\end{array}\right)\]



\subsubsection*{Rotation around Y axis}

This was left as an exercise and not covered in the lecture. But,
taking a qubit on the XZ plane so $\varphi=0$ gives:

\[
\left|\widetilde{y}\right\rangle =\cos\frac{\vartheta_{1}}{2}\left|0\right\rangle +\sin\frac{\vartheta_{1}}{2}\left|1\right\rangle \]


Rotating that point by $\vartheta$ radians counterclockwise gives:\[
\left|\widetilde{y}'\right\rangle =\cos\frac{\vartheta_{1}+\vartheta}{2}\left|0\right\rangle +\sin\frac{\vartheta_{1}+\vartheta}{2}\left|1\right\rangle \]


Expressed using a rotation matrix this is:\[
\left(\begin{array}{rr}
a & b\\
c & d\end{array}\right)\left(\begin{array}{r}
\cos\frac{\vartheta_{1}}{2}\\
\sin\frac{\vartheta_{1}}{2}\end{array}\right)=\left(\begin{array}{r}
\cos\frac{\vartheta_{1}+\vartheta}{2}\\
\sin\frac{\vartheta_{1}+\vartheta}{2}\end{array}\right)\]
Which becomes:\[
\left(\begin{array}{r}
a\cos\frac{\vartheta_{1}}{2}+b\sin\frac{\vartheta_{1}}{2}\\
c\cos\frac{\vartheta_{1}}{2}+d\sin\frac{\vartheta_{1}}{2}\end{array}\right)=\left(\begin{array}{r}
\cos\frac{\vartheta_{1}}{2}\cos\frac{\vartheta}{2}-\sin\frac{\vartheta_{1}}{2}\sin\frac{\vartheta}{2}\\
\sin\frac{\vartheta_{1}}{2}\cos\frac{\vartheta}{2}+\cos\frac{\vartheta_{1}}{2}\sin\frac{\vartheta}{2}\end{array}\right)\]
So\[
R_{Y}\left(\vartheta\right)=\left(\begin{array}{rr}
a & b\\
c & d\end{array}\right)=\left(\begin{array}{rr}
\cos\frac{\vartheta}{2} & -\sin\frac{\vartheta}{2}\\
\sin\frac{\vartheta}{2} & \cos\frac{\vartheta}{2}\end{array}\right)\]



\subsection*{Rotations as Exponentials of Pauli Matrices}

Theorem 1 (exercise 4.2): If $A^{2}=I$ then $e^{ixA}=\cos xI-i\sin x$A

Proof (using Taylor series expansions from calculus):\begin{eqnarray*}
e^{-ixA} & = & \sum_{k=0}^{\infty}\frac{i^{k}x^{k}A^{k}}{k!}=\sum_{k\textrm{ odd}}^{\infty}\frac{i^{k}x^{k}A^{k}}{k!}+\sum_{k\textrm{ even}}^{\infty}\frac{i^{k}x^{k}A^{k}}{k!}\\
e^{-ixA} & = & \sum_{k=0}^{\infty}\frac{i^{\left(2k+1\right)}x^{\left(2k+1\right)}A^{\left(2k+1\right)}}{\left(2k+1\right)!}+\sum_{k=0}^{\infty}\frac{i^{\left(2k\right)}x^{\left(2k\right)}A^{\left(2k\right)}}{\left(2k\right)!}\\
 & = & iA\sum_{k=0}^{\infty}\frac{\left(-1\right)^{k}x^{\left(2k+1\right)}}{\left(2k+1\right)!}+I\sum_{k=0}^{\infty}\frac{\left(-1\right)^{k}x^{\left(2k\right)}}{\left(2k\right)!}\\
 & = & iA\sin x+I\cos x\end{eqnarray*}



\section*{Lecture 8 (12 February)}


\subsection*{Z-Y Decomposition}

Theorem 2: Any 1-qubit gate can be decomposed as\[
U=e^{i\alpha}R_{Z}\left(\beta\right)R_{Y}\left(\gamma\right)R_{Z}\left(\delta\right)\]
(This is theorem 4.1 in textbook)

Proof:

Start by expressing U as:\[
U=\left(\begin{array}{cc}
X_{11}e^{i\varphi_{11}} & X_{12}e^{i\varphi_{12}}\\
X_{21}e^{i\varphi_{21}} & X_{22}e^{i\varphi_{22}}\end{array}\right)\]
Because U is orthonormal, vector norm of rows and columns is 1, so:\begin{eqnarray*}
X_{11}^{2}+X_{12}^{2} & = & 1\\
X_{21}^{2}+X_{22}^{2} & = & 1\\
X_{11}^{2}+X_{21}^{2} & = & 1\\
X_{12}^{2}+X_{22}^{2} & = & 1\end{eqnarray*}
Begin decomposing U by pulling out Z rotations (note that in general,
post-multiplying with a diagonal matrix gives you multiples of the
original columns, pre-multiplying with diagonal matrix gives you multiples
of the original rows):\begin{eqnarray*}
U & = & \left(\begin{array}{cc}
X_{11} & X_{12}\\
X_{21}e^{i\left(\varphi_{21}-\varphi_{11}\right)} & X_{22}e^{i\left(\varphi_{22}{-\varphi}_{12}\right)}\end{array}\right)\left(\begin{array}{cc}
e^{i\varphi_{11}} & 0\\
0 & e^{i\varphi_{12}}\end{array}\right)\\
 & = & \left(\begin{array}{cc}
1 & 0\\
0 & e^{i\left(\varphi_{21}-\varphi_{11}\right)}\end{array}\right)\left(\begin{array}{cl}
X_{11} & X_{12}\\
X_{21} & X_{22}e^{i\left(\varphi_{22}{-\varphi}_{12}-\left(\varphi_{21}-\varphi_{11}\right)\right)}\end{array}\right)\left(\begin{array}{cc}
e^{i\varphi_{11}} & 0\\
0 & e^{i\varphi_{12}}\end{array}\right)\end{eqnarray*}
The two outer matrices are Z rotations, and middle matrix can also
be expressed as rotations, but different kinds of rotations, depending
on the values inside.

Case 1: $X_{11}=0\quad\Longrightarrow\quad X_{12}^{2}=1\quad\Longrightarrow\quad X_{22}=0\quad\Longrightarrow\quad X_{21}^{2}=1$

Case 1.1: $X_{12}$ and $X_{21}$ have the same sign. In this case,
the matrix is the product of Y and Z rotations:\[
\pm\left(\begin{array}{rr}
0 & 1\\
1 & 0\end{array}\right)=\pm\left(\begin{array}{rr}
0 & -1\\
1 & 0\end{array}\right)\left(\begin{array}{rr}
1 & 0\\
0 & -1\end{array}\right)=\pm R_{Y}\left(\pi\right)Z\]


Case 1.2: $X_{12}$ and $X_{21}$ have different signs. In this case,
the matrix is a Y rotation:\[
\pm\left(\begin{array}{rr}
0 & -1\\
1 & 0\end{array}\right)=\pm R_{Y}\left(\pi\right)\]


Case 2: $X_{12}=0\quad\Longrightarrow\quad X_{22}^{2}=1\quad\Longrightarrow\quad X_{21}=0\quad\Longrightarrow\quad X_{11}^{2}=1$

Case 2.1: $X_{11}$ and $X_{22}$ have the same sign. In this case
the matrix is just identity:\[
\pm\left(\begin{array}{rr}
1 & 0\\
0 & 1\end{array}\right)=\pm I\]


Case 2.2: $X_{11}$ and $X_{22}$ have different signs. In this case
the matrix is Z:\[
\pm\left(\begin{array}{rr}
1 & 0\\
0 & -1\end{array}\right)=\pm Z\]


Case 3: All $X_{ij}\neq0$. Letting ${\varphi=\varphi}_{22}{-\varphi}_{12}-\left(\varphi_{21}-\varphi_{11}\right)$,
because the matrix is unitary we know:\begin{eqnarray*}
\left(\begin{array}{cc}
X_{11} & X_{21}\end{array}\right)\left(\begin{array}{c}
X_{12}\\
X_{22}e^{i\varphi}\end{array}\right) & = & 0\\
X_{11}X_{12}+X_{21}X_{22}e^{i\varphi} & = & 0\end{eqnarray*}
In order for that to be true, the expression $e^{i\varphi}=\cos\varphi+i\sin\varphi$
cannot have an imaginary component, so $\sin\varphi=0$ and $\varphi=k\pi$.

{[}DUNNO: The fact that the matrix is unitary and all entries are
real is enough to make it rotation about Y?]

Theorem 3: $U$ can be decomposed as $U=e^{i\alpha}AXBXC$ where $ABC=I$.
Book has recipe for $ABC$ which serves as proof. (Corollary 4.2).
In summary, \begin{eqnarray*}
A & = & R_{z}R_{Y}\\
B & = & R_{Y}R_{Z}\\
C & = & R_{Z}\end{eqnarray*}



\subsection*{Controlled U, C(U), From 1-Qubit U}

Use the Theorem 3 decomposition above. Start with just the phase shift,
$e^{i\alpha}$. A controlled circuit for the phase shift $C\left(e^{i\alpha}I\right)$should
have the following behavior:

\begin{tabular}{|c|c|}
\hline 
Input&
Output\tabularnewline
\hline
\hline 
$\left|0\right\rangle \left|j\right\rangle $&
$\left|0\right\rangle \left|j\right\rangle $\tabularnewline
\hline 
$\left|1\right\rangle \left|j\right\rangle $&
$\left|1\right\rangle e^{i\alpha}\left|j\right\rangle $\tabularnewline
\hline
\end{tabular}

or

\begin{tabular}{|c|c|}
\hline 
Input&
Output\tabularnewline
\hline
\hline 
$\left|0\right\rangle \left|0\right\rangle $&
$\left|0\right\rangle \left|0\right\rangle $\tabularnewline
\hline 
$\left|0\right\rangle \left|1\right\rangle $&
$\left|0\right\rangle \left|1\right\rangle $\tabularnewline
\hline 
$\left|1\right\rangle \left|0\right\rangle $&
$\left|1\right\rangle e^{i\alpha}\left|0\right\rangle $\tabularnewline
\hline 
$\left|1\right\rangle \left|1\right\rangle $&
$\left|1\right\rangle e^{i\alpha}\left|1\right\rangle $\tabularnewline
\hline
\end{tabular}

The outputs from this controlled gate can be produced by a simple
unitary transformation applied to the first qubit: \[
\left(\begin{array}{cc}
1 & 0\\
0 & e^{i\alpha}\end{array}\right)\]


\[
\textrm{Circuit: }\left(I\otimes\left(\begin{array}{cc}
e^{i\alpha} & 0\\
0 & e^{i\alpha}\end{array}\right)^{\#1}\right)=\left(\left(\begin{array}{cc}
1 & 0\\
0 & e^{i\alpha}\end{array}\right)\otimes I\right)\]


(My weird circuit notation would look a lot better in picture form,
but it just shows the gates applied to each qubit (from top to bottom)
written as tensor products. $I$ means no gate operating on a qubit.
Variables or matrices stand for real gates. Controlled gates are written
with numeric superscripts indicating which qubit they are controlled
by. For example, $X^{\#1}$ is $C_{NOT}$ controlled by first qubit.)

Using the circuit above, you can write the circuit for a general $C\left(U\right)$
where $U=e^{i\alpha}AXBXC$ and $ABC=I$:\[
\textrm{Circuit: }\left(\left(\begin{array}{cc}
1 & 0\\
0 & e^{i\alpha}\end{array}\right)\otimes A\right)\left({I\otimes X}^{\#1}\right)\left(I\otimes B\right)\left({I\otimes X}^{\#1}\right)\left(I\otimes C\right)\]


\begin{tabular}{|c|c|}
\hline 
Input&
Output\tabularnewline
\hline
\hline 
$\left|0\right\rangle \left|j\right\rangle $&
$\left|0\right\rangle ABC\left|j\right\rangle =\left|0\right\rangle I\left|j\right\rangle $\tabularnewline
\hline 
$\left|1\right\rangle \left|j\right\rangle $&
$e^{i\alpha}\left|1\right\rangle AXBXC\left|j\right\rangle =\left|1\right\rangle U\left|j\right\rangle $\tabularnewline
\hline
\end{tabular}

The circuit works because when $\left|i\right\rangle $ is 0, the
$C_{NOT}$ gates have no effect and the output for the second qubit
is $ABC$, exactly the same as the input because $ABC=I$


\subsection*{Controlled U, $C^{n}\left(U\right)$, with multiple control inputs}

Using $n$ control qubits to control unitary operation of $k$ qubits:\begin{eqnarray*}
C^{n}\left(U\right)\left|x\right\rangle \left|y\right\rangle  & = & C^{n}\left(U\right)\left|x_{0}\ldots x_{n-1}\right\rangle \left|y_{0}\ldots y_{k-1}\right\rangle \\
 & = & \left|x_{0}\ldots x_{n-1}\right\rangle U^{x_{0}\cdot x_{1}\ldots{\cdot x}_{n-1}}\left|y_{0}\ldots y_{k-1}\right\rangle \\
 & = & \left|x\right\rangle U^{x_{0}\cdot x_{1}\ldots{\cdot x}_{n-1}}\left|y\right\rangle \end{eqnarray*}
$U$ is controlled by product of bits of $\left|x\right\rangle $,
it is only applied when every bit is 1.

In matrix form, \[
C^{n}\left(U\right)=\left(\begin{array}{cc}
I & 0\\
0 & U\end{array}\right)\]


Size of $C^{n}\left(U\right)$ is $2^{n+k}$, size of $I$ is $\left(2^{n}-1\right)\left(2^{k}\right)$,
size of $U$ is $2^{k}$. Each column of the matrix is the output
of a basis state. The columns from $\left|0\cdots0\right\rangle \left|0\cdots0\right\rangle $to
$\left|1\cdots10\right\rangle \left|1\cdots1\right\rangle $for the
first part of the matrix (the bulk of it) just give identify. Then,
the last columns from$\left|1\cdots1\right\rangle \left|0\cdots0\right\rangle $
to $\left|1\cdots1\right\rangle \left|1\cdots1\right\rangle $ apply
$U$ to the last $k$ qubits of the input.


\subsection*{Toffolli Gate}

An example of $C^{n}\left(U\right)$, with $n=2$ and $U=X$.\[
X^{x\cdot y}\left|x\right\rangle \left|y\right\rangle \left|z\right\rangle =\left|x\right\rangle \left|y\right\rangle \left|\left(xy\right)\oplus z\right\rangle \]


NAND gate can be implemented in terms of Toffoli:\[
X^{x\cdot y}\left|x\right\rangle \left|y\right\rangle \left|1\right\rangle =\left|x\right\rangle \left|y\right\rangle \left|\left(xy\right)\oplus1\right\rangle =\left|x\right\rangle \left|y\right\rangle \left|\overline{xy}\right\rangle \]


($\overline{xy}$ is logical inverse of xy)

Fanout can be implemented with:\[
X^{1\cdot x}\left|1\right\rangle \left|x\right\rangle \left|0\right\rangle =\left|1\right\rangle \left|x\right\rangle \left|\left(1\cdot x\right)\oplus0\right\rangle =\left|1\right\rangle \left|x\right\rangle \left|x\right\rangle \]



\section*{Lecture 9 (14 February)}


\subsection*{Implementing Controlled 1-Qubit Gate $C^{2}\left(U\right)$ with
$V^{2}=U$}

\[
\textrm{Circuit: }\left({I\otimes I\otimes U}^{\#1,\#2}\right)=\left(I\otimes I\otimes V^{\#1}\right)\left(I\otimes X^{\#1}\otimes I\right)\left(I\otimes I\otimes{V^{H}}^{\#2}\right)\left(I\otimes X^{\#1}\otimes I\right)\left(I\otimes I\otimes V^{\#2}\right)\]


(Figure 4.8 in book)

Evaluated:

\begin{tabular}{|c|c|c|}
\hline 
$\left|x_{1}\right\rangle $&
$\left|x_{2}\right\rangle $&
$\left|x_{3}\right\rangle $\tabularnewline
\hline 
$\left|x_{1}\right\rangle $&
$\left|x_{2}\right\rangle $&
$V^{x_{2}}\left|x_{3}\right\rangle $\tabularnewline
\hline 
$\left|x_{1}\right\rangle $&
$\left|{x_{1}\oplus x}_{2}\right\rangle $&
$V^{x_{2}}\left|x_{3}\right\rangle $\tabularnewline
\hline 
$\left|x_{1}\right\rangle $&
$\left|{x_{1}\oplus x}_{2}\right\rangle $&
${V^{H}}^{{x_{1}\oplus x}_{2}}{V^{x_{2}}}\left|x_{3}\right\rangle $\tabularnewline
\hline 
$\left|x_{1}\right\rangle $&
$\left|x_{2}\right\rangle $&
${V^{H}}^{{x_{1}\oplus x}_{2}}{V^{x_{2}}}\left|x_{3}\right\rangle $\tabularnewline
\hline 
$\left|x_{1}\right\rangle $&
$\left|x_{2}\right\rangle $&
${V^{x_{1}}}{V^{H}}^{{x_{1}\oplus x}_{2}}{V^{x_{2}}}\left|x_{3}\right\rangle $\tabularnewline
\hline
\end{tabular}

Evaluate third qubit output case by case

Case 1: If $X_{1}\oplus X_{2}=1$ then ${V^{x_{1}}}V^{H}{V^{x_{2}}}\left|x_{3}\right\rangle $

Case 1.1: If $X_{1}=0$ then $X_{2}=1$ and $V^{H}V\left|x_{3}\right\rangle =\left|x_{3}\right\rangle $

Case 1.2: If $X_{2}=0$ then $X_{1}=1$ and ${VV}^{H}\left|x_{3}\right\rangle =\left|x_{3}\right\rangle $

Case 2: If $X_{1}\oplus X_{2}=0$ then ${V^{x_{1}}}{V^{x_{2}}}\left|x_{3}\right\rangle $

Case 2.1: If $X_{1}=X_{2}=0$ then$\left|x_{3}\right\rangle $

Case 2.2: If $X_{1}=X_{2}=1$ then$VV\left|x_{3}\right\rangle =U\left|x_{3}\right\rangle $


\subsubsection*{Toffoli Gate}

Using $V=\frac{1-i}{2}\left(I+iX\right)$ above gives the tofolli
gate. Verify:\begin{eqnarray*}
V^{2} & = & \frac{\left(1-2i-1\right)^{2}}{4}\left(I^{2}+2iX-X^{2}\right)\\
 & = & \frac{-2i}{4}2iX=X\end{eqnarray*}
$V$ can also be rewritten:\begin{eqnarray*}
V & = & \frac{1-i}{2}\left(I+iX\right)\\
 & = & \frac{1-i}{\sqrt{2}}\left(\frac{\sqrt{2}}{2}I+\frac{\sqrt{2}}{2}iX\right)\\
 & = & \frac{1-i}{\sqrt{2}}e^{i\frac{\pi}{4}X}=\frac{1-i}{\sqrt{2}}R_{X}\left(-\frac{\pi}{2}\right)\end{eqnarray*}



\subsection*{No Cloning Theorem}

(Box 12.1, Page 532 in book)

Is there an operator $U$ that satisfies $U\left(\left|\psi\right\rangle \left|s\right\rangle \right)=\left|\psi\right\rangle \left|\psi\right\rangle $
for arbitrary states $\left|\psi\right\rangle $ with some standard
input $\left|s\right\rangle $?

Assuming there is such an operator, the following will be true for
two states$\left|\psi_{1}\right\rangle $ and $\left|\psi_{2}\right\rangle $
\begin{eqnarray*}
U\left(\left|\psi_{1}\right\rangle \left|s\right\rangle \right) & = & \left|\psi_{1}\right\rangle \left|\psi_{1}\right\rangle \\
U\left(\left|\psi_{2}\right\rangle \left|s\right\rangle \right) & = & \left|\psi_{2}\right\rangle \left|\psi_{2}\right\rangle \end{eqnarray*}


Inner product of above equations, left hand side:\[
\left(U\left(\left|\psi_{1}\right\rangle \left|s\right\rangle \right)\right)^{H}\left(U\left(\left|\psi_{2}\right\rangle \left|s\right\rangle \right)\right)\]
\begin{eqnarray*}
 & = & \left(\left|\psi_{1}\right\rangle \left|s\right\rangle \right)^{H}U^{H}U\left(\left|\psi_{2}\right\rangle \left|s\right\rangle \right)\\
 & = & \left(\left\langle \psi_{1}\right|\left\langle s\right|\right)\left(\left|\psi_{2}\right\rangle \left|s\right\rangle \right)\\
 & = & \left\langle \psi_{1}\mid\psi_{2}\right\rangle \left\langle s\mid s\right\rangle \\
 & = & \left\langle \psi_{1}\mid\psi_{2}\right\rangle \end{eqnarray*}
Right hand side:\[
\left(\left|\psi_{1}\right\rangle \left|\psi_{1}\right\rangle \right)^{H}\left(\left|\psi_{2}\right\rangle \left|\psi_{2}\right\rangle \right)\]
\begin{eqnarray*}
 & = & \left(\left\langle \psi_{1}\right|\left\langle \psi_{1}\right|\right)\left(\left|\psi_{2}\right\rangle \left|\psi_{2}\right\rangle \right)\\
 & = & \left\langle \psi_{1}\mid\psi_{2}\right\rangle \left\langle \psi_{1}\mid\psi_{2}\right\rangle \\
 & = & \left\langle \psi_{1}\mid\psi_{2}\right\rangle ^{2}\end{eqnarray*}
Both sides together:\[
\left\langle \psi_{1}\mid\psi_{2}\right\rangle =\left\langle \psi_{1}\mid\psi_{2}\right\rangle ^{2}\]
which can only be true in two cases

Case 1: $\left\langle \psi_{1}\mid\psi_{2}\right\rangle =0$ means
$\left|\psi_{1}\right\rangle \perp\left|\psi_{2}\right\rangle $ 

Case 2: $\left\langle \psi_{1}\mid\psi_{2}\right\rangle =1$ means
$\left|\psi_{1}\right\rangle =\left|\psi_{2}\right\rangle $ 

So a cloning operator $U$ will can work for a single state, or for
two states that are orthogonal, there is no $U$ that can clone states
generally. 


\subsection*{Implementing Controlled n-Qubit Gates $C^{n}\left(U\right)$ (n>2)}

Start off with simple examples and build in complexity


\subsubsection*{U=X, k=1, n=3}

This just means taking a normal Toffili gate\[
\textrm{Circuit: }\left({I\otimes I\otimes X}^{\#1,\#2}\right)\left|x_{1}\right\rangle \left|x_{2}\right\rangle \left|x_{3}\right\rangle \]
and extending it to get an additional control line:

\[
\textrm{Circuit: }\left({I\otimes I\otimes I\otimes I\otimes X}^{\#3,\#4}\right)\left({I\otimes I\otimes X}^{\#1,\#2}\otimes I\otimes I\right)\left|x_{1}\right\rangle \left|x_{2}\right\rangle \left|0\right\rangle \left|x_{3}\right\rangle \left|x_{4}\right\rangle \]


Output of circuit will be $\left|x_{1}\right\rangle \left|x_{2}\right\rangle \left|x_{1}x_{2}\right\rangle \left|x_{3}\right\rangle \left|\left(x_{1}x_{2}x_{3}\right)\oplus x_{4}\right\rangle $,
and the last qubit has the output we are looking for.


\subsubsection*{U=any, k=1, n=any}

In the general case, if you want to control a 1 qubit $U$ with $n$
inputs, you need to have $n-1$ $\left|0\right\rangle $ inputs as
well. Add $n-1$ toffoli gates, taking the product of the first two
qubit lines to the first $\left|0\right\rangle $ input, the product
of the second two lines (\#3 and \#4) onto the second $\left|0\right\rangle $
input, and so on. Halfway down, you reach the first $\left|0\right\rangle $
lines, but you keep taking products in the same pattern, and at the
end, the last $\left|0\right\rangle $ line will have the product
of the first $n$ qubits. Below that, the unitary operation $U$ can
be placed it's own line and can it be controlled by the last $\left|0\right\rangle $
line, right above it, which holds the product of all the control inputs.
An additional $n-1$ toffoli gates can be placed after the unitary
operation, in the same pattern as before, to make the$\left|0\right\rangle $
lines have$\left|0\right\rangle $ outputs.


\subsubsection*{U=$U^{\otimes k}$, k=any, n=1}

\[
Q_{U}\left|c\right\rangle \left|t_{1}t_{2}\cdots t_{k}\right\rangle =\left|c\right\rangle U^{C}\left|t_{1}\right\rangle U^{C}\left|t_{2}\right\rangle \cdots U^{C}\left|t_{k}\right\rangle \]


A special case is $U=X$:

\begin{eqnarray*}
Q_{X}\left|c\right\rangle \left|t_{1}t_{2}\cdots t_{k}\right\rangle  & = & \left|c\right\rangle \left|{c\oplus t}_{1}\right\rangle \left|{c\oplus t}_{2}\right\rangle \cdots\left|{c\oplus t}_{k}\right\rangle \end{eqnarray*}
which can be drawn with a single control node, $k$ $X$ nodes ($\oplus$)
for each affected qubit, and a line connecting all the nodes.

In matrix form, \[
C\left(X^{\otimes k}\right)=\left(\begin{array}{cc}
I & 0\\
0 & X^{\otimes k}\end{array}\right)\]


Size of $C\left(X^{\otimes k}\right)$ is $2^{k+1}$, size of $I$,
$X^{\otimes k}$ and the 0 matrices is $2^{k}$. Each column of the
matrix is the output of a basis state. The columns from $\left|0\right\rangle \left|0\cdots0\right\rangle $to
$\left|0\right\rangle \left|1\cdots1\right\rangle $for the first
half of the matrix just give identify. Then, the last columns from$\left|1\right\rangle \left|0\cdots0\right\rangle $
to $\left|1\right\rangle \left|1\cdots1\right\rangle $ apply $X^{\otimes k}$
to the last $k$ qubits of the input. $X^{\otimes k}$ looks like
a reflected identify matrix, with 1s going from the bottom left corner
to the top right, and 0s everywhere else.

Above can be generalized,\begin{eqnarray*}
Q_{U}\left|c\right\rangle \left|t_{1}t_{2}\cdots t_{k}\right\rangle  & = & \left|c\right\rangle U^{C}\left|t_{1}\right\rangle U^{C}\left|t_{2}\right\rangle \cdots U^{C}\left|t_{k}\right\rangle \\
 & = & \left|c\right\rangle \left(U^{C}\right)^{\otimes k}\left|t_{1}\cdots t_{k}\right\rangle \end{eqnarray*}
And\[
Q_{U}=\left(\begin{array}{cc}
I & 0\\
0 & U^{\otimes k}\end{array}\right)\]



\subsection*{2 Level Matrix Gate}

Acts non-linearly on at most 2 components of a vector, example:\[
\left(U\right)_{dxd}\left(\begin{array}{c}
x_{1}\\
x_{2}\\
x_{3}\\
\vdots\\
x_{d}\end{array}\right)=\left(\begin{array}{c}
{x'}_{1}\\
{x'}_{2}\\
x_{3}\\
\vdots\\
x_{d}\end{array}\right)\textrm{ or }=\left(\begin{array}{c}
{x'}_{1}\\
x_{2}\\
{x'}_{3}\\
\vdots\\
x_{d}\end{array}\right)\textrm{ or }=\left(\begin{array}{c}
x_{1}\\
{x'}_{2}\\
{x'}_{3}\\
\vdots\\
x_{d}\end{array}\right)\]


Mentioned: QR Decomposition, Hausholder matrix


\section*{Lecture 10 (19 February)}

{[}DUNNO: Was late to class, no idea what this is]

Implementation Topic

$C^{2}\left(U\right)$, $C^{n}\left(U\right)$

2-Level Gates /Matrices

\begin{eqnarray*}
\left(\begin{array}{ccc}
\frac{\alpha_{1}}{x} & \frac{\alpha_{2}}{x} & 0\\
\frac{\alpha_{2}}{x} & \frac{\alpha_{1}}{x} & 0\\
0 & 0 & 1\end{array}\right)\left(\begin{array}{ccc}
\alpha_{1} & \beta_{1} & \gamma_{1}\\
\alpha_{2} & \beta_{2} & \gamma_{2}\\
\alpha_{3} & \beta_{3} & \gamma_{3}\end{array}\right) & = & \left(\begin{array}{ccc}
\alpha_{1} & \beta_{1} & \gamma_{1}\\
0 & \beta_{2} & \gamma_{2}\\
\alpha_{3} & \beta_{3} & \gamma_{3}\end{array}\right)\end{eqnarray*}
\[
x=\sqrt{\left|\alpha_{1}\right|^{2}+\left|\alpha_{2}\right|^{2}}\]
\[
\left(\begin{array}{cc}
\frac{\alpha_{1}}{x} & \frac{{-\alpha}_{2}}{x}\end{array}\right)\left(\begin{array}{c}
\frac{{-\alpha}_{2}}{x}\\
\frac{\alpha_{1}}{x}\end{array}\right)=0\]


First matrix is $U_{1}$, second matrix is $U$.

\[
\left(\begin{array}{ccc}
{\bar{\alpha}'}_{1} & 0 & \bar{\gamma}_{1}\\
0 & 1 & 0\\
{-\alpha}_{3} & 0 & {\gamma'}_{3}\end{array}\right)\left(\begin{array}{ccc}
{\alpha''}_{1} & {\beta''}_{1} & {\gamma''}_{1}\\
0 & {\beta''}_{2} & {\gamma''}_{2}\\
0 & {\beta''}_{3} & {\gamma''}_{3}\end{array}\right)=\left(\begin{array}{ccc}
{\alpha''}_{1} & 0 & 0\\
0 & {\beta''}_{2} & {\gamma''}_{2}\\
0 & {\beta''}_{3} & {\gamma''}_{3}\end{array}\right)\]
Repeat as submatrix $\left|{\alpha''}_{1}\right|=1$

\[
U_{3}U_{2}U_{1}U=\left(\begin{array}{ccc}
{\alpha''}_{1} & 0 & 0\\
0 & {\beta''}_{2} & 0\\
0 & 0 & {\gamma''}_{3}\end{array}\right)D\]
$D$ is some diagonal matrix holding relative phases.

\[
U=U_{1}^{-1}U_{2}^{-1}U_{3}^{-1}D=U_{1}^{H}U_{2}^{H}U_{3}^{H}D\]



\subsection*{Measurements}

(Book 2.2.3) Measurements are made with collections of measurement
operators, $\left\{ M_{j}\right\} $, where operators are Hermitian
matrices, not necessarily unitary. There is one measurement operator
$M_{j}$ for each possible outcome, $j$. The measurements satisfy
the completeness equation:\[
\sum_{j=0}^{k-1}M_{j}^{H}M_{j}=I\]
Given a state $\left|\psi\right\rangle ,$ an outcome $j$ occurs
with probability \[
p\left(j\right)=\left\langle \psi\right|M_{j}^{H}M_{j}\left|\psi\right\rangle =\left\Vert M_{j}\left|\psi\right\rangle \right\Vert ^{2}\]
causing the state to collapse to $\frac{M_{j}\left|\psi\right\rangle }{\sqrt{p\left(j\right)}}$.

The probabilities of all possible outcomes $j$ sum to one. Proof\begin{eqnarray*}
1 & = & \left\langle \psi\mid\psi\right\rangle =\left\langle \psi\right|I\left|\psi\right\rangle =\left\langle \psi\right|\sum_{j}M_{j}^{H}M_{j}\left|\psi\right\rangle \\
 & = & \sum_{j}\left\langle \psi\right|M_{j}^{H}M_{j}\left|\psi\right\rangle =\sum_{j}p\left(j\right)\end{eqnarray*}



\subsection*{Projective Measurements}

Projective measurements are measurements on the computational basis.

Example 1:

$M_{j}=\left|j\right\rangle \left\langle j\right|=\left(\begin{array}{ccccc}
 &  & 0\\
 &  & \vdots\\
0 & \ldots & 1 & \ldots & 0\\
 &  & \vdots\\
 &  & 0\end{array}\right)$

$M_{j}$ is zero matrix with single one row and column $j+1$.

Observe $M_{j}^{H}=M_{j}$ (matrix is Hermitian) and $M_{j}^{H}M_{j}=M_{j}$
(because it's a projection matrix and $\left|j\right\rangle \left\langle j\mid j\right\rangle \left\langle j\right|=\left|j\right\rangle \left\langle j\right|$).

\[
p\left(j\right)=\left\Vert M_{j}\left|\psi\right\rangle \right\Vert ^{2}=\left\Vert \left|j\right\rangle \left\langle j\mid\psi\right\rangle \right\Vert ^{2}=\left|\left\langle j\mid\psi\right\rangle \right|^{2}\]


\[
M_{j}\left|\psi\right\rangle =\left|j\right\rangle \left\langle j\mid\psi\right\rangle =\left\langle j\mid\psi\right\rangle \left|j\right\rangle \]
\[
\left|\psi\right\rangle =\sum_{j}\left|j\right\rangle \left\langle j\mid\psi\right\rangle =\sum_{j}c_{j}\left|j\right\rangle \]
\[
\sum_{j=0}^{2^{n}-1}M_{j}^{H}M_{j}=\sum_{j}M_{j}=\sum_{j}=\left|j\right\rangle \left\langle j\right|=I\]


Example 2:

\begin{eqnarray*}
\left|\psi\right\rangle  & = & a\left|0\right\rangle +b\left|1\right\rangle \\
M_{1} & = & \left|+\right\rangle \left\langle +\right|\\
M_{2} & = & \left|-\right\rangle \left\langle -\right|\\
\left|+\right\rangle  & = & \frac{\left|0\right\rangle +\left|1\right\rangle }{\sqrt{2}}\\
\left|-\right\rangle  & = & \frac{\left|0\right\rangle -\left|1\right\rangle }{\sqrt{2}}\\
M_{j}^{H} & = & M_{j}\\
M_{j}^{H}M_{j} & = & M_{j}\end{eqnarray*}


Completeness relation

\[
\left|+\right\rangle \left\langle +\right|+\left|-\right\rangle \left\langle -\right|=\frac{1}{2}\left(\begin{array}{rr}
1 & 1\\
1 & 1\end{array}\right)+\frac{1}{2}\left(\begin{array}{rr}
1 & -1\\
-1 & 1\end{array}\right)=\left(\begin{array}{rr}
1 & 0\\
0 & 1\end{array}\right)\]


\[
M_{1}\left|\psi\right\rangle =\left|+\right\rangle \left\langle +\right|\left|\psi\right\rangle =\cdots=\left(\frac{a}{\sqrt{2}}+\frac{b}{\sqrt{2}}\right)\left|+\right\rangle \]


\[
M_{2}\left|\psi\right\rangle =\left|-\right\rangle \left\langle -\right|\left|\psi\right\rangle =\frac{1}{\sqrt{2}}\left(a-b\right)\left|-\right\rangle \]
\[
p\left(1\right)=\left\Vert M_{1}\left|\psi\right\rangle \right\Vert ^{2}=\frac{\left|a+b\right|^{2}}{2}\]
\[
p\left(2\right)=\left\Vert M_{2}\left|\psi\right\rangle \right\Vert ^{2}=\frac{\left|a-b\right|^{2}}{2}\]


Example 3

Measuring some qubits and not others. Say measuring $k$ qubits in
a system of $k+n$ qubits. Then $M_{j}=\left|j\right\rangle \left\langle j\right|\otimes I$
where $\left|j\right\rangle \left\langle j\right|$ is a size $2^{k}$matrix
and $I$ is size $2^{n}$.

Properties

$M_{j}^{H}=M_{j}$

Means matrix is Hermetian and therefore that it has real eigenvalues.
In other words it's observable because eigenvalues are what you observe.\[
M_{j}^{H}M_{j}=\left(\left|j\right\rangle \left\langle j\right|\otimes I\right)\left(\left|j\right\rangle \left\langle j\right|\otimes I\right)=\left|j\right\rangle \left\langle j\mid j\right\rangle \left\langle j\right|\otimes II=\left|j\right\rangle \left\langle j\right|\otimes I=M_{j}\]
\begin{eqnarray*}
M_{j}\left|\psi\right\rangle  & = & M_{j}\left|\psi_{1}\right\rangle \left|\psi_{2}\right\rangle \\
 & = & \left(\left|j\right\rangle \left\langle j\right|\otimes I\right)\left|\psi_{1}\right\rangle \left|\psi_{2}\right\rangle \\
 & = & \left|j\right\rangle \left\langle j\mid\psi_{1}\right\rangle \otimes I\left|\psi_{2}\right\rangle \\
 & = & \left\langle j\mid\psi_{1}\right\rangle \left(\left|j\right\rangle \left|\psi_{2}\right\rangle \right)\end{eqnarray*}
\begin{eqnarray*}
p\left(j\right) & = & \left\Vert M_{j}\left|\psi\right\rangle \right\Vert ^{2}\\
 & = & \left\Vert \left\langle j\mid\psi_{1}\right\rangle \left(\left|j\right\rangle \left|\psi_{2}\right\rangle \right)\right\Vert ^{2}\\
 & = & \left|\left\langle j\mid\psi_{1}\right\rangle \right|^{2}\left\Vert \left|j\right\rangle \left|\psi_{2}\right\rangle \right\Vert ^{2}\\
 & = & \left|\left\langle j\mid\psi_{1}\right\rangle \right|^{2}\end{eqnarray*}


Reason for last step is that $\left|j\right\rangle $ and $\left|\psi_{2}\right\rangle $
are both normal:

\begin{eqnarray*}
\left\Vert \left|j\right\rangle \left|\psi_{2}\right\rangle \right\Vert ^{2} & = & \left(\left|j\right\rangle \left|\psi_{2}\right\rangle \right)^{H}\left(\left|j\right\rangle \left|\psi_{2}\right\rangle \right)\\
 & = & \left(\left\langle j\right|\left\langle \psi_{2}\right|\right)\left(\left|j\right\rangle \left|\psi_{2}\right\rangle \right)\\
 & = & \left\langle j\mid j\right\rangle \left\langle \psi_{2}\mid\psi_{2}\right\rangle \\
 & = & 1\cdot1=1\end{eqnarray*}



\section*{Lecture 11 (21 February)}


\subsection*{Distinguishing states with certainty}

Can we distinguish between two states $\left|\psi_{1}\right\rangle $
and $\left|\psi_{2}\right\rangle $ with certainty (with probability
1)? (Similar proof page 87, box 2.3)

Assume it is possible, then there are measurement operators $M_{1},M_{2},\ldots,M_{k}$
so that \[
I=\sum_{j}M_{j}^{H}M_{j}\]
Given states $\left|\psi_{1}\right\rangle $ and $\left|\psi_{2}\right\rangle $,
then probabilities of outcomes $1$ and $2$ (respectively) should
be:\begin{eqnarray*}
p_{\psi_{1}}\left(1\right) & = & \left\langle \psi_{1}\right|M_{1}^{H}M_{1}\left|\psi_{1}\right\rangle =1\\
p_{\psi_{2}}\left(2\right) & = & \left\langle \psi_{2}\right|M_{2}^{H}M_{2}\left|\psi_{2}\right\rangle =1\end{eqnarray*}
This implies that $M_{1}\left|\psi_{1}\right\rangle $ and $M_{1}\left|\psi_{2}\right\rangle $
are unit vectors. Using the completeness equation, it also implies
$M_{1}\left|\psi_{2}\right\rangle =0$ and $M_{2}\left|\psi_{1}\right\rangle =0$.

(Completeness equation \[
M_{1}^{H}M_{1}+M_{2}^{H}M_{2}=I\]


leads to \[
1=\left\langle \psi_{1}\right|I\left|\psi_{1}\right\rangle =\left\langle \psi_{1}\right|M_{1}^{H}M_{1}\left|\psi_{1}\right\rangle +\left\langle \psi_{1}\right|M_{2}^{H}M_{2}\left|\psi_{1}\right\rangle \]
\[
1=\left\langle \psi_{2}\right|I\left|\psi_{2}\right\rangle =\left\langle \psi_{2}\right|M_{1}^{H}M_{1}\left|\psi_{2}\right\rangle +\left\langle \psi_{2}\right|M_{2}^{H}M_{2}\left|\psi_{2}\right\rangle \]
 and because$\left\langle \psi_{1}\right|M_{2}^{H}M_{2}\left|\psi_{1}\right\rangle =1$
and $\left\langle \psi_{2}\right|M_{2}^{H}M_{2}\left|\psi_{2}\right\rangle =1$
the other terms must be 0.)

State$\left|\psi_{1}\right\rangle $ can be written in using $\left|\psi_{2}\right\rangle $
and another vector $\left|Z\right\rangle $ as a basis, where$\left\Vert \left|Z\right\rangle \right\Vert =1$,
$\left|Z\right\rangle \perp\left|\psi_{2}\right\rangle $:

\[
\left|\psi_{1}\right\rangle =\alpha\left|\psi_{2}\right\rangle +\beta\left|Z\right\rangle \]
\[
M_{1}\left|\psi_{1}\right\rangle =\alpha M_{1}\left|\psi_{2}\right\rangle +\beta M_{1}\left|Z\right\rangle \]


Assume $\left|\psi_{1}\right\rangle $ and $\left|\psi_{2}\right\rangle $
are not orthogonal, then $\left\langle \psi_{1}\mid\psi_{2}\right\rangle \neq0$
and$\alpha\neq$0, so $\left|\beta\right|<1$. Then below, you have
a contradiction, proving they must be orthogonal.\[
1=\left\Vert M_{1}\left|\psi_{1}\right\rangle \right\Vert ^{2}=\left|\beta\right|^{2}\left\Vert M_{1}\left|Z\right\rangle \right\Vert ^{2}\leq\left|\beta\right|^{2}<1\]
Note that $\left\Vert M_{1}\left|Z\right\rangle \right\Vert ^{2}$just
means $\left\langle Z\right|M_{1}^{H}M_{1}\left|Z\right\rangle $.


\subsection*{Some Properties of Operators and Completeness}

Given:\[
\left|\psi_{1}\right\rangle \perp\left|\psi_{2}\right\rangle \]
\[
M_{1}=\left|\psi_{1}\right\rangle \left\langle \psi_{1}\right|\]
\[
M_{2}=\left|\psi_{2}\right\rangle \left\langle \psi_{2}\right|\]
$M_{1}$and $M_{2}$ are symmetric non-negative definate, which means
that for all $\left|x\right\rangle $, $\left\langle x\right|M\left|x\right\rangle \geq0$.
This can be verified as follows:\[
\left\langle x\right|M\left|x\right\rangle =\left\langle x\right|M^{H}M\left|x\right\rangle =\left\Vert M\left|x\right\rangle \right\Vert ^{2}\geq0\]


Symmetric non-negative definate matrices have non-negative eigenvalues.

Define:

\[
M=I-M_{1}-M_{2}\]


Observe it's symmetric. This means eigenvalues are real. Check that
it is positive semi-definite, that for all $\left|\psi\right\rangle $,\[
\left\langle \psi\right|M\left|\psi\right\rangle =\left\langle \psi\mid\psi\right\rangle -\left\langle \psi\right|M_{1}\left|\psi\right\rangle -\left\langle \psi\right|M_{2}\left|\psi\right\rangle \geq0\]
\[
M_{1}\left|\psi\right\rangle =\left|\psi_{1}\right\rangle \left\langle \psi_{1}\mid\psi\right\rangle \]
\[
M_{2}\left|\psi\right\rangle =\left|\psi_{2}\right\rangle \left\langle \psi_{2}\mid\psi\right\rangle \]
\[
\left\langle \psi\right|M_{1}\left|\psi\right\rangle =\left|\left\langle \psi_{1}\mid\psi\right\rangle \right|^{2}\]
\[
\left\langle \psi\right|M_{2}\left|\psi\right\rangle =\left|\left\langle \psi_{2}\mid\psi\right\rangle \right|^{2}\]
\[
\left\langle \psi\right|M\left|\psi\right\rangle =1-\left|\left\langle \psi_{1}\mid\psi\right\rangle \right|^{2}-\left|\left\langle \psi_{2}\mid\psi\right\rangle \right|^{2}\overset{?}{=}0\]


Need to find prove that above is $\geq0$. $\left|\psi\right\rangle $
can be expressed as

\[
\left|\psi\right\rangle =\left|\psi_{1}\right\rangle \left\langle \psi_{1}\mid\psi\right\rangle +\left|\psi_{2}\right\rangle \left\langle \psi_{2}\mid\psi\right\rangle +\left|z\right\rangle \]
For some $\left|z\right\rangle \perp\left|\psi_{1}\right\rangle ,\left|\psi_{2}\right\rangle $.
Taking inner product with $\left|\psi\right\rangle $ gives: \[
1=\left\langle \psi\mid\psi\right\rangle =\left|\left\langle \psi_{1}\mid\psi\right\rangle \right|^{2}+\left|\left\langle \psi_{2}\mid\psi\right\rangle \right|^{2}+\left\Vert \left|z\right\rangle \right\Vert ^{2}\geq0\]
Rearranging,\[
1-\left|\left\langle \psi_{1}\mid\psi\right\rangle \right|^{2}-\left|\left\langle \psi_{2}\mid\psi\right\rangle \right|^{2}=\left\Vert \left|z\right\rangle \right\Vert ^{2}=\left\langle \psi\right|M\left|\psi\right\rangle \geq0\]


Which tells us $M$ is symmetric non-negative definite. This means
we can do spectral decomposition:\begin{eqnarray*}
M & = & V\left(\begin{array}{cccc}
\lambda_{1} & 0 & 0 & 0\\
0 & \lambda_{2} & 0 & 0\\
0 & 0 & \ddots & 0\\
0 & 0 & 0 & \lambda_{4}\end{array}\right)V^{H}\\
 & = & V\left(\begin{array}{cccc}
\sqrt{\lambda_{1}} & 0 & 0 & 0\\
0 & \sqrt{\lambda_{2}} & 0 & 0\\
0 & 0 & \ddots & 0\\
0 & 0 & 0 & \sqrt{\lambda_{4}}\end{array}\right)V^{H}V\left(\begin{array}{cccc}
\sqrt{\lambda_{1}} & 0 & 0 & 0\\
0 & \sqrt{\lambda_{2}} & 0 & 0\\
0 & 0 & \ddots & 0\\
0 & 0 & 0 & \sqrt{\lambda_{4}}\end{array}\right)V^{H}\end{eqnarray*}
since $V^{H}V=I$. Now, define $M_{3}=\sqrt{M}$

Results of measuring state $\left|\psi_{1}\right\rangle $:

\begin{tabular}{|c|c|}
\hline 
Outcome&
Probability\tabularnewline
\hline
\hline 
1&
$p_{\psi_{1}}\left(1\right)=1=\left\langle \psi_{1}\right|M_{1}\left|\psi_{1}\right\rangle $\tabularnewline
\hline 
2&
$p_{\psi_{1}}\left(2\right)=0=\left\langle \psi_{1}\right|M_{2}\left|\psi_{1}\right\rangle $\tabularnewline
\hline 
3&
$p_{\psi_{1}}\left(3\right)=0$ (see below)\tabularnewline
\hline
\end{tabular}

\begin{eqnarray*}
p_{\psi_{1}}\left(3\right)=0 & = & \left\langle \psi_{1}\right|M_{3}^{H}M_{3}\left|\psi_{1}\right\rangle \\
 & = & \left\langle \psi_{1}\right|\left(I-M_{1}-M_{2}\right)\left|\psi_{1}\right\rangle \\
 & = & \left\langle \psi_{1}\mid\psi_{1}\right\rangle -\left\langle \psi_{1}\right|M_{1}\left|\psi_{1}\right\rangle -\left\langle \psi_{1}\right|M_{2}\left|\psi_{1}\right\rangle \\
 & = & 1-1-0\end{eqnarray*}


For $\left|\psi_{2}\right\rangle $

\begin{tabular}{|c|c|}
\hline 
Outcome&
Probability\tabularnewline
\hline
\hline 
1&
$p_{\psi_{2}}\left(1\right)=0$\tabularnewline
\hline 
2&
$p_{\psi_{2}}\left(2\right)=1$\tabularnewline
\hline 
3&
$p_{\psi_{2}}\left(3\right)=0$\tabularnewline
\hline
\end{tabular}

(Review of matrix types:

Normal - $A^{H}A=AA^{H}$, matrix commutes with it's transpose 

Unitary - $A^{H}A=I$ or $A^{H}=A^{-1}$, type of normal matrix, eigenvalues
all have absolute value of 1.

Hermetian - $A=A^{H}$, type of normal matrix, eigenvalues are real

Positive Definite - hermitian and $x^{H}Ax>0$ for all $x$. (if not
hermetian, some values of $x^{H}Ax$ would be complex)

Projection matrix - hermetian and $A^{2}=A$, is positive semi-definite,
eigenvalues are all 0 or all 1)


\subsection*{EPR States / Bell States}

(page 25)

\[
\textrm{Circuit:}\left(I\otimes X^{\#1}\right)\left(H\otimes I\right)\]
\[
\left|0\right\rangle \left|0\right\rangle ^{\underrightarrow{\left(H\otimes I\right)}}\frac{\left|00\right\rangle +\left|10\right\rangle }{\sqrt{2}}{}^{\underrightarrow{\left(I\otimes X^{\#1}\right)}}\frac{\left|00\right\rangle +\left|11\right\rangle }{\sqrt{2}}=\left|\beta_{00}\right\rangle \]


\[
\left|i\right\rangle \left|j\right\rangle ^{\underrightarrow{\left(H\otimes I\right)}}\frac{\left|0\right\rangle +\left(-1\right)^{i}\left|1\right\rangle }{\sqrt{2}}\left|j\right\rangle {}^{\underrightarrow{\left(I\otimes X^{\#1}\right)}}\frac{\left|0j\right\rangle +\left(-1\right)^{i}\left|1\bar{j}\right\rangle }{\sqrt{2}}=\left|\beta_{ij}\right\rangle \]


\begin{eqnarray*}
\left|\beta_{00}\right\rangle  & = & \frac{\left|00\right\rangle +\left|11\right\rangle }{\sqrt{2}}\\
\left|\beta_{01}\right\rangle  & = & \frac{\left|01\right\rangle +\left|10\right\rangle }{\sqrt{2}}\\
\left|\beta_{10}\right\rangle  & = & \frac{\left|00\right\rangle -\left|11\right\rangle }{\sqrt{2}}\\
\left|\beta_{11}\right\rangle  & = & \frac{\left|01\right\rangle -\left|10\right\rangle }{\sqrt{2}}\end{eqnarray*}
Property 1: if you measure first qubit, you know second qubit.

Property 2: Bell states are entangled, and therefore can't be written
as the product of two entangled qubits.\[
\left(a_{1}\left|0\right\rangle +b_{1}\left|1\right\rangle \right)\left(a_{2}\left|0\right\rangle +b_{2}\left|1\right\rangle \right)\]
\[
a_{1}a_{2}\left|00\right\rangle +a_{1}b_{2}\left|01\right\rangle +b_{1}a_{2}\left|10\right\rangle +b_{1}b_{2}\left|11\right\rangle \]


There are no values of $a_{1}$ , $b_{1}$, $a_{2}$, $b_{2}$ that
can give one of the bell states.

Property 3: Bell states are pairwise orthogonal. Proof: \begin{eqnarray*}
\left\langle \beta_{i_{1}j_{1}}\mid\beta_{i_{2}j_{1}}\right\rangle  & = & \left(\frac{\left\langle 0j_{1}\right|+\left(-1\right)^{i_{1}}\left\langle 1\bar{j_{1}}\right|}{\sqrt{2}}\right)\left(\frac{\left|0j_{2}\right\rangle +\left(-1\right)^{i_{2}}\left|1\bar{j_{2}}\right\rangle }{\sqrt{2}}\right)\\
 & = & \frac{1}{2}\left(\left\langle 0j_{1}\mid0j_{2}\right\rangle +0+0+\left(-1\right)^{i_{1}+i_{2}}\left\langle 1\bar{j_{1}}\mid1\bar{j_{2}}\right\rangle \right)\\
 & = & \frac{1}{2}\left(\left\langle j_{1}\mid j_{2}\right\rangle +\left(-1\right)^{i_{1}+i_{2}}\left\langle \bar{j_{1}}\mid\bar{j_{2}}\right\rangle \right)\end{eqnarray*}


Case 1: $j_{1}\neq j_{2}$ then $\left\langle \beta_{i_{1}j_{1}}\mid\beta_{i_{2}j_{1}}\right\rangle =0$

Case 2: $j_{1}=j_{2}$

Case 2.1: $i_{1}\neq i_{2}$ then $\left\langle \beta_{i_{1}j_{1}}\mid\beta_{i_{2}j_{1}}\right\rangle =0$
(because exponent $i_{1}+i_{2}$ is odd)

Case 2.2: $i_{1}=i_{2}$ then $\left\langle \beta_{i_{1}j_{1}}\mid\beta_{i_{2}j_{1}}\right\rangle =1$

So inner product is zero unless $i_{1}=i_{2}$ and $j_{1}=j_{2}$.

\[
\left\langle \beta_{i_{1}j_{1}}\mid\beta_{i_{2}j_{1}}\right\rangle =\left(\frac{\left\langle 0j_{2}\right|+\left(-1\right)^{i_{2}}\left\langle 1\bar{j_{2}}\right|}{\sqrt{2}}\right)\left(\frac{\left|0j_{2}\right\rangle +\left(-1\right)^{i_{2}}\left|1\bar{j_{2}}\right\rangle }{\sqrt{2}}\right)\]



\subsection*{Quantum Teleportation}

{[}Book 1.3.7 p27]

\[
\textrm{Circuit:}\left(I\otimes I\otimes Z^{M\#1}X^{M\#2}\right)\left(H\otimes I\otimes I\right)\left(I\otimes X^{\#1}\otimes I\right)\left|\psi\right\rangle \left|\beta_{00}\right\rangle \]


\begin{eqnarray*}
\left|\psi\right\rangle \left|\beta_{00}\right\rangle  & = & \left|\psi\right\rangle \frac{\left|00\right\rangle +\left|11\right\rangle }{\sqrt{2}}\\
 & ^{\underrightarrow{\left(I\otimes X^{\#1}\otimes I\right)}} & a\left|0\right\rangle \frac{\left|00\right\rangle +\left|11\right\rangle }{\sqrt{2}}+b\left|1\right\rangle \frac{\left|10\right\rangle +\left|01\right\rangle }{\sqrt{2}}\\
 & ^{\underrightarrow{\left(H\otimes I\otimes I\right)}} & \frac{a}{2}\left(\left|0\right\rangle +\left|1\right\rangle \right)\left(\left|00\right\rangle +\left|11\right\rangle \right)+\frac{b}{2}\left(\left|0\right\rangle -\left|1\right\rangle \right)\left(\left|10\right\rangle +\left|01\right\rangle \right)\\
 & = & \frac{1}{2}\left|00\right\rangle \left(a\left|0\right\rangle +b\left|1\right\rangle \right)+\frac{1}{2}\left|01\right\rangle \left(a\left|1\right\rangle +b\left|0\right\rangle \right)\\
 &  & +\frac{1}{2}\left|10\right\rangle \left(a\left|0\right\rangle -b\left|1\right\rangle \right)+\frac{1}{2}\left|11\right\rangle \left(a\left|1\right\rangle -b\left|0\right\rangle \right)\\
 & = & \frac{1}{2}\left(\left|00\right\rangle \left|\psi\right\rangle +\left|01\right\rangle X\left|\psi\right\rangle +\left|10\right\rangle Z\left|\psi\right\rangle +\left|10\right\rangle XZ\left|\psi\right\rangle \right)\end{eqnarray*}


By measuring first two qubits, you can know what $X$ and $Z$ filters
to apply the third qubit in to make it equivalent original input value
$\left|\psi\right\rangle $. This means that if you have two entangled
qubits (of the bell state $\beta_{00}$) in seperate locations, you
can use them to transmit an arbitrary qubit over a classical channel.


\section*{Lecture 12 (26 February)}


\subsection*{Lecture 11 Review}

EPR States: $\beta_{ij}=\left|0j\right\rangle +-\left(-1\right)^{i}1\left|1\bar{j}\right\rangle $


\subsection*{Superdense Coding}

{[}Book 2.3, p97]

Just like in teleportation, Alice and Bob each have 1 qubit of a 2-qubit
entangled state, $\beta_{00}$. Alice wants to send 2 classical bits
of information by sending Bob a single quantum bit. She can do this
by sending Bob her half of the entangled qubit after she applies one
of four operations to it, depending on the classical bits she wants
to send. The operations are shown below, and result in Bell states
which Bob can distinguish to determine the original classical bits.

\begin{tabular}{|c|c|}
\hline 
Bits&
Qubit\tabularnewline
\hline
\hline 
00&
$\left|\beta_{00}\right\rangle =\frac{\left|00\right\rangle +\left|11\right\rangle }{\sqrt{2}}\underrightarrow{I\otimes I}\frac{\left|00\right\rangle +\left|11\right\rangle }{\sqrt{2}}=\left|\beta_{00}\right\rangle $\tabularnewline
\hline 
01&
$\left|\beta_{00}\right\rangle =\frac{\left|00\right\rangle +\left|11\right\rangle }{\sqrt{2}}\underrightarrow{Z\otimes I}\frac{\left|00\right\rangle -\left|11\right\rangle }{\sqrt{2}}=\left|\beta_{10}\right\rangle $\tabularnewline
\hline 
10&
$\left|\beta_{00}\right\rangle =\frac{\left|00\right\rangle +\left|11\right\rangle }{\sqrt{2}}\underrightarrow{X\otimes I}\frac{\left|10\right\rangle +\left|01\right\rangle }{\sqrt{2}}=\left|\beta_{01}\right\rangle $\tabularnewline
\hline 
11&
$\left|\beta_{00}\right\rangle =\frac{\left|00\right\rangle +\left|11\right\rangle }{\sqrt{2}}\underrightarrow{iY\otimes I}\frac{\left|01\right\rangle -\left|10\right\rangle }{\sqrt{2}}=\left|\beta_{11}\right\rangle $\tabularnewline
\hline
\end{tabular}


\subsection*{Quantum Queries}

Mechanism to insert data into a quantum computer.

Assume you have a boolean function $f=\left\{ 0,1\right\} \rightarrow\left\{ 0,1\right\} $,
then this is a corresponding unitary operation $U_{f}$ which is defined
on the basis states as: $U_{f}\left|i\right\rangle \left|j\right\rangle =\left|i\right\rangle \left|j\oplus f\left(i\right)\right\rangle $.

Proving $U_{f}$ is unitary:

$\left|i\right\rangle \left|j\right\rangle \underrightarrow{U_{f}}\left|i\right\rangle \left|j\oplus f\left(i\right)\right\rangle \underrightarrow{U_{f}}\left|i\right\rangle \left|j\oplus f\left(i\right)\oplus f\left(i\right)\right\rangle =\left|i\right\rangle \left|j\right\rangle $ 

$\left(U_{f}\right)^{2}=I$ therefore $U_{f}=U_{f}^{-1}$and $U_{f}$
is unitary.


\subsubsection*{Quantum Parallelism}

Inputing a superposition state to $U_{f}$ computes a result of multiple
inputs to the function $f$ in just a single operation.

\[
\textrm{Circuit: }U_{f}\left(H\otimes I\right)\left|0\right\rangle \left|0\right\rangle \]


\begin{eqnarray*}
\left|00\right\rangle  & \underrightarrow{H\otimes I} & \frac{\left|0\right\rangle +\left|1\right\rangle }{\sqrt{2}}\left|0\right\rangle \\
 & \underrightarrow{U_{f}} & \frac{\left|0\right\rangle }{\sqrt{2}}\left|0\oplus f\left(0\right)\right\rangle +\frac{\left|1\right\rangle }{\sqrt{2}}\left|0\oplus f\left(1\right)\right\rangle \\
 & = & \frac{\left|0f\left(0\right)\right\rangle +\left|1f\left(1\right)\right\rangle }{\sqrt{2}}\end{eqnarray*}


Single output state contains both values of function $f$.


\subsection*{General Quantum Queries}

Assume you have a boolean function $f=\left\{ 0,\ldots,2^{n}-1\right\} \rightarrow\left\{ 0,1\right\} $,
then there is a corresponding unitary operation $U_{f}$ which is
defined on the basis states as: $U_{f}\left|i\right\rangle \left|j\right\rangle =\left|i\right\rangle \left|j\oplus f\left(i\right)\right\rangle $.

\[
\textrm{Circuit: }U_{f}\left(H^{\otimes n}\otimes I\right)\left|0\right\rangle ^{\otimes n}\left|0\right\rangle \]


\begin{eqnarray*}
\left|0\ldots0\right\rangle \left|0\right\rangle  & \underrightarrow{H^{\otimes n}\otimes I} & H^{\otimes n}\left|0\ldots0\right\rangle \left|0\right\rangle \\
 & = & \left(H\left|0\right\rangle \otimes\cdots\otimes H\left|0\right\rangle \right)\left|0\right\rangle \\
 & = & \frac{1}{2^{n/2}}\sum_{j=0}^{2^{n}-1}\left|j\right\rangle \left|0\right\rangle \\
 & \underrightarrow{U_{f}} & \frac{1}{2^{n/2}}\sum_{j=0}^{2^{n}-1}\left|j\right\rangle \left|f\left(j\right)\right\rangle \end{eqnarray*}


Quantum parallelism is not enough to exploit power of quantum computing,
because even though the final state is a combination of all possible
outputs of the function $f$, when measurement occurs it will only
give a single, random output. Need to find ways to combine the values
to be able to efficiently measure some global property of the function.


\subsubsection*{Matrix Representation of $U_{f}$}

When $f$ is boolean function of 1 bit:

$U_{f}=\left(\begin{array}{cc}
X^{f\left(0\right)}\\
 & X^{f\left(1\right)}\end{array}\right)$

$U_{f}\left|i\right\rangle \left|j\right\rangle =\left|i\right\rangle \left|j\oplus f\left(i\right)\right\rangle $

Case $i=0$, $f\left(0\right)=0$, $\left|0j\right\rangle \rightarrow\left|0j\right\rangle $

Case $i=0$, $f\left(0\right)=1$, $\left|0j\right\rangle \rightarrow\left|0\bar{j}\right\rangle $

Case $i=1$, $f\left(1\right)=0$, $\left|1j\right\rangle \rightarrow\left|1j\right\rangle $

Case $i=1$, $f\left(1\right)=1$, $\left|1j\right\rangle \rightarrow\left|1\bar{j}\right\rangle $

When $f$ is boolean function of $m$ bits:

$U_{f}=\left(\begin{array}{cccc}
X^{f\left(0\right)}\\
 & X^{f\left(1\right)}\\
 &  & \ddots\\
 &  &  & X^{f\left(2^{m}-1\right)}\end{array}\right)$

When $f$ is function of $m$ bits returning $n$ bits:

$f=\left\{ 0,\ldots,2^{m}-1\right\} \rightarrow\left\{ 0,\ldots,2^{n}-1\right\} $

$U_{f}\left|i_{1}\ldots i_{n}\right\rangle \left|j_{1}\ldots j_{n}\right\rangle =U_{f}\left|i\right\rangle \left|j\right\rangle =\left|i\right\rangle \left|j\oplus f\left(i\right)\right\rangle $

where $\oplus$ is addition mod $n$. $U_{f}$ is a permutation matrix
(which makes it unitary) with a single 1 in each column. 

$U_{f}$ is made up of shifting matrixes, which work like: $A_{p}\left|j\right\rangle =\left|p\oplus j\right\rangle $
for $j,p=0,\ldots,2^{n}-1$

$A_{p}=\left(\begin{array}{cccccccc}
 &  &  &  & 1\\
 &  &  &  &  & 1\\
 &  &  &  &  &  & 1\\
 &  &  &  &  &  &  & 1\\
1\\
 & 1\\
 &  & 1\\
 &  &  & 1\end{array}\right)$

Matrix $A_{p}$ has 1 in first column at position $p+1$, then one
row down in each column after that. Some special cases of shifting
matrices are $A_{0}=I$ and when $n=1$, $A_{1}=X$. But, back to
$U_{f}:$

$U_{f}\left|i\right\rangle \left|j\right\rangle =\left|i\right\rangle \left|j\oplus f\left(i\right)\right\rangle =\left|i\right\rangle A_{f\left(i\right)}\left|j\right\rangle =\left(I\otimes A_{f\left(i\right)}\right)U_{f}\left|i\right\rangle \left|j\right\rangle $

$U_{f}=\left(\begin{array}{cccc}
A_{f\left(0\right)}\\
 & A_{f\left(1\right)}\\
 &  & \ddots\\
 &  &  & A_{f\left(2^{m}-1\right)}\end{array}\right)$


\section*{Lecture 13 (28 February)}


\subsection*{Lecture 12 Review}

$U_{f}\left|i\right\rangle \left|j\right\rangle =\left|i\right\rangle \left|j\oplus f\left(i\right)\right\rangle $

Homework Hint: When $U_{f}^{2}\neq I$

\begin{eqnarray*}
U_{f}U_{f}\left|i\right\rangle \left|j\right\rangle  & = & U_{f}\left|i\right\rangle \left|j\oplus f\left(i\right)\right\rangle \\
 & = & \left|i\right\rangle \left|j\oplus f\left(i\right)\oplus f\left(i\right)\right\rangle \\
 & = & \left|i\right\rangle \left|j\oplus2f\left(i\right)\right\rangle \end{eqnarray*}



\subsection*{Deutsch's Algorithm}

Given $f:\left\{ 0,1\right\} \rightarrow\left\{ 0,1\right\} $ compute
$f\left(0\right)\oplus f\left(1\right)$

\[
\textrm{Circuit: }\left[M\otimes I\right]\left(H\otimes I\right)U_{f}\left(H\otimes H\right)\left|0\right\rangle \left|1\right\rangle \]


\begin{eqnarray*}
\left|0\right\rangle \left|1\right\rangle  & \underrightarrow{H\otimes H} & \left(\frac{\left|0\right\rangle +\left|1\right\rangle }{\sqrt{2}}\right)\left(\frac{\left|0\right\rangle -\left|1\right\rangle }{\sqrt{2}}\right)\\
 & = & \frac{1}{2}\left(\left|00\right\rangle -\left|01\right\rangle +\left|10\right\rangle -\left|11\right\rangle \right)\\
 & \underrightarrow{U_{f}} & \frac{1}{2}\left(\left|0f\left(0\right)\right\rangle -\left|0\overline{f\left(0\right)}\right\rangle +\left|1f\left(1\right)\right\rangle -\left|1\overline{f\left(1\right)}\right\rangle \right)\\
 & = & \frac{1}{2}\left(\left|0\right\rangle \left(\left|f\left(0\right)\right\rangle -\left|\overline{f\left(0\right)}\right\rangle \right)+\left|1\right\rangle \left(\left|f\left(1\right)\right\rangle -\left|\overline{f\left(1\right)}\right\rangle \right)\right)\end{eqnarray*}


Case $f\left(0\right)=0$, $\left|f\left(0\right)\right\rangle -\left|\overline{f\left(0\right)}\right\rangle =\left|0\right\rangle -\left|1\right\rangle $

Case $f\left(0\right)=1$, $\left|f\left(0\right)\right\rangle -\left|\overline{f\left(0\right)}\right\rangle =\left|1\right\rangle -\left|0\right\rangle $

Therefore $\left|f\left(0\right)\right\rangle -\left|\overline{f\left(0\right)}\right\rangle =\left(-1\right)^{f\left(0\right)}\left(\left|0\right\rangle -\left|1\right\rangle \right)$

Continuing\ldots{}

\begin{eqnarray*}
 & = & \frac{1}{2}\left(\left(-1\right)^{f\left(0\right)}\left|0\right\rangle \left(\left|0\right\rangle -\left|1\right\rangle \right)+\left(-1\right)^{f\left(1\right)}\left|1\right\rangle \left(\left|0\right\rangle -\left|1\right\rangle \right)\right)\\
 & = & \frac{1}{\sqrt{2}}\left(\left(-1\right)^{f\left(0\right)}\left|0\right\rangle +\left(-1\right)^{f\left(1\right)}\left|1\right\rangle \right)\frac{\left|0\right\rangle -\left|1\right\rangle }{\sqrt{2}}\\
 & = & \frac{1}{\sqrt{2}}\left(-1\right)^{f\left(0\right)}\left(\left|0\right\rangle +\left(-1\right)^{f\left(1\right)-f\left(0\right)}\left|1\right\rangle \right)\frac{\left|0\right\rangle -\left|1\right\rangle }{\sqrt{2}}\end{eqnarray*}


Case $f\left(0\right)=f\left(1\right)$, then $\left(\left|0\right\rangle +\left(-1\right)^{f\left(1\right)-f\left(0\right)}\left|1\right\rangle \right)=\left|0\right\rangle +\left|1\right\rangle $

Case $f\left(0\right)\neq f\left(1\right)$, then $\left(\left|0\right\rangle +\left(-1\right)^{f\left(1\right)-f\left(0\right)}\left|1\right\rangle \right)=\left|0\right\rangle -\left|1\right\rangle $

Continuing\ldots{}

\begin{eqnarray*}
 & \underrightarrow{H\otimes I} & \left\{ \begin{array}{cc}
\left(-1\right)^{f\left(0\right)}\left|0\right\rangle \frac{\left|0\right\rangle -\left|1\right\rangle }{\sqrt{2}} & \textrm{ if }f\left(0\right)=f\left(1\right)\\
\left(-1\right)^{f\left(0\right)}\left|1\right\rangle \frac{\left|0\right\rangle -\left|1\right\rangle }{\sqrt{2}} & \textrm{ if }f\left(0\right)\neq f\left(1\right)\end{array}\right.\\
 & = & \pm\left|f\left(0\right)\oplus f\left(1\right)\right\rangle \frac{\left|0\right\rangle -\left|1\right\rangle }{\sqrt{2}}\end{eqnarray*}



\subsection*{Deutsch-Jonsa Algorithm}

Given $f:\left\{ 0,\ldots,2^{n}-1\right\} \rightarrow\left\{ 0,1\right\} $ 

where function $f$ is either balanced or constant. Constant means
$f\left(j\right)=f\left(0\right)\forall j$. Balanced means if $A_{o}=\left\{ j:f\left(j\right)=0\right\} $
and $A_{1}=\left\{ j:f\left(j\right)=1\right\} $, then $\left|A_{0}\right|=\left|A_{1}\right|=2^{n-1}$.
The algorithm determines whether a function is constant or balanced,
assuming it won't be any thing else.


\subsubsection*{Classical Solution}

Requires $2^{n-1}+1$ evaluations worst case. Algorithm is to loop
through the inputs, checking to see if the function ever returns two
different values. If it does return two different values, the function
is not constant and the loop can be terminated. After the halfway
point, if only one value has been returned, the function is not balanced
and can be labeled constant.


\subsubsection*{Quantum Solution}

\[
\textrm{Circuit: }\left[M\otimes I\right]\left(H\otimes I\right)U_{f}\left(H^{\otimes n}\otimes H\right)\left|0\right\rangle ^{\otimes n}\left|1\right\rangle \]


\begin{eqnarray*}
\left|0\right\rangle ^{\otimes n}\left|1\right\rangle  & \underrightarrow{H^{\otimes n}\otimes H} & \left(\frac{1}{2^{n/2}}\sum_{j=0}^{2^{n}-1}\left|j\right\rangle \right)\left(\frac{\left|0\right\rangle -\left|1\right\rangle }{\sqrt{2}}\right)\\
 & = & \frac{1}{2^{n/2}}\sum_{j=0}^{2^{n}-1}\left(\frac{\left|j0\right\rangle -\left|j1\right\rangle }{\sqrt{2}}\right)\\
 & \underrightarrow{U_{f}} & \frac{1}{2^{n/2}}\sum_{j=0}^{2^{n}-1}\left(\frac{\left|jf\left(j\right)\right\rangle -\left|j\overline{f\left(j\right)}\right\rangle }{\sqrt{2}}\right)\\
 & = & \frac{1}{2^{n/2}}\sum_{j=0}^{2^{n}-1}\left|j\right\rangle \left(\frac{\left|f\left(j\right)\right\rangle -\left|\overline{f\left(j\right)}\right\rangle }{\sqrt{2}}\right)\\
 & = & \frac{1}{2^{n/2}}\sum_{j=0}^{2^{n}-1}\left|j\right\rangle \left(-1\right)^{f\left(j\right)}\left(\frac{\left|0\right\rangle -\left|1\right\rangle }{\sqrt{2}}\right)\\
 & \underrightarrow{H^{\otimes n}\otimes I} & \frac{1}{2^{n/2}}\sum_{j=0}^{2^{n}-1}\left(\frac{1}{2^{n/2}}\sum_{k=0}^{2^{n}-1}\left(-1\right)^{j\cdot k}\left|k\right\rangle \right)\left(-1\right)^{f\left(j\right)}\left(\frac{\left|0\right\rangle -\left|1\right\rangle }{\sqrt{2}}\right)\\
 & = & \sum_{k}a_{k}\left|k\right\rangle \left(\frac{\left|0\right\rangle -\left|1\right\rangle }{\sqrt{2}}\right)\end{eqnarray*}


Setting $a_{k}=\frac{1}{2^{n}}\sum_{j}\left(-1\right)^{j\cdot k}\left(-1\right)^{f\left(j\right)}$
to represent the {}``amplitude'' of each $k$.

Looking at $a_{0}=\frac{1}{2^{n}}\sum_{j}\left(-1\right)^{f\left(j\right)}$:

If function $f$ is constant then $a_{0}=\pm1$ which means $a_{k}=0$
for all $k\neq0$. This is because of completeness, if coefficient
of one basis state 1, all others must be zero. If function $f$ is
balanced then $a_{0}=0.$ 

Homework: What do we need to do to detect 3/4 balanced instead of
1/2 balanced.


\subsubsection*{Randomized Classical Algorithm}

Generate $k$ random input to function $f$, if function evaluated
at any two of the inputs is different, the function will be labeled
balanced, otherwise it's considered constant. Algorithm can fail,
outputting constant when the function is actually balanced.

$A_{0}=\left\{ j:f\left(j\right)=0\right\} $, $A_{1}=\left\{ j:f\left(j\right)=1\right\} $

Balanced when $\left|A_{0}\right|=\left|A_{1}\right|$

Probability of picking 1 sample which is 0: $p\left(1,0\right)=\frac{1}{2}$

Probability of picking $k$ samples which are 0: $p\left(k,0\right)=\frac{1}{2^{k}}$

Probability of picking 1 sample which is 1: $p\left(1,1\right)=\frac{1}{2}$

Probability of picking $k$ samples which are 1: $p\left(k,1\right)=\frac{1}{2^{k}}$

Probability of failure given $f$ is balanced: $p\left(k,0\right)+p\left(k,1\right)=\frac{2}{2^{k}}$

Set $p>\frac{2}{2^{k}}$ to succeed with arbitrary probability.


\section*{Lectures 14/15 (5/7 March)}


\subsection*{Midterm and Midterm Review}


\section*{Lecture 16 (19 March)}

{[}Book Chapter 5]


\subsection*{Discrete Fourier Transform}

Maps vectors $x_{0},\ldots,x_{N-1}\rightarrow y_{0},\ldots,y_{N-1}$
like:\[
y_{k}=\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}x_{j}e^{2\pi ikj/N}\]
Cost $O\left(N^{2}\right)$

1965 -- Cooley-Tukey Fast Fourier Transform (FFT) cost $O\left(N\log N\right)$


\subsection*{Quantum Fourier Transform}

Input state $\left|j\right\rangle $ for $j=0,\ldots,N-1$ where $N=2^{n}$
($N$ is power of 2): \[
F\left|j\right\rangle =\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}e^{2\pi ijk/N}\left|k\right\rangle \]



\subsubsection*{Equivalence to Discrete Transform}

\begin{eqnarray*}
F\left(\sum_{j=0}^{N-1}x_{j}\left|j\right\rangle \right) & = & \sum_{j=0}^{N-1}x_{j}F\left|j\right\rangle \\
 & = & \sum_{j=0}^{N-1}x_{j}\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}e^{2\pi ijk/N}\left|k\right\rangle \\
 & = & \sum_{k=0}^{N-1}\left(\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}x_{j}e^{2\pi ijk/N}\right)\left|k\right\rangle \end{eqnarray*}



\subsubsection*{Applied to $\left|0\right\rangle $\[
F\left|0\right\rangle =\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}e^{2\pi i0k/N}\left|k\right\rangle =\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\left|k\right\rangle =H^{\bigotimes n}\left|0\right\rangle ^{\bigotimes n}\]
}


\subsubsection*{Matrix representation}

$F\left|j\right\rangle =\frac{1}{\sqrt{N}}\left(\begin{array}{c}
\vdots\\
e^{2\pi ijk/N}\\
e^{2\pi ij\left(k+1\right)/N}\\
\vdots\end{array}\right)$

$F=\frac{1}{\sqrt{N}}\left(\begin{array}{cccc}
1 & 1 & \cdots & 1\\
1 & e^{2\pi i1/N} &  & e^{2\pi i\left(N-1\right)/N}\\
\vdots & \vdots & \ddots & \vdots\\
1 & e^{2\pi i\left(N-1\right)/N} &  & e^{2\pi i\left(N-1\right)^{2}/N}\end{array}\right)$

$F=\frac{1}{\sqrt{N}}\left(e^{2\pi ijk/N}\right)_{k,j=0,\ldots,N-1}$


\subsubsection*{Proof F is Unitary}

\begin{eqnarray*}
F^{H} & = & \frac{1}{\sqrt{N}}\left(e^{-2\pi ijk/N}\right)_{j,k=0,\ldots,N-1}\\
F^{H}F & = & \frac{1}{N}\left(\sum_{k=0}^{N-1}e^{-2\pi ipk/N}e^{2\pi ikq/N}\right)_{p,q=0,\ldots,N-1}\\
 & = & \frac{1}{N}\left(\sum_{k=0}^{N-1}e^{2\pi ik\left(q-p\right)/N}\right)_{p,q}\end{eqnarray*}


If $p=q$, $\left(F^{H}F\right)_{p,q}=1$

If $p\neq q$, \begin{eqnarray*}
\left(F^{H}F\right)_{p,q} & = & \sum_{k=0}^{N-1}e^{2\pi ik\left(q-p\right)/N}\\
 & = & \frac{e^{2\pi i\left(q-p\right)\frac{N-1}{N}}e^{2\pi i\left(q-p\right)\frac{1}{N}}-1}{e^{2\pi i\left(q-p\right)\frac{1}{N}}-1}\\
 & = & \frac{e^{2\pi i\left(q-p\right)}-1}{e^{2\pi i\left(q-p\right)\frac{1}{N}}-1}\\
 & = & 1-1=0\end{eqnarray*}


Therefore, $F^{H}F=I$, and $F$ is unitary.

(Formula for sum of a geometric progression used above: $\sum_{k=0}^{n}r^{k}=\frac{r^{n+1}-1}{r-1}$
)


\subsubsection*{Tensor Product Representation}

Notation:

$j=j_{1}j_{2}\ldots j_{n}=j_{1}2^{n-1}+j_{2}2^{n-2}+\ldots+j_{n}$ 

$\frac{j}{2^{n}}=0.j_{1}j_{2}\ldots j_{n}=j_{1}\frac{1}{2}+j_{2}\frac{1}{2^{2}}+j_{n}\frac{1}{2^{n}}$

$\frac{j}{2^{\ell}}=j_{1}\ldots j_{n-\ell}.j_{n-\ell+1}\ldots j_{n}$

$e^{2\pi i\frac{j}{2^{\ell}}}=e^{2\pi i\left(j_{1}\ldots j_{n-\ell}.j_{n-\ell+1}\ldots j_{n}\right)}$

Lemma:\[
F\left|j\right\rangle =F\left|j_{1}\ldots j_{n}\right\rangle =\frac{\left|0\right\rangle +e^{2\pi i0.j_{n}}\left|1\right\rangle }{\sqrt{2}}\otimes\frac{\left|0\right\rangle +e^{2\pi i0.j_{n-1}j_{n}}\left|1\right\rangle }{\sqrt{2}}\otimes\cdots\otimes\frac{\left|0\right\rangle +e^{2\pi i0.j_{1}j_{2}\ldots j_{n}}\left|1\right\rangle }{\sqrt{2}}\]


Proof, start with:\[
F\left|j\right\rangle =\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}e^{2\pi ijk/N}\left|k\right\rangle \]
Decompose $k=\left(k_{1}\ldots k_{n}\right)$

\begin{eqnarray*}
F\left|j\right\rangle  & = & \frac{1}{\sqrt{N}}\sum_{k_{1}=0}^{1}\cdots\sum_{k_{n}=0}^{1}e^{2\pi ij0.k_{1}\ldots k_{n}}\left|k_{1}\right\rangle \ldots\left|k_{n}\right\rangle \\
 & = & \frac{1}{\sqrt{N}}\sum_{k_{1}=0}^{1}\cdots\sum_{k_{n}=0}^{1}e^{2\pi ij\left(k_{1}\frac{1}{2}+k_{2}\frac{1}{2^{2}}+\cdots+k_{n}\frac{1}{2^{n}}\right)}\left|k_{1}\right\rangle \ldots\left|k_{n}\right\rangle \\
 & = & \frac{1}{\sqrt{N}}\sum_{k_{1}=0}^{1}\cdots\sum_{k_{n}=0}^{1}\bigotimes_{\ell=1}^{n}e^{2\pi ijk_{\ell}\frac{1}{2^{\ell}}}\left|k_{\ell}\right\rangle \\
 & = & \frac{1}{\sqrt{N}}\bigotimes_{\ell=1}^{n}\sum_{k_{\ell}=0}^{1}e^{2\pi ijk_{\ell}\frac{1}{2^{\ell}}}\left|k_{\ell}\right\rangle \end{eqnarray*}


Simple example illustrating last step:

\begin{eqnarray*}
 &  & \sum_{k_{1}=0}^{1}\sum_{k_{2}=0}^{1}e^{2\pi ijk_{1}\frac{1}{2}/N}e^{2\pi ijk_{2}\frac{1}{4}}\left|k_{1}\right\rangle \left|k_{2}\right\rangle \\
 &  & =\left(\sum_{k_{1}=0}^{1}e^{2\pi ijk_{1}\frac{1}{2}}\left|k_{1}\right\rangle \right)\left(\sum_{k_{2}=0}^{1}e^{2\pi ijk_{2}\frac{1}{4}}\left|k_{2}\right\rangle \right)\end{eqnarray*}


Continuing:

\begin{eqnarray*}
F\left|j\right\rangle  & = & \bigotimes_{\ell=1}^{n}\left(\frac{\left|0\right\rangle +e^{2\pi ij/2^{\ell}}\left|1\right\rangle }{\sqrt{2}}\right)\end{eqnarray*}


Dividing $j$ by $2^{\ell}$ is equivalent to moving the decimal point
in the binary representation of $j$ by $\ell$ places to the left.
Additionally, after the shift, any digits to the left of the dot can
be discarded. This is because the function $e^{xi}$ has a period
of $2\pi$, so the only the fractional part of $\frac{j}{2^{\ell}}$
matters, and the whole number part can be set to $0.$

\[
F\left|j\right\rangle =F\left|j_{1}\ldots j_{n}\right\rangle =\frac{\left|0\right\rangle +e^{2\pi i0.j_{n}}\left|1\right\rangle }{\sqrt{2}}\otimes\frac{\left|0\right\rangle +e^{2\pi i0.j_{n-1}j_{n}}\left|1\right\rangle }{\sqrt{2}}\otimes\cdots\otimes\frac{\left|0\right\rangle +e^{2\pi i0.j_{1}j_{2}\ldots j_{n}}\left|1\right\rangle }{\sqrt{2}}\]


At $\ell=1$, term is: $\left(\frac{\left|0\right\rangle +e^{2\pi i0.j_{n}}\left|1\right\rangle }{\sqrt{2}}\right)$ 

At $\ell=2$, term is: $\left(\frac{\left|0\right\rangle +e^{2\pi i0.j_{n-1}j_{n}}\left|1\right\rangle }{\sqrt{2}}\right)$ 

At $\ell=3$, term is: $\left(\frac{\left|0\right\rangle +e^{2\pi i0.j_{n-2}j_{n-1}j_{n}}\left|1\right\rangle }{\sqrt{2}}\right)$ 

Tip: Remember this lemma for final


\subsection*{Fourier Transform as Circuit}

Define $R_{k}=\left(\begin{array}{cc}
1 & 0\\
0 & e^{2\pi i/2^{k}}\end{array}\right)$

$R_{0}=\left(\begin{array}{cc}
1 & 0\\
0 & 1\end{array}\right)=I$

$R_{1}=\left(\begin{array}{cc}
1 & 0\\
0 & -1\end{array}\right)=Z$

$R_{2}=\left(\begin{array}{cc}
1 & 0\\
0 & i\end{array}\right)=S$

$R_{3}=\left(\begin{array}{cc}
1 & 0\\
0 & e^{\pi i/4}\end{array}\right)=T$

When evaluating cost of implementing fourier transform, assume implementing
each of one these $R$ gates has unit cost. The assumption may not
necessarily be true in an actual implementation.

\[
\textrm{Circuit:}\bigotimes_{\ell=1}^{n}\left(R_{n-\ell+1}^{\# n}\ldots R_{2}^{\#\ell+1}H\right)\left|j_{\ell}\right\rangle \]


First Qubit:

\[
\left|j_{1}\right\rangle \xrightarrow{H}\frac{\left|0\right\rangle +\left(-1\right)^{j_{1}}\left|1\right\rangle }{\sqrt{2}}=\frac{\left|0\right\rangle +e^{2i\pi0.j_{1}}\left|1\right\rangle }{\sqrt{2}}\]


Trick used: $e^{2\pi i0.j_{1}}=\left\{ \begin{array}{cc}
1 & j_{1}=0\\
e^{2\pi i/2} & j_{1}=1\end{array}\right.=\left(-1\right)^{j_{1}}$

\begin{eqnarray*}
 & \xrightarrow[w/j_{2}]{R_{2}} & \frac{R_{2}^{j_{2}}\left|0\right\rangle +e^{2i\pi0.j_{1}}R_{2}^{j_{2}}\left|1\right\rangle }{\sqrt{2}}\\
 & = & \frac{\left|0\right\rangle +e^{2i\pi0.j_{1}}e^{2\pi ij_{2}/2^{2}}\left|1\right\rangle }{\sqrt{2}}\\
 & = & \frac{\left|0\right\rangle +e^{2i\pi0.j_{1}j_{2}}\left|1\right\rangle }{\sqrt{2}}\\
 & \xrightarrow[w/j_{3}]{R_{3}} & \frac{R_{3}^{j_{3}}\left|0\right\rangle +e^{2i\pi0.j_{1}}R_{3}^{j_{3}}\left|1\right\rangle }{\sqrt{2}}\\
 & = & \frac{\left|0\right\rangle +e^{2i\pi0.j_{1}j_{2}j_{3}}\left|1\right\rangle }{\sqrt{2}}\\
 & \vdots\\
 & \xrightarrow[w/j_{n}]{R_{n}} & \frac{\left|0\right\rangle +e^{2i\pi0.j_{1}j_{2}\ldots j_{n}}\left|1\right\rangle }{\sqrt{2}}\end{eqnarray*}


Second qubit:

\begin{eqnarray*}
\left|j_{2}\right\rangle  & \xrightarrow{H} & \frac{\left|0\right\rangle +e^{2i\pi0.j_{2}}\left|1\right\rangle }{\sqrt{2}}\\
 & \xrightarrow[w/j_{3}]{R_{2}} & \frac{\left|0\right\rangle +e^{2i\pi0.j_{2}}e^{2\pi ij_{3}/2^{2}}\left|1\right\rangle }{\sqrt{2}}\\
 & = & \frac{\left|0\right\rangle +e^{2i\pi0.j_{2}j_{3}}\left|1\right\rangle }{\sqrt{2}}\\
 & \xrightarrow[w/j_{4}]{R_{3}} & \frac{\left|0\right\rangle +e^{2i\pi0.j_{2}j_{3}}e^{2\pi ij_{4}/2^{3}}\left|1\right\rangle }{\sqrt{2}}\\
 & = & \frac{\left|0\right\rangle +e^{2i\pi0.j_{2}j_{3}j_{4}}\left|1\right\rangle }{\sqrt{2}}\\
 & \vdots\\
 & \xrightarrow[w/j_{n}]{R_{n-1}} & \frac{\left|0\right\rangle +e^{2i\pi0.j_{2}\ldots j_{n}}\left|1\right\rangle }{\sqrt{2}}\end{eqnarray*}


Last qubit:

\begin{eqnarray*}
\left|j_{n}\right\rangle  & \xrightarrow{H} & \frac{\left|0\right\rangle +e^{2i\pi0.j_{n}}\left|1\right\rangle }{\sqrt{2}}\end{eqnarray*}


Circuit output is\[
\frac{\left|0\right\rangle +e^{2i\pi0.j_{1}\ldots j_{n}}\left|1\right\rangle }{\sqrt{2}}\otimes\cdots\otimes\frac{\left|0\right\rangle +e^{2i\pi0.j_{n}}\left|1\right\rangle }{\sqrt{2}}\]


which is the Lemma 1 expression for the Fourier transform with qubits
in reverse order. To correct this, $\left\lfloor \frac{n}{2}\right\rfloor $
swap gates can be used to swap the top and bottom bits, second to
top and second to bottom bits, and so on. Each swap gate is made of
3 CNOT gates.

Cost: Each qubit requires $O\left(n\right)$ gates to transform, total
cost is $O\left(n^{2}\right)$ for transforming all qubits and $O\left(n\right)$
for swaps, which is $O\left(n^{2}\right)$ total. Best classical cost
is $O\left(N\log N\right)=O\left(2^{n}n\right)$, so quantum implementation
represents an exponential speedup.

Next Lecture: Phase Estimation

Homework: Implement \emph{reverse} fourier transform, finding algorithm
and cost.


\section*{Lecture 17 (21 March)}


\subsection*{Lecture 16 Review}

$F\left|j\right\rangle =\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}e^{2\pi ijk/N}\left|k\right\rangle $

$F\left|j_{1}\ldots j_{n}\right\rangle =\left(\frac{\left|0\right\rangle +e^{2\pi i0.j_{n}}\left|k\right\rangle }{\sqrt{0}}\right)\otimes\cdots\otimes\left(\frac{\left|0\right\rangle +e^{2\pi i0.j_{1}\ldots j_{n}}\left|k\right\rangle }{\sqrt{0}}\right)$

Cost: quantum implementation $O\left(n^{2}\right)$ beats classical
$O\left(2^{n}n\right)=O\left(N\log N\right)$

Hint: Finding $F^{H}$, problem 1 next homework. Two approaches. One
is to look at the circuit and determine meaning of the conjugate transpose
as an operator. Other is to look at the definition of $F^{H}$which
differs only by a minus sign. \[
F^{H}\left|j\right\rangle =\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}e^{-2\pi ijk/N}\left|k\right\rangle \]
Cost should be the same.


\subsection*{Phase Estimation}


\subsubsection*{Overview}

Heart of many quantum algorithms. Related to solution to Schrodinger's
equation, important for quantum simulation.

Problem: Given unitary matrix $U$, size $N\times N$ where $N=2^{k}$
(using $k$ instead of $n$ as in previous lecture because $n$ is
used for something else here). Also given $\left|u\right\rangle $,
eigenvector of $U$, so

\[
U\left|u\right\rangle =\lambda\left|u\right\rangle =e^{2\pi i\varphi}\left|u\right\rangle \]


for $\varphi\in\left[0,1\right]$. Goal is to find approximation of
$\varphi$ with accuracy $2^{-n}$. Algorithm is covered in this lecture,
the correctness in shown next lecture. $\varphi$ can be represented
as:

\[
\varphi=0.\varphi_{1}\varphi_{2}\ldots\varphi_{n}\varphi_{n+1}\]


If only $n$ digits are given, precision is lost but bounded by a
maximum error. Maximum error can be computed by assuming every digit
after the $n$th is 1 when it should be zero:

\[
\sum_{j=n+1}^{\infty}\frac{1}{2^{j}}=\frac{1}{2^{n+1}}\sum_{j=0}^{\infty}\frac{1}{2^{j}}=\frac{1}{2^{n+1}}\left(\frac{1}{1-\frac{1}{2}}\right)=2^{^{-n}}\]



\subsubsection*{Givens}

1. Given$\left|u\right\rangle $, eigenvector as superposition state
$k$ qubits long.

2. Given controlled operators $U^{2^{j}}$ for $j=0,2,\ldots$ implemented
as black boxes.

{[}See also paper: Quantum Algorithms Revisited]


\subsubsection*{Algorithm}

To see understand the algorithm, it helps to look at how a$U^{2^{j}}$
gate controlled by an $H\left|0\right\rangle $ qubit acts:\begin{eqnarray*}
\frac{\left|0\right\rangle \left|u\right\rangle +\left|1\right\rangle \left|u\right\rangle }{\sqrt{2}} & \xrightarrow{C\left(U^{2^{j}}\right)} & \frac{\left|0\right\rangle \left|u\right\rangle +\left|1\right\rangle U^{2^{j}}\left|u\right\rangle }{\sqrt{2}}\\
 & = & \frac{\left|0\right\rangle \left|u\right\rangle +\left|1\right\rangle e^{2\pi i\varphi2^{j}}\left|u\right\rangle }{\sqrt{2}}\\
 & = & \frac{\left|0\right\rangle +\left|1\right\rangle e^{2\pi i\varphi2^{j}}}{\sqrt{2}}\left|u\right\rangle \end{eqnarray*}


Using different values of $j$ results in qubits that can be expressed
in terms of different portions of the bitwise representation of $\varphi$:

$U^{2^{t-1}}\rightarrow\left|0\right\rangle +e^{2\pi i\varphi2^{t-1}}\left|1\right\rangle =\left|0\right\rangle +e^{2\pi i0.\varphi_{t}\varphi_{t+1}\ldots}\left|1\right\rangle $

$U^{2^{t-2}}\rightarrow\left|0\right\rangle +e^{2\pi i\varphi2^{t-2}}\left|1\right\rangle =\left|0\right\rangle +e^{2\pi i0.\varphi_{t-1}\varphi_{t}\varphi_{t+1}\ldots}\left|1\right\rangle $

$\vdots$

$U^{2^{1}}\rightarrow\left|0\right\rangle +e^{2\pi i\varphi2}\left|1\right\rangle =\left|0\right\rangle +e^{2\pi i0.\varphi_{2}\ldots\varphi_{t}\varphi_{t+1}\ldots}\left|1\right\rangle $

$U^{2^{0}}\rightarrow\left|0\right\rangle +e^{2\pi i\varphi}\left|1\right\rangle =\left|0\right\rangle +e^{2\pi i0.\varphi_{1}\ldots\varphi_{t}\varphi_{t+1}\ldots}\left|1\right\rangle $

As can be seen above, $U^{2^{j}}$ essentially means shift $\varphi$
by $j$ bits to the left. The whole number portion of the resulting
numbers is discarded because the exponential function is periodic.

The states shown above look like the states that would result from
$F\left|\varphi_{1}\ldots\varphi_{t}\right\rangle $, where $F$ is
the quantum fourier transform.


\subsubsection*{Circuit}

Circuit is made of two registers, top register is $t$ $\left|0\right\rangle $
qubits, bottom register is $\left|u\right\rangle $ (which is $k$
qubits long). Hadamard gates are applied to each $\left|0\right\rangle $
qubit in the first register, and output of those is used to control
a sequence of $U^{2^{j}}$ gates on the second register. The first
gate on the second register, $U^{2^{0}}$, is controlled by the $H\left|0\right\rangle $
output on the first qubit, then there is a $U^{2^{1}}$gate controlled
by $H\left|0\right\rangle $ from the second qubit, followed by a
$U^{2^{2}}$ gate controlled by the third qubit, and so on. {[}Textbook
figure 5.2 page 222]

After these gates, an inverse fourier transform is applied to the
first register, and measurement of that register on the computational
basis yields the binary digits of the representation of $\varphi$.

We need to show that before the inverse fourier transform is applied,
the top register has value $\frac{1}{2^{t/2}}\sum_{k=0}^{2^{t}-1}e^{2\pi ik\varphi}\left|k\right\rangle $.
This can be proved with induction. Start with the last two qubits:

\begin{eqnarray*}
 &  & \frac{1}{2}\left(\left|0\right\rangle +e^{2\pi i2\varphi}\left|1\right\rangle \right)\left(\left|0\right\rangle +e^{2\pi i\varphi}\left|1\right\rangle \right)\\
 &  & =\left|00\right\rangle +e^{2\pi i\varphi}\left|01\right\rangle +e^{2\pi i2\varphi}\left|10\right\rangle +e^{2\pi i3\varphi}\left|11\right\rangle \end{eqnarray*}


Then the inductive step is:\begin{eqnarray*}
 &  & \frac{1}{\sqrt{2}}\left(\left|0\right\rangle +e^{2\pi i2^{t-1}\varphi}\left|1\right\rangle \right)\left(\frac{1}{2^{\left(t-1\right)/2}}\sum_{k=0}^{2^{t-1}-1}e^{2\pi ik\varphi}\left|k\right\rangle \right)\\
 &  & =\frac{1}{2^{t/2}}\sum_{k=0}^{2^{t-1}-1}\left(e^{2\pi ik\varphi}\left|0k\right\rangle +e^{2\pi i\left(k+2^{t-1}\right)\varphi}\left|1k\right\rangle \right)\\
 &  & =\frac{1}{2^{t/2}}\sum_{j=0}^{2^{t}-1}e^{2\pi ij\varphi}\left|j\right\rangle \end{eqnarray*}



\subsubsection*{Circuit and Expression}

A second interpretation of phase estimation can be seen by looking
at the overall circuit diagram {[}Textbook figure 5.3 page 223].

\begin{eqnarray*}
\left|0\right\rangle ^{\otimes t}\left|u\right\rangle  & \xrightarrow{H^{\otimes t}\otimes I} & \frac{1}{2^{t/2}}\sum_{j=0}^{2^{t}-1}\left|j\right\rangle \left|u\right\rangle \\
 & \xrightarrow{U^{j}} & \frac{1}{2^{t/2}}\sum_{j=0}^{2^{t}-1}\left|j\right\rangle U^{j}\left|u\right\rangle \\
 & = & \frac{1}{2^{t/2}}\sum_{j=0}^{2^{t}-1}\left|j\right\rangle e^{2\pi ij\varphi}\left|u\right\rangle \\
 & \xrightarrow{F^{H}} & \sum_{\ell=0}^{2^{t}-1}g\left(\ell,\varphi\right)\left|\ell\right\rangle \end{eqnarray*}


We aren't solving for the coefficients of possible output basis states
right now, we just refer to them here as $g\left(\ell,\varphi\right)$
or $\alpha_{\ell}$. (The next lecture solves for $\alpha_{\ell}$).
Now when $\varphi$ can be expressed as $0.\varphi_{1}\ldots\varphi_{t}$
exactly, there is unique $\ell$ so that\[
\left|a_{\ell}\right|=\left|g\left(\ell_{1}\varphi\right)\right|=1\]


and all the other $\alpha_{\ell}$ values are 0. The algorithm succeeds
in this case, but it also succeeds more generally, and this is shown
in the next lecture.

(Above depends on the fact that the sequence of controlled-U operations
in the circuit transform a basis state $\left|j\right\rangle \left|u\right\rangle $
to $\left|j\right\rangle U^{j}\left|u\right\rangle .$ This is exercise
5.7 in the book, and can be seen from the fact that if $j$ has a
$t$ bit representation:\begin{eqnarray*}
\left|j\right\rangle U^{j}\left|u\right\rangle  & = & \left|j\right\rangle U^{j_{t}2^{o}+j_{t-1}2^{t}+\cdots+j_{1}2^{t-1}}\left|u\right\rangle \\
 & = & \left|j\right\rangle U^{2^{o}j_{t}}\times U^{2^{1}j_{t-1}}\times\cdots\times U^{2^{t-1}j_{t}}\left|u\right\rangle \end{eqnarray*}
)

Cost of circuit in gates is $t$ H gates, $t$ controlled $U^{2^{j}}$
gates (assuming the exponents don't affect cost), and an $F^{H}$
gate which has cost $t^{2}$. $O\left(t+t+t^{2}\right)=O\left(t^{2}\right)$.
Cost in qubits is $t+k$, $O\left(t+k\right)$

Application: If you have real matrix, $A$, so that $A=A^{T}$, $e^{iA}$
is unitary, $ih\frac{g\psi\left(x,t\right)}{gt}=H\psi\left(x,t\right)$
where $h$ is Planck's constant, $H$ is Hamiltonian.


\section*{Lecture 18 (26 March)}

Missed Class, filling in blanks from Textbook section 5.2.1. 

Output of the first register of the phase estimation circuit before
inverse fourier transform is: \begin{eqnarray*}
 &  & \frac{1}{2^{t/2}}\left(\left|0\right\rangle +e^{2\pi i2^{t-1}\varphi}\left|1\right\rangle \right)\left(\left|0\right\rangle +e^{2\pi i2^{t-2}\varphi}\left|1\right\rangle \right)\ldots\left(\left|0\right\rangle +e^{2\pi i2^{0}\varphi}\left|1\right\rangle \right)\\
 &  & =\frac{1}{2^{t/2}}\sum_{k=0}^{2^{t}-1}e^{2\pi i\varphi k}\left|k\right\rangle \end{eqnarray*}
If $\varphi=0.\varphi_{1}\ldots\varphi_{t}$ exactly, applying inverse
fourier transform to this state gives state $\left|\varphi_{1}\ldots\varphi_{t}\right\rangle $.
When $\varphi$ cannot be represented with $t$ bits, the analysis
below applies.

Let $b$ be integer in the range 0 to $2^{t}-1$ such that $b/2^{t}=0.b_{1}\ldots b_{t}$
is the best $t$ bit approximation to $\varphi$ which is less than
$\varphi$. Error is $\delta\equiv\varphi-b/2^{t}$ and $0\le\delta\le2^{t-1}$.
Applying the inverse fourier transform to the first register gives:\begin{eqnarray*}
 &  & \frac{1}{2^{t}}\sum_{\ell=0}^{2^{t}-1}\sum_{k=0}^{2^{t}-1}e^{-2\pi ik\ell/2^{t}}e^{2\pi i\varphi k}\left|\ell\right\rangle \\
 &  & =\sum_{\ell=0}^{2^{t}-1}\frac{1}{2^{t}}\sum_{k=0}^{2^{t}-1}\left(e^{2\pi i\left(\varphi-\ell/2^{t}\right)}\right)^{k}\left|\ell\right\rangle \\
 &  & =\sum_{\ell=0}^{2^{t}-1}\alpha_{\ell-b}\left|\ell\right\rangle \end{eqnarray*}


Let $\alpha_{\ell}$ be the amplitude of $\left|b+\ell\right\rangle $
(taking addition inside the state and subtraction in the subscript
of $\alpha$ to be modulo $2^{t}$):\begin{eqnarray*}
\alpha_{\ell} & \equiv & \frac{1}{2^{t}}\sum_{k=0}^{2^{t}-1}\left(e^{2\pi i\left(\varphi-\left(b+\ell\right)/2^{t}\right)}\right)^{k}\\
 & = & \frac{1}{2^{t}}\frac{1-e^{2\pi i\left(2^{t}\varphi-\left(b+\ell\right)\right)}}{1-e^{2\pi i\left(\varphi-\left(b+\ell\right)/2^{t}\right)}}\\
 & = & \frac{1}{2^{t}}\frac{1-e^{2\pi i\left(2^{t}\delta-\ell\right)}}{1-e^{2\pi i\left(\delta-\ell/2^{t}\right)}}\end{eqnarray*}


The second step follows from the formula for sum of a geometric series,
the third from substituting $\delta=\varphi-b/2^{t}$.

Introduce new variables. Take the output of the final measurement
to be $m$, and chose an error tolerance, $e$ which is a positive
integer such that if $\left|m-b\right|>e$, the algorithm is considered
to have failed. The probability of that failure condition is:\[
p\left(\left|m-b\right|>e\right)=\sum_{\ell=-2^{t-1}+1}^{-\left(e+1\right)}\left|\alpha_{\ell}\right|^{2}+\sum_{\ell=e+1}^{2^{t-1}}\left|\alpha_{\ell}\right|^{2}\]
For any real $\theta$, $\left|1-e^{i\theta}\right|\le2$, so\[
\left|\alpha_{\ell}\right|\le\frac{1}{2^{t}\left|1-e^{2\pi i\left(\delta-\ell/2^{t}\right)}\right|}\]
Whenever $-\pi\le\theta\le\pi$, then $\left|1-e^{i\theta}\right|\ge2\left|\theta\right|/\pi$.
And when $-2^{t-1}<\ell\le2^{t-1}$, then $-\pi\le2\pi\left(\delta-\ell/2^{t}\right)\le\pi$,
therefore:\[
\left|\alpha_{\ell}\right|\le\frac{1}{2^{t}\cdot2\left(\delta-\ell/2^{t}\right)}=\frac{1}{-\frac{1}{2}\left(\ell-2^{t}\delta\right)}\]
And\begin{eqnarray*}
p\left(\left|m-b\right|>e\right) & \le & \frac{1}{4}\left(\sum_{\ell=-2^{t-1}+1}^{-\left(e+1\right)}\frac{1}{\left(\ell-2^{t}\delta\right)^{2}}+\sum_{\ell=e+1}^{2^{t-1}}\frac{1}{\left(\ell-2^{t}\delta\right)^{2}}\right)\\
 & \le & \frac{1}{4}\left(\sum_{\ell=-2^{t-1}+1}^{-\left(e+1\right)}\frac{1}{\ell^{2}}+\sum_{\ell=e+1}^{2^{t-1}}\frac{1}{\left(\ell-1\right)^{2}}\right)\\
 & \le & \frac{1}{2}\sum_{\ell=e}^{2^{t-1}+1}\frac{1}{\ell^{2}}\\
 & \le & \frac{1}{2}\int_{e-1}^{2^{t-1}-1}d\ell\frac{1}{\ell^{2}}\\
 & = & \frac{1}{2\left(e-1\right)}\end{eqnarray*}


Second step follows because $0\le2^{t}\delta\le1$.

When approximating $\varphi$ to an accuracy of $2^{-n}$, $e=2^{t-n}-1$.
When using $t=n+p$ qubits in phase estimation, then the probability
of success is $1-\frac{1}{2\left(2^{p}-2\right)}$. Let $\epsilon$
be the probability of failure, then you can find minimum $t$ that
won't exceed that failure rate:\begin{eqnarray*}
\epsilon & = & \frac{1}{2\left(2^{p}-2\right)}\\
2^{p} & = & \frac{1}{2\epsilon}+2\\
p & = & \log_{2}\left(\frac{1}{2\epsilon}+2\right)\end{eqnarray*}
So for success probability of at least $1-\epsilon$, choose $t=n+\left\lceil \log_{2}\left(2+\frac{1}{2\epsilon}\right)\right\rceil $:


\section*{Lecture 19 (28 March)}


\subsection*{Homework Hint}

Homework 4, Problem 2: Convolution Theorem and Fourier Transform

Given coefficients of basis states $\alpha_{0}$, $\alpha_{N-1}$
and $\beta_{0}$, $\beta_{N-1}$ which tranform into $\gamma_{0}$,
$\gamma_{N-1}$ and $\delta_{0}$, $\delta_{N-1}$

Discrete FT:\[
\gamma_{j}=\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\alpha_{k}e^{2\pi ijk/N},\quad\delta_{j}=\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\beta_{k}e^{2\pi ijk/N}\]
Inverse FT:\[
\alpha_{j}=\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\gamma_{k}e^{-2\pi ijk/N},\quad\beta_{j}=\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\delta_{k}e^{-2\pi ijk/N}\]
Convolution:\[
\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\sum_{\ell=0}^{N-1}\alpha_{\ell}\beta_{j-\ell}\left|j\right\rangle \]


Use FT formulas to substitute $\alpha_{\ell}$ and $\beta_{j-\ell}$
above:\[
\beta_{j-\ell}=\frac{1}{\sqrt{N}}\sum_{k=0}^{N-1}\delta_{k}e^{-2\pi i\left(j-\ell\right)k/N}\]


Result is messy, you end up with four sums, but it simplifies.


\subsection*{Performance Analysis of Phase Estimation}

We can compute bounded probability of failure and use that to determine
how many qubits to use in top register to get desired accuracy. Last
lecture proved:\[
Pr\left\{ \left|m-b\right|>e=2^{t-n}-1\right\} \le\frac{1}{2\left(e-1\right)}<\epsilon\]
where $\epsilon$ is highest allowed probability of failure, $m$
is the measurement of the first register on the computational basis,
$b$ is the representation of $\varphi$ expressed as a measurement,
$e$ is our error tolerance, expressed as the highest allowed absolute
difference between $m$ and $b$. $t$ is the number of qubits in
the top register and $n$ is the desired accuracy in bits, which is
just an alternate expression of error tolerance.

This expression of probability of failure and accuracy is unwieldy
and not what we originally set out to determine, which was finding:\[
Pr\left\{ \left|\varphi-\hat{\varphi}\right|\leq2^{-n}\right\} \]
where $\hat{\varphi}=\frac{m}{2^{t}}$. To find this, we switch to
finding probability of failure instead of probability of success because
that it is easier to bound that from above.\[
Pr\left\{ \left|\varphi-\hat{\varphi}\right|>2^{-n}\right\} =Pr\left\{ \left|\varphi-\frac{b}{2^{t}}+\frac{b}{2^{t}}-\hat{\varphi}\right|>2^{-n}\right\} \]
Using the triangle inequality ($\left|a+b\right|\le\left|a\right|+\left|b\right|$)
:\begin{eqnarray*}
 & \le & Pr\left\{ \left|\varphi-\frac{b}{2^{t}}\right|+\left|\frac{b}{2^{t}}-\hat{\varphi}\right|>2^{-n}\right\} \\
 & \le & Pr\left\{ 2^{-t}+\left|\frac{b}{2^{t}}-\hat{\varphi}\right|>2^{-n}\right\} \\
 & = & Pr\left\{ \left|\frac{b}{2^{t}}-\hat{\varphi}\right|>2^{-n}-2^{-t}\right\} \\
 & = & Pr\left\{ \left|b-m\right|>2^{t-n}-1\right\} \\
 & = & Pr\left\{ \left|b-m\right|>e\right\} \\
 & \le & \frac{1}{2\left(e-1\right)}\end{eqnarray*}



\subsection*{P.E. w/ approx Eigenvector}

Phase estimation algorithm requires an eigenvector of the matrix $U$,
but it is also possible to use approximations of an eigenvector and
still get meaningful results. {[}Paper: Abrams + Lloyd]

Given$\left|u\right\rangle $, an approximate eigenvector which can
be expressed in terms of real eigenvectors $\left|u_{k}\right\rangle $
as:\[
\left|u\right\rangle =\sum_{k=0}^{N-1}d_{k}\left|u_{k}\right\rangle \]
We would like to estimate the phase $\varphi_{0}$ corresponding to
$\lambda_{0}=e^{2\pi i\varphi_{0}}\left|u_{0}\right\rangle $. The
of the P.E. on this input is:\begin{eqnarray*}
\left|0\right\rangle ^{\otimes t}\left|u\right\rangle  & \xrightarrow{H^{\otimes t}\otimes I} & \frac{1}{2^{t/2}}\sum_{j=0}^{2^{t}-1}\left|j\right\rangle \left|u\right\rangle \\
 & = & \frac{1}{2^{t/2}}\sum_{j=0}^{2^{t}-1}\left|j\right\rangle \sum_{k=0}^{2^{t}-1}d_{k}\left|u_{k}\right\rangle \\
 & = & \sum_{k=0}^{2^{t}-1}d_{k}\frac{1}{2^{t/2}}\sum_{j=0}^{2^{t}-1}\left|j\right\rangle \left|u_{k}\right\rangle \\
 & \xrightarrow{U^{j}} & \sum_{k=0}^{2^{t}-1}d_{k}\frac{1}{2^{t/2}}\sum_{j=0}^{2^{t}-1}\left|j\right\rangle U^{j}\left|u_{k}\right\rangle \\
 & = & \sum_{k=0}^{2^{t}-1}d_{k}\frac{1}{2^{t/2}}\sum_{j=0}^{2^{t}-1}e^{2\pi i\varphi_{k}j}\left|j\right\rangle \left|u_{k}\right\rangle \\
 & \xrightarrow{F^{H}\otimes I} & \sum_{k=0}^{2^{t}-1}d_{k}\sum_{j=0}^{2^{t}-1}g\left(\varphi_{k},j\right)\left|j\right\rangle \left|u_{k}\right\rangle \end{eqnarray*}
$g\left(\varphi_{k},j\right)$ in the previous lecture was $\alpha_{j}$,
the amplitude of output state $j$ in the top register. The last lecture
showed that $\alpha_{j}$ amplitudes were bounded from above, and
that if $j$ was far from $b$, then $\alpha_{j}$ would be low.

Next, measure top register to find $Pr\left\{ \left|m-b_{o}\right|<e\right\} $
where $0<\varphi_{0}-\frac{b_{0}}{2^{t}}<2^{-t}$. Probability of
any measurement $m$ is: \[
P_{m}=\sum_{k=0}^{N-1}\left|d_{k}g\left(\varphi_{k},m\right)\right|^{2}\]
Let $G$ be set of measurements which satisfy $\left|m-b_{o}\right|<e$,
then \begin{eqnarray*}
Pr\left\{ G\right\}  & = & \sum_{k=0}^{N-1}\sum_{m\in G}\left|d_{k}g\left(\varphi_{k},m\right)\right|^{2}\\
 & \ge & \left|d_{0}\right|^{2}\sum_{m\in G}\left|g\left(\varphi_{0},m\right)\right|^{2}\\
 & = & \left|d_{0}\right|^{2}\left(1-\epsilon\right)\end{eqnarray*}
 where $\epsilon$ is probability of failure given real eigenvector
$\left|u_{0}\right\rangle $ ($\frac{1}{2\left(e-1\right)}<\epsilon$)
and $d_{0}=\left\langle u_{0}|u\right\rangle $


\subsection*{Applications of P.E.: Order Finding}

Given $x$, $N$ positive integers, $x<N$, and $\gcd\left(x,N\right)=1$.

Definition: The order of $x$ modulo $N$ is the least positive integer
r so $x^{r}=1\left(\textrm{mod }N\right)$

Example:

$x=1$, $r=1$

$x=2$, $N=5$, $r=4$

$x=5$, $N=21$


\subsubsection*{Lemma}

Lemma: The order of $x$ modulo $N$ is $\le N$

Proof: 

For $k=1,2,3,\ldots,N$, and $r_{k}\in\left\{ 0,1,\ldots,N-1\right\} $\[
x^{k}=\ell_{k}N+r_{k}\]


Assume none of the remainders $r_{k}$ in the range of $k$ is one,
$r_{k}\ne1$ $\forall k=1,\ldots,N$ 

If that's the case, then two of the remainders in the range have be
the same, $\exists k,p:\: r_{k}=r_{p}$\begin{eqnarray*}
x^{k} & = & \ell_{k}N+r_{k}\\
x^{p} & = & \ell_{p}N+r_{p}\end{eqnarray*}
Subtracting these:\[
x^{k}-x^{p}=x^{p}\left(x^{k-p}-1\right)=\left(\ell_{k}-\ell_{p}\right)N\]
Case $\ell_{p}=\ell_{k},$ then $x^{k-p}=1$

Case $\ell_{p}\ne l_{k}$, since $N$ cannot divide $x^{p}$ because
$\gcd\left(x,N\right)=1$, $N$ divides $x^{k-p}-1$:\begin{eqnarray*}
x^{k-p}-1 & = & \ell N\\
x^{k-p} & = & 1\left(\textrm{mod }N\right)\end{eqnarray*}
which means $r\le k-p\le N$. 

Both of these cases contain contradictions, which means the assumption
that none of the remainders $r_{k}$ is $1$ for $k=1,2,3,\ldots,N$
is false, and the order must be $\le N$.


\subsubsection*{Algorithm}

Clasically: No known algorithm solving order finding in polylog $N$

Quantum: P.E. solves in poly log $N$ operations (gates)

Given $L=\left\lceil \log_{2}N\right\rceil $, the unitary operator
to use for phase estimation transforms like:\[
U\left|y\right\rangle =\left\{ \begin{array}{ll}
\left|xy\textrm{ mod }N\right\rangle  & y=0,1,2,\ldots,N-1\\
\left|y\right\rangle  & y=N,N+1,\ldots,2^{L}-1\end{array}\right.\]


Example: $x=2$, $N=5$, $L=\left\lceil \log_{2}5\right\rceil =3$

\begin{tabular}{|c|c|}
\hline 
$\left|y\right\rangle $&
$U\left|y\right\rangle $\tabularnewline
\hline
\hline 
$\left|0\right\rangle $&
$\left|0\right\rangle $\tabularnewline
\hline 
$\left|1\right\rangle $&
$\left|2\right\rangle $\tabularnewline
\hline 
$\left|2\right\rangle $&
$\left|4\right\rangle $\tabularnewline
\hline 
$\left|3\right\rangle $&
$\left|1\right\rangle $\tabularnewline
\hline 
$\left|4\right\rangle $&
$\left|3\right\rangle $\tabularnewline
\hline 
$\left|5\right\rangle $&
$\left|5\right\rangle $\tabularnewline
\hline 
$\left|6\right\rangle $&
$\left|6\right\rangle $\tabularnewline
\hline 
$\left|7\right\rangle $&
$\left|7\right\rangle $\tabularnewline
\hline
\end{tabular}


\section*{Lecture 20 (2 April)}


\subsection*{Lecture 19 Review}

Item 1: With initial state $\left|u\right\rangle $, eigenvector for
phase estimation satisfies $\varphi-\hat{\varphi}\le2^{-n}$ where
$n$ is the number of bits of desired accuracy, and $\hat{\varphi}=\frac{m}{2^{t}}$
is the measured value approximating $\varphi$. This condition has
to hold with probability$\ge\left(1-\epsilon\right)$, $\epsilon$
being the allowed probability of failure.

Item 2: If the initial state is some arbitrary initial vector, $\left|\tilde{u}\right\rangle $,
instead of an eigenvector, the output will still satisfy $\varphi-\hat{\varphi}\le2^{-n}$
with probability $\ge\left|\left\langle u|\tilde{u}\right\rangle \right|^{2}\left(1-\epsilon\right)$.
{[}There is another proof of this fact in 2 lines in a paper online
about constructing initial states]

Example: Take unitary matrix $U$, which has two phases $\varphi_{1}$,
$\varphi_{2}$ and two eigenvectors $u_{1}$, $u_{2}$. The eigenvalues
are related to the phases like $\lambda_{1}=e^{2\pi i\varphi_{1}}$,
$\lambda_{2}=e^{2\pi i\varphi_{2}}$. If the initial state is $\left|\tilde{u}\right\rangle =\frac{1}{2}\left|u_{1}\right\rangle +\frac{\sqrt{3}}{2}\left|u_{2}\right\rangle $,
the phase estimation algorithm will give close approximation of $\varphi_{1}$
with probability $\left(\frac{1}{2}\right)^{2}\left(1-\epsilon\right)$,
and a close approximation of $\varphi_{2}$ with probability $\left(\frac{\sqrt{3}}{2}\right)^{2}\left(1-\epsilon\right)$.


\subsection*{Order Finding}

Given $x$, $N$: $x<N$ and $\gcd\left(x,N\right)=1$ (meaning $x$,
and $N$ are coprime), find the least positive integer $r$ so $x^{r}=1\left(\textrm{mod }N\right)$.


\subsubsection*{U Matrix}

The phase estimation algorithm can solve this problem using the matrix
$U$ that transforms like:\[
U\left|y\right\rangle =\left\{ \begin{array}{ll}
\left|xy\textrm{ mod }N\right\rangle  & y=0,1,2,\ldots,N-1\\
\left|y\right\rangle  & y=N,N+1,\ldots,2^{L}-1\end{array}\right.\]


where $L=\left\lceil \log_{2}N\right\rceil $.

$U$ is a permutation matrix, meaning that if it is input with a basis
state, it's output is another just basis state, and each different
input maps to a different output, so it outputs all possible basis
states. And because states from $N$ to $2^{L}$are mapped to themselves,
the bottom right corner of the matrix is actually the identity matrix,
so\[
U=\left(\begin{array}{cc}
P & 0\\
0 & I\end{array}\right)\]


To show $U$ is unitary to suffices to show that it is $1:1$, and
it suffices to show that by showing $P$ is $1:1$ since \[
U^{H}U=\left(\begin{array}{cc}
P^{H} & 0\\
0 & I\end{array}\right)\left(\begin{array}{cc}
P & 0\\
0 & I\end{array}\right)=\left(\begin{array}{cc}
P^{H}P & 0\\
0 & I\end{array}\right)=\left(\begin{array}{cc}
I & 0\\
0 & I\end{array}\right)\]



\subsubsection*{Number Theory Aside}

Given $x$, $N$ then there might be a multiplicative inverse $b$
so $bx=1\left(\textrm{mod }N\right)$

Examples:

$x=2$, $N=5$, $b=3$

$x=2$, $N=4$, there is no $b$ because $\gcd\left(2,4\right)=2>1$:

\begin{eqnarray*}
2b & = & 1\left(\textrm{mod }4\right)\\
2b-1 & = & 4\ell\\
\textrm{odd} & = & \textrm{even}\end{eqnarray*}


$x$ has multiplicative inverse $x^{-1}\left(\textrm{mod }N\right)$
iff $\gcd\left(x,N\right)=1$.


\subsubsection*{Showing U is Unitarry}

To show that the mapping $xy\left(\textrm{mod }N\right)$ is 1:1 for
different values of $y$, we need to show no two values of $y$ give
the same output.

Take $z=xy_{1}\left(\textrm{mod }N\right)$ and $z=xy_{2}\left(\textrm{mod }N\right)$.
The order finding problem assumes $x$ and $N$ are coprime, so we
don't have to worry about multiplicative inverses not existing and:\begin{eqnarray*}
x^{-1}xy_{1}\left(\textrm{mod }N\right) & = & x^{-1}xy_{2}\left(\textrm{mod }N\right)\\
\left(1+\ell N\right)y_{1}\left(\textrm{mod }N\right) & = & \left(1+\ell N\right)y_{2}\left(\textrm{mod }N\right)\\
y_{1}\left(\textrm{mod }N\right) & = & y_{2}\left(\textrm{mod }N\right)\\
y_{1} & = & y_{2}\end{eqnarray*}
Therefore $P$ is 1:1 $\Rightarrow$ $U$ is 1:1 $\Rightarrow$ $U$
is unitary .

If $P$ is a permutation matrix then $P^{-1}=P^{T}$


\subsubsection*{Eigenvector of U}

Definition: For $S=0,\ldots,r-1$ define $\left|u_{s}\right\rangle =\frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}e^{-2\pi isk/r}\left|x^{k}\left(\textrm{mod }N\right)\right\rangle $

Then\begin{eqnarray*}
U\left|u_{s}\right\rangle  & = & \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}e^{-2\pi isk/r}U\left|x^{k}\left(\textrm{mod }N\right)\right\rangle \\
 & = & \frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}e^{-2\pi isk/r}\left|x^{k+1}\left(\textrm{mod }N\right)\right\rangle \\
 & = & \frac{1}{\sqrt{r}}\sum_{k=1}^{r}e^{-2\pi is\left(k-1\right)/r}\left|x^{k}\left(\textrm{mod }N\right)\right\rangle \\
 & = & \frac{1}{\sqrt{r}}e^{2\pi is/r}\sum_{k=1}^{r}e^{-2\pi isk/r}\left|x^{k}\left(\textrm{mod }N\right)\right\rangle \end{eqnarray*}


Case $k=r$, then $e^{-2\pi isr/r}=1$, $\left|x^{r}\left(\textrm{mod }N\right)\right\rangle =\left|1\right\rangle $

Case $k=0$, then $e^{-2\pi is0/r}=1$, $\left|x^{0}\left(\textrm{mod }N\right)\right\rangle =\left|1\right\rangle $

This means we can sum from $0$ to $r-1$ instead of $1$ to $r$:

\begin{eqnarray*}
U\left|u_{s}\right\rangle  & = & \frac{1}{\sqrt{r}}e^{2\pi is/r}\sum_{k=0}^{r-1}e^{-2\pi isk/r}\left|x^{k}\left(\textrm{mod }N\right)\right\rangle \\
 & = & e^{-2\pi is/r}\left|u_{s}\right\rangle \end{eqnarray*}



\subsubsection*{Phase Estimation for Order Finding}

The phase of matrix $U$ given eigenvector $\left|u_{s}\right\rangle $
will be $\frac{s}{r}$ and the output of phase estimation $\hat{\varphi}$,
will approximate this.

Possible problems with using this approach to find $r$:

1. We do not know how to construct initial state $\left|u_{s}\right\rangle $.

2. We do not know how to get $r$ from $\varphi=\frac{s}{r}$.

3. We do not know how to compute $U^{j}$.


\subsubsection*{Initial State for Phase Estimation}

Regarding problem 1, it turns out there is a trivial way to construct
a suitable approximate initial state. Take the combination of all
eigenvectors: \begin{eqnarray*}
\frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}\left|u_{s}\right\rangle  & = & \frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}\frac{1}{\sqrt{r}}\sum_{k=0}^{r-1}e^{-2\pi isk/r}\left|x^{k}\left(\textrm{mod }N\right)\right\rangle \\
 & = & \frac{1}{r}\sum_{k=0}^{r-1}\sum_{s=0}^{r-1}e^{-2\pi isk/r}\left|x^{k}\left(\textrm{mod }N\right)\right\rangle \end{eqnarray*}


Case $k=0$, this simplifies to $\left|1\right\rangle $

Case $k>0$, the coefficients for each output state are given by geometric
series:

\[
\frac{e^{-2\pi ik/r\cdot\left(r-1+1\right)}-1}{e^{-2\pi ik/r}-1}=\frac{1-1}{e^{-2\pi ik/r}-1}=0\]


(Geometric series\begin{eqnarray*}
\sum_{k=0}^{n}r^{k} & = & r^{0}+r^{1}+\cdots+r^{n}\\
\left(1-r\right)\sum_{k=0}^{n}r^{k} & = & \left(r^{0}+r^{1}+\cdots+r^{n}\right)-\left(r^{1}+r^{2}+\cdots+r^{n+1}\right)\\
 & = & r^{0}-r^{n+1}\\
\sum_{k=0}^{n}r^{k} & = & \frac{1-r^{n+1}}{1-r}\end{eqnarray*}


So,\begin{eqnarray*}
\frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}\left|u_{s}\right\rangle  & = & \frac{1}{r}r\left|x^{0}\left(\textrm{mod }N\right)\right\rangle =\left|1\right\rangle \end{eqnarray*}


The state$\left|1\right\rangle $ is equal to a combination of all
the eigenvectors of $U$, and also happens to be extremely easy to
implement, making it a good initial input for phase estimation. Note
that the state $\left|1\right\rangle $ is $L$ qubits long, expressed
as $\left|0\ldots01\right\rangle $ in binary.

Showing P.E. with this initial state (following circuit diagram 5.3
again, page 223):

\begin{eqnarray*}
\left|0\right\rangle ^{\otimes t}\left|1\right\rangle  & = & \left|0\right\rangle ^{\otimes t}\frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}\left|u_{s}\right\rangle \\
 & = & \frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}\left|0\right\rangle ^{\otimes t}\left|u_{s}\right\rangle \\
 & \xrightarrow{H^{\otimes t}\otimes I} & \frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}\frac{1}{2^{t/2}}\sum_{j=0}^{2^{t}-1}\left|j\right\rangle \left|u_{s}\right\rangle \\
 & \xrightarrow{U^{j}} & \frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}\frac{1}{2^{t/2}}\sum_{j=0}^{2^{t}-1}\left|j\right\rangle U^{j}\left|u_{s}\right\rangle \\
 & = & \frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}\frac{1}{2^{t/2}}\sum_{j=0}^{2^{t}-1}\left|j\right\rangle e^{2\pi isj/r}\left|u_{s}\right\rangle \\
 & = & \sum_{s=0}^{r-1}\frac{1}{\sqrt{r}}\left(\frac{1}{2^{t/2}}\sum_{j=0}^{2^{t}-1}e^{2\pi isj/r}\left|j\right\rangle \right)\left|u_{s}\right\rangle =\left|\psi\right\rangle \\
 & \xrightarrow{F^{H}\otimes I} & \sum_{s=0}^{r-1}\frac{1}{\sqrt{r}}\left(\sum_{\ell=0}^{2^{t}-1}g\left(\varphi_{s},\ell\right)\left|\ell\right\rangle \right)\left|u_{s}\right\rangle \end{eqnarray*}


$\varphi_{s}$ is just $\frac{s}{r}$. If $\varphi_{s}2^{t}$ is an
exact whole number, then $g\left(\varphi_{s},\ell\right)$ is $1$
when $\ell=\varphi_{s}2^{t}$ and $0$ otherwise.

In the general case, assuming initial state is $\left|u_{s}\right\rangle $,
phase estimation produces an approximation with $n$ bits accuracy
satisfying $\left|\varphi-\hat{\varphi}\right|\le2^{-n}$ with probability
$\left(1-\epsilon\right)$. Since we are starting with state $\left|1\right\rangle $
instead of $\left|u_{s}\right\rangle $, the success probability is
$\ge\left(\frac{1}{\sqrt{r}}\right)^{2}\left(1-\epsilon\right)$

This success probability, which is the probability of $\hat{\varphi}$
being close to $\frac{s}{r}$ for some specific value of $s$, is
very small. In reality though, we don't care which value of $s$ (which
eigenvector) phase estimation returns the phase for, because we only
care about the ratio $\frac{s}{r}$ which we can recover from any
$s$. The success probability is high enough to allow this.


\section*{Lecture 21 (4 April)}


\subsection*{Lecture 20 Review}

Phase estimation for order finding

Initial state $\left|1\right\rangle =\frac{1}{\sqrt{r}}\sum_{s=0}^{r-1}\left|u_{s}\right\rangle $
($L$ qubits long)

U matrix given by:\[
U\left|y\right\rangle =\left\{ \begin{array}{ll}
\left|xy\textrm{ mod }N\right\rangle  & y=0,1,2,\ldots,N-1\\
\left|y\right\rangle  & y=N,N+1,\ldots,2^{L}-1\end{array}\right.\]
where $L=\left\lceil \log_{2}N\right\rceil $.

Accuracy needed is $n=2L+1$.\[
\left|\varphi_{s}-\hat{\varphi}_{s}\right|=\left|\frac{s}{r}-\hat{\varphi}_{s}\right|\le2^{-\left(2L+1\right)}\]
\[
\lambda_{s}=e^{2\pi is/r}\]
Success probability is $\frac{1}{r}\left(1-\epsilon\right)$ for each
\emph{individual} $s$ using $t=2L+1+\left\lceil \log_{2}\left(\frac{1}{2\epsilon}+2\right)\right\rceil $

Recovering denominator of $\frac{s}{r}$ is impossible for individual
numerator because success probability is too low. But overall, if
we don't care about individual values of $s$, then we can get a high
enough probability ratio.


\subsection*{Deriving order from estimated phase}

Question 2 unanswered from last time: How to get $r$ from $\hat{\varphi}_{s}$,
assuing phase estimation suceeded, or\[
\left|\frac{s}{r}-\hat{\varphi}_{s}\right|\le2^{-\left(2L+1\right)}\]
for some $s$.

Theorem: If $\left|\frac{s}{r}-\hat{\varphi}_{s}\right|\le\frac{1}{2r^{2}}$,
then $\frac{s}{r}$ is a convergent of a continued fraction for $\varphi$,
and can be computed from $\varphi$ in $O\left(L^{3}\right)$ operations,
using continued fraction algorithm. {[}Theorem 5.1, and A.4.16 p637]

It is not hard to satisfy condition needed to apply this theorem:

\begin{eqnarray*}
L=\left\lceil \log_{2}N\right\rceil  & \ge & \log_{2}N\\
2L+1 & \ge & 2\log_{2}N+1=2\log_{2}N+\log_{2}2=\log_{2}\left(2N^{2}\right)\\
-\left(2L+1\right) & \le & -\log_{2}\left(2N^{2}\right)\\
2^{-\left(2L+1\right)} & \le & 2^{-\log_{2}\left(2N^{2}\right)}=2^{\log_{2}\left(\frac{1}{2N^{2}}\right)}=\frac{1}{2N^{2}}\le\frac{1}{2r^{2}}\\
\left|\varphi-\hat{\varphi}_{s}\right| & \le & \frac{1}{2r^{2}}\end{eqnarray*}



\subsubsection*{Continued Fractions}

Any real number $x$ be represented as a sequence of integers $\left[a_{0},a_{1},\ldots a_{n}\right]$
which are terms in a continued fraction:\[
x=a_{o}+\frac{1}{a_{1}+\frac{1}{a_{2}+\frac{1}{\cdots+\frac{1}{a_{n-1}+\frac{1}{a_{n}}}}}}\]
Example:\begin{eqnarray*}
\frac{43}{18} & = & 2+\frac{7}{18}\\
 & = & 2+\frac{1}{\frac{18}{7}}\\
 & = & 2+\frac{1}{2+\frac{4}{7}}\\
 & = & 2+\frac{1}{2+\frac{1}{1+\frac{3}{4}}}\\
 & = & 2+\frac{1}{2+\frac{1}{1+\frac{1}{1+\frac{1}{3}}}}\end{eqnarray*}
The sequence of $a_{i}$ values can continue forever when $x$ is
an arbitrary real, but will end when $x$ is a rational number because
the sequence of remainders will be strictly decreasing, and the procedure
for determining $a_{i}$ terminates in $\log\left(\textrm{numerator or denominator}\right)$.
In the case of order finding, it converges in $O\left(t\right)$ or
$O\left(L\right)$steps.

Reason: The procedure divides when remainder is $\ge2$ and stops
when remainer is $1$ or $0$. Since are dividing repeatedly by numbers
which are $\ge2$, it only takes $\log N$ iterations before reaching
$0$ or $1$.

Continued fraction cost per step is $t^{2}$ for the division of a
$t$ bit number. This is $O\left(L^{2}\right)$. Total cost of the
algorithm is the cost per steps times number of steps, or $O\left(L^{3}\right)$.

{[}More information on Continued Fraction Algorithm in Appendix p635-6,
theorem A.4.15).


\subsubsection*{Continued Fractions as Simple Fractions}

Given $\left[a_{0},a_{1},\ldots,a_{N}\right]$ then $\left[a_{0},a_{1},\ldots,a_{n}\right]=\frac{P_{n}}{Q_{n}}$
for $n<N$. Running continued fraction algorithm on $\hat{\varphi}$
at some point in the middle should give the fraction $\frac{s}{r}$.

(Examples of continued fractions made into simple fractions:

$a_{0}=\frac{a_{0}}{1}$

$a_{0}+\frac{1}{a_{1}}=\frac{a_{0}a_{1}+1}{a_{1}}$

$a_{0}+\frac{1}{a_{1}+\frac{1}{a_{2}}}=a_{0}+\frac{a_{2}}{a_{1}a_{2}+1}=\frac{a_{0}a_{1}a_{2}+a_{0}+a_{2}}{a_{1}a_{2}+1}$

$a_{0}+\frac{1}{a_{1}+\frac{1}{a_{2}+\frac{1}{a_{3}}}}=a_{0}+\frac{1}{a_{1}+\frac{a_{3}}{a_{2}a_{3}+1}}=a_{0}+\frac{a_{2}a_{3}+1}{a_{1}a_{2}a_{3}+a_{1}+a_{3}}=\frac{a_{0}a_{1}a_{2}a_{3}+a_{0}a_{1}+a_{0}a_{3}+a_{2}a_{3}+1}{a_{1}a_{2}a_{3}+a_{1}+a_{3}}$

)

The following formulas give numerators and denominators without the
need for all the manipulation above:

$p_{0}=a_{0}$, $q_{0}=1$

$p_{1}=a_{0}a_{1}+1$, $q_{1}=a_{1}$

$p_{n}=a_{n}p_{n-1}+p_{n-2}$, $q_{n}=a_{n}q_{n-1}+q_{n-2}$

Examples:

\begin{tabular}{|c|c|}
\hline 
$\left[a_{0}\right]$&
$a_{0}=\frac{a_{0}}{1}=\frac{p_{0}}{q_{0}}$\tabularnewline
\hline 
$\left[a_{0},a_{1}\right]$&
$a_{0}+\frac{1}{a_{1}}=\frac{a_{0}a_{1}+1}{a_{1}}=\frac{p_{1}}{q_{1}}$ \tabularnewline
\hline 
$\left[a_{0},a_{1},a_{2}\right]$&
$a_{0}+\frac{1}{a_{1}+\frac{1}{a_{2}}}=\frac{a_{0}\left(a_{1}+\frac{1}{a_{2}}\right)+1}{a_{1}+\frac{1}{a_{2}}}=\frac{p_{1}+\frac{p_{0}}{a_{2}}}{\frac{a_{1}a_{2}+1}{a_{2}}}=\frac{p_{1}a_{2}+p_{0}}{a_{2}q_{1}+q_{0}}=\frac{p_{2}}{q_{2}}$\tabularnewline
\hline
\end{tabular}


\subsubsection*{Continued Fraction Examples}

Ex 1: $\frac{9}{15}=0+\frac{1}{\frac{15}{9}}$, continue running with
$\frac{15}{9}$

Ex 2: $0.333=\frac{333}{1000}=0+\frac{1}{\frac{1000}{333}}=0+\frac{1}{3+\frac{1}{333}}$

$p_{0}=a_{0}=0$, $q_{0}=1$, $\frac{p_{0}}{q_{0}}=0$

$p_{1}=a_{0}a_{1}+1=1$, $q_{1}=a_{1}=3$, $\frac{p_{0}}{q_{0}}=\frac{1}{3}$

$p_{2}=a_{2}p_{1}+p_{0}=333\cdot1+0=333$

$q_{2}=a_{2}q_{1}+q_{0}=333\cdot3+1=1000$

$\frac{p_{2}}{q_{2}}=\frac{333}{1000}$

If we would have started over with $\frac{1000}{333}=3+\frac{1}{333}$,
then:

$p_{0}=a_{0}=3$, $q_{0}=1$, $\frac{p_{0}}{q_{0}}=\frac{3}{1}$

$p_{1}=333\cdot3+1=1000$, $q_{1}=333\cdot1=333$, $\frac{p_{1}}{q_{1}}=\frac{1000}{333}$


\subsubsection*{Order Finding Algorithm}

Algorithm after phase estimation is classical. Get $\hat{\varphi}=\left[a_{0},\ldots,a_{m}\right]$
determine $\frac{p_{n}}{q_{n}}$, for $n=0,\ldots,m$. For each $q_{n}$,
check if $x^{q_{n}}\overset{?}{=}1\left(\textrm{mod }N\right)$. If
the equation is satisfied, then $r=q_{n}$. 

The algorithm may fail in two seperate cases:

1. If phase estimation fails

2. If $\gcd\left(s,r\right)>1$. If this is the case, recovering the
denominator of $\frac{s}{r}$ will give $r$ divided by the gcd, instead
of just $r$. $\frac{s}{r}=\frac{s'}{r'}$, $r'<r$, $x^{r}\neq1\left(\textrm{mod }N\right)$

Can overcome these types of failures by repeating algorithm, but need
to compute success probablity to know how many times to repeat. Note
that \# of primes < $r$ is $\frac{r}{2\log r}$ 

So the overall success probability is: $\frac{r}{2\log r}\frac{1}{r}\left(1-\epsilon\right)=\frac{1-\epsilon}{2\log r}\ge\frac{1-\epsilon}{2\log N}$
since $r<N$

($\frac{r}{2\log r}\frac{1}{r}$ is the probability that $s$ is prime,
since s is less than $r$)

If we repeat $2\log N$ times, then success probability of having
at least 1 success is $\ge\left(1-\left(1-\frac{1-\epsilon}{2\log N}\right)^{2\log N}\right)$

$\approx1-e^{-\frac{1-\epsilon}{2\log N}\left(2\log N\right)}=1-e^{-\left(1-\epsilon\right)}$


\section*{Lecture 22 (9 April)}


\subsection*{Review: Order Finding}

Used P.E. to get $\left|\frac{s}{r}-\hat{\varphi}\right|\le2^{-\left(2L-1\right)}$,
$L=\left\lceil \log_{2}N\right\rceil $

Use $\hat{\varphi}$ as an approximation to $\frac{s}{r}$ in continued
fraction algorithm to get $s$, $r$ individually in $O\left(L^{3}\right)$
ops. Test $x^{r}\overset{?}{=}1\left(\textrm{mod }N\right)$ with
result. If true, then finished, otherwise repeat.

The probablity that phase estimation succees and that $s$ is prime
is \[
\frac{r}{2\log r}\frac{1-\epsilon}{r}=\frac{1-\epsilon}{2\log r}\]
(where $\frac{r}{2\log r}$ is number of primes $\le r$)\[
\ge\frac{1-\epsilon}{2\log N}\]
$2\log N$ rep will yield \# succ $\ge1$ w/prob $1-e^{-\left(1-\epsilon\right)}$

Repeating overall means $O\left(L^{4}\right)=O\left(\left(\log N\right)^{4}\right)$


\subsection*{Modular Exponentiation}

(iii) How to implement $U^{j}$, or how to compute $X^{i}\left(\textrm{mod }N\right)$.
Use modular multiplication:

$0\le j\le2^{t}-1$, $j=\sum_{k=0}^{t-1}a_{k}2^{k}$, $a_{k}\in\left\{ 0,1\right\} $

$x^{j}=x^{\sum_{k=0}^{t-1}a_{k}2^{k}}=x^{a_{0}}x^{a_{1^{2}}}\cdots x^{a_{\left(n-1\right)}2^{t-1}}$

$x^{j}\left(\textrm{mod }N\right)=\left(x^{a_{0}}\cdots x^{a_{\left(n-1\right)}2^{t-1}}\right)$

Ex: $x^{5}\left(\textrm{mod }N\right)=x^{2^{2}+1}\left(\textrm{mod }N\right)$

$=\left(x^{2}\left(\textrm{mod }N\right)x^{2}\left(\textrm{mod }N\right)x\left(\textrm{mod }N\right)\right)\left(\textrm{mod }N\right)$

$N=11$, $x=5$

$5^{5}\left(\textrm{mod }N\right)=\left(\left(5^{2}\textrm{mod }N\right)\left(5^{2}\textrm{mod }N\right)\right)\left(5\textrm{mod }N\right)$

$3\cdot3\cdot5\left(\textrm{mod }11\right)=1\left(\textrm{mod }N\right)$

P.E. $U$, $U^{2}$, $U^{4}$, $U^{8}$, $U^{2^{t}-1}$ $O\left(1\right)$

$x$, $x^{2}$, $x^{4}$, $x^{8}$ 

$x$, $x\cdot x$, $x^{2}\cdot x^{2}$, $x^{4}\cdot x^{4}$ 

Why does modular multiplication work

$x_{1}=\ell_{1}N+r_{1}$

$x_{2}=\ell_{2}N+r_{2}$

$x_{1}x_{2}\left(\textrm{mod }N\right)=\left(\ell_{1}\ell_{2}N^{2}+\ell_{1}r_{2}N+\ell_{2}r_{1}N+r_{1}r_{2}\right)\left(\textrm{mod }N\right)=r_{1}r_{2}\left(\textrm{mod }N\right)$

If $U$ has different forms, not always easy to compute powers. If
it were, quantum could easily solve NP complete problems. Example
of not easy $U$:

$U=e^{iA}$, $U^{j}=e^{ijA}$


\subsection*{Factoring}

Shor's algorithm

Given composite number $N$, which we want to express as $m\cdot n$.
Application: cryptography, where the problem is assumed to be hard.
Traditional algorithm: number field sieve with time $2^{C\left(\log N\right)^{1/3}\left(\log\log N\right)^{2/3}}$,
$c$ is const $>0$.

Related to order finding.

Definitions:

$N$ - composite number

$x$, $N$ - coprime, $1<x<N$ 

$r$ - order $x^{r}=1\left(\textrm{mod }N\right)$

$L-\left\lceil \log_{2}N\right\rceil $ - bits to represent $N$ 

Theorem 1: N composite, $x$ is a nontrivial solution of $x^{2}=1\left(\textrm{mod }N\right)$.
Nontrivial means $1<x<N-1$. \begin{eqnarray*}
x^{2}-1 & = & \left(x-1\right)\left(x+1\right)\\
x & \ne & 1\left(\textrm{mod }N\right)=1\\
x & \ne & -1\left(\textrm{mod }N\right)=N-1\end{eqnarray*}


$N$ should not divide $\left(x-1\right)$ and $\left(x+1\right)$.
If true, at least one of $\gcd\left(x-1,N\right)$ or $\gcd\left(x+1,N\right)$
is a non-trivial factor, and can be computed in $O$$\left(L^{3}\right)$
operations using euclid's algorithm.

Proof

$x^{2}-1=\ell N$, equivalently, $\left(x-1\right)\left(x+1\right)=\ell N$ 

$1<x<N-1$

$x-1<N-2<N-1$

$N$ does not divide $\left(x+1\right)$

Tells you $N$ and $x-1$ or $x-1$ must have a common factor.

Take $\gcd\left(x-1,N\right)$ and $\gcd\left(x-+1,N\right)$, done.

How to compute $\gcd\left(a,b\right)$ with $a$, $b$ postive L-bit
integers:

1. If $a<b$, $\gcd\left(a,b\right)=\gcd\left(b,a\right)$, find $\max\left(a,b\right)$and
make it $a$

2. $a=\ell b+r_{1}$

$\gcd\left(a,b\right)=\gcd\left(b,r_{1}\right)$

if $r_{1}=0$ $\gcd\left(a,b\right)=b$

if $r_{1}=1$ $\gcd\left(a,b\right)=1$

else $r_{1}\ne\left(0,1\right)$ repeat

Gives a sequence of remainders $b=\ell_{2}r_{1}+r_{2}$

Example 1

$\gcd\left(6825,1430\right)=65$

\begin{eqnarray*}
6825 & = & 4\cdot1430+1105\\
1430 & = & 1\cdot1105+325\\
1105 & = & 3\cdot325+130\\
325 & = & 2\cdot130+65\\
130 & = & 2\cdot65+0\end{eqnarray*}


Example 2

$\gcd\left(7,4\right)=1$

\begin{eqnarray*}
7 & = & 1\cdot4+3\\
4 & = & 1\cdot3+1\\
3 & = & 3\cdot1+0\end{eqnarray*}


How many steps: decreasing sequence of $r_{k}$, dividing by numbers
$\ge2$, so $O\left(L\right)$ steps. Cost per step is cost per division
is $O\left(L^{2}\right)$. Total cost: $O\left(L^{3}\right)$.

Theorem 2: (no proof given). $N$ is composite and odd and $N=p_{1}^{a_{1}}p_{2}^{a_{2}}\ldots p_{m}^{a^{m}}$,
$p_{i}$ are primes, of which there are $m$ many. Choose $x\in\left\{ 1,\ldots,N-1\right\} $
uniformly at random. If $r$ is order of $x\left(\textrm{mod }N\right)$,
so $x^{r}=1\left(\textrm{mod }N\right)$, then probability $\left\{ \textrm{r even and }x^{r/2}\neq-1\left(\textrm{mod }N\right)\right\} \ge1-\frac{1}{2^{m}}.$

$x^{r/2}+1+\ell N$.

if $n=2$ prob $>1-\frac{1}{2^{2}}=\frac{3}{4}$ 

even if $n=1$ prob $>\frac{1}{2}$

If you can verify solution, even probabilities $<\frac{1}{2}$ are
ok, just repeat. As long as probability isn't exponentially tiny,
verification is all you need to get away with tiny probabilities.


\subsection*{Reduction of factoring to order finding}

High level summary, steps later

Choose random $x$ and find $r$.

$x^{r}=1\left(\textrm{mod }N\right)$

if $r$ is even $=\left(x^{r/2}\right)^{2}$ and you can use theorem
2

return $\gcd\left(x^{r/2}-1,N\right)$ or $\gcd\left(x^{r/2}+1,N\right)$

Wednesday: details, grover's algorithm


\section*{Lecture 23 (11 April)}

Theorem 1: $x^{2}=1\left(\textrm{mod }N\right)$

$\left(x-1\right)\left(x+1\right)=\ell N$ $\gcd\left(x-1,N\right)$
or $\gcd\left(x+1,N\right)$

$x\neq\pm\left(\textrm{mod }N\right)$

Ex 1: $N=15$, $x=4$, $x^{2}=16=1\left(\textrm{mod }15\right)$

$\left(x-1\right)\left(x+1\right)=15$

$\gcd\left(3,15\right)\times\gcd\left(5,15\right)=\ell N$

Both gcd's are factors

Ex 2: $N=12$, $x=7$, $x^{2}=49=1\left(\textrm{mod }12\right)$

$\left(x-1\right)\left(x+1\right)=6\cdot8=48=4\cdot12$

$\ell=4$, $N=12$

$\gcd\left(6,12\right)=6$, $\gcd\left(8,12\right)=4$

$6\cdot4\ne12$, both gcd's are not factors

Therefore take one gcd, get another factor by division.Look at pages
15-16 of schor's papers.


\subsection*{Reduction to order finding}

Choose $x\in\left\{ 1,\ldots,N-1\right\} $

Find order r, $x^{r}=1\left(\textrm{mod }N\right)$, use theorem

If r is even $\left(x^{r/2}-1\right)\left(x^{r/2}+1\right)=\ell N$ 

then $\gcd\left(x^{2}-1,N\right)$ or $\gcd\left(x^{2}+1,N\right)$

there are constraints, we cover them later

assuming r is even, assuming not a trivial solution (as indicated
by theorem). In even case, you know $x^{r/2}\ne1\left(\textrm{mod }N\right)$
because $r$ is order, order is smallest $r$.

Theorem: If $N$ is odd and composite and factors as $N=p_{1}^{\alpha_{1}}p_{2}^{\alpha_{2}}\ldots p_{n}^{\alpha_{n}}$
$p_{n}$ primes and pick one $X=\left\{ 1,\ldots,N-1\right\} $ uniformly
at random. $Pr\left\{ \textrm{r even and }x^{r/2}\neq-1\left(\textrm{mod }N\right)\right\} \ge1-\frac{1}{2^{n}}$


\subsection*{Shor Factoring Algorithm}

Input: Composite number N

Output: Factor of N

Runtime: $O\left(L^{3}\right)=O\left(\left(\log N\right)^{3}\right)$

Probability success $\ge\frac{3}{4}$ 

Steps:

1. If $N$ even output 2

2. Determine if $N=a^{b}$, for some $a\ge1$, $b\ge2$. If so, determine
$n$ and stop.

3. Uniformly chose $x\in\left\{ 1,\ldots,N-1\right\} $. If $\gcd\left(x,N\right)>1m$
return $\gcd\left(x,N\right)$.

4. Only quantum step. Use order finding algorithm, obtain $r$ order
of $x$ mod $N$.

5. If $r$ is even and $x^{r/2}\ne-1\left(\textrm{mod }N\right)$,
then return $\gcd\left(x^{r/2}-1,N\right)$ or $\gcd\left(x^{r/2}+1,N\right)$
doesn't matter which. Otherwise algorithm fails.

Remarks

Step 1: Step 1 is easy

Step 2: How to check $N=a^{b}$ for $a\ge3$, $b\ge2$, we know $b\le\log N\le L$

$b=\left\{ 2,3,4,\ldots,L\right\} $

Check if $a^{k}=N$ for each $b$ and integer $a$. Book uses algorithm
to find $a$, but you can use binary search. Bisection isn't so bad
because only need sign information, don't need to compute whole powers.
Cost of bisection in $\log N=L$ steps, error $\le\frac{1}{2N}$,
cost per step is cost of repeated querying $O\left(\log\log N\right)$.
Total cost $O\left(\log^{2}N\log\log N\right)$

Alternative: Newton's method

$x_{i+1}=x_{i}-\frac{f\left(x\right)}{f'\left(x\right)}=x_{i}-\frac{x_{i}^{-b}-N}{bx_{i}^{b-1}}$

$\left|x_{i}-N^{1/b}\right|=O\left(\left|x_{i}-N^{1/b}\right|^{2}\right)$

Quadratic convergence, taking as few steps as needed.

After steps 1 and 2 know $x$ is odd and has more than one prime factor.

Combine w/ theorem 2 to see that prob $\ge\frac{3}{4}=1-\frac{1}{2^{2}}$.
2 is number of factors ($2>1$).

Step 3: Use euclid algorithm with cost $O\left(L^{3}\right)=O\left(\log^{3}N\right)$
to get $\gcd\left(x,N\right)$. if $>1$ stop, else continue knowing
$x$,$N$ are coprime.

Step 4: $x$, $N$ coprime, so order finding. Cost $O\left(L^{3}\right)$
or $O\left(L^{4}\right)$, depending which way you do, not significant.
Gives $r$, so $x^{r}=1\left(\textrm{mod }N\right)$. 

Theorem 2: $Pr\left\{ \textrm{r even and }x^{r/2}\ne-1\left(\textrm{mod }N\right)\right\} \ge1-\frac{1}{2^{2}}=\frac{3}{4}$. 

Step 5: Check r even

$x^{r/2}\ne-1\left(\textrm{mod }N\right)$?

If so, $\gcd\left(x^{r/2}-1,N\right)$ or $\gcd\left(x^{r/2}+1,N\right)$ 

Example:

$N=a\left(13\times7\right)$

1. Not even

2. Not $N\ne a^{b}$

3. Say $x=4$, $\gcd\left(4,9\right)=1$ coprime

4. Order of $x=4\left(\textrm{mod }91\right)=1$

$r=6$, $4^{6}=2^{12}=4096=1\left(\textrm{mod }91\right)$

$4096=45\cdot91+1$

5. $r=6$ even

$x^{r/2}=4^{3}=2^{6}=64=64\left(\textrm{mod }91\right)\ne-1\left(\textrm{mod }91\right)$

$\gcd\left(63,91\right)=\gcd\left(63,28\right)=\gcd\left(28,7\right)=7$

$\gcd\left(65,91\right)=\gcd\left(65,26\right)=\gcd\left(26,13\right)=13$

Both of them are not factors, but they are both divisors.


\subsection*{Search, counting algorithms}

Grover's algorithms

Boolean mean, Brascyd et al (amplitude, amplification, estimations)

Applications many problems science / engineering, integration, approximation,
path integrations, differential equations (Schrodinger eqn).


\section*{Lecture 24 (16 April)}


\subsection*{Searching / Counting Algorithm}

Given a function\[
f:\left\{ 0,1,\ldots,N-1\right\} \rightarrow\left\{ 0,1\right\} \]
as in Deutsch Josza, find which inputs produce an output.

$N=2^{n}$, $N$ is huge

We use queries, or oracle calls\[
Q_{f}\left|x\right\rangle \left|y\right\rangle =\left|x\right\rangle \left|y\oplus f\left(x\right)\right\rangle \]
$\left|x\right\rangle $ is $n$ qubits, $\left|y\right\rangle $
is 1 qubit.

Using $H\left|1\right\rangle $ as an input:

\begin{eqnarray*}
Q_{f}\left|x\right\rangle \frac{\left|0\right\rangle -\left|1\right\rangle }{\sqrt{2}} & = & \frac{1}{\sqrt{2}}\left(\left|x\right\rangle \left|0\oplus f\left(x\right)\right\rangle -\left|x\right\rangle \left|1\oplus f\left(x\right)\right\rangle \right)\\
 & = & \frac{1}{\sqrt{2}}\left(\left|x\right\rangle \left|f\left(x\right)\right\rangle -\left|x\right\rangle \left|\overline{f\left(x\right)}\right\rangle \right)\end{eqnarray*}
if $f\left(x\right)=0$ then $\left|x\right\rangle \frac{\left|0\right\rangle -\left|1\right\rangle }{\sqrt{2}}$.

if $f\left(x\right)=1$ then $\left|x\right\rangle \frac{\left|1\right\rangle -\left|0\right\rangle }{\sqrt{2}}$.\begin{eqnarray*}
Q_{f}\left|x\right\rangle \frac{\left|0\right\rangle -\left|1\right\rangle }{\sqrt{2}} & = & \left(-1\right)^{f\left(x\right)}\left|x\right\rangle \frac{\left|0\right\rangle -\left|1\right\rangle }{\sqrt{2}}\end{eqnarray*}
With this input, the $\left|y\right\rangle $ qubit is unchanged,
there is just an overall phase shift. This is more convenient for
analysis than the general $Q_{f}\left|x\right\rangle \left|y\right\rangle $
function.


\subsection*{Search}

\begin{eqnarray*}
M_{f} & = & \left\{ x:f\left(x\right)=1\right\} \\
M & = & \left|M_{f}\right|\ge1\end{eqnarray*}
Problem is to find elements of $M_{f}$. This is a reverse lookup
problem, like searching an unordered database. Unlike the quantum
solution for the factoring problem, the quantum solution for this
problem is not exponentially faster, just polylog. Another difference
is that this quantum solution beats the upper bound of the equivalent
classical solution, whereas the quantum factoring algorithm only beats
known classical algorithms.

Related Problem: Boolean Mean

\[
S\left(f\right)=\frac{1}{N}\sum_{x=0}^{N-1}f\left(x\right)=\frac{M}{N}\]



\subsubsection*{Classsical Search Algorithms}

1. Deterministic Algorithm. Lower bound $O\left(N\right)$, because
you may have to evaluate $N$ times before search succeeds.

2. Randomized Algorithms. (See paper Beals et al). Lower bound is
also $O\left(N\right)$. No proof, but basic idea follows.

Algorithm:

Choose $x$ uniformly at random with replacement.

If $f\left(x\right)=1$ stop with success.

If $f\left(x\right)=0$ fail.

Repeat $k$ times.

Probability of failure first time is $1-\frac{M}{N}$. If $M=1$,
$1-\frac{1}{N}>C$.

Probability to fail in $k$ trials is $\left(1-\frac{M}{N}\right)^{k}\le\delta$.
Set desired tolerance to $\delta$.\[
k\log\left(1-\frac{M}{N}\right)=\log\delta\]
\begin{eqnarray*}
k & = & \frac{\log d}{\log\left(1-\frac{M}{N}\right)}\approx\frac{\log d}{-\frac{M}{N}}=\frac{N}{M}\log\frac{1}{d}\end{eqnarray*}
Approximation holds when $M\ll N$. In this case, algorithm is $O\left(N\right)$,
in general case algorithm is $O\left(\frac{N}{M}\right)$.

General hint: $\log\left(1+x\right)\approx x$ when $x$ is tiny.
This is used frequently in complexity analysis, and is based on the
power series expansion.

When algorithm is run without replacement, probability of failure
is\[
\frac{\left(\begin{array}{c}
N-M\\
k\end{array}\right)\left(\begin{array}{c}
M\\
0\end{array}\right)}{\left(\begin{array}{c}
N\\
k\end{array}\right)}=\frac{\left(\begin{array}{c}
N-1\\
k\end{array}\right)}{\left(\begin{array}{c}
N\\
k\end{array}\right)}=\frac{\left(N-1\right)!}{k!\left(N-k-1\right)!}=\frac{N-k}{N}=1-\frac{k}{N}\]
this is bounded by a constant unless $k$ is $O\left(N\right)$


\subsubsection*{Repeating\[
\left(1-\frac{k}{N}\right)^{S}\le\delta\]
\[
S=\frac{N}{k}\log\frac{1}{\delta}\Rightarrow S_{k}=N\log\frac{1}{\delta}=O\left(N\right)\]
}


\subsubsection*{Quantum Search Algorithm}

Grover's Algorithm, $O\left(\sqrt{\frac{N}{M}}\right)$ counting the
number of queries of $Q_{f}$.

Algorithm: Given some initial state $\left|\psi_{0}\right\rangle $.
Apply operator then query, then operator, repeating as neccesary.
\[
\left|\psi_{1}\right\rangle =Q_{F}U_{T}Q_{F}U_{T-1}\ldots U_{2}Q_{F}U_{1}\left|\psi_{0}\right\rangle \]


using $T$ queries.


\subsection*{Boolean Mean}

\[
S\left(f\right)=\frac{1}{N}\sum_{x=0}^{N-1}f\left(x\right)=\frac{M}{N}\]



\subsubsection*{Classical Algorithms}

1. Deterministic Algorithm. Find lower bound on number of evaluations
given error tolerance $\epsilon$. To do this we need to ensure\[
\max_{f}\left|S\left(f\right)-\hat{S}\left(f\right)\right|\le\epsilon\]
For $k$ evaluations, assume $f\left(x\right)=0$ to get lower bound,
we then know that $0\le S\left(f\right)\le\frac{M-k}{N}$. Take an
estimate at the middle of this range to get least possible error in
worst case: \[
\hat{S}\left(f\right)=\frac{0+\left(1-\frac{k}{N}\right)}{2}\]
In this case\[
\max_{f}\left|S\left(f\right)-\hat{S}\left(f\right)\right|^{2}=\frac{1}{2}\left(1-\frac{k}{N}\right)\]
\begin{eqnarray*}
\frac{1}{2}\left(1-\frac{k}{N}\right) & < & \epsilon\\
N-k & \le & 2N\epsilon\\
k & \ge & N\left(1-2\epsilon\right)\end{eqnarray*}



\section*{Lecture 25 (18 April)}


\subsection*{Searching + Counting}

Classical Algorithms, Deterministic and Random $O\left(N\right)$,
$1\le M\ll N$. 

Quantum Algorithm $O\left(\sqrt{\frac{N}{M}}\right)$


\subsection*{Counting / Boolean Mean}

Classical deterministic algorithm: $k\ge N\left(1-2\epsilon\right)$

Classical randomized algorithm: Choose $k$ inputs at random computing
\[
\hat{S}\left(f\right)=\frac{1}{k}\sum_{i=1}^{k}f\left(x_{i}\right)\]
\[
k:x_{i}\in\left\{ 0,\ldots,N-1\right\} \]
This is a Monte Carlo algorithm. Instead of finding the lower bound
error, find the expected error\[
\left(E_{x_{1}\ldots x_{k}}\left[S\left(f\right)-\hat{S}\left(f\right)\right]^{2}\right)^{1/2}\le\frac{1}{\sqrt{k}}<\epsilon\]
\[
k=\min\left(\frac{1}{\epsilon^{2}},N\right)\]
Chebyshev inequality\begin{eqnarray*}
Pr\left\{ \left|S\left(f\right)-\hat{S}\left(f\right)\right|>\tau\right\}  & \le & \frac{E\left(\left(S\left(f\right)-\hat{S}\left(f\right)\right)^{2}\right)}{\tau^{2}}\\
\tau & = & 2\epsilon\\
Pr\left\{ \left|S\left(f\right)-\hat{S}\left(f\right)\right|>2\epsilon\right\}  & \le & \frac{E\left(\left(S\left(f\right)-\hat{S}\left(f\right)\right)^{2}\right)}{4\epsilon^{2}}\end{eqnarray*}
\[
k=\min\left(\frac{1}{\epsilon},N\right)\]



\subsubsection*{Quantum Algorithm}

Provides provable polynomial speedup over classical randomized algorithm.
This is unlike factoring where there is no known lower bound and we
are beating known classical algorithms without any proof that there
isn't an unknown classical algorithm which could be faster.


\subsection*{Grover's Search}

1. Apply oracle $Q_{f}$ (from Deutsch-Jozsa) or the nice oracle $O_{f}$
(from previous lecture), $O_{f}\left|x\right\rangle =\left(-1\right)^{f\left(x\right)}\left|x\right\rangle $.

2. Apply $H^{\otimes n}$

3. Apply phase shift $Q_{0}$ which is a reflaction about $\left|0\right\rangle $
\begin{eqnarray*}
Q_{0} & = & 2\left|0\right\rangle \left\langle 0\right|-I\\
Q_{0}\left|0\right\rangle  & = & 2\left|0\right\rangle \left\langle 0|0\right\rangle -I\left|0\right\rangle =\left|0\right\rangle \\
Q_{0}\left|y\right\rangle  & = & 2\left|0\right\rangle \left\langle 0|y\right\rangle -I\left|y\right\rangle =-\left|y\right\rangle ,\: y\ne0\end{eqnarray*}
so for any basis state $\left|y\right\rangle $ \[
Q_{0}\left|y\right\rangle =\left(-1\right)^{\delta_{0}y}\left|y\right\rangle \:\forall y=0,\ldots,N-1\]


4. Apply $H^{\otimes n}$

All 4 operations can be combined with one operator\begin{eqnarray*}
G & = & H^{\otimes n}\left(2\left|0\right\rangle \left\langle 0\right|-I\right)H^{\otimes n}O_{f}\\
 & = & \left(2H^{\otimes n}\left|0\right\rangle \left\langle 0\right|H^{\otimes n}-H^{\otimes n}H^{\otimes n}\right)O_{f}\\
 & = & \left(2\left|\psi\right\rangle \left\langle \psi\right|-I\right)O_{f}\end{eqnarray*}
where\[
\left|\psi\right\rangle =\frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\left|j\right\rangle \]
$2\left|\psi\right\rangle \left\langle \psi\right|-I$ acts as a reflection
about $\left|\psi\right\rangle $ because for $\left|z\right\rangle \perp\left|\psi\right\rangle $
\begin{eqnarray*}
\left(2\left|\psi\right\rangle \left\langle \psi\right|-I\right)\left|\psi\right\rangle  & = & \left|\psi\right\rangle \\
\left(2\left|\psi\right\rangle \left\langle \psi\right|-I\right)\left|z\right\rangle  & = & -\left|z\right\rangle \end{eqnarray*}



\subsection*{Analysis}

\[
M_{f}=\left\{ x:f\left(x\right)=1\right\} ,\:1\le M=\left|M_{f}\right|\le N-1\]


Define two states$\left|\alpha\right\rangle $ and $\left|\beta\right\rangle $
so \begin{eqnarray*}
\left|\alpha\right\rangle  & = & \frac{1}{\sqrt{N-M}}\sum_{x\notin M_{f}}\left|x\right\rangle \\
\left|\beta\right\rangle  & = & \frac{1}{\sqrt{M}}\sum_{x\in M_{f}}\left|x\right\rangle \end{eqnarray*}
$\left\Vert \left|\alpha\right\rangle \right\Vert =\left\Vert \left|b\right\rangle \right\Vert =1$
and $\left\langle a|b\right\rangle =0$\begin{eqnarray*}
\left|\psi\right\rangle  & = & \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\left|j\right\rangle \\
 & = & \frac{1}{\sqrt{N}}\left(\sqrt{N-M}\left|\alpha\right\rangle +\sqrt{M}\left|\beta\right\rangle \right)\\
 & = & \frac{\sqrt{N-M}}{\sqrt{N}}\left|\alpha\right\rangle +\frac{\sqrt{M}}{\sqrt{N}}\left|\beta\right\rangle \end{eqnarray*}
Idea of algorithm is to boost change initial state $\left|\psi\right\rangle $
boosting the amplitude of $\left|\beta\right\rangle $ so the state
that is measured will likely be in $M_{f}$.\begin{eqnarray*}
\left|\psi\right\rangle  & = & \left\langle \alpha|\psi\right\rangle \left|\alpha\right\rangle +\left\langle \beta|\psi\right\rangle \left|\beta\right\rangle \\
\left\langle \alpha|\psi\right\rangle  & = & \frac{1}{\sqrt{N-M}}\frac{1}{\sqrt{N}}\sum_{x\notin M_{f}}\sum_{y=0}^{N-1}\left\langle x|y\right\rangle \\
 & = & \frac{1}{\sqrt{N-M}}\frac{1}{\sqrt{N}}\sum_{x\notin M_{f}}1\\
 & = & \frac{1}{\sqrt{N-M}}\frac{1}{\sqrt{N}}\left(N-M\right)\\
 & = & \sqrt{\frac{N-M}{N}}\end{eqnarray*}
Similarly for $\left|\beta\right\rangle .$ Because $\left\Vert \left|\psi\right\rangle \right\Vert ^{2}=\frac{N-M}{N}\left\Vert \left|\alpha\right\rangle \right\Vert ^{2}+\frac{M}{N}\left\Vert \left|\beta\right\rangle \right\Vert ^{2}=1$,
$\left|\psi\right\rangle $ can be written as\[
\left|\psi\right\rangle =\cos\frac{\vartheta}{2}\left|\alpha\right\rangle +\sin\frac{\vartheta}{2}\left|\beta\right\rangle \]
where \begin{eqnarray*}
\cos\frac{\vartheta}{2} & = & \sqrt{\frac{N-M}{N}}\\
\sin\frac{\vartheta}{2} & = & \sqrt{\frac{M}{N}}\end{eqnarray*}



\subsubsection*{Powers of G}

Want to determine $G\left|\psi\right\rangle ,G^{2}\left|\psi\right\rangle ,G^{3}\left|\psi\right\rangle ,\ldots,G^{k}\left|\psi\right\rangle $\begin{eqnarray*}
G & = & \left(2\left|\psi\right\rangle \left\langle \psi\right|-I\right)O_{f}\\
O_{f}\left|\alpha\right\rangle  & = & \frac{1}{\sqrt{N-M}}\sum_{x\notin M_{f}}O_{f}\left|x\right\rangle \\
 & = & \frac{1}{\sqrt{N-M}}\sum_{x\notin M_{f}}\left(-1\right)^{f\left(x\right)=1}\left|x\right\rangle \\
 & = & \left|\alpha\right\rangle \\
O_{f}\left|\beta\right\rangle  & = & \frac{1}{\sqrt{M}}\sum_{x\in M_{f}}O_{f}\left|x\right\rangle \\
 & = & \frac{1}{\sqrt{M}}\sum_{x\in M_{f}}\left(-1\right)^{f\left(x\right)=1}\left|x\right\rangle \\
 & = & -\left|\beta\right\rangle \end{eqnarray*}
So when operator $O_{f}$ is applied to $\left|\alpha\right\rangle $,
it is unchanged. When the operator is applied to $\left|\beta\right\rangle $
it is reflected. Given this, we can see $G$ applied to a state creates
a rotation of that state in the $\left|\alpha\right\rangle $, $\left|\beta\right\rangle $
plane. Previously we showed expressed $\left|\psi\right\rangle $
in terms of an angle $\frac{\vartheta}{2}$ \[
\left|\psi\right\rangle =\cos\frac{\vartheta}{2}\left|\alpha\right\rangle +\sin\frac{\vartheta}{2}\left|\beta\right\rangle \]
allowing the state $\left|\psi\right\rangle $ to be represented graphically
as a 2 dimensional vector in the $\left|\alpha\right\rangle ,\left|\beta\right\rangle $
plane oriented $\frac{\vartheta}{2}$ degrees above the $\left|\alpha\right\rangle $
axis. Applying $O_{f}$ to this state negates $\left|\beta\right\rangle $
component reflecting it about the $\left|\alpha\right\rangle $ axis
resulting in a vector $\frac{\vartheta}{2}$ degrees below the $\left|\alpha\right\rangle $
axis. Applying $2\left|\psi\right\rangle \left\langle \psi\right|-I$
is the same as a reflection about $\left|\psi\right\rangle $. This
results in a state oriented $\frac{\vartheta}{2}+\left(\frac{\vartheta}{2}--\frac{\vartheta}{2}\right)=\frac{3\vartheta}{2}$
degrees above the $\left|\alpha\right\rangle $ axis. ($\frac{\vartheta}{2}$
being the angle of the $\left|\psi\right\rangle $ state relative
to $\left|\alpha\right\rangle $, $\left(\frac{\vartheta}{2}--\frac{\vartheta}{2}\right)$
being the angular distance between $\left|\psi\right\rangle $ and
$O_{f}\left|\psi\right\rangle $). The result of the two reflections
is \[
G\left|\psi\right\rangle =\cos\frac{3\vartheta}{2}\left|\alpha\right\rangle +\sin\frac{3\vartheta}{2}\left|\beta\right\rangle \]
which taken together are equivalent to a rotation by $2\vartheta$.
Applying the $G$ operator repeatedly is then equivalent to \[
G^{k}\left|\psi\right\rangle =\cos\left(\frac{2k+1}{2}\vartheta\right)\left|\alpha\right\rangle +\sin\left(\frac{2k+1}{2}\vartheta\right)\left|\beta\right\rangle \]
when a good value for $k$ is chosen, $\sin\left(\frac{2k+1}{2}\vartheta\right)$
will be close to 1 and measuring $G^{k}\left|\psi\right\rangle $
will yield a state from the $\left|\beta\right\rangle $ superposition
with high probability. Recall that any state in $\left|\beta\right\rangle $
is a solution to the search problem. More formally, for a measurement
$\left|x\right\rangle $ on the computational basis\begin{eqnarray*}
Pr\left\{ x\in M_{f}\right\}  & = & \sin^{2}\left(\frac{2k+1}{2}\vartheta\right)\end{eqnarray*}



\section*{Lecture 26 (23 April)}


\subsection*{Grover's Review}

\begin{eqnarray*}
G & = & H^{\otimes n}\left(2\left|0\right\rangle \left\langle 0\right|-I\right)H^{\otimes n}O_{f}\\
 & = & \left(2\left|\psi\right\rangle \left\langle \psi\right|-I\right)O_{f}\\
O_{f}\left|x\right\rangle  & = & \left(-1\right)^{f\left(x\right)}\left|x\right\rangle \\
\left|\alpha\right\rangle  & = & \frac{1}{\sqrt{N-M}}\sum_{x\notin M_{f}}\left|x\right\rangle \\
\left|\beta\right\rangle  & = & \frac{1}{\sqrt{M}}\sum_{x\in M_{f}}\left|x\right\rangle \\
\left|\psi\right\rangle  & = & \frac{1}{\sqrt{N}}\sum_{j=0}^{N-1}\left|j\right\rangle =H^{\otimes n}\left|0\right\rangle ^{\otimes n}\\
G^{k}\left|\psi\right\rangle  & = & \cos\left(\frac{2k+1}{2}\vartheta\right)\left|\alpha\right\rangle +\sin\left(\frac{2k+1}{2}\vartheta\right)\left|\beta\right\rangle \\
\sin\left(\frac{\vartheta}{2}\right) & = & \sqrt{\frac{M}{N}}\\
\cos\left(\frac{\vartheta}{2}\right) & = & \sqrt{\frac{M-N}{N}}\end{eqnarray*}



\subsection*{Grover's Analyis (continued)}

Need to find value of $k$ that gives $G^{k}\left|\psi\right\rangle $
close to $\left|\beta\right\rangle $. Start with success probability
of algorithm assuming $k$ is known. For $x\in M_{f}$\begin{eqnarray*}
\left\langle x\right|G^{k}\left|\psi\right\rangle  & = & \left|\sin\left(\frac{2k+1}{2}\vartheta\right)\left\langle x|\beta\right\rangle \right|^{2}\\
 & = & \left|\sin\left(\frac{2k+1}{2}\vartheta\right)\frac{1}{\sqrt{M}}\right|^{2}\\
 & = & \sin^{2}\left(\frac{2k+1}{2}\vartheta\right)\frac{1}{M}\\
Pr\left\{ \textrm{measuring }x\in M_{f}\right\}  & = & M\sin^{2}\left(\frac{2k+1}{2}\vartheta\right)\frac{1}{M}\\
 & = & \sin^{2}\left(\frac{2k+1}{2}\vartheta\right)\frac{1}{M}\end{eqnarray*}
Success probability is therefore $\sin^{2}\left(\frac{2k+1}{2}\vartheta\right)$
given a $k$. $\frac{2k+1}{2}\vartheta$ should be close to $\frac{\pi}{2}$,
so \[
\frac{\pi}{2}-\frac{\vartheta}{2}\le\frac{2k+1}{2}\vartheta<\frac{\pi}{2}+\frac{\vartheta}{2}\]
If $\frac{M}{N}<\frac{1}{2}$ then $\sqrt{\frac{M}{N}}=\sin\frac{\vartheta}{2}<\sin\frac{\pi}{4}=\sqrt{\frac{1}{2}}$
and $0\le\vartheta\le\frac{\pi}{2}$\[
\pi-\vartheta\le\left(2k+1\right)\vartheta<\pi+\vartheta\]
\[
\frac{\pi}{\vartheta}-1\le2k+1<\frac{\pi}{\vartheta}+1\]
\[
\frac{\pi}{2\vartheta}-1\le k<\frac{\pi}{2\vartheta}\]


$\sqrt{\frac{M}{N}}=\sin\frac{\vartheta}{2}\approx\frac{\vartheta}{2}$,
a valid approximation when $\vartheta$ is tiny. In this case $\varphi\approx2\sqrt{\frac{M}{N}}$,
and $k=\frac{\pi}{2\vartheta}\approx\frac{\pi}{4}\sqrt{\frac{N}{M}}$,
so a good $k$ can be set $k=\left\lceil \frac{\pi}{4}\sqrt{\frac{N}{M}}\right\rceil $,
making the complexity of the algorithm in terms of oracle calls $O\left(N\right)$.

When $M$ is larger, you need a more precise analysis without the
approximation. In this case use\begin{eqnarray*}
\sin\frac{\vartheta}{2} & = & \sqrt{\frac{M}{N}}\\
\cos\frac{\vartheta}{2} & = & \sqrt{\frac{N-M}{N}}\end{eqnarray*}
Then use a trig identity\begin{eqnarray*}
\sin\vartheta & = & 2\sin\frac{\vartheta}{2}\cos\frac{\vartheta}{2}=2\sqrt{\frac{M}{N}}\sqrt{\frac{N-M}{N}}\\
\varphi & = & \arcsin\left(2\sqrt{\frac{M\left(N-M\right)}{N^{2}}}\right)\\
k & = & \frac{\pi}{2\vartheta}\end{eqnarray*}
To see what happens when $\frac{M}{N}\ge\frac{1}{2}$ look at the
relation\[
\sin^{2}\vartheta=\frac{4M\left(N-M\right)}{N^{2}}=4\frac{M}{N}\left(1-\frac{M}{N}\right)\]
and note that $\vartheta$ gets smaller as $M$ increases from $\frac{N}{2}$
to $N$. Because $\vartheta$ gets smaller, $k$ gets larger, and
algorithm gets slower to the point where it is not better than a random
classical algorithm. 


\subsection*{Grover's Algorithm Circuit}

\[
\textrm{Circuit: }\left(G^{k}\right)\left(H^{\otimes n}\otimes I\right)\left(\left|0\right\rangle ^{\otimes n}\otimes\frac{\left|0\right\rangle -\left|1\right\rangle }{\sqrt{2}}\right)\]
(Diagram Figure 6.1, Page 251)

\begin{eqnarray*}
\left|0\right\rangle ^{\otimes t}\frac{\left|0\right\rangle -\left|1\right\rangle }{\sqrt{2}} & \xrightarrow{H^{\otimes n}\otimes I} & \left|\psi\right\rangle \frac{\left|0\right\rangle -\left|1\right\rangle }{\sqrt{2}}\\
 & \xrightarrow{G^{k}} & \left(\cos\left(\frac{2k+1}{2}\vartheta\right)\left|\alpha\right\rangle +\sin\left(\frac{2k+1}{2}\vartheta\right)\left|\beta\right\rangle \right)\frac{\left|0\right\rangle -\left|1\right\rangle }{\sqrt{2}}\end{eqnarray*}



\subsection*{Estimating M}

Grovers assumes $M$ is known. If $M$ is unknown, there are two approaches.

1. Brasard, et al. Apply $G^{j}$ for random $j$, and show expected
number of steps is $O\left(\sqrt{N/M}\right)$. 

2. Find $M$ using $\sin\frac{\vartheta}{2}=\sqrt{\frac{M}{N}}$ and
estimating $\vartheta$. Since this also gives you the boolean mean
it lets you {}``hit 2 birds for the price of one.'' We cover this
second approach.\begin{eqnarray*}
G & = & \left(2\left|\psi\right\rangle \left\langle \psi\right|-I\right)O_{f}\\
G\left|\alpha\right\rangle  & = & \cos\left(\vartheta\right)\left|\alpha\right\rangle +\sin\left(\vartheta\right)\left|\beta\right\rangle \\
G\left|\beta\right\rangle  & = & \cos\left(\vartheta+\frac{\pi}{2}\right)\left|\alpha\right\rangle +\sin\left(\varphi+\frac{\pi}{2}\right)\left|\beta\right\rangle \\
 & = & -\sin\left(\vartheta\right)\left|\alpha\right\rangle +\cos\left(\vartheta\right)\left|\beta\right\rangle \end{eqnarray*}
The effect of $G$ on the $\left|\alpha\right\rangle $ vector above
is determined by looking at reflections and rotations on the $\left|\alpha\right\rangle $,
$\left|\beta\right\rangle $ plane (Figure 6.3, page 253). Applying
$O_{f}$ to $\left|\alpha\right\rangle $ does not change anything
because as shown earlier, $O_{f}$ is a reflection about the $\left|\alpha\right\rangle $
axis. Applying $\left(2\left|\psi\right\rangle \left\langle \psi\right|-I\right)$
to $\left|\alpha\right\rangle $ reflects the state about $\left|\psi\right\rangle $.
Since $\left|\psi\right\rangle $ is $\frac{\vartheta}{2}$ degrees
above $\left|\alpha\right\rangle $, reflecting $\left|\alpha\right\rangle $
about it is equivalent to rotating the state by $2\cdot\frac{\vartheta}{2}=\vartheta$
degrees. The resulting vector has magnitudes of $\cos\left(\vartheta\right)$
in the $\left|\alpha\right\rangle $ direction and $\sin\left(\vartheta\right)$
in the $\left|\beta\right\rangle $ direction. $G\left|\beta\right\rangle $
is derived similarly. The relation above can be used to express $G$
as a transformation on the $\left|\alpha\right\rangle ,$ $\left|\beta\right\rangle $
basis:\[
G=\left(\begin{array}{cc}
\cos\vartheta & -\sin\vartheta\\
\sin\vartheta & \cos\vartheta\end{array}\right)\]


The eigenvalues of $G$ are given by\begin{eqnarray*}
0 & = & \left|\begin{array}{cc}
\cos\vartheta-\lambda & -\sin\vartheta\\
\sin\vartheta & \cos\vartheta-\lambda\end{array}\right|\\
 & = & \left(\cos\left(\vartheta\right)-\lambda\right)^{2}+\sin^{2}\left(\vartheta\right)\\
\left(\cos\left(\vartheta\right)-\lambda\right)^{2} & = & -\sin^{2}\left(\vartheta\right)\\
\cos\left(\vartheta\right)-\lambda & = & \pm i\sin\left(\vartheta\right)\\
\lambda & = & \cos\left(\vartheta\right)\pm i\sin\left(\vartheta\right)\\
 & = & e^{\pm i\vartheta}\end{eqnarray*}
Phase estimation is performed on $G$ to find $\vartheta$, which
can in turn be used to find $M$ and $k$.


\section*{Lecture 27 (25 April)}


\subsection*{Review: Grover's Algorithm}

$G^{k}$, $k=\frac{\pi}{2\vartheta}$, $\sin\frac{\vartheta}{2}=\sqrt{\frac{M}{N}}$

When $M$ is small, the following approximation for $k$ is valid:
$k\approx\left\lceil \frac{\pi}{4}\sqrt{\frac{M}{N}}\right\rceil $ 

Otherwise $k$ can be found using $\vartheta=\arcsin\left(2\frac{M\left(N-M\right)}{N^{2}}\right)$.

If $M=1$, $k=O\left(\sqrt{N}\right)$

If $M$ is unknown, can use estimate of $\vartheta$ to find it. Estimating
$\vartheta$ happens with phase estimation on $G$, which expressed
as a transformation on the $\left|\alpha\right\rangle $, $\left|\beta\right\rangle $
basis looks like\[
G=\left(\begin{array}{cc}
\cos\vartheta & -\sin\vartheta\\
\sin\vartheta & \cos\vartheta\end{array}\right)\]
and has eigenvalues, $\lambda_{\pm}=e^{\pm i\vartheta}$.


\subsection*{Phase Estimation for $\vartheta$}

Phase estimation requires us to generate an initial state which approximates
one or more eigenvectors of $G$. 


\subsubsection*{Finding Eigenvectors of G}

Denote unknown eigenvector as $\left(x\left|\alpha\right\rangle +y\left|\beta\right\rangle \right)$
so:\[
G\left(x\left|\alpha\right\rangle +y\left|\beta\right\rangle \right)=e^{\pm i\vartheta}\left(x\left|\alpha\right\rangle +y\left|\beta\right\rangle \right)\]
Expanding the left side gives:\begin{eqnarray*}
xG\left|\alpha\right\rangle +yG\left|\beta\right\rangle  & = & x\left(\cos\vartheta\left|\alpha\right\rangle +\sin\vartheta\left|\beta\right\rangle \right)+y\left(-\sin\vartheta\left|\alpha\right\rangle +\cos\vartheta\left|\beta\right\rangle \right)\end{eqnarray*}
Which is true when $x\cos\vartheta-y\sin\vartheta=xe^{\pm i\vartheta}$
and $x\sin\vartheta+y\cos\vartheta=ye^{\pm i\vartheta}$

\begin{eqnarray*}
x\cos\vartheta-y\sin\vartheta & = & xe^{\pm ig}\\
x\cos\vartheta-y\sin\vartheta & = & x\left(\cos\vartheta\pm i\sin\vartheta\right)\\
-y & = & \pm ix\textrm{ when }\sin\vartheta\ne0,\frac{\vartheta}{2}\ne k\frac{\pi}{2}\end{eqnarray*}
Which gives eigenvector of the form $x\left|\alpha\right\rangle \pm ix\left|\beta\right\rangle $.
Normalized, the eigenvectors are \begin{eqnarray*}
\left|\psi_{+}\right\rangle  & = & \frac{\left|\alpha\right\rangle +i\left|\beta\right\rangle }{\sqrt{2}}\\
\left|\psi_{-}\right\rangle  & = & \frac{\left|\alpha\right\rangle -i\left|\beta\right\rangle }{\sqrt{2}}\end{eqnarray*}
$\left|\alpha\right\rangle $ and $\left|\beta\right\rangle $ can
be rewritten as\begin{eqnarray*}
\left|\alpha\right\rangle  & = & \frac{1}{\sqrt{2}}\left(\left|\psi_{+}\right\rangle +\left|\psi_{-}\right\rangle \right)\\
\left|\beta\right\rangle  & = & \frac{i}{\sqrt{2}}\left(\left|\psi_{+}\right\rangle -\left|\psi_{-}\right\rangle \right)\end{eqnarray*}



\subsubsection*{Generating Initial State}

$\left|\psi\right\rangle $ can be used as an initial state because
it is a combination of eigenvectors:

\begin{eqnarray*}
\left|\psi\right\rangle  & = & \frac{1}{\sqrt{N}}\sum_{x}\left|x\right\rangle \\
 & = & \cos\left(\frac{\vartheta}{2}\right)\left|\alpha\right\rangle +\sin\left(\frac{\vartheta}{2}\right)\left|\beta\right\rangle \\
 & = & \cos\left(\frac{\vartheta}{2}\right)\frac{1}{\sqrt{2}}\left(\left|\psi_{+}\right\rangle +\left|\psi_{-}\right\rangle \right)+\sin\left(\frac{\vartheta}{2}\right)\frac{i}{\sqrt{2}}\left(\left|\psi_{+}\right\rangle -\left|\psi_{-}\right\rangle \right)\\
 & = & \frac{1}{\sqrt{2}}\left(\cos\left(\frac{\vartheta}{2}\right)+i\sin\left(\frac{\vartheta}{2}\right)\right)\left|\psi_{+}\right\rangle +\frac{1}{\sqrt{2}}\left(\cos\left(\frac{\vartheta}{2}\right)-i\sin\left(\frac{\vartheta}{2}\right)\right)\left|\psi_{-}\right\rangle \\
 & = & \frac{1}{\sqrt{2}}e^{i\frac{\vartheta}{2}}\left|\psi_{+}\right\rangle +\frac{1}{\sqrt{2}}e^{-i\frac{\vartheta}{2}}\left|\psi_{-}\right\rangle \end{eqnarray*}


Note: Coefficients to $\left|\psi_{+}\right\rangle $ and $\left|\psi_{-}\right\rangle $
above are not important. Any state which was a combination of the
two eigenvectors would work for finding the boolean mean.


\subsubsection*{Phase Estimation Results}

The result of phase estimation with $G$ and initial state $\left|\psi\right\rangle $
can be used to find boolean mean\[
S\left(f\right)=\frac{1}{N}\sum_{x}f\left(x\right)=\frac{M}{N}=\sin^{2}\left(\frac{\vartheta}{2}\right)\]
Phase estimation gives$\left|\varphi-\hat{\varphi}\right|\le2^{\eta_{0}}$
, $\hat{\varphi}=\frac{d}{2^{t}}$ with probability $\left(1-\epsilon\right)$
using $t=\eta_{0}+\left\lceil \log\left(2+\frac{1}{2\epsilon}\right)\right\rceil $
qubits in the top register. Phase estimation will approximate $\lambda_{+}$
with probability\[
\left(1-\epsilon\right)\left|\frac{1}{\sqrt{2}}e^{i\frac{\vartheta}{2}}\right|^{2}\]
and approximate $\lambda_{-}$ with probability\[
\left(1-\epsilon\right)\left|\frac{1}{\sqrt{2}}e^{-i\frac{\vartheta}{2}}\right|^{2}\]
Eigenvalues again are

\begin{eqnarray*}
\lambda_{+} & = & e^{i\vartheta}=e^{2\pi i\vartheta/\left(2\pi\right)}\\
\lambda_{-} & = & e^{i\left(2\pi-\vartheta\right)}=e^{-2\pi i\left(2\pi-\vartheta\right)/\left(2\pi\right)}\\
\varphi_{+} & = & \frac{\vartheta}{2\pi}\\
\varphi_{-} & = & \frac{2\pi-\vartheta}{2\pi}\end{eqnarray*}


Error bounds look like \begin{eqnarray*}
\left|\varphi_{\pm}-\hat{\varphi}\right| & \le & 2^{-\eta_{0}}\\
\left|\pi\varphi_{\pm}-\pi\hat{\varphi}\right| & \le & \frac{\pi}{2^{\eta_{0}}}\\
\pi\varphi_{+} & = & \frac{\vartheta}{2}\\
\pi\varphi_{-} & = & \pi-\frac{\vartheta}{2}\\
\left|\frac{\vartheta}{2}-\pi\hat{\varphi}\right| & \le & \frac{\pi}{2^{\eta_{0}}}\textrm{ w/prob }\frac{1}{2}\left(1-\epsilon\right)\\
\left|\pi-\frac{\vartheta}{2}-\pi\hat{\varphi}\right| & \le & \frac{\pi}{2^{\eta_{0}}}\textrm{ w/prob }\frac{1}{2}\left(1-\epsilon\right)\end{eqnarray*}
But we aren't using phase estimation to compute phase, we are using
it to compute $M$ which is related to the sin, so we need a different
bound:\begin{eqnarray*}
\left|\sin^{2}\left(\frac{\vartheta}{2}\right)-\sin^{2}\left(\frac{\pi j}{2^{t}}\right)\right| & \le & \frac{\pi}{2^{\eta_{0}}}\sqrt{S\left(f\right)\left(1-S\left(f\right)\right)}+\frac{\pi^{2}}{2^{2\eta_{0}}}\end{eqnarray*}
(from paper BHMT lemma 7, page 15)

$j$ is measurement in computational basis

since $\sin^{2}\left(\frac{\varphi}{2}\right)=\sin^{2}\left(\pi-\frac{\varphi}{2}\right)=S\left(f\right)$

$\left.\begin{array}{c}
\sin^{2}\left(\frac{\vartheta}{2}\right)\approx\frac{\vartheta}{2}\\
\sin^{2}\left(\frac{\pi j}{2}\right)\approx\frac{\pi j}{2}\end{array}\right\} \rightarrow\left(\frac{\vartheta}{2}\right)^{2}-\left(\frac{\pi i}{2}\right)^{2}=\left(\frac{\vartheta}{2}+\frac{\pi i}{2}\right)\left(\frac{\vartheta}{2}-\frac{\pi i}{2}\right)$


\subsubsection*{Phase Estimation Circuit}

The circuit for using phase estimation to compute the boolean mean
is the same as the circuit for normal phase estimation. (Figure 6.7
page 262)

The output of the circuit in the bottom register will be either $\left|\psi_{+}\right\rangle $
or $\left|\psi_{-}\right\rangle $. The top register needs just enough
bits to be able to distinguish $\frac{1}{N}$ from $0$. 

In general, there is no efficient way to make $G^{2^{j}}$ gates,
just have to apply $G$ repeatedly, so the number of quesries is $\tau=2^{t-1}=\Theta\left(2^{t}\right)=\Theta\left(2^{\eta_{0}}\right)$.
Error is $O\left(\frac{1}{\tau}\right)$. $t=\eta_{0}+\left\lceil log_{2}\left(2+\frac{1}{2\epsilon}\right)\right\rceil $.
This is the best possible, see paper {[}Nayak+Wu], algorithm is optimal.


\section*{Lecture 28 (30 April)}

Review for Final
\end{document}