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

\newcommand{\dftn}{{\rm DFT}_N}
\newcommand{\dft}{{\rm DFT}}
\newcommand{\qftn}{{\rm QFT}_N}
\newcommand{\qft}{{\rm QFT}}


\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{\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{\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
\newcommand{\nl} {\mathcal{L}_1}

\newcommand{\NP}{{\rm NP}}
\newcommand{\coNP}{\operatorname{co-NP}}
\newcommand{\FACTOR}{{\rm FACTOR}}
\newcommand{\zns}{Z_N^*}
\newcommand{\ORDER}{{\rm ORDER}}

\begin{document}

\title{\vspace{-10mm}Introduction to Quantum Computation, UPB\\Winter 2022, Assignment 8\\{\large
\vspace{2mm}Due: January 12, at start of tutorial}}
\date{}
\maketitle


\section{Exercises}
\begin{enumerate}
    \item Let $U\in\mathcal{L}(\complex^d)$ be a unitary operator with eigenvalues $e^{2\pi i \theta_k}$ for $\theta_k\in[0,1)$. Assume for simplicity that all $\theta_k$ can be expressed perfectly using $n$ bits.
    \begin{enumerate}
        \item Let $\ket{\psi_k}$ be an eigenvector of $U$ with eigenvalue $e^{2\pi i \theta_k}$. In class, we saw that the phase estimation algorithm maps $\ket{0^n}\ket{\psi_k}\mapsto \ket{2^n\theta_k}\ket{\psi_k}$. In other words, we extract the \emph{phase} of the eigenvalue. What happens when the input state $\ket{\psi_k}$ \emph{is not} an eigenvector of $U$? In other words, suppose we instead input state $\ket{0^n}\ket{\phi}$ to the phase estimation algorithm. What state does the algorithm produce? What happens when we measure the first register of the output in the standard basis?
        \item Suppose for all $k\in\set{1,\ldots, d}$, $\theta_k\in\set{0,1/2}$, i.e. $U$ has eigenvalues in $\set{1,-1}$. Given any state $\ket{\phi}$ as for part (a), give a quantum circuit for randomly projecting $\ket{\phi}$ onto either the $+1$ or $-1$ eigenspace of $U$, with the help of a classical register which indicates which of the two spaces we've projected onto. What is the expression determining the probability of projecting down to each of the two eigenspaces (this should depend on $\ket{\phi}$)?
        \item Consider the special case of part (b) in which $U$ is a $2\times 2$ unitary matrix, and is Hermitian. Suppose we wish to measure state $\ket{\phi}$ via observable $U$, i.e. to obtain outcome $1$ or $-1$ (the eigenvalues of $U$), and then project $\ket{\phi}$ onto the corresponding eigenspace. Give a simple circuit which accomplishes this.
    \end{enumerate}
    \item
        Just as we defined norms of vectors, one can define norms on matrices. For $A\in\mathcal{L}(\complex^d)$, define the \emph{induced Euclidean norm} (a.k.a. operator or spectral norm)
        \[
            \norm{A}:= \max_{v\in\complex^d\text{ s.t. }\norm{v}_2=1} \norm{Av}_2,
        \]
        where recall $\norm{v}_2=\sqrt{\langle v,v\rangle}$ denotes the Euclidean norm of $v$. In other words, the spectral norm tells the maximum amount by which $A$ can ``stretch'' a vector $v$. Based on this, we can define distance measure $d(A,B)=\norm{A-B}$.
    \begin{enumerate}
        \item Let us first understand why the spectral norm is useful in quantum information. Given two unitaries $U,U'\in\mathcal{L}(\complex^d)$ such that $\norm{U-U'}\leq \epsilon$ for some small $\epsilon\approx 0$, and an arbitrary state $\ket{\psi}\in\complex^d$, why is it intuitively difficult to distinguish via any measurement the output of $U\ket{\psi}$ versus $U'\ket{\psi}$?

        \item Let us now apply the intuition behind (a) to simplify the circuit for the quantum Fourier transform. Consider phase gate
        \[
            V=
        \left(
          \begin{array}{cc}
            1 & 0 \\
            0 & e^{i\phi} \\
          \end{array}
        \right).
        \]

         Compute $d(I,V)$, for $I$ the $2\times 2$ identity matrix.
        \item Consider a circuit consisting of $L$ unitary operations $U_i\in\mathcal{L}(\complex^d)$,

            \[
                U=U_L U_{L-1}\cdots U_1.
            \]
            Suppose we omit an arbitrary operation $U_i$, i.e. set $U'=U_L\cdots U_{i+1}U_{i-1}\cdots U_1$. Show that $\norm{U-U'}=\norm{I-U_i}$. (Hint: Convince yourself first that the spectral norm is unitarily invariant, i.e. $\norm{A}=\norm{UAV}$ for any unitaries $U$ and $V$.)
        \item More generally, it can be shown that if we drop a set of unitaries $S=\set{U_i}$ from $U$, then
        \[
            \norm{U-U'}\leq \sum_{U_i\in S}\norm{I- U_i}.
        \]
        The proof proceeds by induction on $\abs{S}$, and the proof idea essentially is the same as for a simpler problem, which you will instead solve in this question. For any unitary matrices $U,V,U',V'$, show that
        \[
            \norm{UV-U'V'}\leq\norm{U-U'}+\norm{V-V'}.
        \]
        Intuitively, this says that if we replace ``ideal'' unitaries $U$ and $V$ with ``approximate'' ones $U'$ and $V'$, respectively, the effect of replacing $UV$ with $U'V'$ can be bounded via the spectral norm.

        (Hint: Add and subtract a carefully chosen term to $UV-U'V'$, and then apply the triangle inequality and submultiplicativity properties for the spectral norm, which say that $\norm{A+B}\leq\norm{A}+\norm{B}$ and $\norm{AB}\leq \norm{A}\norm{B}$, respectively.)

        \item Observe now that the quantum Fourier Transform $\qftn$ for $N=2^n$ from class requires $O(n^2)$ gates. Given the exercises above, design a quantum circuit $U'$ using just $O(n\log n)$ gates, such that $\norm{U-U'}\leq 1/n$. (Hints: (1) Recall from class that for large $s$, the entry $e^{2\pi i/2^s}\approx 1$ in the phase gates $R_s$. Reflecting on this should give you an overall battle plan for how to approach this question. (2) To formalize things, start by proving that $\abs{e^{2\pi i/2^s}-1}\leq 2\pi/2^s$. The Wikipedia page for trigonometric identities, as well as Taylor series truncations, will be your friends here. The answer to this hint should tell you how roughly many phase gates you need on each wire to ensure the overall error spectral norm stays below $1/n$.)

            \end{enumerate}

    \item
    \begin{enumerate}
        \item Prove that $\FACTOR\in\NP\cap\coNP$. In your containment proof for $\coNP$, you will need to argue that the number of factors is at most polylogarithmic in the input $N$ to $\FACTOR$.
        \item Recall from Fact 16 of Lecture 10 that for any prime $p\in\ints^+$, there is a generator $g\in Z_p$, such that any $e\in Z_p$ can be written $g^k\equiv e\mod p$ for some $k\in \set{1,\ldots, p-1}$. Using Fermat's Little Theorem, prove that picking non-zero $e$ uniformly at random from $Z_p$ is equivalent to picking $k\in\set{1,\ldots,p-1}$ uniformly at random. In your answer,  \emph{do not} assume \emph{a priori} that $k\in\set{1,\ldots, p-1}$ as stated in Fact 16; rather, start by assuming there is some $k$ for each $e$, and use FLT to prove that indeed WLOG $k\in \set{1,\ldots, p-1}$.
    \end{enumerate}


\end{enumerate}

\end{document}