%JULIA HEADER
\documentclass{article}
\usepackage{amsmath,amsthm}
\usepackage{amssymb,latexsym}
\usepackage{epsfig}
\usepackage{hyperref}
\usepackage{float}
\usepackage{fullpage}
\usepackage{enumerate}
\usepackage{paralist}
\usepackage{graphicx}
\usepackage{algpseudocode}
%\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{\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}

%END SEV HEADER

%%%YOU MIGHT WANT TO KEEP THESE THREE LINES INSTEAD OF YOURS
\usepackage{color,graphicx}
\newcommand{\snote}[1]{\textcolor{blue}{ {\textbf{(Sev: }#1\textbf{) }}}}
\newcommand{\jnote}[1]{\textcolor{red}{ {\textbf{(Julia: }#1\textbf{) }}}}

\bibliographystyle{alpha}

\begin{document}

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

This homework gets you to practice using Grover's algorithm and amplitude amplification.

\section{Exercises}
\begin{enumerate}
    \item Recall the unstructured search problem, for which we are given black-box access to the bits of a string $x=x_1\cdots x_N\in\set{0,1}^N$, for $N=2^n$. The goal is to find a solution, i.e. an index $i$ such that $x_i=1$, if such an index exists. Denote by $t$ the Hamming weight $x$, i.e. the number of bits of $x$ which are set to $1$; note that $t$ is unknown to you.

        In the lecture, we saw that running the Grover iterate $k=O(\sqrt{N/t})$ times suffices to find a solution. However, this depended on knowing $t$, which one does not know in general. Nevertheless, it is possible to find a solution even without knowing $t$ using an expected number of $O(\sqrt{N/t})$ queries. In this question, we will see how.\\

                Consider the following algorithm:
                \begin{enumerate}
                    \item[i.] Set $m=1$, $\lambda = 6/5$.
                    \item[ii.] Choose $j$ uniformly at random from set $\set{1,\ldots, m}$.
                    \item[iii.] Apply the Grover iterate $j$ times.
                    \item[iv.] Measure, and stop if a solution is found.
                    \item[v.] Else, set $m=\min(\lambda m, \sqrt{N})$. Return to Step ii.
                \end{enumerate}
            We now analyze this algorithm. Assume throughout this question that $t\leq 3N/4$. (Why is the problem trivial to solve if $t>3N/4$?)
            \begin{enumerate}
                \item Set $\theta$ such that $\sin^2\theta = t/N$, and $m_0=1/\sin(2\theta)$. Show that $m_0<\sqrt{N/t}$.
                \item It can be shown that whenever $m\geq 1/\sin(2\theta)$, the probability of obtaining a correct solution in step iv is at least $1/4$. Thus, intuitively, we wish to increment $m$ up to at least $1/\sin(2\theta)$ in step v as quickly as possible, but without using more than $O(\sqrt{N/t})$ queries. This explains the use of a geometric progression obtained by multiplying by $\lambda>1$ each time step v is run.\\

                    What is the number of times step ii has to be run before we are guaranteed $m\geq 1/\sin(2\theta)$?
                \item  Once $m\geq 1/\sin(2\theta)$, we shall say the algorithm has reached the ``critical stage''. Show that the algorithm requires $O(\sqrt{N/t})$ queries to reach the critical stage.
                \item Suppose the algorithm reaches the critical stage. Show that the expected number of Grover iterations needed to find a solution is now $O(\sqrt{N/t})$. Conclude that the total number of queries required by the algorithm is $O(\sqrt{N/t})$.
            \end{enumerate}


           % \underline{Solution:} There are two parts to this question: Devising the algorithm itself, and then analyzing it.
%
%            For the first, we use a standard trick in algorithms design which is worth remembering. Namely, we run Grover's algorithm repeatedly, each time trying the next candidate value for $t$ from the sequence $t'=N/2,N/4,N/8,\ldots$. In other words, in iteration $i$, we set $t'=N/2^{i}$.
%
%            The second part is to realize that by choosing the geometric progression above for $t'$, we may not guess the correct value of $t$ \emph{exactly}, but at least there exists some $t^*$ in our progression satisfying $t\leq t^*\leq 2t$. But recall we said
%
%            Before we show this, let us calculate the overall query cost of the algorithm. Namely, the query cost in iteration $i$ is $O(\sqrt{N/t'})\in O(\sqrt{2^{i}})$. This implies the total cost over all iterations scales as the geometric series (where we assume that once we try $t'=t^*$, the algorithm finds a solution and we can stop trying smaller values of $t'$):
%            \[
%                \sum_{i=0}^{\lceil\log (N/t)\rceil-1} {2}^{i/2} =\frac{1-{2}^{\lceil \log (N/t) \rceil/2}}{1-\sqrt{2}}\in O(\sqrt{N/t}).
%            \]
%
%            Finally, let us show that if we replace $t$ with $ct$ for $c\in[1/2,2]$, the probability of success in Grover's algorithm by repeating the Grover iterate $O(ct$ times
%            \item Using part (a), give a quantum query algorithm which finds \emph{all $t$ solutions} using an expected number of $O(\sqrt{Nt})$ queries. (Hint: Note that your algorithm from part (a) produces a uniformly random sample from the set of solutions (with high probability).)\\
%
%            \vspace{-2mm}\underline{Solution:}


    \item      Assume we have black-box query access to a sequence of $N=2^n$ distinct integers, $x=x_0x_1\cdots x_{N-1}$ for $x_i\in\ints$. Specifically, we assume the ability to apply both the query map $O_x\;:\;\ket{i,0}\mapsto\ket{i,x_i}$ and its inverse. Note that each integer $x_i$ can be arbitrarily large, i.e. do not assume each integer is at most (say) $N$ in absolute value.

        Devise a quantum query algorithm, which with probability at least $2/3$, finds the minimum $x_i$ over all indices $i$. You should use $O(\sqrt{N})$ queries. You do not need to formally work out the full details of the algorithm and its analysis. Rather, describe the algorithm and argue why its runtime should be $O(\sqrt{N})$ at a high level.

        Hint: Try to do something along the lines of running Quicksort while being able to run Grover's algorithm as a subroutine. For your runtime analysis, you may simplify the Quicksort analysis by assuming that picking an index $i$ uniformly at random yields ``roughly'' the median of the sequence $x$, i.e. approximately half the indices $j$ will have $x_j<x_i$.

\end{enumerate}

\end{document}
