% Created by Fang Song on April 5 2020. 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}
\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}
\usepackage{circuitikz}
\usepackage{mdframed} %
\mdfdefinestyle{figstyle}{ %
  linecolor=black!7, %
  backgroundcolor=black!7, %
  innertopmargin=10pt, %
  innerleftmargin=25pt, %
  innerrightmargin=25pt, %
  innerbottommargin=10pt %
}

%----------Header--------------------%
\def\course{CS 410/510 Introduction to Quantum Computing}
\def\term{Portland State U, Spring 2020}
\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 #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}}

%-----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}}

%=======Main document==============%
\begin{document}

%----Specs: change accordingly-----%
\newif\ifstudent % comment out false
% \studenttrue 
 \studentfalse

\def\hwnum{6} %
\def\issuedate{05/17/2020} %
\def\duedate{11:59pm PDT, \textbf{05/31/2020}} % 
\def\yourname{your name} % put your name here
%------------------------------%
\ifstudent
\hw{\hwnum}{\issuedate}{Student: \yourname}{Due: \duedate}%
\else
\hw{\hwnum}{\issuedate}{\prof}{Due: \duedate}%
\fi
\noindent \textbf{Instructions.}  This problem set contains \numpages\
pages (including this cover page) and \numquestions\
questions. Problems marked with ``\mG'' are required for 510
students. Students enrolled in 410 will get bonus points for solving
them. A random subset of problems will be graded.

Your solutions will be graded on \emph{correctness} and
\emph{clarity}. You should only submit work that you believe to be
correct, and you will get significantly more partial credit if you
clearly identify the gap(s) in your solution. It is good practice to
start any long solution with an informal (but accurate) summary that
describes the main idea.

You need to submit a PDF file via Gradescope before the
deadline. Either a clear scan of you handwriting or a typeset document
is accepted. You will get 5 bonus points for typing in LaTeX (Download
and use the accompany TeX file).

\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.

\newpage 
\begin{questions}
  
\question (Search for a quantum state) Suppose you are given a black
  box $U_\phi$ that identifies an unknown quantum state $\ket{\phi}$
  (which may not be a computational basis state). Specifically,
  $U_\phi\ket{\phi}= - \ket{\phi}$, and
  $U_\phi{\ket{\xi}} = \ket{\xi}$ for any state $\ket{\xi}$ satisfying
  $\langle \phi | \xi \rangle = 0$. Consider an algorithm for
  preparing $\ket{\phi}$ that starts from some fixed state
  $\ket{\psi}$ and repeatedly applies the unitary transformation
  $VU_\phi$, where $V = 2\ket{\psi}\bra{\psi} - I$ is a reflection about
  $\ket{\psi}$.  Let
  \[ \ket{\phi^\perp} = \frac{e^{-i \lambda}\ket{\psi} -
      \sin(\theta)\ket{\phi}}{\cos(\theta)} \] denote a state
  orthogonal to $\ket{\phi}$ in $span\{\ket{\phi}, \ket{\psi}\}$,
  where $\bra\phi \psi \rangle =e^{i\lambda } \sin(\theta) $ for some
  $\lambda,\theta \in \mathbb{R}$.
  \begin{parts}
    
  \part[4] Write the initial state $\ket{\psi}$ in the basis
    $\{\ket{\phi}, \ket{\phi^\perp}\}$.

    \newpage 
  \part[6] Write $U_\phi$ and $V$ as matrices in the basis
    $\{\ket{\phi}, \ket{\phi^\perp}\}$.
  
\newpage 
\part[5] Let $k$ be a positive integer. Compute $(VU_\phi)^k$.

  \newpage
\part[5] Compute $\bra{\phi}(VU_\phi)^k\ket{\psi}$.

\newpage 
\part[5] Suppose that $\left|\bra{\phi}\psi\rangle\right|$ is
  small. Approximately what value of $k$ should you choose in order
  for the algorithm to prepare a state close to $\ket{\phi}$, up to a
  global phase? Express your answer in terms of
  $\left|\bra{\phi}\psi\rangle\right|$.

\newpage 
  \end{parts} 

\question (Mixed states and density matrix)

\begin{parts}
\part[5] A density matrix $\rho$ corresponds to a pure state if and
  only if $\rho = \kera{\psi}$ for some $\ket{\psi}$. Show that $\rho$
  corresponds to a pure state if and only if $Tr(\rho^2) = 1$.

  \newpage 
  \part[5] Show that every $2\times 2$ density matrix $\rho$ can be
  expressed as an equally weighted mixture of pure states. That is
  $\rho = \frac 1 2 \kera{\psi_1} + \frac 1 2 \kera{\psi_2}$ (Note:
  the two states need not be orthogonal).

  \newpage 
  \part[5] Imagine two parties Alice and Bob. Alice flips a biased coin
  which is HEADS with probability $\cos^2(\pi/8)$. Alice prepares
  $\ket{0}$ when she sees coin $0$ and $\ket{1}$ otherwise. From
  Alice’s perspective (who knows the coin value), the density matrix
  of the state she created will be either $\kera{0}$ or
  $\kera{1}$. She then sends the qubit to Bob. What is the density
  matrix of the state from Bob’s perspective (who does not know the
  coin value)? Write down the matrix.

  \newpage 
  \bonuspart[5] Let $\{p_i,\ket{\psi_i}\}_{i=0}^1$ and
  $\{q_j,\ket{\phi_j}\}_{j=0}^1$ be two ensembles of pure
  states. Define $\ket{\tilde \psi_i} = \sqrt{p_i} \ket{\psi_i}$ and
  $\ket{\tilde\phi_j} = \sqrt{q_j} \ket{\phi_j}$ for all $i,j$. Show
  that the two ensembles produce the same density matrix \textbf{if
    and only if} there is a unitary $U = \left(
    \begin{array}{lr}
      u_{00} & u_{01}\\
      u_{10} & u_{11}
    \end{array} \right)$ such that
  
  \[ \ket{\tilde\psi_0} = u_{00} \ket{\tilde\phi_0} +
    u_{01}\ket{\tilde\phi_1}, \text{ and } \ket{\tilde\psi_1} = u_{10}
    \ket{\tilde\phi_0} + u_{11}\ket{\tilde\phi_1} \, .\]
  
\newpage

\end{parts}

\question (Swap test) Let $\ket{\psi}$ and $\ket{\phi}$ be arbitrary
  single-qubit states (not necessarily computational basis states),
  and let SWAP denote the 2-qubit gate that swaps its input qubits
  (i.e., $\text{SWAP}\ket{x}\ket{y} = \ket{y}\ket{x}$ for any
  $x,y \in \bit$).

  \begin{parts}
  \part[5] Compute the output state of the following quantum circuit:
      \begin{mdframed}[style=figstyle]
        \centerline{\Qcircuit @C=.5em @R=0em @!R {
            \lstick{\ket{0}} & \gate{H} & \ctrl{1} & \gate{H} & \qw \\
            \lstick{\ket{\psi}} & \qw  & \multigate{1}{SWAP} & \qw & \qw \\
            \lstick{\ket{\phi}}& \qw & \ghost{SWAP} & \qw & \qw } }
\end{mdframed}

\newpage

\part[5] Suppose the top qubit in the above circuit is measured in the
  computational basis. What is the probability that the measurement
  result is 0 and what is the posterior state of the remaining two
  qubits in this case?

  \newpage 

\part[5] Suppose the two input qubits are in a mixed state
  $\rho\otimes \sigma$. What is the probability of measuring 0 if we
  run the circuit on them?
  
  \newpage
  \bonuspart[5] How do the results of the previous parts change if the
  bottom two registers are $n$-qubit states, and swap denotes the
  $2n$-qubit gate that swaps the first $n$ qubits with the last $n$
  qubits?

  \newpage 
  \end{parts}

\question (5-qubit code) Consider a quantum error correcting code that
  encodes one logical qubit into five physical qubits, with the
  logical basis states

  \begin{align*}
    \ket{0_L} = & \frac{1}{4}(\ket{00000} \\
                & +\ket{10010} + \ket{01001} + \ket{10100} + \ket{01010} + \ket{00101}
    \\
                &  -\ket{11000} - \ket{01100} - \ket{00110} -\ket{00011} - \ket{10001}\\
                & - \ket{01111} - \ket{10111} - \ket{11011}
                  -\ket{11101} - \ket{11110} )  \\
    \ket{1_L} = & \frac{1}{4}(\ket{11111} \\
                & + \ket{01101} + \ket{10110} + \ket{01011} + \ket{10101} +
                  \ket{11010}\\
                & - \ket{00111} - \ket{10011} - \ket{11001} -
                  \ket{11100} - \ket{01110} \\
                & - \ket{10000} - \ket{01000} - \ket{00100} -
                  \ket{00010} - \ket{00001} )
  \end{align*}

  \begin{parts}
  \part[5] Show that $\ket{0_L}$ and $\ket{1_L}$ are simultaneous
    eigenstates (with eigenvalue +1) of the operators below. (Hint:
    You can show this without explicitly checking every case.)
    \begin{align*}
      & X\otimes Z \otimes Z \otimes X \otimes I      \\
      & I \otimes X \otimes Z \otimes Z \otimes X \\
      & X\otimes I \otimes X \otimes Z \otimes Z\\
      & Z\otimes X \otimes I \otimes X \otimes Z\\
      & Z\otimes Z \otimes X \otimes I \otimes X  
    \end{align*}
    \newpage
  \part[5] Show that this code can correct an $X$ or $Z$ error acting
    on any of the five qubits. You should explain how the different
    possible errors would be reflected by a measurement of the error
    syndrome.

    \newpage

  \part[5] Find logical Pauli operators $X_L$ and $Z_L$ such that
    \[ X_L\ket{0_L} = \ket{1_L}, X_L \ket{1_L} = \ket{0_L}; \quad
      Z_L\ket{0_L} = \ket{0_L}, Z_L\ket{1_L} = -\ket{1_L} \, . \]
  \end{parts}
  
\end{questions}


\end{document}
