min-finding.tex

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{algorithm}
\usepackage{algpseudocode}

\begin{document}
\pagestyle{empty} 

\begin{algorithm}[ht]
	\caption{Finding the minimum}
	\label{FindingMin}
	\begin{algorithmic}[1]

		\Require Quantum access to a N-dimensional vector $u$.
		\Ensure Find the index of the minimum value of $u$ with probability at least $1/2$.
		\vspace{10pt}
		\State Uniformly choose a threshold index $j$ from $0..N-1$.
		\Repeat
		\State Initialize the memory as $\sum_{i} \frac{1}{\sqrt{N}}|i\rangle|j\rangle$.
		Mark every item $i$ for which $u_i < u_j$.
		\State Apply QESA.
		\State Measure the index register. Suppose the output is $i'$.

		Assign $j \leftarrow i'$ to be the new threshold index if $u_{i'} < u_j$.
		\Until the queries to $U$ are more than $22.5\sqrt{N} + 1.4\log^2{N}$.
		\State Return $j$.
	\end{algorithmic}
\end{algorithm}

\end{document}