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


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

\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{\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}}

\newcommand{\klh}{MAX-$k$-local Hamiltonian}

\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 4\\{\large To be completed by: Tuesday, December 15, start of tutorial}}
\date{}
\maketitle
\noindent \textbf{This assignment assumes the notation and terminology from Lectures 4 and 5.}

\section{Exercises}
\begin{enumerate}
    \item
        \textbf{A BQP-complete problem: Matrix inversion.} In this question, we assume the terminology from Section 3 of Lecture 4 of the course notes.
        \begin{enumerate}
            \item  Recall from Lecture 4 the equation
        \[
            \ket{\widetilde{x}}=\frac{1}{\sqrt{m+1}}\left(\ket{0}\ket{0^n}+\ket{1}V_1\ket{0^n}+\cdots+\ket{m}V_m\cdots V_1\ket{0^n}\right).
        \]
            Assume, without loss of generality, that in all but the last time step, $m$, $V$ sets the output qubit to $\ket{0}$, and only in time step $m$ does $V$ perform a CNOT to copy over its answer to the output qubit. Prove that (where recall $\Pi=\ketbra{1}{1}$ is a single qubit projector onto the output qubit of the second register):
    \begin{itemize}
        \item If $V$ denotes a YES instance, then $\bra{\widetilde{x}}\Pi\ket{\widetilde{x}}\geq \frac{2}{3(m+1)}$.
        \item If $V$ denotes a NO instance, then $\bra{\widetilde{x}}\Pi\ket{\widetilde{x}}\leq \frac{1}{3(m+1)}$.
    \end{itemize}

        \item How can we modify $V$ in a seemingly trivial manner in order to boost the completeness/soundness bounds of the previous exercise to constants (i.e. independent of $m$)?

            \item Choose $A=I-e^{-1/m}U$ for scalar $e^{-1/m}$. Prove that now $\kappa(A)\in O(m)$ for the new definition of $A$. (Hint: You only need to use the fact that $U$ is unitary, not the specific definition of $U$. Also, use the fact that for normal operators $A$, the singular values of $A$ are $\set{\abs{\lambda(A)}}$ (why?).)
        \end{enumerate}

    \item
        \textbf{Weak error reduction for QMA.} Suppose the QMA prover sends $k$ copies of its proof, $\ket{\psi}$, instead of a single copy. On the $j$th copy of the proof, the verifier runs the verification circuit $Q_n$. Finally, the verifier measures the output qubits of all runs of $Q_n$, takes a majority vote of the resulting bits, and accepts if and only if the majority function yields $1$. Prove that this procedure indeed amplifies the completeness and soundness parameters for QMA. (Hint: In the NO case, a cheating prover is \emph{not} obligated to send $k$ copies of some state $\ket{\psi}$ in tensor product, but rather can cheat by sending a large entangled state $\ket{\phi}\in\B{k\cdot p(n)}$ across all $k$ proof registers. Why does entanglement across proofs not help the prover in the NO case?)

    \item \textbf{Strong error reduction for QMA.} All references below are to the Lecture 5 course notes.
    \begin{enumerate}
        \item Prove Equations $(8)$-$(11)$.
        \item What is $\enorm{S_0Q^\dagger E_1Q\ket{\phi}}$?
        \item Prove that after we measure the right hand side of Equation~(6) with $\set{S_0,S_1}$, we obtain $S_1$ with probability $p$ and $S_0$ with probability $1-p$. Similarly, measuring the right hand side of Equation~(7) with ${S_0,S_1}$ yields $S_0$ with probability $p$ and $S_1$ with probability $1-p$.

        \item  Conclude from the last exercise that after the first iteration of the while loop, $y_1=y_2$ with probability $p$. Accordingly, $y_1\neq y_2$ with probability $1-p$.\\
    \end{enumerate}
\end{enumerate}

\end{document}