%You can leave alone everything before Line 84.
\documentclass{article}
\usepackage{url,amsfonts, amsmath, amssymb, amsthm}
\usepackage{pict2e}
\usepackage[percent]{overpic}
% Page layout
\setlength{\textheight}{8.75in}
\setlength{\columnsep}{2.0pc}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{0in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\parindent}{1pc}
\newcommand{\shortbar}{\begin{center}\rule{5ex}{0.1pt}\end{center}}
%\renewcommand{\baselinestretch}{1.1}
% Macros for course info
\newcommand{\courseNumber}{CMSC/PHYS 457}
\newcommand{\courseTitle}{Introduction to Quantum Computing}
\newcommand{\semester}{Spring 2023}
% Theorem-like structures are numbered within SECTION units
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{statement}[theorem]{Statement}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{fact}{Fact}
%definition style
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}{Example}
%\newtheorem{problem}{Problem}
\newtheorem{exercise}{Exercise}
\newtheorem{algorithm}{Algorithm}
%remark style
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{reduction}[theorem]{Reduction}
%\newtheorem{question}[theorem]{Question}
\newtheorem{question}{Question}
%\newtheorem{claim}[theorem]{Claim}
%
% Proof-making commands and environments
\newcommand{\beginproof}{\medskip\noindent{\bf Proof.~}}
\newcommand{\beginproofof}[1]{\medskip\noindent{\bf Proof of #1.~}}
\newcommand{\finishproof}{\hspace{0.2ex}\rule{1ex}{1ex}}
\newenvironment{problem}[1]{\medskip\noindent{\bf Problem #1.~}}{\shortbar}
\newenvironment{solution}[1]{\medskip\noindent{\bf Solution #1.~}}{\shortbar}
%====header======
\newcommand{\solutions}[3]{
%\renewcommand{\thesolution}{{\large #2}.\arabic{problem}}
\vspace{-2ex}
\begin{center}
{\small \courseNumber, \courseTitle
\hfill {\large \bf {Due: #1} }\\
\semester, University of Maryland \hfill
{\em Date: #3}}\\
\vspace{-1ex}
\hrulefill\\
\vspace{4ex}
{\Large #2}\\
\vspace{2ex}
\end{center}
\shortbar
\vspace{3ex}
}
\newcommand{\points}[1]{\textit{(#1 points)}}
\newcommand{\bonus}[1]{\textit{(Bonus: #1 points)}}
\include{qmacros}
\usepackage{colonequals}
%\newcommand{\ket}[1]{\lket\microspace #1 \microspace\rket}
%\newcommand{\bra}[1]{\lbra\microspace #1 \microspace\rbra}
%\newcommand{\<}{\langle}
%\renewcommand{\>}{\rangle}
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\solutions{February 16th, 2023}{Assignment 1}{\today}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% Begin the solution for each problem by
% \begin{solution}{Problem Number} and ends it with \end{solution}
%
% the solution for Problem 1
Please submit it electronically to ELMS. This assignment is 6\% in your total points. For the simplicity of the grading, the total points for the assignment are 60. Note that we will reward the use of Latex for typesetting with bonus points (an extra 5\% of your points).
\begin{problem}{1}
\emph{Quantum Circuits}
\begin{enumerate}
\item \points{10} \label{prob:cccnot} The \textsc{cccnot} (triple-controlled \textsc{not}) gate is a four-bit reversible gate that flips its fourth bit if and only if the first three bits are all in the state $1$. Show how to implement a \textsc{cccnot} gate using Toffoli gates. You may use additional workspace as needed. You may assume that bits in the workspace start with a particular value, either $0$ or $1$, provided you return them to that value.
\item \bonus{10} Show that a Toffoli gate cannot be implemented using any number of \textsc{cnot} gates, with any amount of workspace. Hence the \textsc{cnot} gate alone is not universal. (Hint: It may be helpful to think of the gates as performing arithmetic operations on integers mod $2$.)
\end{enumerate}
\end{problem}
\begin{problem}{2}
\emph{Mach-Zehnder interferometer with a phase shift.}
\[
\begin{overpic}[scale=0.5]{mz}
\put(53.75,48.75){$e^{i\varphi}$}
\put(74.75,67){$0$}
\put(93,48.75){$1$}
\end{overpic}
\]
Analyze the experiment depicted above using the mathematical model described in class. (Note that the model from class differs slightly from the model described in the textbook; in particular, you should use the matrix $\frac{1}{\sqrt2}\left(\begin{smallmatrix}1 & 1\\1 & -1\end{smallmatrix}\right)$ to model the beamsplitters.)
\begin{enumerate}
\item \points{3} Compute the quantum state of the system just before reaching the detectors. Express your answer using Dirac notation.
\item \points{3} Compute the probability that the ``$0$'' detector clicks as a function of $\varphi$, and plot your result for $\varphi \in [0,2\pi]$.
\end{enumerate}
\end{problem}
\begin{problem}{3}
\begin{enumerate}
\item \points{3} Express each of the three Pauli operators,
\[
X = \begin{pmatrix}0 & 1\\1 & 0\end{pmatrix},\quad
Y = \begin{pmatrix}0 & -i\\i & 0\end{pmatrix},\quad
Z = \begin{pmatrix}1 & 0\\0 & -1\end{pmatrix},
\]
using Dirac notation in the computational basis.
\item \points{2} Find the eigenvalues and the corresponding eigenvectors of each Pauli operator. Express the eigenvectors using Dirac notation.
\item \points{2} Write the operator $X \otimes Z$ as a matrix and using Dirac notation (in both cases using the computational basis).
\item \points{3} What are the eigenspaces of the operator $X \otimes Z$? Express them using Dirac notation.
\item \points{3} Using the Spectral Decomposition show that $HXH^\dagger=Z$, where
\[ H = \frac{1}{\sqrt{2}}\begin{pmatrix}1 & 1\\1 & -1\end{pmatrix} \]
\end{enumerate}
\end{problem}
\begin{problem}{4} \emph{Unitary operations and measurements.}
Consider the state
\[
|\psi\> = \frac{2}{3}|00\> + \frac{1}{3}|01\> - \frac{2}{3}|11\>.
\]
\begin{enumerate}
\item \points{3} Let $|\phi\> = (I \otimes H) |\psi\>$, where $H$ denotes the Hadamard gate. Write $|\phi\>$ in the computational basis.
\item \points{3} Suppose the first qubit of $|\phi\>$ is measured in the computational basis. What is the probability of obtaining $0$, and in the event that this outcome occurs, what is the resulting state of the second qubit?
\item \points{3} Suppose the second qubit of $|\phi\>$ is measured in the computational basis. What is the probability of obtaining $0$, and in the event that this outcome occurs, what is the resulting state of the first qubit?
\item \points{3} Suppose $|\phi\>$ is measured in the computational basis. What are the probabilities of the four possible outcomes? Show that they are consistent with the marginal probabilities you computed in the previous two parts.
\end{enumerate}
\end{problem}
\begin{problem}{5}
Let $\theta$ be a fixed, known angle. Suppose someone flips a fair coin and, depending on the outcome, either gives you the state
\[
|0\> \qquad\text{or}\qquad \cos\theta |0\> + \sin\theta |1\>
\]
(but does not tell you which).
\begin{enumerate}
\item \points{4} Consider measuring the given state in the orthonormal basis consisting of
\[
|\phi\> = \cos\phi |0\> + \sin\phi |1\>, \qquad |\phi^\perp \> = \sin\phi |0\> - \cos\phi |1\>
\]
Find the probabilities of all the possible measurement outcomes for each possible value of the given state
\item \points{5} Calculate the probability of correctly distinguishing the two possible states using the above measurement (In terms of $\phi$)
\item \bonus{5} Calculate the optimal value of $\phi$ in order to best distinguish the states. What is the optimal success probability?
\end{enumerate}
\end{problem}
\begin{problem}{6} \emph{Non-cloning theorem.} Please provide your answer and a brief explanation.
\begin{itemize}
\item \points{5} (Clone a random bit?) Given one sample of an unknown biased random coin (say, $0$ with probability $p$ and $1$ with probability $1-p$ and $p$ unknown), is there a procedure to create two copies of such biased random coin? Namely, this procedure needs to generate two independent random coins with the same $p$.
\item \points{5} (Clone one certain basis?) Is there a procedure to clone qubits restricted to $\{\ket{+}, \ket{-}\}$?
\item \bonus{5} (Clone with many samples?) If you are given 1000 samples of an unknown biased random coin, is it possible to create 1,000,000 independent copies of the random coin? Here we allow the generated copies can be a little different from the original copy. Note that the precise number 1000 (or 1,000, 000) does not change the answer.
\end{itemize}
\end{problem}
\end{document}