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

\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.}}
\newcommand{\klh}{\operatorname{k-LH}}
\newcommand{\hin}{H_{\rm in}}
\newcommand{\hout}{H_{\rm out}}
\newcommand{\hprop}{H_{\rm prop}}
\newcommand{\hstab}{H_{\rm stab}}
\newcommand{\psihist}{\ket{\psi_{\rm hist}}}
\newcommand{\psihistp}{\ket{\psi'_{\rm hist}}}
\newcommand{\psihistb}{\bra{\psi_{\rm hist}}}
\newcommand{\Null}{\operatorname{Null}}


\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}{\lambda_{\operatorname{min}}}
\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{\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{\pBPP}{{\rm PromiseBPP}}
\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{\unitaries}{U(\spa{A}\otimes\spa{B})}

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


\mathchardef\mhyphen="2D

\newcommand{\ayes}{A_{\rm yes}} %CHECK
\newcommand{\ano}{A_{\rm no}} %CHECK
\newcommand{\nl} {\mathcal{L}_1}


\bibliographystyle{alpha}

\begin{document}

\title{\vspace{-10mm}Quantum Complexity Theory, UPB\\Winter 2020, Assignment 6\\{\large To be completed by: Tuesday, January 26, start of tutorial}}
\date{}
\maketitle
\noindent \textbf{This assignment assumes the notation and terminology from Lectures 7 and 8.}

\section{Exercises}
\begin{enumerate}
    \item \textbf{Gentle measurement.} In this exercise we state and prove a variant of the Gentle Measurement Lemma seen in class. Let $\ket{\psi}$ be a pure quantum state, and consider any $0\preceq M\preceq I$. (For example, $M$ could be a projector, but need not be.) Suppose $\trace(M\ketbra{\psi}{\psi})\geq 1-\epsilon$ for $\epsilon>0$. Prove that
        \[
            \trnorm{\ketbra{\psi}{\psi}-\frac{\sqrt{M}\ketbra{\psi}{\psi}\sqrt{M}}{\trace(M\ketbra{\psi}{\psi})}}\leq 2\sqrt{\epsilon}.
        \]
     \item \textbf{SDPs.} In our standard form for SDPs, we used Hermiticity-preserving maps $\Psi$ and $\Psi^*$, where recall the latter is the \emph{adjoint} of the former.
        \begin{enumerate}
            \item Let $\Phi(X)=UXU^\dagger$ for unitary $U$. What is $\Phi^{*}$?

            \item Let $\Phi(X_{AB})=\trace_B(X_{AB})$. What is $\Phi^{*}$?
        \end{enumerate}
    \item \textbf{QIP=PSPACE.} Recall in the correctness analysis, and particularly in Lemma 40, that we defined dual feasible solution
    \[
        Y=\frac{1+2\epsilon}{T}\sum_{t=0}^{T-1}\frac{1}{\beta_t}\Pi_t.
    \]
    \begin{enumerate}
        \item Show that $Y\succeq 0$.
        \item Prove that
    \[
        \trace(W_T)=\trace\left(e^{-\epsilon\delta\sum_{j=0}^{T-1}\Phi^*\left(\frac{1}{\beta_j}\Pi_j\right)}\right)\geq e^{-\epsilon\delta\lmin\left(\Phi^*\left(\sum_{j=0}^{T-1}\frac{1}{\beta_j}\Pi_j\right)\right)}.
    \]
        \item For any $t\in{1,\ldots, T}$, use the Golden-Thompson inequality to show that
    \[
        \trace(W_t)\leq \trace(W_{t-1}e^{-\epsilon\delta\Phi^*(\Pi_{t-1}/\beta_{t-1})}).
    \]
    \item Use the fact that for any Hermitian $M$ satisfying $0\preceq M\preceq I$, and every real $r>0$,
    \[
        e^{rM}\preceq I+re^{r}M\quad\text{and}\quad e^{-rM}\preceq I-re^{-r}M,
    \]
    to obtain that
    \[
        e^{-\epsilon\left[\delta\Phi^*(\Pi_{t-1}/\beta_{t-1})\right]}\preceq I-\epsilon\delta e^{-\epsilon}\Phi^*(\Pi_{t-1}/\beta_{t-1}).
    \]
    (Hint: Use submultiplicativity of the spectral norm to show that $\snorm{\Phi^*(\Pi_{t-1})}\leq\snorm{Q^{-1}}$.)

    \end{enumerate}
\end{enumerate}
\end{document}
