<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt]{article}

\usepackage{hyperref}
\usepackage{xcolor}


\usepackage{amssymb, amsmath, lineno, amsthm, pdfsync, bbm, graphicx}
\usepackage{MnSymbol,wasysym}


\tolerance=2000
\textwidth 6.55in
\textheight 9.0in
\oddsidemargin 0.001in
\evensidemargin 0.001in
\topmargin -0.4in

\newtheorem{theorem}{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{theoremnonum}{Theorem} 
\newtheorem{definition}{Definition}[section] 
\newtheorem{lemma}[theorem]{Lemma} 
\newtheorem{corollary}[theorem]{Corollary} 
\newtheorem{claimnonum}{Claim} 
\newtheorem{mycomment}{comment}[section] 
\newtheorem{conjecture}[theorem]{Conjecture} 
\newtheorem{problem}{Problem} 
\newcommand{\finishproof}{~$\Box$}
\newtheorem{remark}{Remark} 


\newcommand{\AND}{\; \wedge \;}

\newcommand{\SAT}{{\sf SAT}}
\newcommand{\DTIME}{{\sf DTIME}}
\newcommand{\NTIME}{{\sf NTIME}}
\newcommand{\DSPACE}{{\sf DSPACE}}
\newcommand{\NSPACE}{{\sf NSPACE}}
\newcommand{\EE}{{\sf E}}
\newcommand{\EXP}{{\sf EXP}}
\newcommand{\NEXP}{{\sf NEXP}}
\newcommand{\PSPACE}{{\sf PSPACE}}
\newcommand{\eL}{{\sf L}}
\newcommand{\NL}{{\sf NL}}
\newcommand{\LOGSPACE}{{\sf LOGSPACE}}
\newcommand{\Pe}{{\sf P}}
\newcommand{\NP}{{\sf NP}}
\newcommand{\coNP}{{\sf coNP}}
\newcommand{\FP}{{\sf FP}}
\newcommand{\PH}{{\sf PH}}
\newcommand{\CH}{{\sf CH}}
\newcommand{\PP}{{\sf PP}}
\newcommand{\num}{{\sf\#}}
\newcommand{\numP}{{\sf\#\Pe}}
\newcommand{\ParP}{{\mbox{$\oplus$\Pe}}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}} 
\newcommand{\C}{\mathbb{C}}
\newcommand{\R}{\mathbb{R}} 
\newcommand{\ket}[1]{{|{#1} \rangle}} 
\newcommand{\bra}[1]{{\langle {#1}|}}
\newcommand{\bracket}[2]{{\langle {#1} | {#2} \rangle}}
\newcommand{\nb}{{\bf {\sf n}}} 
\newcommand{\Xb}{{\bf {\sf X}}}
\newcommand{\Xbi}{{\Xb}_i}
\newcommand{\Xbj}{{\Xb}_j}
\newcommand{\nbt}{{\tilde{\nb}}}
\newcommand{\nbi}{{\nb_i}}
\newcommand{\nbj}{{\nb_j}}
\newcommand{\nbti}{{\tilde{\nb}_i}}
\newcommand{\nbtj}{{\tilde{\nb}_j}}
\newcommand{\Sb}{{{\bf{\sf S}}}}
\newcommand{\Cb}{{\bf {\sf C}}}
\newcommand{\Zb}{{\bf {\sf Z}}}
\newcommand{\Yb}{{\bf {\sf Y}}}
\newcommand{\Hb}{{\bf {\sf H}}}
\newcommand{\Ub}{{\bf {\sf U}}}
\newcommand{\Vb}{{\bf {\sf V}}}
\newcommand{\Ufb}{{\bf {\sf U}}_f}
\newcommand{\blue}[1]{\textcolor{blue}{#1}}
%\newcommand{\gcd}{{\mbox{\rm gcd}}}

\sloppy
 
\begin{document}
\thispagestyle{empty}
% The paper really starts here.

\noindent {\bf Assignment 5}\\
\noindent DUE: Thursday, 4/27/2023, work in pairs.\\[-0.2in]

\begin{enumerate}
\item
The first problem is about proving the correctness of
 our construction
of a quantum circuit for computing the Quantum Fourier Transform (QFT).
From the original QFT, we derived the following form (same thing, written in two ways):
\begin{eqnarray*}
   \Ub_{FT} &amp; = &amp; \frac{1}{2^{n/2}}\left(\ket{0} + e^{2\pi i 0.x_n}\ket{1}\right)\otimes
                  \left(\ket{0} + e^{2\pi i 0.x_{n-1}x_n}\ket{1}\right)\otimes
                  \cdots
                  \otimes
                  \left(\ket{0} + e^{2\pi i 0.x_1\cdots x_n}\ket{1}\right)\\
   &amp; = &amp; \frac{1}{2^{n/2}}\bigotimes\limits_{j=0}^{n-1}\left(\ket{0} + 
              e^{2\pi i 0.x_{n-j}x_{n-j+1}x_{n-j+2}\cdots x_n}\ket{1}\right)\label{final}
\end{eqnarray*}
where, with $x = x_12^{n-1} + x_22^{n-2} + \cdots + x_{n-1}2 + x_n$,
 we defined 
 $0.x_{n-j}x_{n-j+1}x_{n-j+2}\cdots x_n = x_{n-j}2^{-1} + 
 x_{n-j+1}2^{-2} + x_{n-j+2}2^{-3} + \cdots + x_n2^{-j}$.
 From this we derived the circuit depicted below. Prove, by induction
 on $j$, that the output of the $j^{th}$ wire in the circuit is
the $j^{th}$ factor in the above tensor product, namely,
$\ket{0} + 
              e^{2\pi i 0.x_{n-j}x_{n-j+1}x_{n-j+2}\cdots x_n}\ket{1}$.
The base case $j=0$ was done in class, as was $j=1$ (although in class the indexing differed by 1, i.e., we had $j=1$ and $2$). Follow through with an inductive proof that if the factor is correct for $j$ it is also correct
for $j+1$.

\input{qftcircuit.pdf_t}

HINT: Pay careful attention to what happens as you go from line $j$
(with input state $\ket{x_{n-j}}$) to $j+1$ (with input state
$\ket{x_{n-j-1}}$).\\

\hrule

\item Here we'll turn the crank in the final stage of Shor's algorithm (which is classical, but still very interesting), where we determine $r$ based on continued fractions. The process was discussed in class and is detailed in Appendix K. Following the second example in the text, we give possible values for $y$. The idea is to find $r$. 

Take $n = 14$ and suppose we first find $y = 8374$. Using the continued fraction expansion of $y/2^n$, find the first partial sum with denominator $&lt; 2^7 = 128$. This gives you one candidate $r$. Give the computation and state the value of the candidate $r$. Now suppose we repeated the entire quantum algorithm (QFT and all) and obtained $y = 8556$. Via the same procedure, you should find another candidate $r$, which is a multiple of the first one. Which one is the correct $r$?\\

\hrule

\item Finally, let's carefully derive a relation which leads to the stated run time of Grover's algorithm. We use the definitions and notations given in the text and in lecture:
\begin{eqnarray*}
\ket{\phi} &amp; = &amp; \frac{1}{2^n}\sum\limits_{x=0}^{2^n - 1}\ket{x}\\
   \ket{a_{\perp}} &amp; = &amp; \frac{1}{\sqrt{2^n-1}}\sum\limits_{x = 0, x \not = a}^{2^n - 1}\ket{x}\\
   W &amp; = &amp; 2\ket{\phi}\bra{\phi} - 1\\
   V &amp; = &amp; 1 - 2\ket{a}\bra{a}\\
   \sin(\theta) &amp; = &amp; \frac{1}{2^{n/2}},~~~~~\mbox{\rm ~in terms of which we find,}\\
   	\ket{\phi}  &amp; = &amp; \sin(\theta)\ket{a} + \cos(\theta)\ket{a_{\perp}}
\end{eqnarray*}
\begin{enumerate}
\item Using some elementary trigonometric identities, prove that
\begin{eqnarray*}
    WV\ket{a} &amp; = &amp; \cos(2\theta)\ket{a} - \sin(2\theta)\ket{a_{\perp}}\\
    WV\ket{a_{\perp}} &amp; = &amp; \sin(2\theta)\ket{a} + \cos(2\theta)\ket{a_{\perp}}.
\end{eqnarray*}
\item Using part (a), prove the following by induction on $k$:
\begin{eqnarray}\label{main}
   (WV)^k\ket{\phi} = \sin((2k+1)\theta)\ket{a} + \cos((2k+1)\theta)\ket{a_{\perp}}.
\end{eqnarray}
You will almost certainly find the following identities\footnote{No need to prove these identities, but if you have some free time on your hands, you may find it fun to exploit our old friend
$e^{i\theta} = \cos\theta + i\sin\theta$ to derive them.} useful:
\begin{eqnarray*}
    \sin((2k+1)\theta)\cos(2\theta)+\cos((2k+1)\theta)\sin(2\theta)
       &amp; = &amp; \sin((2k+3)\theta)\\
    -\sin((2k+1)\theta)\sin(2\theta) + \cos((2k+1)\theta)\cos(2\theta)
       &amp; = &amp; \cos((2k+3)\theta).
\end{eqnarray*}
\item Now remember what we're after in Grover's algorithm: $\ket{a}$!
The parameter $k$ is the number of times we apply the Grover
iterate $WV$ to $\ket{\phi}$ in order to get as close as possible
to $\ket{a}$. Show how Eq.~(\ref{main}) leads to a desired
value of $k$ of about $\frac{\pi}{4}2^{n/2} = \frac{\pi}{4}\sqrt{N}$
(where $N$ here is defined as $2^n$). 

\end{enumerate}

\end{enumerate}


\end{document}
</pre></body></html>