\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{\fid}{\operatorname{F}}
\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{\trans}[1]{\setft{T}\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{\dim}{\operatorname{dim}}
\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}

\begin{document}

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

\section{Exercises}
\begin{enumerate}
    \item \textbf{Local Hamiltonians.}
         Recall that in the NP-complete problem MAX CUT, the input consists of a simple, undirected graph $G=(V,E)$, and a threshold parameter $t$. The output is to decide whether the maximum cut in $G$ has size at least $t$. Here, a \emph{cut} in $G$ is a partition $\set{V_1,V_2}$ of $V$, and the \emph{size} of the cut is the number of edges in $E$ with precisely one endpoint in each of $V_1$ and $V_2$. Give a $2$-local Hamiltonian $H$ on $n$ qubits whose ground state energy $\lambda(H)$ equals precisely $\abs{E}-\opt$, for $\opt$ the size of the optimal cut in $G$. (Hint: For each edge $(i,j)\in E$, start by thinking about $2$-local quantum constraint $H_{ij}=Z_i\otimes Z_j$; what is the matrix representation of $H_{ij}$?)

    \item \textbf{Containment of $\klh$ in $\QMA$.}
    \begin{enumerate}
        \item In class, given $k$-local Hamiltonian $H=\sum_{i=1}^m H_i$, we saw how to put $\klh$ in QMA for $k\in O(1)$ via a simple measurement strategy: Given the ground state $\ket{\psi}$ as a proof, we picked a uniformly random local constraint $H_i$ and measured it (as an observable) against our state $\ket{\psi}$. The expected value of this measurement was $\lmin(H)/m$. We then converted this to a high-probability statement via the H\"{o}ffding bound.

            There is, however, a more complicated ``off-the-shelf'' way of achieving the same containment, which we explore in this question: The phase estimation algorithm. You may assume for this question that $\snorm{H_i}\leq 1$ for each $i$.
            \begin{enumerate}
                \item Suppose we could simulate $U=e^{icH}$ perfectly in polynomial time for $c\in O(1/\poly(n))$. Show how to use the quantum phase estimation algorithm (QPE) from Lecture 4 to verify the ground state energy of $H$ in polynomial time. Two points you will need to consider: (1) To which accuracy must the phase be implemented, and how does this affect how many times we call $U$ as a black box? (2) In the NO case (i.e. when $\lmin(H)\geq \beta$), why does your approach correctly reject any proof $\ket{\psi}$?
                \item We are left with the task of simulating $U=e^{icH}$. For simplicity, assume we have $H=H_1+H_2$ (for $H_i$ each acting on $k$ qubits). A tool we may use for the simulation is the \emph{Trotter formula}, which says that for evolution time $t\in\reals^+$,
                    \[
                        e^{i(H_1+H_2)t}=\left(e^{\frac{iH_1t}{r}}e^{\frac{iH_2t}{r}}\right)^r + O(t^2/r).
                    \]
                    In other words, we can break up the time evolution as a \emph{product} of evolving $H_1$ and $H_2$ independently for short time slices, $t/r$. The error $\epsilon$ so attained (with respect to spectral norm) then scales as $\epsilon\in O(t^2/r)$, assuming $\snorm{e^{ic(H_1+H_2)t}}\leq 1$ (why does this hold for all $t\in\reals$?).
                    \begin{enumerate}
                        \item Recall that our goal is to simulate $U=e^{ic(H_1+H_2)}$. Since $\klh$ has an inverse polynomial completeness-soundness gap, it suffices to simulate $U$ to within error $\epsilon:=1/p(n)$ for some sufficiently large polynomial $p$; call this simulation $U_\epsilon$. What choices of $t$ and $n$ suffice to implement $U_\epsilon$ according to the Trotter formula?

                        \item Show how to use the Trotter formula to implement $U'$ for your choice of $t$ and $n$. (Hint: How many qubits does $e^{iH_jt}$ act on?)
                    \end{enumerate}
            \end{enumerate}
    \end{enumerate}
    \item \textbf{QMA-hardness of $\klh$.} This question will get you to work through some of the missing details in the proof of QMA-hardness presented in class. Again, we assume the notation introduced therein.
        \begin{enumerate}
            \item Prove that $\psihistb \hout\psihist=\frac{1}{m+1}\Pr[V\text{ rejects }\ket{\psi}]\leq \frac{\epsilon}{m+1}$  in the YES case.
            \item Prove that
\[
    U\hprop U^\dagger = \sum_{t=0}^{m-1} -I\otimes\ketbra{t+1}{t}_D - I\otimes\ketbra{t}{t+1}_D+ I\otimes\ketbra{t}{t}_D+ I\otimes\ketbra{t+1}{t+1}_D.
\]
Convince yourself that $U\hprop U^\dagger = I_{A,B,C}\otimes \Lambda_D$ indeed has representation
\[
    \Lambda := \left(
                 \begin{array}{cccccc}
                   1 & -1 & 0 & 0 & 0 & \cdots \\
                   -1 & 2 & -1 & 0 & 0 &\cdots \\
                   0 & -1 & 2 & -1 & 0 &\cdots\\
                   0 & 0& -1 & 2 & -1 &\cdots\\
                   0 & 0 & 0 & -1 &\ddots & \ddots \\
                   \vdots & \vdots & \vdots & \vdots & \ddots & \ddots
                 \end{array}
               \right).
\].
        \item In the NO case, prove that $\max_{\substack{\ket{y}\in\Null(\hprop')\\\enorm{\ket{y}}=1}} \bra{y}\Pi_{N_2}\ket{y}=\frac{m-1}{m+1}$.
        \item In the NO case, prove that $\bra{y}\Pi_{N_1}+\Pi_{N_3}\ket{y}\leq \frac{1+\sqrt{\epsilon}}{m+1}$.
        \end{enumerate}
\end{enumerate}
\end{document}
