% Instructions: you don't need to change anything in the macros, but
% feel free to define new commands as you wish. Starting from the main
% body, change the specs (e.g., your
% name). use \begin{solution} \end{solution} environment to write your
% solutions. Don't forget to list your collaborators.
\documentclass[12pt,answers]{exam}
%============Macros==================%
\usepackage{amsmath,amsfonts,amssymb,amsthm}
\usepackage{qcircuit}
\usepackage[margin=1in]{geometry}
%--------------Cosmetic----------------%
\usepackage{mathtools}
\usepackage{hyperref}
\hypersetup{
colorlinks=true,
linkcolor=blue,
filecolor=magenta,
urlcolor=cyan,
}
\usepackage{fullpage}
\usepackage{microtype}
\usepackage{xspace}
\usepackage[svgnames]{xcolor}
\usepackage[sc]{mathpazo}
\usepackage{enumitem}
\setlist[enumerate]{itemsep=1pt,topsep=2pt}
\setlist[itemize]{itemsep=1pt,topsep=2pt}
%----------Header--------------------%
\def\course{CSCE 440/640 Quantum Algorithms}
\def\term{Texas A\&M U, Spring 2019}
\def\prof{Lecturer: Fang Song}
\newcommand{\handout}[5]{
\renewcommand{\thepage}{\arabic{page}}
\begin{center}
\framebox{
\vbox{
\hbox to 5.78in { \hfill \large{\course} \hfill }
\vspace{2mm}
\hbox to 5.78in { {\Large \hfill \textbf{#5} \hfill} }
\vspace{2mm}
\hbox to 5.78in { \term \hfill \emph{#2}}
\hbox to 5.78in { {#3 \hfill \emph{#4}}}
}
}
\end{center}
\vspace*{4mm}
}
\newcommand{\hw}[4]{\handout{#1}{#2}{#3}{#4}{Homework #1}}
\newcommand{\ex}[4]{\handout{#1}{#2}{#3}{#4}{Exercise #1}}
%-----defs and commands-----%
\def\mG{[\textbf{G}]\xspace}
\def\veps{\varepsilon}
\def\tr{\mathrm{tr}}
\newcommand{\bit}{\{0,1\}}
\newcommand{\bra}[1]{\langle #1 \rvert}
\newcommand{\ket}[1]{\lvert #1 \rangle}
\newcommand{\kera}[1]{\ket{#1}\bra{#1}}
\newcommand{\negl}{\text{negl}}
\newcommand{\complex}{\mathbb{C}}
\newcommand{\integer}{\mathbb{Z}}
\newcommand{\srd}[2]{\textsf{SR}_{#1}^{#2}(X)}
\newcommand{\corr}[1]{{\color{blue}{#1}}}
%=======Main document==============%
\begin{document}
%----Specs: change accordingly-----%
\newif\ifstudent % comment out false
\studenttrue
%\studentfalse
\def\issuedate{Feb. 18, 2019, \corr{Update: 02/24/2019}}
\def\duedate{March 6, 2019, before class} %
\def\yourname{your name} % put your name here
%------------------------------%
\ifstudent
\hw{3}{\issuedate}{Student: \yourname}{Due: \duedate}%
\else
\hw{3}{\issuedate}{\prof}{Due: \duedate}%
\fi
\noindent \textbf{Instructions.} Only PDF format is accepted (type it
or scan clearly). Your solutions will be graded on \emph{correctness}
and \emph{clarity}. You should only submit work that you believe to be
correct; if you cannot solve a problem completely, you will get
significantly more partial credit if you clearly identify the gap(s)
in your solution. For this problem set, a random subset of problems
will be graded. Problems marked with ``\mG'' are required for graduate
students. Undergraduate students will get bonus points for solving
them. \medskip
\noindent You may collaborate with others on this problem set.
% and consult external sources.
However, you must \textbf{\emph{write up your own solutions}} and
\textbf{\emph{list your collaborators}} for each problem.
\begin{questions}
\question (Linear algebra modulo 2) The integers modulo 2 constitute
a field $F_2$: a set of numbers (namely 0 and 1) for which all the
standard operations of plus, minus, times, and division-by-nonzero
work as expected. The set of all $n$-dimensional vectors in this case
is denoted $F_2^n$. (Other examples of fields include the real
numbers, the complex numbers, the rational numbers, and the integers
modulo p whenever p is prime. Also, you are most likely used to the
cases $R^n$ and $C^n$, when the scalars are reals and complexes,
respectively.)
\begin{parts}
\part[5] Show that it is possible that $u\cdot u = 0$ for some
$u\neq 0$, where $u\cdot v:= \sum_{i=1}^n u_i v_i \pmod 2$ is the
``dot product'' in $F_2^n$. Is this possible in $R^n$ with the usual
inner product?
\part[5] Recall that a set of vectors $u_1,\ldots, u_k$ is said to be
linearly independent if the only linear combination
$c_1u_1 + \ldots + c_k u_k$ that equals 0 is the trivial one with
$c_1 = c_2 = \ldots = c_k = 0$. The \emph{span} (set of all linear
combinations) of $k$ linearly independent vectors is called a
$k$-dimensional subspace. Show that in $F_2^n$ , every k-dimensional
subspace contains exactly $2^k$ vectors.
\part[5] Consider a system of equations $Ax = 0$ (where
$A \in F_2^{ m\times n}$ is a matrix and $x$ is a vector of $n$
unknowns). Show that the set of solutions $x$ to $Ax = 0$ forms a
subspace of dimension equal to $n - r$, where $r$ is the maximum
size of a linearly independent set of rows of $A$.
\part[5] For a more general system $Ax = b$ for some fixed
$b\in F_2^n$, prove that either there is no solution, or else there
are $2^{\corr{n - r}}$ solutions. Again $r$ is the maximum size of a linearly
independent set of rows of $A$.
\end{parts}
\question (Deferred measurement) We will show that if one has a
quantum circuit with partial measurement gates in the middle, one
can replace it with an equivalent quantum in which all the
measurement gates are at the end without incurring much loss in
efficiency.
Consider an $n$-qubit quantum circuit, and assuming the first
intermediate measurement gate is applied to the 1st qubit at time
step $t$. Let $\ket{\psi_i}$ denote the quantum state just prior to
time $t$. Recall when the measurement is applied, two things happen:
First, one classical bit of information $b$ appears on the
measurement gate's readout. Second, the state collapses according to
the usual rules.
\begin{parts}
\part[5] Now we start to make a new circuit. We introduce a new
$(n + 1)$st qubit, initialized in $\ket{0}$. Second, we replace
the measurement gate on qubit \#1 at time t with a CNOT gate whose
control qubit is \#1 and whose target qubit is \#$(n +
1)$. Finally, we immediately apply a measurement gate to the
$(n + 1)$st qubit, and treat its readout as ``b''. Assume we then
henceforth ignore the (n + 1)st qubit. Show that this gives an
exact simulation of the original circuit’s
operation.
Note that since Operations on disjoint sets of qubits commute
(Cf. HW2 Problem 4a), we can imagine that instead of measuring it
immediately (just after time $t$), we instead delay its
measurement to the very end of the computation. In this way, we’ve
effectively deferred the first intermediate measurement of the
quantum circuit to the end. By repeating this for all intermediate
measurement gates, we can always move all measurement gates to the
end (at the cost of adding one extra qubit and CNOT each time).
\part (Bonus 5 pts) A curious reader may ask, what if I needed the
measurement outcome ``b'' to decide the next operation (e.g.,
apply $X$ on 5th qubit if $b=1$ and $H$ on 7th qubit if $b=0$) in
the original circuit? Now that the measurement gets delayed, how
can I proceed? Help the reader resolve this, and estimate the
cost.
\end{parts}
\question (Semi-classical quantum Fourier transform) If we will
measure right after the QFT, then we can construct a simpler circuit
with 1-qubit gates only.
\begin{parts}
\part[5] For $k>0$, let \begin{equation*}
R_k = \left(
\begin{array}{cc c c}
1 & 0 &0 &0\\
0 & 1 &0 &0 \\
0 & 0 & 1& 0 \\
0 & 0 & 0 & e^{2\pi i /{2^k}}
\end{array} \right)
\end{equation*}
be a two-qubit controlled phase gate. Show that it is symmetric,
i.e., it gives the same operation if you reverse the control and
target qubits.
\part[10] Recall the QFT circuit (Fig.~\ref{fig:qft}), where $R_k$ is
as above.
\begin{figure}[ht]
\centerline{ \Qcircuit @C=1em @R=0.75em {
\lstick{\ket{x_{n-1}}} & \gate{H} & \gate{R_2} & \cdots & \gate{R_{n-1}} & \gate{R_{n}} & \qw & \qw & \qw & \qw & \qw & \qw & \qw & \qw & \rstick{\ket{y_0}} \qw \\
\lstick{\ket{x_{n-2}}} & \qw & \ctrl{-1} & \qw & \qw & \qw & \gate{H} & \cdots & \gate{R_{n-2}} & \gate{R_{n-1}} & \qw & \qw & \qw & \qw & \rstick{\ket{y_1}} \qw \\
\lstick{\vdots } & & & \ddots & & & & \ddots & & & \ddots
& &
& & \rstick{\vdots } \\
\lstick{\ket{{x_1}}} & \qw & \qw & \qw & \ctrl{-3} & \qw & \qw & \qw & \ctrl{-2} & \qw & \qw & \gate{H} & \gate{R_2} & \qw & \rstick{\ket{{y_{n-2}}}} \qw \\
\lstick{\ket{x_{0}}} & \qw & \qw & \qw & \qw & \ctrl{-4} &
\qw & \qw & \qw & \ctrl{-3} & \qw & \qw & \ctrl{-1} &
\gate{H} & \rstick{\ket{y_{n-1}}} \qw } }
\caption{QFT circuit in $\mathbb{Z}_{2^n}$.}
\label{fig:qft}
\end{figure}
Because of part a), we get an equivalent circuit below by flipping the
control and target qubits of each phase gate (Fig.~\ref{fig:qftr}).
\begin{figure}[ht!]
\centerline{ \Qcircuit @C=1em @R=0.75em {
\lstick{\ket{x_{n-1}}} & \gate{H} & \ctrl{1} & \cdots & \ctrl{3} & \ctrl{4} & \qw & \qw & \qw & \qw & \qw & \qw & \qw & \qw & \rstick{\ket{y_0}} \qw \\
\lstick{\ket{x_{n-2}}} & \qw & \gate{R_2} & \qw & \qw & \qw & \gate{H} & \cdots & \ctrl{2} & \ctrl{3} & \qw & \qw & \qw & \qw & \rstick{\ket{y_1}} \qw \\
\lstick{\vdots } & & & \ddots & & & & \ddots & & &\ddots & &
& & \rstick{\vdots } \\
\lstick{\ket{{x_1}}} & \qw & \qw & \qw
& \gate{R_{n-1}} & \qw & \qw & \qw
& \gate{R_{n-2}} & \qw & \qw & \gate{H} & \ctrl{1} & \qw & \rstick{\ket{{y_{n-2}}}} \qw \\
\lstick{\ket{x_{0}}} & \qw & \qw & \qw & \qw & \gate{R_n} & \qw
& \qw & \qw & \gate{R_{n-1}} & \qw & \qw & \gate{R_2} & \gate{H}
& \rstick{\ket{y_{n-1}}} \qw } }
\caption{QFT circuit in $\mathbb{Z}_{2^n}$.}
\label{fig:qftr}
\end{figure}
Note that on all wires, the qubits' lifetimes end by being control
bits. Show that we will obtain equivalent results if we measure each
qubit after its Hadamard gate, then use the outcome to
\emph{classically} control whether or not to apply the phase gate, as
in Fig.~\ref{fig:qftsc}.
\begin{figure}[ht!]
\centerline{ \Qcircuit @C=1em @R=0.75em {
\lstick{\ket{x_{n-1}}} & \gate{H} & \meter & \qw & \qw & \qw & \qw & \qw & \qw & \qw & \qw & \qw & \rstick{{y_0}} \qw \\
\lstick{\ket{x_{n-2}}} & \qw & \qw & \gate{R_2^{y_0}} & \gate{H} & \meter & \qw & \qw & \qw & \qw & \qw & \qw & \rstick{{y_1}} \qw \\
\lstick{\vdots } & & & \vdots & & & & & \vdots & &
& & \rstick{\vdots } \\
\lstick{\ket{{x_1}}} & \qw & \qw &
\gate{R_{n-1}^{y_0}} & \qw & \qw &
\gate{R_{n-2}^{y_1}} & \cdots & \gate{H} & \meter
& \qw & \qw & \rstick{{{y_{n-2}}}} \qw \\
\lstick{\ket{x_{0}}} & \qw & \qw & \gate{R_n^{y_0}} & \qw & \qw
& \gate{R_{n-1}^{y_1}} & \qw & \qw & \qw & \gate{R_2^{y_{n-2}}} & \gate{H} &
\meter & \rstick{y_{n-1}} \qw } }
\caption{QFT circuit in $\mathbb{Z}_{2^n}$.}
\label{fig:qftsc}
\end{figure}
\end{parts}
\question (Square root of a quantum operation) Let $U$ be a unitary
quantum circuit on $n$ qubits. In this problem, we want to construct
another circuit that computes a square root of $U$ (i.e., a unitary
$V$ such that $V^2 = U$).
\begin{parts}
\part[5] Let $X = \left(
\begin{array}{lr}
0 & 1\\
1 & 0
\end{array} \right)$ be the matrix for a 1-qubit NOT gate. Find a $2\times 2$ matrix $V$ (i.e.,
1-qubit gate) such that $V^2 = X$.
\part[5] Suppose we construct $V$ by simply taking the square root
of each gate $U_i$ in circuit $U$, does this work, i.e. is
$V^2 = U$? Justify your answer.
\part[20] We explore a strategy of implementing $V$ using the
\emph{phase estimation} algorithm. Suppose $U$ is constituted by $s$
two-qubit gates. We study a simple case here. Let
$\{\ket{\psi_x}: x \in \{0,\ldots, 2^n - 1\}\}$ be a set of
orthonormal eigenvectors of $U$ with eigenvalues in
$\{\pm 1, \pm i\}$. Namely
$U \ket{\psi_x} = i^{\phi_x} \ket{\psi_x}$ with
$\phi_x \in \{0,1,2,3\}$. We outline a construction of $V$ as
follows such that $V\ket{\psi_x} = \omega^{\phi_x} \ket{\psi_x}$
where $\omega= e^{2\pi i /8}$:
\begin{itemize}
\item Construct a generalized-control-$U$, with two control-qubits,
i.e.,
$\ket{a b}\otimes \ket{c} \mapsto \ket{a b}\otimes
U^{ab}{\ket{c}}$. (A word on notation: $ab$ is the two-bit string,
e.g., $01$, and it is identified with an integer in
$\{0,1,2,3\}$.)
\item Then apply the phase-estimation algorithm to this
controlled-$U$ gate, which results in a circuit that computes
$ab = \phi_x$, in two ancillary qubits
for any input $\ket{\psi_x}$.
\item Apply gates to those two ancilliary qubits to induce the
mapping $\ket{ab} \mapsto \omega^{ab}\ket{ab}$.
\item Then apply the inverse of the phase-estimation circuit.
\end{itemize}
Answer the following questions:
\begin{enumerate}[label=\roman*)]
\item Explain how to construct a circuit computing the two-qubit
controlled-$U$ operation using $3s$ 3-qubit gates. (\corr{You may
assume that you can implement the single-qubit controlled version
of each two-qubit gate in $U$ by a 3-qubit gate.})
\item Explain how to construct a circuit computing $ab = \phi_x$ on
input {$\ket{\psi_x}$} using $3s$ 3-qubit gates, one 2-qubit gate,
and four 1-qubit gates.
\item Give a quantum circuit consisting of two 1-qubit gates that
maps each basis state $\ket{ab}$ to $\omega^{ab}\ket{ab}$.
\item Verify that the construction $V$ is correct, i.e.,
$V\ket{\psi_x} = \omega^{\phi_x} \ket{\psi_x}$. Explain why this
implies $V^2 = U$, namely $V$ computes the squre root of $U$ on any
input state $\ket{\psi}$.
\end{enumerate}
Note: the total gate cost is $6s$ 3-qubit gates plus two 2-qubit
gates plus eight 1-qubit gates. This can be converted into a circuit
consisting of $O(s)$ 2-qubit gates, not much more than the original
circuit.
\end{parts}
\question (Experimentally realizing Shor’s algorithm)
\begin{parts}
\part[5] Read the paper
\href{https://arxiv.org/pdf/1301.7007.pdf}{Pretending to factor
large numbers on a quantum computer} by Smolin, Smith, and
Vargo. Summarize their main critique of prior experiments.
\part[5] \mG Read the paper
\href{http://sci-hub.tw/http://science.sciencemag.org/content/351/6277/1068}{Realization
of a scalable Shor algorithm} by Monz et al. Do you feel it
adequately addresses the criticisms in the Smolin–Smith–Vargo paper?
Why or why not?
\end{parts}
\end{questions}
\end{document}