\documentclass{article}
\usepackage{amsmath,amsthm}
\usepackage{amssymb,latexsym}
\usepackage{epsfig}
\usepackage{hyperref}
\usepackage{float}
\usepackage{fullpage}
\usepackage{enumerate}
\usepackage{paralist}
\usepackage{graphicx}
\usepackage{algpseudocode}


\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{assumption}[theorem]{Assumption}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{alg}[theorem]{Algorithm}
\newtheorem{protocol}[theorem]{Protocol}
\newtheorem{problem}[theorem]{Problem}

\newcommand{\ip}[2]{\left\langle #1 , #2\right\rangle}
\newcommand{\tr}{\trace}
\newcommand{\setft}[1]{\mathrm{#1}}
\newcommand{\lin}[1]{\setft{L}\left(#1\right)}
\newcommand{\density}[1]{\setft{D}\left(#1\right)}
\newcommand{\unitary}[1]{\setft{U}\left(#1\right)}
\newcommand{\herm}[1]{\setft{Herm}\left(#1\right)}
\newcommand{\pos}[1]{\setft{Pos}\left(#1\right)}
\newcommand{\sep}[1]{\setft{Sep}\left(#1\right)}
\newcommand{\rank}[1]{\operatorname{rank}(#1)}
\newcommand{\ex}{\paragraph{Exercise.}}

\def\I{I}
\def\({\left(}
\def\){\right)}
\def\X{\mathcal{X}}
\def\Y{\mathcal{Y}}
\def\Z{\mathcal{Z}}
\def\W{\mathcal{W}}
\def\yes{\text{yes}}
\def\no{\text{no}}
\def\blog{\textup{log}}
\newcommand{\A}{\spa{A}}
\newcommand{\B}{\spa{B}}
\newcommand{\UA}{U_A}


\newcommand{\myparagraph}[1]{\paragraph{#1.}}

\newcommand{\eps}{\varepsilon}
\newcommand{\epssdp}{\varepsilon_{\rm sdp}}
\newcommand{\bra}[1]{\langle #1|}
\newcommand{\ket}[1]{|#1\rangle}
\newcommand{\braket}[2]{\langle #1|#2\rangle}
\newcommand{\ketbra}[2]{\ket{#1}{\bra{#2}}}
\newcommand{\lmin}[1] {\lambda_{\operatorname{min}}(#1)}
\newcommand{\lmax}[1] {\lambda_{\operatorname{max}}(#1)}
\newcommand{\lhyes} {\operatorname{LH_{yes}}}
\newcommand{\lhno} {\operatorname{LH_{no}}}
\newcommand{\CQ}{\mathcal{CQ}}
\newcommand{\lh}{\operatorname{LH}}
\newcommand{\flh}{\operatorname{5-LH}}
\newcommand{\klhh}{\operatorname{k-LH}}
\newcommand{\qma}{\operatorname{QMA}}
\newcommand{\enc}[1]{\left<#1\right>}

\newcommand{\C}{C}
\newcommand{\Id}{Id} %CHECK
\newcommand{\Exs}[2]{E_{#1}[#2]} %CHECK

\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}

\newcommand{\trace}{{\rm Tr}}

\newcommand{\norm}[1]{\left\|\,#1\,\right\|}       % norm
\newcommand{\pnorm}[1]{\left\|\,#1\,\right\|_p}       % norm
\newcommand{\onorm}[1]{\norm{#1}_{\mathrm{1}}}      % Euclidean norm for vectors
\newcommand{\enorm}[1]{\norm{#1}_{\mathrm{2}}}      % Euclidean norm for vectors
\newcommand{\trnorm}[1]{\norm{#1}_{\mathrm {tr}}}  % trace norm
\newcommand{\fnorm}[1]{\norm{#1}_{\mathrm {F}}}    % frobenius norm
\newcommand{\snorm}[1]{\norm{#1}_{\mathrm {\infty}}}    % spectral norm

\newcommand{\set}[1]{{\left\{#1\right\}}}    % braces for set notation
\newcommand{\ve}[1]{\mathbf{#1}}
\newcommand{\abs}[1]{\left\lvert #1 \right\rvert}
\newcommand{\optprod}{\OPT_P}
\newcommand{\opt}{\operatorname{OPT_1}}
\newcommand{\optt}{\operatorname{OPT_2}}
\newcommand{\newopt}{\operatorname{NEW-OPT}}
\newcommand{\swap}{\operatorname{SWAP}}
\newcommand{\poly}{\operatorname{poly}}
\newcommand{\cc}{d^{\frac{k}{2}}}
\newcommand{\OPT}{{\rm OPT}}
\newcommand{\QMA}{{\rm QMA}}
\newcommand{\MQA}{{\rm MQA}}
\newcommand{\NP}{{\rm NP}}
\newcommand{\PP}{{\rm P}}
\newcommand{\PH}{{\rm PH}}
\newcommand{\BPP}{{\rm BPP}}
\newcommand{\BQP}{{\rm BQP}}
\newcommand{\TCSP}{{\rm 2-CSP}}

\newcommand{\complex}{{\mathbb C}}
\newcommand{\reals}{{\mathbb R}}
\newcommand{\ints}{{\mathbb Z}}
\newcommand{\nats}{{\mathbb N}}

\newcommand{\spa}[1]{\mathcal{#1}}
\newcommand{\dens}{\mathcal{D}(\spa{A}\otimes\spa{B})}

\newcommand{\LL}{\mathcal{L}}
\newcommand{\DD}{\mathcal{D}}
\newcommand{\HH}{\mathcal{H}}
\newcommand{\UU}{\mathcal{U}}

\newcommand{\ayes}{A_{\rm yes}} %CHECK
\newcommand{\ano}{A_{\rm no}} %CHECK

\begin{document}

\title{\vspace{-10mm}Introduction to Quantum Computation, UPB\\Winter 2022, Assignment 6\\{\large Due: Thursday, December 1, at start of tutorial}}
\date{}
\maketitle

\section*{Exercises}
\begin{enumerate}
    \item Let $X_p$ be a random variable denoting a coin flip with bias $p\in[0,1]$, i.e. a coin flip which lands HEADS with probability $p$. In class, we claimed the maximum entropy $H(X_p)=1$ is achieved when $p=1/2$, i.e. when we have a fair coin.
        \begin{enumerate}
            \item Convince yourself of this fact visually by plotting $H(X_p)$ as $p$ ranges from $0$ to $1$. You may use a mathematics package such as Mathematica (available for download free at UPB), Matlab, GNU Octave (like Mathematica, but free for everyone), or anything that produces a plot. My hope is you will use this exercise as an excuse to download Mathematica or Octave and start tinkering with them, as they are very useful packages. (Matlab is excellent as well, but is not free at UPB.)
            \item Now prove rigorously that in the range $p\in[0,1]$, $H(X_p)$ is maximized for $p=1/2$. Hint: A simple and elegant proof can be given by first computing $2^{H(X_p)}$, and then applying the weighted Arithmetic-Geometric Mean inequality, which states in our setting that for $x_1,x_2,w_1,w_2\geq 0$
                \[
                    \frac{w_1x_1+w_2x_2}{w_1+w_2}\geq \sqrt[w_1+w_2]{x_1^{w_1}x_2^{w_2}}.
                \]
            \item Use Part (b) to argue that among two-qubit pure states $\ket{\psi_{AB}}\in\complex^2\otimes \complex^2$, the only states which are ``maximally entangled'' (i.e. maximizing the quantity $E(\ket{\psi_{AB}})$ from class) are those whose reduced state is $\rho_A = I/2$.
            \item Finally, prove that it does not matter whether we take $\rho_A$ or $\rho_B$ in Part (c) --- namely, prove that for any $\ket{\psi_{AB}}\in\complex^2\otimes\complex^2$,
                \[
                    S(\rho_A)=S(\rho_B).
                \]
                Observe that this is true even if $\rho_A\neq\rho_B$.
        \end{enumerate}

    \item This question asks you to practice working with operator functions, as they play a fundamental role in quantum computation. In particular, you will show that an operator $U$ is unitary if and only if there exists a Hermitian operator $H$ such that $U=e^{iH}$ for complex number $i$. This ties back to one of the most important equations in quantum mechanics, the \emph{Schr\"{o}dinger} equation, which roughly says that quantum systems evolve in time according to some ``Hamiltonian'' $H$, whose action on the system is given by $e^{iH}$; this is how the notion of unitary evolution actually comes about.

        \begin{enumerate}
        \item Let $H\in\herm{\complex^n}$ and $c\in\complex$. Using the Taylor series definition of $e^{cH}$, what does the spectral decomposition of $e^{cH}$ look like?
        \item Prove that for any $H\in\herm{\complex^d}$, $e^{iH}$ is unitary.
        \item Next, characterize the set of possible eigenvalues for a unitary matrix.
        \item Now prove that for any unitary $U\in\unitary{\complex^n}$, there exists an $H\in\herm{\complex^n}$ such that $U=e^{iH}$.
        \end{enumerate}

    \item In stark contrast to the complex numbers, for which $e^{x+y}=e^xe^y$ for all $x,y\in\complex$, the matrix analogue of this identity does \emph{not} hold in general.
        \begin{enumerate}
            \item Prove that for normal $X,Y$, if $[X,Y]=XY-YX=0$, then $e^{X+Y}=e^Xe^Y$. (Hint: Use the fact that commuting normal operators simultaneously diagonalize in a common eigenbasis.)
            \item Although $e^{X+Y}=e^Xe^Y$ does not hold for all normal $X$ and $Y$, the operator $e^{X+Y}$ can nevertheless be approximated via the Lie Product Formula, which says that for  any normal $X$ and $Y$:
                \[
                    e^{X+Y}=\lim_{m\rightarrow\infty}\left(e^{\frac{X}{m}}e^{\frac{Y}{m}}\right)^m.
                \]
                In words, to approximate $e^{X+Y}$, we can repeatedly switch back and forth between applying small slices of $e^{X/m}$ and $e^{Y/m}$ instead. (Think of $m$ as a very large number.)

                Prove the Lie Product formula. (Hints: Your goal is to argue that
                \[
                    e^{\frac{X}{m}}e^{\frac{Y}{m}}=e^{\frac{X}{m}+\frac{Y}{m}+O\left(\frac{1}{m^2}\right)}.
                \]
                Once you have this, you can use the continuity of the exponential to take the limit as $m\rightarrow\infty$. To get the equation above, start by using Taylor series expansions to write $e^{\frac{X}{m}}e^{\frac{Y}{m}}$ up to first order terms. Then use the fact that there is a constant $c$ which, for all $n\times n$ matrices $B$ with $\snorm{B}< 1/2$, satisfies $\snorm{\log(I+B)-B}\leq c\snorm{B}^2$. Here, $\snorm{X}$ denotes the spectral or operator norm of matrix $X$, which can formally be defined equivalently as either the largest singular value of X, or the largest eigenvalue of $\sqrt{X^\dagger X}$. In the special case where $X$ is diagonalizable, $\snorm{X}$ equals the largest absolute value of any eigenvalue of $X$, i.e. $\max_{\lambda(X)}\abs{\lambda(X)}$.)
        \end{enumerate}
\end{enumerate}

\end{document}