Sequential quantum mixing for slowly evolving sequences of Markov chains
Vedran Dunjko
Hans J. Briegel
%Quantum random walks offer a framework for the design of novel quantum algorithms, %using which polynomial, and even superpolynomial speed-ups have been reported. %Nonetheless, even quadratic speed-ups are not guaranteed for all problems of interest. In this work we consider the problem of preparation of the stationary distribution of irreducible, time-reversible Markov chains, which is a fundamental task in algorithmic Markov chain theory. For the classical setting, this task has a complexity lower bound of $\Omega(1/\delta)$, where $\delta$ is the spectral gap of the Markov chain, and other dependencies contribute only logarithmically. In the quantum case, the conjectured complexity is $O(\sqrt{\delta^{-1)$ (with other dependencies contributing only logarithmically). However, this bound has only been achieved for a few special classes of Markov chains. In this work, we provide a method for the sequential preparation of stationary distributions for sequences of general time-reversible $N-$state Markov chains, akin to the setting of simulated annealing methods. The complexity of preparation we achieve is $O(\sqrt{\delta^{-1 N^{1/4)$, neglecting logarithmic factors. While this result falls short of the conjectured optimal time, it still provides at least a quadratic improvement over other straightforward approaches for quantum mixing, applied in this setting.
Quantum_mixing_sequences_VD_HJB.tex
\documentclass[aps,pra,onecolumn,superscriptaddress,notitlepage,nofootinbib]{revtex4-1}
%\documentclass[letter,twocolumn]{article}
%%\documentclass[pra,superscriptaddress,nofootinbib]{revtex4-1}
%\documentclass[prl,twocolumn,showpacs]{revtex4-1}
%ff
%

%
%\usepackage[german]{babel}
%\usepackage{enumitem}
%\usepackage[perpage]{footmisc}

\usepackage{mathtools}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{relsize}
\usepackage{mathrsfs}
%\usepackage[]{mathbbol}

\newcommand{\bbfamily}{\fontencoding{U}\fontfamily{bbold}\selectfont}
\DeclareMathAlphabet{\mathbbold}{U}{bbold}{m}{n}

%
\usepackage{euscript}%changes caligraphic font, see http://www.maths.usyd.edu.au/u/SMS/texdoc/euscript.pdf
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amsbsy}
%
\usepackage{amsthm}
\newtheorem{theorem}{Theorem}%[section]
%\newtheorem{proof}{Proof}%[section]
%
\usepackage{bbm}
\usepackage{bm}
\usepackage{epsfig}
\usepackage{epstopdf}
\usepackage{dsfont}


\usepackage[colorlinks]{hyperref}
\usepackage[figure,table]{hypcap}
%\usepackage[symbol]{footmisc}
\usepackage{enumerate}
\usepackage{geometry}
\geometry{a4paper,left=20mm,right=20mm, top=35mm, bottom=3cm}
%
\hypersetup{
	bookmarksnumbered,
	pdfstartview={FitH},
	citecolor={darkgreen},
	linkcolor={darkred},
       linktoc={page},
	urlcolor={darkblue},
	pdfpagemode={UseOutlines}}

\usepackage{color}
\def\red#1{\textcolor{red}{#1}}
\def\new#1{\textcolor{blue}{#1}}
\def\blue#1{\textcolor{blue}{#1}}
\def\todo#1{\textcolor{blue}{#1}}
\def\green#1{\textcolor{darkgreen}{#1}}


\definecolor{darkgreen}{RGB}{40,130,40}
\definecolor{darkblue}{RGB}{0,0,190}
\definecolor{darkred}{RGB}{238,0,0}
\usepackage{soul}
%
\usepackage{float}
\usepackage{algorithm}
\let\thealgorithm\relax
\floatname{algorithm}{Protocol}


\def\EQ#1{\begin{eqnarray}#1\end{eqnarray}}
\newcommand{\djj}{d\kern-0.4em\char"16\kern-0.1em}
%\newtheorem{theorem}{Theorem}


\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
\newtheorem{proposition}{Proposition}
\newtheorem{defn}{Definition}
\newtheorem{prop}{Proposition}\def\PRO{\begin{prop}}\def\ORP{\end{prop}}
\newtheorem{coro}{Corollary}\def\COR{\begin{coro}}\def\ROC{\end{coro}}
\newtheorem{theo}{Theorem}\def\TH{\begin{theo}}\def\HT{\end{theo}}
\newtheorem{algo}{Algorithm}\def\TH{\begin{theo}}\def\HT{\end{theo}}
\newtheorem{defi}[prop]{Definition}\def\DE{\begin{defi}}\def\ED{\end{defi}}
\newtheorem{lemme}[prop]{Lemma}\def\LE{\begin{lemme}}\def\EL{\end{lemme}}

\def\one{\mathbb{I}}
\def\hil{\mathcal{H}}
\def\ora#1{\overrightarrow{#1}}
\def\ket#1{\left| #1 \right\rangle}
\def\bra#1{\left\langle #1 \right|}
\def\dm#1{\left|#1 \right\rangle \left\langle #1 \right|}
%\usepackage[labelsep=colon]{caption}
%\renewcommand{\figurename}{Figure}
%\renewcommand*{\thefootnote}{\fnsymbol{footnote}}



%\setlength{\oddsidemargin}{.5in}
%\setlength{\textwidth}{5.5in}

\usepackage{amsmath,amsfonts,amssymb}
\usepackage{wrapfig}
\usepackage{graphicx}
\usepackage{bbm}
\usepackage{graphics}
\def \ni {{\vskip 0.5 cm}}
\def \pz {{\noindent}}
\def \beq {\begin{equation}}
\def \eeq {\end{equation}}
\def \ba {\begin{eqnarray}}
\def \ea {\end{eqnarray}}
%
\newcommand{\upp}{\hspace{-0.2 pt}\uparrow}
\newcommand{\downn}{\hspace{-0.2 pt}\downarrow}
\newcommand{\dt}{\mbox{d}t}
\newcommand{\ketbrad}[1]{|#1\rangle\!\langle #1|}
\newcommand{\mb}[1]{\mbox{\boldmath$#1$}}
\newcommand{\mc}[1]{{\mathcal #1}}
\newcommand{\mean}[1]{\langle#1\rangle}
\newcommand{\Mean}[1]{\left\langle#1\right\rangle}



\begin{document}

\title{Sequential quantum mixing for slowly evolving sequences of Markov chains}



\author{Vedran Dunjko}
\email{vedran.dunjko@uibk.ac.at}
%\thanks{The first two authors have contributed equally to this work.}
\affiliation{Institut f\"{u}r Theoretische Physik, Universit{\"{a}}t Innsbruck, Technikerstra{\ss}e 25, A-6020 Innsbruck, Austria}
\affiliation{Institut f\"{u}r Quantenoptik und Quanteninformation der {\"{O}}sterreichischen Akademie der Wissenschaften, Innsbruck, Austria}
\affiliation{Division of Molecular Biology, Ru\djj er Bo\v{s}kovi\'{c} Institute, Bijeni\v{c}ka cesta 54, 10002 Zagreb, Croatia.}

\author{Hans J. Briegel}

\email{hans.briegel@uibk.ac.at}
\affiliation{Institut f\"{u}r Theoretische Physik, Universit{\"{a}}t Innsbruck, Technikerstra{\ss}e 25, A-6020 Innsbruck, Austria}
%\affiliation{Institut f\"{u}r Quantenoptik und Quanteninformation der {\"{O}}sterreichischen Akademie der Wissenschaften, Innsbruck, Austria}

\begin{abstract}
%Quantum random walks offer a framework for the design of novel quantum algorithms, 
%using which polynomial, and even superpolynomial speed-ups have been reported.  %Nonetheless, even quadratic speed-ups are not guaranteed for all problems of interest.

In this work we consider the problem of preparation of the stationary distribution of irreducible, time-reversible Markov chains, which is a fundamental task in algorithmic Markov chain theory.
For the classical setting, this task has a complexity lower bound of $\Omega(1/\delta)$, where $\delta$ is the spectral gap of the Markov chain, and other dependencies contribute only logarithmically. In the quantum case, the conjectured complexity is  $O(\sqrt{\delta^{-1}})$ (with other dependencies contributing only logarithmically). However,  this bound has only been achieved for a few special classes of Markov chains.
 In this work, we provide a method for the sequential preparation of stationary distributions for sequences of general time-reversible $N-$state Markov chains, akin to the setting of simulated annealing methods. 
 The complexity of preparation we achieve is $O(\sqrt{\delta^{-1}} N^{1/4})$, neglecting logarithmic factors. While this result falls short of the conjectured optimal time, it still provides at least a quadratic improvement over other straightforward approaches for quantum mixing, applied in this setting.
\end{abstract}


\maketitle

%
%OLD ABSTRACT:Quantum random walks offer a framework for the design of novel quantum algorithms, 
%and often, the presented results exhibit a quadratic improvement over classical random walk-based algorithms, and in certain more specialized cases, even super polynomial speed-ups have been achieved.  Nonetheless, even quadratic speed-ups are not guaranteed for all problems of interest. Recently, we have reported a quadratic speed-up of a class of reinforcement learning agents (so called reflective Projective Simulation agents) by employing the Szegedy-type quantum walks. The mathematical problem which was resolved in that work was sampling from a distribution, specified as the unique stationary distribution of a given Markov chain, conditioned on the sample coming from some chosen subset of the state space of the Markov chain.
%It was shown that a quadratic improvement can be achieved over the classical analogue, under the assumption that one had access to a quantum analogue of the stationary distribution to start with. While in the context of learning agents, there are multiple ways this assumption can be fulfilled, the general question of speeding up classical mixing processes has insofar not been resolved. In this work, inspired by the setting of learning agents we considered previously, we provide a method for the preparation of initial states in time $\tilde{O}(\sqrt{\delta^{-1}} N^{1/4})$ for general time-reversible Markov chains, provided they come from a slowly evolving sequence of Markov chains, akin to the setting of Markov Chain Monte Carlo methods. While this result falls short of the conjectured time $\tilde{O}(\sqrt{\delta^{-1}} \log(N))$, in certain cases, this yields at least a quadratic improvement over thus far suggested approaches employing Szegedy-type quantum random walks.




\section{Introduction}

Quantum random walks exhibit features that can be significantly different to their classical counterparts. As a famous example, the hitting time, which is a fundamental quantity in the theory of random walks, can be exponentially reduced if so-called coined quantum walks are employed \cite{2003_Kempe_Contemp_Phys}. However, such strong results are only known to hold for a few special classes of undirected random walks.
Alternative approaches to quantization of random walks over more general graphs, in which case we talk about Markov chains (MCs), most often aim at more modest polynomial improvements. 
Using the so-called Szegedy-type quantum walks, a generic quadratic improvement in hitting times \cite{2010_Krovi} was shown for all time-reversible MCs\footnote{The guaranteed quadratic improvement is shown, provided only one target element exists.}.  The generality of the setting, while preventing superpolynomial speedups, compensates with its greater applicability. Early on, related approaches have e.g. provided a basis for a quadratic improvement of algorithms for element distinctness \cite{2004_Ambainis}, element detection \cite{2004_Szegedy_IEEE} and the triangle problem \cite{2005_Magniez}. Setting aside hitting times, quantum walks have been investigated for their capacity to speed up mixing processes, that is, the task of preparing stationary distributions of a given MC. This task constitutes another fundamental problem of Markov chain theory. Efficient mixing is, for instance, important in the context of Markov Chain Monte Carlo (MCMC) algorithms. MCMC methods are, for instance, central to many algorithmic solutions to hard combinatorial problems and problems stemming from statistical physics \cite{1999_Newman}. Quantum improvements in this context have already been reported \cite{2007_Richter, 2007_Richter_NJP, 2008_Wocjan, 2008_Somma_PRL, 2012_Yung, 2011_Temme_Nature}.  Beyond MCMC-related applications, efficient mixing also extends the applicability of the aforementioned quantum hitting time speedups, as the preparation of the relevant stationary distributions is sometimes assumed to be an affordable primitive \cite{2011_Magniez_SIAM,2010_Krovi}.
However, despite the considerable interest, the quantum speedup of mixing processes has only been shown for certain classes of MCs \cite{2000_Nayak,2001_Aharonov, 2001_Ambainis,2002_Moore,2007_Richter}, and it is an open conjecture that a generic quadratic speedup for mixing can be obtained for all time-reversible MCs \cite{2007_Richter}. For a recent review on quantum walks see \emph{e.g.} \cite{2011_Reitzner}.


In this work we consider the problem of sequentially generating stationary distributions of sequences of slowly evolving Markov chains, illustrated in Fig \ref{Fig1}b.
\begin{figure}
\label{Fig1}
\includegraphics[trim=0 20 0 0, clip=true, width=0.76\textwidth]{Fig1.pdf}
\caption{
Standard simulated annealing is presented in part  a) of the figure: at each time-step $k,$ we produce a sample from the distribution $\bar{\pi}_k$ which need not be exactly the stationary distribution of the Markov chain MC$_k$. This is used as the initial distribution for the next Markov chain. However, the last sample is distributed (approximately) according to $\pi_t$ which is the stationary distribution of MC$_t$ and the target distribution.
Part b) of the figure represents our setting: the sequential sampling from a slowly evolving sequence of Markov chains. At each time-step $k,$ we are required to produce an element sampled from $\pi_k,$ which is a good approximation of the stationary distribution of the Markov chain MC$_k$.
The sequence need not terminate, or it may be arbitrarily long.
}
\end{figure}
This setting is similar to the scenario of simulated annealing, in which case quantum improvements have already been achieved \cite{2008_Wocjan, 2008_Somma_PRL, 2009_Wocjan}. There is, however, a key distinction between the annealing settings and ours: in annealing settings, the target is to produce a sample from the stationary distribution of the final chain only, whereas the intermediary chains have only an accessory role. In contrast, in our case, we must produce samples sequentially, for each chain in the sequence (and, indeed, the sequence can in principle be infinite). The motivation for this problem stems from recent work in artificial intelligence (AI) \cite{2014_Paparo}, by the authors and other collaborators, but may have broader applicability. We will comment on this further later.

For our problem, we first identify two classes of Markov chains, characterized by the distance of their stationary distribution from the uniform distribution.
 These two classes cover all discrete time-reversible Markov chains, and for both classes mixing can be achieved in time $O(\sqrt{\delta^{-1}} N^{1/4})$, neglecting logarithmic terms. The methods used for mixing differ for the two classes, and the second technique (utilized when the target distribution is, in a sense we specify later, \emph{far} from the uniform distribution) requires additional information about the underlying Markov chain. In particular, it requires a small number of samples from the very underlying stationary distribution we seek to construct. While this additional information cannot be straightforwardly recovered given just one MC, we show that in the context of slowly evolving Markov chains, it can.

The structure of this paper is as follows. In Section \ref{Sect2} we present related work and clarify the distinction between our and previously studied settings. Following this, in Section \ref{Sect3} we cover the preliminaries and introduce all the (sub)-protocols required for our main result. Finally, in Section \ref{Sect4} we give our main result, and finish off with a brief discussion in Section \ref{Sect5}.


%Nonetheless, for the purposes of MCMC approaches, Szegedy-type quantum walk operators have been used to provide a quantum speed-up in simulated annealing algorithms, by gradually transforming an initial, easy-to-prepare quantum state of some fixed Markov chain, to a quantum state encoding the stationary distribution of a target Markov chain, via a sequence of intermediary Markov chains, smoothly interpolating between the initial and the target chain. 
%
%
%This setting resembles the MCMC setting we mentioned previously, considered in \cite{2008_Wocjan, 2008_Somma_PRL, qmetropolis, quantumquantummetorpolis} with the distinction that, in our case, the process works independently of the length of the sequence of Markov chains \footnote{This is true up to logarithmically contributing factors.}, and there is no need for continuous quantum memory between time-steps $t$ and $t+1$.
%These two properties are vital in the context of learning agents, where the lifespan of the agent (maximal $t$ it can reach) is in principle unbounded, and where the need for long-term quantum memory may be prohibitive.
%The price we pay is in terms of a factor of $O(N^{1/4})$ which does not appear in the other works. \red{check this, they may have something else costly as well.}
%The basic idea we will use is as follows. If we assume $P(0)$ is a symmetric matrix, then $\pi(0)$ is uniform, and easy to generate efficiently. Moreover, if $\pi(k)$ is not too far from $\pi(0)$, for small values of $k,$ then by using the quantum walk operator $W(P(k)),$ as defined by Szegedy, we can, with cost $\tilde{O}(1/\sqrt{\delta}),$ perform a  (approximate) projective measurement of a uniform distribution state $\ket{u} = 1/\sqrt{N}\sum_i \ket{i}$ to the state $\ket{\pi(k)},$ which will succeed with a probability equal to the fidelity between $\pi(k)$ and the uniform distribution. Additional quadratic improvement can be obtained by employing quantum phase amplification. This provides the first regime for attaining the desired state $\ket{\pi(k)}$.
%If the fidelity is too small for this process to be efficient (more precisely, if this process requires more than $O(N^{1/4})$ steps in the phase amplification subroutine), then a different regime for the preparation is employed. As we will show, there exists a set of elements in $\pi(k)$ which occur with probability higher than $N^{-1/2}$, which can be identified with only a few samples from $\pi(k)$.
%These samples can be obtained efficiently from the previous step $k-1$.
%At this point, by using 'unsearching' (that is, running the quantum hitting time algorithm \emph{backwards}), we can re-create the state $\ket{\pi(k)},$ starting from just classical information, in time $O(N^{1/4})\tilde{O}(1/\sqrt{\delta})$. 
%We note that 'unsearching' has already been proposed as a means to reach the stationary distribution in \cite{Richer, and Childs [10] in richter}, but was disqualified as a promising approach for the general problem, due to square-root dependency on the inverse of the smallest probability occurring in $\pi_k$ (in the classical case, this dependency also exists, but is only logarithmic).
%In this work, we use the context of the sequence of slowly changing Markov chains to provide a mechanism for guaranteeing the 'unsearch' process starts from the best, rather than a worst case setting.
%
\section{Related work}
\label{Sect2}

The setting of slowly evolving MCs is especially relevant in the pervasive simulated annealing methods.
In MCMC methods in general, the task is to produce a sample from the stationary distribution of some target MC $P_T$. For concreteness, this can be the Gibbs distribution $\sigma_T$ of a physical system at a target (low) temperature $T$. Markov chains which have $\sigma_T$ as the stationary distribution are easy to construct, but, in general, the \emph{mixing time} required to achieve stationarity is prohibitive. Better results are often achieved by using simulated annealing methods, in which one constructs a sequence of MCs $P_1, \ldots, P_t =P_T$, which, for instance, encode the Gibbs distributions at gradually decreasing temperatures. The choice of the temperature-dependent sequence is often referred to as the annealing schedule. The fact that the temperatures decrease gradually ensures that the stationary distributions of neighboring chains are close, so the sequence is slowly evolving.
As the temperature corresponding to $P_1$ is high, the stationary distribution of $P_1$ is essentially uniform, and $P_1$ mixes rapidly (effectively in one step).  Simulated annealing is then realized by sequentially applying the chains $P_1$ to $P_t$ to the initial distribution.
In this process, no individual chain fully mixes, but nonetheless, often the reached distribution approximates the target distribution well, even when the number of steps $t$ is substantially smaller than the mixing time of $P_T$ itself.

Quantum variants (and generalizations) of the classical annealing approach have been previously addressed in, for instance, \cite{2008_Wocjan, 2008_Somma_PRL, 2009_Wocjan}. There, the so-called Szegedy walk operators are employed instead of the classical transition matrices $P_t$. The approaches differ, with one commonality: at each time-step, the quantum state obtained from the previous step is used in the subsequent step, and thus quantum coherence is maintained throughout the steps of the protocols.

Our setting is inspired by a recent result by the authors and other collaborators where Szegedy-type quantum walks are used in problems of AI \cite{2014_Paparo}.
In the so-called reflective Projective Simulation (rPS) model of artificial intelligence,
at each time-step $t$, the target action of an rPS agent is encoded in the stationary distribution of a MC $P_t$ which is gradually modified as the agent learns through the interaction with the environment.
The agent's action, which is chosen by sampling from this distribution, has to be output at each time-step.
 For more details on the Projective Simulation model for AI, we refer the reader to \cite{2014_Paparo,Julian12,2012_Briegel}. 
Viewed abstractly, in this setting we have an, in principle, infinite sequence (a stream) of MCs $P_1, P_2, \ldots, P_t, \ldots$ which is slowly evolving. At each time-step $t$, we are required to produce an element sampled according to the stationary distribution of $P_t$ \footnote{For completeness, in the rPS model the agent actually needs to produce a sample from a renormalized tail of the stationary distribution, which can have very low cumulative weight, making the process very slow. To resolve this problem, we have employed a quantum approach in \cite{2014_Paparo}.}. In contrast, in simulated annealing, the sequence is finite, and we are only required to produce a sampled element distributed according to the stationary distribution of the \emph{last} MC.
The quantum approaches to simulated annealing cannot be straightforwardly applied to our setting, as this would require measuring the quantum state at each step. This would prevent all the quantum speedup. Alternatively, the sequence would have to be re-run from the beginning at each time-step, which is not acceptable as the sequence can be of arbitrary length.
The differences between the two settings are illustrated in  Figs. \ref{Fig1}a and \ref{Fig1}b.
It is worthwhile noting that even the classical simulated annealing methods do not immediately help with our task. In classical simulated annealing, at each time step $t$ we are dealing with a classical sample (corresponding to step $t$) which can be copied. However, one cannot output the classical sample at time - step $t$, and use it as a seed for the next time-step: this would induce correlations between the samples at different time-steps whereas we require independent samples \cite{1997_Aldous}\footnote{This problem can be circumvented by letting each MC from the sequence fully mix. However, in this case we lose any advantage of simulated annealing, and just perform brute-force mixing at each time-step.}. 

%Thus, the state of the memory \footnote{We note that the rPS agent actually has a Markov chain for each percept, and the update function can correlate distinct Markov chains, however, this is not relevant for the work presented in this paper.} of the agent is, over time captured by a sequence of Markov chains $P(1), P(2), \ldots, P(k), \ldots$
%where $k$ denotes the round of interaction with the environment, and both the current state of the memory $P(k)$, and the current environmental response are required to  specify the next state of the memory $P(k+1)$. That is each $P(k)$ only determines a possible set (in principle, arbitrarily large) of next memory configurations.
%Each $P(k)$ is required to be ergodic, aperiodic and time-reversible, and thus has a unique stationary distribution $\pi(k) = (\pi_i(k))_{i=1}^{N}, \ \pi_i(k)\in [0,1], \sum_i \pi_i(k) =1$, where $N$ is the size of the ECM network, so $P(k) \pi(k) = \pi(k)$.
%The output of the agent, at time-step $t$ is given with the conditional probability distribution $\tilde{\pi} = \mathcal{N} (\pi_i(k))_{i \in A},$ where $A$ is the set of action nodes and $\mathcal{N}$ the appropriate normalization factor.
%A classical algorithm can realize the desired distribution with $\tilde{O}(\mathcal{N}/\delta)$ calls to $P(k),$ where $\delta$ is the spectral gap of the operator $P(k),$ whereas by employing the Szegedy walk operator, the same distribution can be sampled from with cost $\tilde{O}(\sqrt{\mathcal{N}/\delta}),$ provided the initial state $\ket{\pi(k)} = \sum_i \sqrt{\pi_i(k)} \ket{i}$ is available. With additional constraints (e.g. if the underlying operator $P(k)$ is rank-one, or if $P(k)$ has the property that a known state $i$ has a constant probability for all $k$), we can, in the context of rPS agents ensure that the initial state is available. 
%In this paper however, we abstract the mathematical problem and present a method for generating the initial state $\ket{\pi(k)} = \sum_i \sqrt{\pi_i(k)} \ket{i}$ with no assumptions on the underlying Markov chain $P(k),$ but assuming that the stationary distributions $\pi(k)$ and $\pi(k+1)$ of consecutive Markov chains are close, in terms of total variation distance.


\section{Preliminaries}
\label{Sect3}
In this section, we will set up the notation and define the basic tools we will employ throughout this paper. Part of the presentation is inspired, and closely follows, the approach given in \cite{2011_Magniez_SIAM}.



The basic building block we will use in this work is the so-called Szegedy walk operator $W(P),$ defined for any ergodic, aperiodic and time-reversible Markov chain $P$. First, we will briefly recap a few basic notions regarding Markov chains for the convenience of the reader, and refer to \cite{1998_Norris} for further details.
Throughout this paper, with $P$ we will denote a left-stochastic matrix (a matrix with non-negative, real entries which add up to one in every column). As $P,$ along with an initial distribution, specifies a Markov chain, we will refer to $P$ as the transition matrix and the Markov chain, interchangeably. If $P$ is irreducible and aperiodic, then there exists a unique stationary distribution $\pi,$ such that $P \pi = \pi$ \footnote{In this work we will adhere to the convention in which the transition matrices are left-stochastic, and act on column-vectors from the left.}.
Here, $\pi$ denotes a distribution over the state space, represented as a non-negative column vector $\pi = (\pi_i)_{i=1}^{N},$ $\pi_i \in \mathbbmss{R}^{+}_0$, such that $\sum_i \pi_i =1.$ 
If $\pi$ is a distribution, then we will refer to the element which occurs with a largest probability $i_{max} = \textup{argmax}_{i} \pi_i$ as a mode of the distribution $\pi,$ and the corresponding largest probability $\pi_{max} = \textup{max}_{i} \pi_i$ as the probability of a mode. Note that while the mode need not be unique, the probability of the/a mode is.

The final property we will require is that the Markov chain $P$ is time-reversible, that is, that it satisfies detailed balance: an ergodic Markov chain $P$ with stationary distribution $\pi$ is time-reversible if the following holds:
\EQ{
\pi_i P_{ij} = \pi_j P_{ji}, \forall\ i,j.
}
More generally, for an ergodic Markov chain $P,$ over the state space of size $N$ with stationary distribution $\pi$, we define the time-reversed Markov chain $P^{\ast}$ with $P^{\ast} = D(\pi) P^{\tau} D(\pi)^{-1},$ where $D$ is the diagonal matrix $D=diag(\pi_1, \ldots, \pi_N).$\footnote{The inverse of $D$ always exists, as stationary distributions of irreducible aperiodic Markov chains have non-zero support over the entire state space.} Then, $P$ is time-reversible if $P=P^{\ast}.$

Next, we review the basics of so-called Szegedy-type quantum walks, to an extent inspired by the presentation given in \cite{2011_Magniez_SIAM}

\subsection{The Szegedy walk operator}

While the Szegedy walk operator $W(P)$ can be defined directly, it will be useful for us to construct it from a more basic building block, the diffusion operator $U_P.$ The diffusion operator $U_P$ acts on two quantum registers of $N$ states, (partially) defined as follows:
\EQ{
U_{P} \ket{i}_{\textup{I}}\ket{0}_{\textup{II}} = \ket{i}_{\textup{I}} \sum_{j=1}^{N}\sqrt{P_{ji}} \ket{j}_{\textup{II}}.\label{UP}
}
The operator $U_P$ is a natural quantum analog of the operator $P$ in the sense that a classical random walk can be recovered by applying $U_P$, measuring the second register, re-setting the first register to $\ket{0}$, and swapping the registers.
While $U_P$ is not uniquely defined, any operator satisfying Eq. (\ref{UP}) will do the job.

The operator $U_P,$ and its adjoint are then used to construct the following operator:
\EQ{
\textit{ref}(A) = U_P (\mathbbmss{1}_{\textup{I}} \otimes Z_{\textup{II}}) U_P^{\dagger},
} 
where $Z = 2 \ket{0}\bra{0} - \mathbbmss{1},$ reflects over the state $\ket{0}$.
The operator $\textit{ref}(A)$ is itself a reflector, reflecting over the subspace $A = \textup{span}(\{ U_P \ket{i} \ket{0} \}_i)$.
The Szegedy quantum walk is often explained as a bi-partite walk between two copies of the original graph, and $\textit{ref}(A)$ corresponds to one direction. The other direction is established by defining the diffusion operator in the opposite direction: $V_P = \textit{SWAP}_{\textup{I},\textup{II}}\, U_P\, \textit{SWAP}_{\textup{I},\textup{II}},$ and proceeding analogously as in the case for the set $A$, to generate the $\textit{ref}(B)$ operator, reflecting over $B = \textup{span}(\{ V_P \ket{0} \ket{j} \}_j)$.
The Szegedy walk operator is then defined as $W(P) = \textit{ref}(B) \textit{ref}(A)$. 
In \cite{2004_Szegedy_IEEE,2011_Magniez_SIAM} it was shown that the operator $W(P)$ and $P$ are closely related, in particular in the case when $P$ is time-reversible.

 

Often we will be referring to the \emph{coherent encoding} of a distribution $\pi,$ denoted $\ket{\pi}.$ The state $\ket{\pi}$ is a pure state of an $N-$level system given by $\ket{\pi} = \sum_{i=1}^{N} \sqrt{\pi_i} \ket{i}.$ It is clear that a computational basis measurement (so a projective measurement w.r.t. the basis $\{\ket{i} \}_i$) of the state $\ket{\pi}$ outputs an element distributed according to $\pi$.

In the context of Szegedy-type quantum walks, it is convenient to define another type of a coherent encoding, relative to a Markov chain $P$, which we temporarily denote $\ket{\pi'}.$ This encoding is defined by $\ket{\pi'} =U_{P} \ket{\pi}_{\textup{I}} \otimes \ket{0}_{\textup{II}}$, where $U_P$ is the Szegedy diffusion operator.
It is easy to see that $\ket{\pi}$ and $\ket{\pi'}$ are trivially related via the diffusion map (more precisely, the isometry $\ket{\pi} \rightarrow U_P \ket{\pi} \otimes \ket{0}$) and moreover that the computational measurement of the first register of $\ket{\pi'}$ also recovers the distribution $\pi$.
Due to this, by abuse of notation, we shall refer to both encodings as \emph{the coherent encoding} of the distribution $\pi,$ and denote them both with $\ket{\pi},$ where the particular encoding will be clear from the context. However, for the majority of the text, we will be using the latter meaning.

 



 With these definitions in place we can further clarify the relationship between the classical transition operator $P$ and the Szegedy walk operator $W(P).$ Let $\pi$ be the stationary distribution of $P,$ so $P \pi = \pi$. 
 Then the coherent encoding of the stationary distribution $\pi$ of $P$, given by $\ket{\pi} = U_P \sum_{i} \sqrt{\pi_i} \ket{i} \ket{0},$ is also a +1 eigenstate of $W(P)$, that is, $W(P)\ket{\pi} = \ket{\pi}$. Moreover, in the subspace $A+B$, so-called \emph{busy subspace}, it is the unique $+1$ eigenstate. On the orthogonal complement of the busy subspace, $W(P)$ acts as the identity.
 
Moreover, the spectrum of $P$ and $W(P)$ is intimately related, and in particular the spectral gap \EQ{\delta = 1- \max_{{ \lambda \in \sigma(P) \atop \lambda \not= 1}} |\lambda|,} 
 where $\lambda$ denote the eigenvalues of $P$ and $\sigma(P)$ denotes the spectrum of $P$,  is essentially quadratically smaller than the phase gap \EQ{\Delta = \min\left\{  2 | \theta| | e^{i \theta} \in \sigma\left(W\left(P\right)\right),\ \theta \not= 0\right\} , }  where $\theta$ denote the arguments of the eigenvalues, i.e. eigenphases, of $W(P)$.
 This relationship is at the very basis of all speedup obtained from employing Szegedy-type quantum walks, which we shall elaborate further.
In this paper we will not use other results than those we briefly exposed here, and we refer the interested reader to \cite{2011_Magniez_SIAM, 2010_Krovi} for further details.

\subsection{$\ket{\pi}$ projective measurement}
The first application of the walk operator $W(P)$ allows us to approximate a projective measurement on the $\ket{\pi}$ state, where $\pi$ is the stationary distribution of $P$.
 
This is achieved by using Kitaev's phase detection algorithm\footnote{The original algorithm by Kitaev allowed the estimation of the eigenphases of a given operator, where the final step is an inverse quantum Fourier transform ($QFT^{\dagger}$) on the phase containing register. This algorithm can be, for our purposes, further simplified by substituting the $QFT^{\dagger}$ with the suitable number of Hadamard gates, as suggested in \cite{2008_Wocjan}. This substitution maintains the probability of observing a 'zero' phase, and the corresponding post-selected state, thus can be used to detect a non-zero phase. For this reason, this slightly tweaked algorithm is called the phase \emph{detection} algorithm.} \cite{1996_Kitaev}
on $W(P)$ (with precision $ \tilde{O}(1/\sqrt{\delta})$),
which, if followed by the measurement of the phase-containing register, approximates the projective measurement on the state $\ket{\pi}.$ 
To understand why this holds, recall that the $W(P)$ operator has the state $\ket{\pi}$ as the unique $+1$ eigenstate, in the busy subspace. Moreover the values of the phases of all other eigenstates (in the same subspace) are at least $\Delta$. 

Thus, provided the state we perform the measurement on is in $A + B$,  the residual state, conditioned on detecting zero phase, is a good approximation of $\ket{\pi}.$ The error can be further suppressed by iterating the procedure, as was suggested in  \cite{2011_Magniez_SIAM}, there for the purpose of approximate reflection, which we will elaborate on next.
More precisely, the errors can be made exponentially small with linear overhead, yielding an overall cost $\tilde{O}(1/\sqrt{\delta})$. Here, the $\tilde{O}$, the so-called soft-O notation ignores the logarithmically contributing factors, in this case stemming from the quality of the approximation. This result can be seen as a consequence of Theorem 6 in \cite{2011_Magniez_SIAM}.
This is a very useful tool for 'purifying' an already good approximation of the target state $\ket{\pi}.$ However, this projective measurement behaves correctly only if we are guaranteed the state we have is in the space $A + B.$ 
Fortunately, this is easy to achieve. In particular, testing whether a given state is in $A$ (or $B$) is straightforward: one simply applies $U_P^{\dagger}$ (or $V_P^\dagger$) and checks the contents of the second (or first) register. Provided we observe the state $\ket{0},$ we are guaranteed that we are in the correct subspace. Since the target state $\ket{\pi}$ is in $A,$ it will suffice to check whether the initial state is in $A$ first and if it is perform the $\ket{\pi}$ projective measurement. The sequence of these two measurement ($A$ membership measurement, followed by the phase measurement) constitutes the $\ket{\pi}$ projective measurement.
The success probability of this measurement, applied on the pure state $\ket{\psi}$ is in $O (F(\ket{\psi},\ket{\pi})),$ that is on the order of the fidelity $F(\ket{\psi},\ket{\pi}) = |\bra{\psi}\pi \rangle |^2$ between the input state and the $\ket{\pi}$ state. Note that if the measurement were perfect, the success probability would be exactly the fidelity. 
%The phase measurement we have described above was a central tool in many of the works considering quantum improvements  Markov Chain Monte Carlo methods Szegedy-type quantum walks \cite{2008_Wocjan, 2008_Somma_PRL, others, Qmetrop, QQmetrop? }.


\subsection{Approximate reflection over $\ket{\pi}$}
One of the central tools in the theory of Szegedy-type quantum walk is the so-called Approximate Reflection Operator $ARO(P) \approx 2\dm{\pi} - \mathbbmss{1}$, which approximately reflects over the state $\ket{\pi}$ \cite{2011_Magniez_SIAM}.
The basic idea for the construction of this operator is similar to the one we gave for the $\ket{\pi}$ projective measurement. 
By applying Kitaev's phase detection algorithm on $W(P)$ (with precision $O(\log(\Delta))$), applying a phase flip to all states with phase different from zero, and by undoing the phase detection algorithm, we obtain an arbitrarily good approximation of the reflection operator $R(P) = 2 \dm{\pi} - \mathbbmss{1}$, for any state within $A+B$.
The errors of the approximation can be efficiently suppressed by iteration (by the same arguments as for the $\ket{\pi}$ measurement) \cite{2011_Magniez_SIAM}, so the cost of the approximate reflection operator is again in $\tilde{O}(1/\Delta) = \tilde{O}(1/\sqrt{\delta}).$ 

Thus, the second gadget in our toolbox is the operator $ARO(P),$ which approximates a perfect reflection $R(P)$ on $A+B$, while incurring a cost of $\tilde{O}(1/\sqrt{\delta})$ calls to the walk operator $W(P)$.

The operator $ARO(P)$ is central to many of the results employing Szegedy-type walks \cite{2011_Magniez_SIAM, 2010_Krovi}, in particular in tasks of element finding, as we shall clarify next.

\subsection{Element searching and unsearching}
The approximate reflection operator $ARO(P)$, along with the capacity to flip the phase of a chosen subset of the computational basis elements, suffices for the implementation of an amplitude amplification \cite{2000_Brassard} algorithm. This, in turn, allows us to find the chosen elements with a quantum speed-up. 
To illustrate this, assume we are given the state $\ket{\pi},$ the (ideal) reflector $R(P),$ and assume we are interested in finding some set of elements $M \subseteq \{1, \ldots, N \}$.
The subset $M$ is typically specified by an oracular access to a phase flip operator defined with $Z_M = \mathbbmss{1} - 2\sum_{i \in S} \dm{i}$.
The element searching then reduces to iterated applications of $Z_M R(P)$ (which can be understood as a generalized Grover iteration, more precisely amplitude amplification) onto the initial state $\ket{\pi}.$ 
Let $\tilde{\pi}$ denote the conditional probability distribution obtained by post-selecting on elements in $M$ from $\pi,$ so
\EQ{
\tilde{\pi} = \left\lbrace \begin{tabular}{cl}\vspace{0.1cm}
$\dfrac{\pi_i}{\epsilon},$& $\textup{if} \ i\in M$\\
0,& \textup{otherwise},
\end{tabular}  \right. \label{EQ3}
} with $\epsilon = \sum_{j \in M} \pi_j.$ Let $\ket{\tilde{\pi}} = U_P \sum_i \sqrt{\tilde{\pi}_i} \ket{i} \ket{0}$ denote the coherent encoding of $\tilde{\pi}.$  Note that the measurement of the first register of $\ket{\tilde{\pi}}$ outputs an element in $M$ with probability 1. Thus the capacity for preparing this state implies that the desired element from $M$ can be found, directly by measurement. 

As it was shown in \cite{2011_Magniez_SIAM}, applications of $Z_M $ and $R(P)$ leave the register state in the two-dimensional subspace $\textup{span}( \{ \ket{\pi}, \ket{\tilde{\pi}} \})$ and moreover, using $\tilde{O}(1/\sqrt{\epsilon})$ applications of the two reflections will suffice to produce a state $\ket{\psi} \in \textup{span}  \{ \ket{\pi}, \ket{\tilde{\pi}} \}$ such that $| \bra{\psi} \tilde{\pi} \rangle |^2$  is a large constant. Measuring the first register of such a state will result in an element in $M$ with a constant probability, which means that iterating this process $k$ times ensures an element in $M$ is found with an exponentially increasing probability in $k$.
However, since the state $\ket{\psi}$ is also in $ \textup{span}  \{ \ket{\pi}, \ket{\tilde{\pi}} \},$ it is easy to see that the measured outcome, conditional on being in the set $M$, will indeed be distributed according to $\tilde{\pi}$.

In our recent work \cite{2014_Paparo}, and also in \cite{2010_Krovi}, these results were used to produce a sample from the truncated stationary distribution $\tilde{\pi},$ in time $\tilde{O}(1/\sqrt{\epsilon})\times \tilde{O}(1/\sqrt{\delta})$ where the $\delta$ term stems from the cost of generating the approximate reflection operator $ARO(P)$, and $\tilde{O}(1/\sqrt{\delta})$ corresponds to the number of iterations which have to be applied. This is a quadratic improvement relative to using classical mixing, and position checking processes which would result in the same distribution.

However, the same process can be used \emph{in reverse} to generate the state $\ket{\pi}$ starting from some fixed basis state $\ket{i'} = U_{P} \ket{i} \ket{0} $ 
with cost $\tilde{O}(1/\sqrt{\delta}) \times \tilde{O}(1/\sqrt{\pi_i})$. Note that  $\pi_i = |\bra{\pi} i' \rangle |^2$ is the probability of sampling the element $i$ from the distribution $\pi$.
To see that this works, let $W_{tot}$ correspond to the product of all $R(P) Z_{\{i\}}$ reflections (so $\tilde{O}(1/\sqrt{\pi_i})$ of them)  that need to be applied to find the element $i$. The correctness of the search algorithm then guarantees that the trace distance between the final state and the target state is a (small) constant $c$, so $1/2\| \dm{i'} - W_{tot}\dm{\pi} W_{tot}^\dagger \| \leq c$. But since the trace distance (and also fidelity) are preserved under unitary maps, and since $W_{tot}$ is unitary, we also have that 
$1/2\| W_{tot}^\dagger \dm{i'}W_{tot} - \dm{\pi}  \| \leq c$. Thus the resulting state obtained by reversing the search process is constantly close to the state $\ket{\pi}.$
But then, the $\ket{\pi}$ projection measurement we described previously will recover (an arbitrary good approximation of) the $\ket{\pi}$ state with a constant probability. By iterating this entire process, should it fail (the iteration is possible, since we can generate $\ket{i}$ cheaply on demand), we will get the desired state $\ket{\pi}$ with exponentially increasing probability in the number of attempts. 



Such a process of recovering the state $\ket{\pi}$ corresponds to a classical mixing process. Classical mixing (for time-reversible Markov chains) can be achieved in $O(1/\delta \times \log(1/\pi_{min}))$ (ignoring error terms), whereas the quantum process terminates in $\tilde{O}(1/\sqrt{\delta} \times 1/\sqrt{\pi_{min}})$\footnote{We are ignoring the logarithmically contributing precision term $\log(1/error)$ in both cases.}, where $\pi_{min}$ denotes the smallest occurring probability in $\pi$, in the worst case. Hence we can see a quadratic improvement w.r.t the $\delta$ term in the quantum case. However, the scaling relative to the probability term $\pi_{min}$  constitutes an exponential slowdown relative to the classical mixing bounds, and this trade-off is prohibitive. 


We highlight that the approach we have just described for attaining stationary distributions by running hitting algorithms in reverse was first proposed by Richter \cite{2007_Richter}\footnote{The approach to quantum mixing we outline here was developed before the authors were aware of the observation by Richter, and independently from the paper \cite{2007_Richter}. During a more extensive literature review, the cited paper by Richter was identified as the, to our knowledge, the first paper to outline the idea as a comment in the preliminaries section.}, extending on observations by made by Childs~\cite{2004_Childs, 2007_Richter}. 

The basic idea of this work will be to ensure that the choice of the initial seed state $\ket{i}$ is in fact the best possible.  However, the best possible situation can still be to costly as the highest probability may still be as small as $1/N$, as is the case for the uniform distribution. In these cases there is a more efficient way to prepare the initial state, which we clarify next.

\subsection{Preparation from the uniform distribution}




As we have described previously, the access to the $W(P)$\footnote{More precisely, we require a controlled variant of the $W(P)$ operator.} operator allows us to perform a projective measurement to the state $\ket{\pi}.$
Thus, if we prepare the coherent encoding of the uniform distribution state $\ket{u} = U_{P} \left(1/\sqrt{N} \sum_{i} \ket{i} \ket{0} \right)$, simply by performing the $\ket{\pi}$ projective measurement on it, we still have the probability $F(\ket{u}, \ket{\pi}) = |\bra{u} \pi \rangle|^2 $ of collapsing to the correct state. By repeating this process until we succeed, we obtain a preparation algorithm with expected running time of $\tilde{O}(1/\sqrt{\delta}) \times O(1/F(\ket{u}, \ket{\pi})).$ However, we can improve on this by ``Goverizing" this process, that is, by using amplitude amplification \cite{2000_Brassard}. This amounts to reflecting over $\ket{u}$ and $\ket{\pi}$ iteratively, starting from $\ket{u},$ until we reach a state close to the target state $\ket{\pi},$ with an overall cost $\tilde{O}(1/\sqrt{\delta}) \times O(1/\sqrt{F(\ket{u}, \ket{\pi})})$. 

We use the generalizations of this approach in \cite{2015_Dunjko2} to generate coherent encodings of stationary distributions in the cases where the shape of the target distribution is to some extent known.
For the purposes of this paper, however, we will only require unsearching from the uniform and from Kronecker-delta distributions.

% Assume we are given any pure state in $\ket{\psi} \in A$ , and we have the capacity to implement $ref(\ket{\psi}) = 2 \dm{\psi} - \mathbbmss{1}.$ Then the amplitude amplification protocol, starting from $\ket{\psi}$ (instead of $\ket{i'}$), utilizing $ref(\ket{\psi})$ (in place of $Z_{i}$), applied $O(F(\ket{\psi},\ket{\pi})^{-1/2})$ will yield a state (approximately) which has a constant overlap with $\ket{\pi}$. From this, a $\ket{\pi}$ projective measurement will, with constant probability, yield the target state $\pi$, and the success probability of this entire process can be made exponentially high by iteration.
% 
 
The preparation method starting from the uniform distribution, and also the unsearch approach from a fixed state, are a special cases of the more general amplitude amplification protocol we have just described.


The two methods, unsearching and preparation from uniform, of preparing the state $\ket{\pi}$ are complementary, in the sense that the latter method is more efficient when the stationary distribution is close to uniform, where the unsearching becomes efficient when an element has a high probability (roughly, when the distribution is far from uniform). Our overall approach we present next will use both methods for preparation, and provide a method for identifying the right candidates (elements with the highest probability in $\pi$) for the unsearching approach. 
In what follows, we will say that the (coherent encoding of) distribution $\pi$ is \emph{far from uniform}, if $F(\ket{\pi}, \ket{u})\geq 1/\sqrt{N},$ and otherwise, we will say the distribution (equivalently, its coherent encoding) is \emph{close to uniform.}

\section{The protocol}
\label{Sect4}
We will first establish the notation for the remainder of the paper. A given element of a sequence we are referring to, will, in the remainder of the paper, be specified by a superscript in the cases of transition matrices and spectral gaps, e.g. $P_t, \delta_t$ for the $t^{th}$ element. In the case of distributions, we will use parentheses (e.g. $\pi(t)$), since we have reserved the subscripts to denote a particular probability in a given distribution.

We proceed by formally specifying the setting we consider. We assume we are, at each time-step $t,$ given the Szegedy walk operators $W(P_t),$ associated with a sequence of time-reversible Markov chains $\{ P_t \}_{t=1}^{\infty}$ over the same state space of $N$ elements, along with each spectral gap $\delta_k$\footnote{Effectively, we only require a sensible lower bound on the spectral gap.}. 


The task is, at each time-step $t$, to generate the coherent encoding of the stationary distribution $\ket{\pi(t)}$, with cost in $\tilde{O}(N^{1/4}/\sqrt{\delta_t}).$ 

To achieve this, we require further assumptions, namely that the Markov chains are slowly-evolving. More precisely, we require that the stationary distributions $\pi(t), \pi(t+1)$ of neighboring Markov chains $P_t, P_{t+1}$, respectively, are sufficiently close in terms of the fidelity of their coherent encodings. That is, we require that $F(\ket{\pi(t)},\ket{\pi(t+1)})~\geq~\eta$, where $\eta>0$ is a real constant independent from the spectral gaps, and the state space size. Moreover, we will require that the spectral gaps $\delta_t, \delta_{t+1}$ of neighboring chains $P_t, P_{t+1}$ are relatively close, in the sense which we will specify later. As we will explain,  this last assumption is not vital, but allows for a more convenient statement of the main result. Finally, we will assume that the coherent encoding of the stationary distribution $\ket{\pi(1)}$ of the first Markov chain is easy to generate.

These assumptions are essentially equivalent to the assumptions in \cite{2008_Somma_PRL, 2008_Wocjan}. However, as we have clarified, in contrast to those works, in our result, at each time-step $t,$ the stationary distribution can be prepared \emph{de novo}, that is without using any quantum memory from step $t-1$, with cost $\tilde{O}(N^{1/4}/\sqrt{\delta_t}).$ This, for instance implies that multiple copies can be generated at each time-step as well, if desired, without having to re-run the entire sequence of Markov chains. Moreover, our approach does not depend on the length of the sequence, as each stationary distribution is prepared ``on the fly'', independently from the quantum states utilized in previous steps. Both properties are vital in the context of active learning agents that we have mentioned previously. 

To explain how our protocol works, we will describe two particular settings where the cost of preparation of the encoding of the stationary distribution $\ket{\pi}$ of an $N-$state Markov chain $P$ with spectral gap $\delta$ is in $\tilde{O}(N^{1/4}/\sqrt{\delta}).$

In the first setting the fidelity between the coherent encoding of the uniform distribution $\ket{u}$ and $\ket{\pi}$ is above $N^{-1/2}$. In this case, as we have shown, the preparation starting from uniform has the desired overall cost $\tilde{O}(F(\ket{u}, \ket{\pi})^{-1/2} \delta^{-1/2}) = \tilde{O}(N^{1/4}\sqrt{\delta}).$

In the second setting the stationary distribution $\pi$ of $P$ has the probability of a mode $\pi_{max}$ (the largest occurring probability) larger than $N^{-1/2}$, and the mode state itself $i_{max}$ is known. In this case, unsearching from the element $i_{max}$ will produce the target state with cost in $ \tilde{O}(1/\sqrt{\delta} \times 1/\sqrt{\pi_{max}}) =\tilde{O}(N^{1/4}\sqrt{\delta})$.

Our first technical result shows that any Markov chain $P$ fits in one of the two settings above, which is captured by the following Lemma, proven in the Appendix.

\LE
\label{fid:mode:bounds}
Let $\pi$ be a distribution over $N$ states, such that $F(\ket{u}, \ket{\pi}) \leq 1/\sqrt{N}.$ Then $\max_{i} \pi_i \geq 1/\sqrt{N}$. Moreover, if   $\max_{i} \pi_i < 1/\sqrt{N},$ then $F(\ket{u}, \ket{\pi}) \geq 1/\sqrt{N}. $ 
\EL

The lemma above has a few immediate consequences. First of all, if we are given a Markov chain $P,$ (over $N$ states) with known $\delta$, the mode $i_{max}$ of the corresponding stationary distribution $\pi,$ along with the probability of the mode $\pi_{i_{max}}$, then it is clear that we can prepare the stationary distribution within cost $\tilde{O}( N^{1/4}/\sqrt{\delta})$:  if $\pi_i \geq 1/\sqrt{N},$ we use the ``unsearch from $\ket{i}$" approach. If it is not, then by the second claim of Lemma \ref{fid:mode:bounds}, we know that we can prepare the initial state by the preparation from the uniform distribution within cost $\tilde{O}( N^{1/4}/\sqrt{\delta})$.

It is also easy to see that the assumption of knowing the probability of the mode $\pi_i$ is actually not needed. 
One can first attempt the preparation from the uniform distribution a suitable number of times, where the number of reflections used is upper bounded by $O(N^{1/4})$\footnote{More precisely, we would use the use a randomized approach as presented in \cite{1998_Boyer}, which only requires a lower bound.  We note that the approach of \cite{1998_Boyer} can be applied if a lower bound is known, but also the upper bound should not surpass $1/4$. This is achieved by directly performing the $\ket{\pi}$ projective measurement on the uniform distribution state a couple of times. If it succeeds, we are done, should it fail, we can conclude that the overlap is below $1/4$, as required, except with an exponentially decaying probability in the number of attempts. The same approach, albeit applied to the task of element finding, was first suggested in \cite{2011_Magniez_SIAM} .} - if the target distribution closer than $1/\sqrt{N}$ to the uniform distribution, in terms of the fidelity, then this will succeed with exponentially high probability in the number of attempts. If all attempts fail, we are (except with exponentially small probability) then sure we are in the regime where the mode has a probability higher than $1/\sqrt{N},$ and this is all we need to know.
Then, the unsearching approach, starting from the mode $i_{max}$ will (with high probability) produce the target state if we employ $O(N^{1/4})$ iterations, so with overall cost  $\tilde{O}( N^{1/4}/\sqrt{\delta})$. We will take care of the failure probability of this approach later.

However, even the assumption that the mode (but not the probability of the mode) is known is most often too strong to be justified. Nonetheless, if we are dealing with a scenario in which we have a sequence of Markov chains, such that  a) the stationary distributions of consecutive Markov chains are sufficiently close, and b) the first Markov chain has a known, easy to prepare stationary distribution, then we can recover the same results without the need to explicitly find a mode.

To illustrate how this is achieved, consider the setting of just two Markov chains, $P_1$ and $P_2$, (with corresponding stationary distributions $\pi(1)$, $\pi(2)$, such that $\ket{\pi(1)}$ is easy to prepare. By easy to prepare we mean within the cost $\tilde{O}( N^{1/4}/\sqrt{\delta_1}),$ so it will, for instance, suffice that we know the mode of $\pi(1)$ and it is above $1/\sqrt{N},$ or that the fidelity (relative to the uniform distribution) is above $1/\sqrt{N}$.
 
To prepare the (coherent encoding of the) stationary distribution of $P_2$, we first proceed with the attempt to recover it by unsearching from the uniform distribution. If this succeeds, we are done. 
If this approach should fail, we proceed as follows: we first prepare $c' \in \mathbbmss{N}$ copies of the state $\ket{\pi(1)}$, where $c'$ is a (small) confidence parameter. Recall, we have assumed the stationary distributions of $P_1$ and $P_2$ are close, so we will have that $F(\ket{\pi(1)}, \ket{\pi(2)}) \geq  \eta,$ where $\eta$ is some (large) constant. 
This implies that a projective measurement on the state $\ket{\pi(2)}$ of the state $\ket{\pi(1)}$ will succeed with average probability $\eta$. 
This measurement has cost $\tilde{O}(1/\sqrt{\delta_2}),$ so with overall cost $\tilde{O}(c'/\sqrt{\delta_2} ) $ we can prepare, on average, $c=\eta c'$ copies of the state $\ket{\pi(2)}$\footnote{We note that if $\eta$ is very small (but the assumption is it is independent from $N$ and the spectral gaps) we can do better by utilizing quantum amplitude amplification \cite{2000_Brassard} again - given the initial state $\ket{\pi(1)}$, by using the reflection over it, and the reflection over $\ket{\pi(2)}$, we can obtain the target state $\ket{\pi(2)}$ with a quadratic smaller cost with respect to $\eta$. However, since for this work we assume $\eta$ is constant this still yields the same overall scaling.}.  
In the actual protocol, we will iterate the preparation until we do have $c$ copies, and $c'$ above then establishes the expected number of iterations.

Next, we simply measure (the first register of) all of the $c$ copies of the state, obtaining $c$ independent single element samples from the distribution $\pi(2)$.
As it turns out, this is sufficient for the task at hand. If the fidelity of $\ket{\pi(2)},$ relative to the uniform distribution state $\ket{u}$, is below $1/\sqrt{N}$\footnote{This is the case, except with very small probability, since we assume that the approach of preparation from the uniform distribution had failed.}, then with probability $1-2^{-c}$, at least one state $i$, out of the $c$ independently sampled states, has the corresponding probability $\pi(2)_i \geq{1/{(4 \sqrt{N})}}$.
This result is captured by the following Lemma, and proven in the Appendix:
\pagebreak

\LE\label{main:lemma}
Let $\pi$ be a distribution over $N$ states, and let $F(\ket{\pi}, \ket{u}) \leq 1/\sqrt{N}.$ Then there exists a set of indices 
$S \subseteq \{1, \ldots, N\}$ such that the two following properties hold:
\begin{itemize}
\item $\min_{i \in S} \pi_i \geq \dfrac{1}{4 \sqrt{N}}$ and
\item $P(S) = \sum_{i\in S} \pi_i \geq \dfrac{1}{2}.$
\end{itemize}
\EL


As the next step, we simply sequentially attempt to prepare the target state through unsearching from the sampled states and employing $O(N^{1/4})$ iterations of the reflections. With probability at least $1-2^{-c}$, one of the attempts will succeed. 
%Since the failure probability decays exponentially in $c,$ this iterative process introduces an additional multiplicative overhead of $O(1/\log(\epsilon/\eta))$ to the overall process, where $\epsilon$ is the chosen acceptable failure probability of the protocol.

What we have shown is that having a collection of $c$ independent single element samples from $\pi(2)$ suffices to efficiently prepare $\ket{\pi(2)},$ in the regime where the preparation from uniform distribution would not be efficient. From these observations, the presented approach for two Markov chains inductively extends to the setting with a sequence of Markov chains that we wish to consider.
We now give the full protocol, along with a more rigorous analysis.

In what follows, we will be assuming all the approximate reflection operators are in fact exact, and we will deal with the errors induced by approximations later.
The protocol will use two subroutines.  The subroutine \textit{PrepareFromUniform(c)} attempts the preparation from the uniform distribution, using $O(N^{1/4})$ reflections. If the target distribution state close to the uniform distribution state  (in the sense we defined previously), then by utilizing the randomized approach \cite{1998_Boyer} we will obtain the target state except with probability below $1/2$\footnote{Here we again, as a technical point, assume that we have eliminated the possibility that the overlap between the uniform distribution and the target distribution is \emph{over} (or equal to) 1/4, by attempting direct projective measurements first. For this, it will suffice to attempt the projective measurement $3c$ times - failing to generate the target state, if the fidelity is above or equal to 1/4, will then occur with probability below $(3/4)^{3c} \leq 2^{-c} $. Since the cost of the projective measurements does not depend on $N$, we may ignore this in the complexity analysis.}. 
We will, for this subroutine, allow for $c$ attempts to prepare the target distribution. Then we will succeed, whenever the fidelity relative to the uniform distribution state is above $N^{-1/2},$ except with probability $2^{-c}.$
The output of this subroutine is either the coherent encoding of the stationary distribution, or ``unsuccessful" - a flag indicating that the preparation failed and that the target distribution is far from uniform, except with small probability.
The cost of this procedure is $\tilde{O}(c\, N^{1/4}/\sqrt{\delta_t}),$ at time step $t$.


%Next is the \textit{PrepareFromSamples(c)} subroutine. 
%Here, we assume we have access to $c$ elements, independently sampled, from the target distribution. We will attempt the preparation from each sample also $c$ times. Note that we use the same constant $c$ for both the number of samples, and the number of attempts we allow, for simplicity.
%If the given target distribution has an overlap smaller than $N^{-1/2}$ relative to the uniform distribution, then this procedure will succeed except with probability at most $2 \times 2^{-c},$ as we may have bad samples (with probability below $2^{-c}$) and we may also fail to generate the target state from a valid sample (again with probability below $2^{-c}$).

The second is the \textit{PrepareSamples(c)} subroutine.
In the context of the overall protocol, we will make sure that, at each step we generate in total $c$ elements sampled from the target distribution. One of these is output, and all are saved, in the case we need them for the next step.
The $PrepareSamples(c)$ subroutine, used at time-step $t>2,$ back-tracks to the previous step, and first prepares the coherent encoding for the previous step $\ket{\pi(t-1)}.$
Depending on whether the previous stationary distribution is close or far from the uniform (that is, closer or further than $1/\sqrt{N},$ in terms of the fidelity with the uniform distribution) for this we may require $c$ samples from the previous distribution itself. As we have clarified, we will make sure we always have those in the overall protocol.
Given the $c$ samples for the previous step, the encoding $\ket{\pi(t-1)}$ can be generated with cost $\tilde{O}(c\, N^{1/4}/\sqrt{\delta_{t-1}}),$ except with probability $2^{-c}$ by Lemma \ref{main:lemma} (in the case we accidentally have bad samples), either by using the preparation from the samples, or by preparing from the uniform. 
Following this, on the state $\ket{\pi(t-1)}$ we apply a $\ket{\pi(t)}-$ projective measurement (with cost $\tilde{O}(1/\sqrt{\delta_t})$) and with probability $\eta$ we succeed to project onto $\ket{\pi(t)}$. 
This process is repeated until $c$ copies of $\ket{\pi(t)}$ are generated, and they may be immediately measured. One of the sampled elements (measurement outcomes) is output, and the other $c$ sampled elements are stored for future use by the $PrepareSamples$ subroutine.

The situation is analogous in the case the previous distribution was prepared from the uniform.

We highlight that, irrespective of the method we used at time step $t-1$, $PrepareSamples(c)$ will attempt to regenerate the states $\ket{\pi(t-1)}$ by using the original approach first, but, if that should fail, it will switch to the alternative\footnote{Note note that switch from the samples approach to the preparation from uniform approach is always possible, and the switch from the uniform to the samples approach is possible because we will always, regardless of the regime, prepare and store $c$ independently sampled elements.}.


In the case $PrepareSamples(c)$ is run at time-step $t=2,$ the procedure is analogous as above, with the difference that, by assumption, we can cheaply generate the required encodings $\ket{\pi(1)}$ of the previous step.

This subroutine has expected running time $\tilde{O}(\eta\ c\ N^{1/4}/\sqrt{\delta_{t-1}} ),$ and a failure probability $2^{-c}$. Since we do not consider the scaling in $\eta$, we obtain $\tilde{O}(c\, N^{1/4}/\sqrt{\delta_{t-1}} ).$


Now we can give the protocol, where $t$ denotes the time-steps:

\vspace{0.5cm}

\noindent \textbf{The protocol}\\
\begin{enumerate}
\item If $t=1,$ prepare the corresponding coherent encoding of the stationary distribution, measure, and output the outcome. Keep the operator $W(P_1)$ (and $\delta_1$) in memory for one additional time-step.
\item If $t>1,$ 
execute $PrepareFromUniform(2c),$ $c$ times. If each run generated the target distribution, save  $c$ sampled elements for future use, and output one as the current output.
If any run returns ``unsuccessful", abort, and run $PrepareSamples(c).$ In both cases replace the stored operator $W(P_{t-1})$ with the current  $W(P_{t})$ (also $\delta_{t-1}$ with $\delta_{t}$,) and proceed to the next time-step.
\end{enumerate}

\subsection{Protocol analysis}
First, we analyze the protocol under the assumption that the realized approximate reflection operators are perfect.
In this case, the protocol above has, at each time-step $t$ (for $t>1$,) the expected running time in  
$\tilde{O}(2c^2 N^{1/4}/\sqrt{ \min \{\delta_{t-1},\delta_{t} \} }  ) = \tilde{O}( c^2\ N^{1/4}/\sqrt{ \min \{\delta_{t-1},\delta_{t} \} } ) $, where $c$ is a confidence parameter, as this expression is the maximum of the costs of both possible preparation subroutines.  

If we have the assumption that the neighboring spectral gaps $\delta_{t-1}$ and $\delta_{t}$ are multiplicatively close, meaning that there exists a constant $\kappa \in \mathbbmss{R}^{+}$ (independent from $N$) such that for all $t>1$ we have that
\EQ{
\delta_{t-1}/\kappa \leq \delta_{t} \leq \kappa \delta_{t-1},
}
then the cost  of preparation is in $\tilde{O}( c^2\, N^{1/4}/\sqrt{\delta_t})$ for each $t$, which was the desired cost.
The protocol can, however, fail with probability $O(2^{-c}),$ which we clarify next.
First, note that the $PrepareFromUniform(c)$ subroutine may fail - that is, report "unsuccessful", although the distribution is in the right regime (close to uniform). 
In our protocol, we call this subroutine $c$ times, with parameter $2c.$ This entire iteration fails if at least one of the runs reported ``unsuccessful", although the target distribution was close enough to the uniform distribution.
If the target distribution is in the required regime, $PrepareFromUniform(2c)$ run once reports ``unsuccessful" with probability $2^{-2c}.$ The probability at least one ``unsuccessful" report in a sequence of $c$ runs is then given with $1-(1-2^{-2c})^{c} = 1-(1-4^{-c})^{c}$. However, we have that $
1-(1-4^{-c})^{c} \leq 2^{-c},
$
which we here prove for completeness.
We have that 
\EQ{
1-(1-4^{-c})^{c} \leq 2^{-c} 
\Leftrightarrow  (1-4^{-c})^{c} \geq  1-2^{-c}.
}
For the expression $(1-4^{-c})^{c}$ we have, by the Bernoulli's inequality, that  $(1-4^{-c})^{c} \geq 1- c\, 4^{-c},$ so it will suffice to show that
$1- c\,4^{-c} \geq 1-2^{-c}$, which is equivalent to $c \leq 2^{c},$ which is true.

Thus in our protocol, failure to prepare the required $c$ independently sampled elements, in the case the distribution is sufficiently close to the uniform distribution, occurs at most with probability $2^{-c}$.

If the distribution is not close to uniform, we may end up running the  $PrepareSamples(c)$ subroutine,
which will attempt the preparation of the $c$ samples, by regenerating the encodings of the stationary distributions of the previous step. For this, it may utilize either the $c$ samples from that distribution or attempt preparation from the uniform distribution state, and in the worst case, it will attempt both. Since the target distribution must be in one of the two regimes, and since both cases have a failure probability of $2^{-c},$ this also gives the overall failure probability.

Hence, we have shown that our protocol, under the assumption that all the reflection operators (and measurements) are perfect, generates a sample from (or a coherent encoding of) the target stationary distribution, with cost in $\tilde{O}(c^2\ N^{1/4}/\sqrt{\delta_t} ),$ with a failure probability in $O(2^{-c}).$

In the real protocol, the reflection over the target state $\ket{\pi}$ is not ideal (as we only achieve an approximation of the reflection) and neither is the $\ket{\pi}$ projective measurement. Taking into account the effects of these imperfections, we obtain the expected run-time of $\tilde{O}(c^3\ N^{1/4}/\sqrt{\delta_t} ),$ with the same failure probability in $O(2^{-c}).$ Analysis of this is provided in the Appendix.

We finish of this section with a comment on how total failure can be dealt with, when failure is not an option. In the context of (effectively) infinite sequences of Markov chains, the exponentially unlikely failure will still occur. In this case, if we are required to proceed although the protocol failed at time-step $t$, one can always prepare a sufficient number of samples from $\ket{\pi_t}$ in time $\tilde{O}(N^{1/2}/\sqrt{\delta_t} ),$ by forcing the preparation from the uniform distribution. 
Although this constitutes a quadratic slowdown (w.r.t. the state space size), it will only occur exponentially rarely, which means that, at least the average preparation cost for each time step can be kept arbitrarily close to $\tilde{O}( N^{1/4}/\sqrt{\delta_t} ).$ 

%The protocol, by its construction, assumes that time and again we must revert one step to generate fresh $c$ samples. In this one-step backtracking process, we still have a $O(2^{-c})$ probability of failing.
%We can improve on this further, by allowing the backtracking of up up to $r$ steps. In this case, the overall failure probability becomes $O( (2^{-c})^r) = O( 2^{-r \times c}).$ Thus we have an alternative method of reducing the failure probability, aside from increasing $c$ directly.  

%
%\section{TEEEEMP}
%
%MC$_{1}$,\ MC$_{2}$, \ MC$_{t}$, \ MC$_{t+1}$
%\EQ{
%\pi_{\textup{init}}
%\pi_1\\
%\pi_2\\
%\pi_t\\
%\pi_{t+1}\\
%\pi_{t-1}
%}
%

\section{Discussion}
 \label{Sect5}
We have presented a quantum algorithm for sequentially generating stationary distributions of an arbitrarily large sequence of Markov chains. The quantum algorithm outperforms classical approaches whenever the spectral gaps $\delta$ of the Markov chains are below $1/\sqrt{N}$, where $N$ is the size of the state space. In contrast, straightforward application of the``mixing by reverse hitting" approach would yield improvements only in a quadratically more stringent regime where $\delta < 1/N$. The basic observation we have used is that the bottle-neck of direct mixing by running hitting algorithms in reverse, can be ameliorated when only a small number of elements sampled from the target distribution are available beforehand. We have shown that this can guarantee that the initial state of the unsearch approach is far from the worse case setting. Following this, we have shown how these samples can be made available in the context of slowly evolving Markov chains.
As we have clarified, the presented algorithm has an immediate application in a recent approach to (quantum) artificial intelligence \cite{2014_Paparo}, but it may be useful in other context as well. For instance, it may offer improvements for problems stemming from statistical physics. One application could be in the case when strictly independent samples from Gibbs distributions of physical systems are required in a large range of temperatures, which include the computationally difficult low-temperature regimes. Other applications may be possible as well, for instance in applications where subsequent Markov chains may depend on the actual outputs of previous mixing steps. In this case, quantum-enhanced classical annealing methods become unsuitable, as they need to keep coherence through the protocol steps \cite{2009_Wocjan}.

As a feature of our protocol, we point out that at each time step can output not just a classical sample from the target stationary distribution, but a coherent encoding of this distribution. This is not a guaranteed characteristic of quantum mixing protocols \cite{2007_Richter}, and makes our approach suitable for combining with other quantum protocols which start from such a coherent encoding \cite{2011_Magniez_SIAM, 2014_Paparo, 2010_Krovi}.

In the protocol we have presented, as in other related works, it is always assumed that aside from the Markov chains themselves, one also has access to the values of the spectral gaps. This is potentially a problematic assumption, since, at least in the general cases, spectral gaps are often difficult to determine. Consequently, methods which do not rely on good lower bounds of the spectral gaps, or, more precisely, which can adaptively estimate the changes in spectral gaps in the context of slowly evolving sequences, are part of ongoing work.

\noindent\textbf{Acknowledgments:\\}
The authors acknowledge the support by the Austrian Science Fund (FWF) through 
the SFB FoQuS F4012, and the Templeton World Charity Foundation grant TWCF0078/AB46. VD thanks G. D. Paparo for initial discussions.



%
%\begin{itemize}
%\item Algorithms above assume $\delta$'s are known (or at least the bounds are). In our algorithm, if only the first $\delta_0$ is known, and aside from this we only know $\delta_k \geq \kappa \delta_{k+1}$, this gives the bound
%$\delta_0 \geq \kappa^{k} \delta_k,$ that is we have an exponential blow up in the bounds on $1/\delta_k$.
%This is unacceptable, as in general $\delta$'s may also decrease, and indeed we may wish to put a bound on the largest $\delta$. Thus, in the case when the multiplicative bounds are known, but nothing else,  it would be necessary to have an algorithm which actually estimates the next $\delta$.
%One simple way of doing this is a log-search procedure for the step $k$. Assume $\delta_{k-1}$ is known. Then we know $\delta_{k-1} \kappa^{-1} \leq \delta_{k} \leq \delta_{k-1} \kappa$. 
%Next, note that by using the known bound $\delta' = \kappa \delta_{k-1}$ on the real $\delta^{real}_{k}$ we can assess whether a guess $\delta_{guess}$ is above $\delta^{real}_{k}$, using the following steps.
%First we perform the relevant mixing procedure (unsearch, or preparation from uniform, depending on the regime), assuming the spectral gap is $\delta_{guess}$ obtaining some state $\ket{\psi_{\delta_{guess}}}$.
%Next, we perform a $\ket{\pi_k}$ projective measurement on $\ket{\psi_{\delta_{guess}}}$, but now using the upper bound value $\delta'$. If the real value $\delta^{real}_{k}\leq \delta_{guess}$ then this measurement will succeed with high probability. Otherwise, the state $\ket{\psi_{\delta_{guess}}}$ will contain contributions of eigenvectors with non-zero phase, and this will be detected by the $\ket{\pi_k}$ projective measurement \footnote{We note that, in principle, one could enhance the performance of this step by performing amplitude amplification, but now amplifying the non-zero phase eigenvectors in $\ket{\psi_{\delta_{guess}}}$, prior to the projective measurement.} \red{What if the contribution of the other guys is low? It does not matter for the current step, as you got your state, since the worst case measurement did not proclaim failure. However, this is true assuming we really did have the worst case bound. Did we? Assume that the bound on $\delta_{k-1}$ was good. Then we got the right state at $k$, but we may have gotten a bad estimate for $\delta_{k}$. We are only in trouble if it is underestimated, and this is actually the only case that can happen by the correctness of the preparation procedure, within errors. 
%If it is underestimated the bound on $\delta_{k+1}$ will be underestimated, and our checking fails in the next step... 
%Need to ponder on this... all our estimates go with factor 2, as it is about the number of ancilla qubits we use in the phase estimation. How do we make sure that if we screw up, we screw up badly enough? Can I have an independent test?}
%However, if we can detect whether the current guess $\delta_{guess}$ is above or below the target value $\delta^{real}_{k},$ we can in a log number of iterations achieve an arbitrary good approximation of the real value using standard binary search. 
% The algorithm above, at each step $k$ has a cost of $\tilde{O}(N^{1/4}/\sqrt{ \kappa \delta_{k-1}})$, which looks like the worst case cost, but only locally. To clarify this, note that, if $(\delta^{real}_j)_j$ are the real spectral gaps of the relevant Markov chains, and $\delta_{0} = \delta^{real}_0$ is known, then an algorithm which utilizes the multiplicative bound at each step only, has, for the $k^{th}$ chain a running efficiency $\tilde{O}(N^{1/4}/\sqrt{ \kappa^{k} \delta_{0}})$. In contrast, the algorithm with the $\delta-$approximation step achieves  
% $\tilde{O}(N^{1/4}/\sqrt{ \kappa \delta^{real}_{k-1}}),$ and since $\kappa$ is constant,  by the multiplicative bounds this is equal to  $\tilde{O}(N^{1/4}/\sqrt{  \delta^{real}_{k}}),$ which is optimal.
% \red{Can we utilize the new fix-point algorithm of Chuang to avoid this issue completely?}
% \item Utilizing quantum memory to get better performance: if we use only classical sampling as a method of extra information, intuitively the best we could have, for the unsearching, is the scaling with $N^{1/4}/c$.
% Can we prepare an initial state which has $c\times \log(N)$ basis elements, use that as a seed?  The problem with quantum states is... how many??? If they need to be carried forward? This probably fails completely... Is this a fundamental no go? I can take $log(N)$ samples, but how can this map to something better than $N^{1/4}/log(N)$??
% 
% \item Avoiding sampling through approximate sampling... Few steps of unsearch, followed by quantum 2-majority vote? 
% \item Can we get more out of the limits on the fidelity? More properties of the distribution than just the two lemmas?
% 
% 
% \item \red{Can we combine this with lloyd? Use his alg to get a constant distance seed, and then Magniez the crap out of it? }
% \end{itemize}
%
%\red{further tweaks, average efficiency, comparison to computational methods.}
%
%



\section{Appendix}
In this section we prove the technical lemmas from the main body of the paper, which we repeat for the benefit of the reader. Following this, we provide an analysis of our protocol covering the imperfections in the reflection operators.

\noindent\textbf{Lemma} \ref{fid:mode:bounds}. \emph{Let $\pi$ be a distribution over $N$ states, such that $F(\ket{u}, \ket{\pi}) \leq 1/\sqrt{N}.$ Then $\max_{i} \pi_i \geq 1/\sqrt{N}$. Moreover, if   $\max_{i} \pi_i \leq 1/\sqrt{N},$ then $F(\ket{u}, \ket{\pi}) \geq 1/\sqrt{N}. $ }

\proof
Assume first that  $\max_{i} \pi_i \leq 1/\sqrt{N}.$ Then, we ask what distribution $\pi$ minimizes the fidelity, relative to the uniform distribution, satisfying the given constraint on the mode(s).
We claim that the distribution which minimizes the fidelity is the distribution $\pi$ (up to permutation of the probabilities, which does not change the overlap with the uniform distribution) defined as follows.

Let $p_{max} = 1/\sqrt{N}$ and $k = \left\lfloor \dfrac{1}{p_{max}} \right\rfloor$.
For all $i$ such that $1 \leq i \leq k$ we set $\pi_i = \pi_{max}.$
Furthermore, we set $\pi_{k+1} = (1 - k \ p_{max}). $ Finally, for all remaining states we set $\pi_{i\geq k+1} = 0.$ 

To see this is the case, first note that the permutation of the probabilities does not change the overlap with the uniform distribution. 
Thus it will suffice to consider distributions whose probabilities are ordered in a decreasing order according to the indices. We will call such distributions decaying distributions \cite{2015_Dunjko2}.
Next, we will say that the decaying distribution $\rho$ is obtained from the decaying distribution $\gamma$ \emph{by separating the probabilities of elements} $i$ \emph{and} $j$ \emph{in} $\gamma,$ (for $i<j$) if the following holds: $\gamma_k = \rho_k$ for all $k \not=i$ and $k\not=j$, and $\gamma_i \leq \rho_i$ and $\gamma_j \geq \rho_j$. Intuitively, to obtain $\rho$ from $\gamma$ we simply shift a part of the mass of the probability at state $j$ to the state at $i$ while maintaining the order.
Next, note that the distribution $\pi$ is the extreme point of such a probability separation process, for all decaying distributions satisfying the constraint on the probability of the mode: $\pi$ can be obtained by iterating this process from any decaying distribution $\sigma$, which satisfies the constraint $\max_{i} \sigma_i \leq 1/\sqrt{N}$. 

For completeness, we illustrate why this works.
For instance, by starting from the smallest non-zero probability element $i$ in $\sigma$, decreasing it, while increasing the largest probability element in  $j$ in the distribution $\sigma$  which is smaller than $p_{max}$ until the modified value of $\sigma_j$ equals $p_{max}$, or until we deplete $\sigma_{i}$. By iterating this procedure, in a finite number of steps we will have reached $\pi$.

Next, we claim that if the decaying distribution $\rho$ is obtained from the decaying distribution $\gamma$ by separating the probabilities of elements $i$ and $j$, then $F(\ket{\gamma} ,\ket{u}) \leq F(\ket{\rho} ,\ket{u}).$
This follows from the convexity of the fidelity relative to the uniform distribution: since we are only changing the probabilities of the elements $i$ and $j$, the distance from the uniform distribution (fixing all other parameters) is  up to squaring proportional to 
$f(p_i, p_j) = \sqrt{p_i} + \sqrt{p_j},$ where $p_i+ p_j$ is constant. This function clearly decreases as $p_i$ grows at the expense of $p_j$.

But since $\pi$ is the extremal point of the process of separating the probabilities (under the constraint that $\pi_{max} \leq p_{max}$), the distribution $\pi$ as defined minimizes the fidelity under the given constraint on the mode of the distribution. 
The fidelity between $\ket{\pi}$ and $\ket{u}$ is now easy to compute:
We have that $F(\ket{\pi}, \ket{u}) = \dfrac{1}{N} \vert \sum_{i} \sqrt{\pi_i} \vert^2,$ and we will evaluate $f(\pi) \mathop{:} = \sum_{i} \sqrt{\pi_i}.$

We have that
 \EQ{
f(\pi) = \left\lfloor \dfrac{1}{p_{max}} \right\rfloor \sqrt{p_{max}} + \sqrt{1 - \left\lfloor \dfrac{1}{p_{max}} \right\rfloor p_{max}} \label{Eq-first}.
}

This expression can be further simplified.
In the following, let for $x\in \mathbbmss{R}^+$, $\{ x\} = x - \lfloor{x} \rfloor$ denote the fractional part of $x$.
Then we have:
\EQ{
\left\lfloor \dfrac{1}{p_{max}} \right\rfloor \sqrt{p_{max}} + \sqrt{1 - \left\lfloor \dfrac{1}{p_{max}} \right\rfloor p_{max}} \\
 =(\dfrac{1}{p_{max}} - \{\dfrac{1}{p_{max}}\})\sqrt{p_{max}} +  \sqrt{1 - (\dfrac{1}{p_{max}} - \{\dfrac{1}{p_{max}}\})p_{max}} \\=
 \dfrac{1}{\sqrt{p_{max}}} - \{\dfrac{1}{p_{max}}\}\sqrt{p_{max}} + \sqrt{ \{\dfrac{1}{p_{max}}\} p_{max} }  \\=
  \dfrac{1}{\sqrt{p_{max}}} + \sqrt{p_{max}}(  \sqrt{ \{\dfrac{1}{p_{max}}\} } - \{\dfrac{1}{p_{max}}\}).
}
Since the fractional part is always between 0 and 1, and since on that interval it holds that $\sqrt{x}>x,$ we have that the expression $(  \sqrt{ \{\dfrac{1}{p_{max}}\} } - \{\dfrac{1}{p_{max}}\})$ is always non-negative, the minimum is zero, and the maximum reached at $x=1/4$ where it reaches the value $1/4$.  
Thus we have $f(\pi) \geq 1/\sqrt{p_{max}}$ so 
\EQ{
F(\ket{\pi}, \ket{u})  = \dfrac{1}{N} f(\pi)^2 \geq  \dfrac{1}{N}\dfrac{1}{\sqrt{p_{max}}^2} = \dfrac{1}{N p_{max}} =  \dfrac{1}{\sqrt{N}} \label{Eq-last}. 
}
This proves the second direction of the lemma.

By taking the contrapositive of the second direction we immediately obtain
\EQ{
F(\ket{u}, \ket{\pi}) < 1/\sqrt{N} \Longrightarrow \max_{i} \pi_i > \dfrac{1}{\sqrt{N}}.
}
For the case that $F(\ket{u}, \ket{\pi}) = 1/\sqrt{N},$ by similar arguments as before, we get $\pi_{max} \geq 1/\sqrt{N},$ so the Lemma holds.
\qed

Next, we prove Lemma \ref{main:lemma}. For convenience we will rephrase it in terms of the function $f$ defined as $f(\pi) \mathop{:} = \sum_{i} \sqrt{\pi_i},$ which is up to a square proportional to the fidelity w.r.t. the uniform distribution: \EQ{F(\ket{\pi}, \ket{u})=  \dfrac{1}{N}f(\pi)^2.}


\vspace{0.5cm}


\noindent \textbf{Lemma} \ref{main:lemma} (rephrased).
\emph{Let $\pi$ be a distribution and let $f(\pi) \leq N^{1/4}.$ Then there exists a set of indices 
$S \subseteq \{1, \ldots, N\}$ such that the two following properties hold:
\begin{itemize}
\item $\min_{i \in S} \pi_i \geq \dfrac{1}{4 \sqrt{N}}$ and
\item $P(S) = \sum_{i\in S} \pi_i \geq \dfrac{1}{2}.$
\end{itemize}}



\proof


Assume the lemma does not hold, that is, for every $S \subseteq \{1, \ldots, N\}$ either 
 $\min_{i \in S} \pi_i < \dfrac{1}{4 \sqrt{N}}$ and/or $ \sum_{i\in S} \pi_i < 1/2.$
 
 Let $S$ be the set of all the indices of all probabilities occurring in $\pi,$
 which are larger or equal to $\dfrac{1}{4 \sqrt{N}} $.
Note that by Lemma \ref{fid:mode:bounds}, since $f(\pi) \leq N^{1/4} \Leftrightarrow F(\ket{u},\ket{\pi}) \leq 1/\sqrt{N}$, there exists at least one probability larger or equal to $\dfrac{1}{\sqrt{N}},$ thus the set $S$ is non-empty and $P(S)>0$. 
 
For this lemma to be false, it then must hold that  $ \sum_{i\in S} \pi_i < \dfrac{1}{2}.$

 
 But then, for the complement set of indices $S^{C} = \{1, \ldots, N \} \setminus S$ the following holds:
 \EQ{P(S^C) = \sum_{i\in S^C} \pi_i  \geq 1/2 , \label{eq:max1}} and
 \EQ{\max_{i\in S^C} \pi_i < \dfrac{1}{4 \sqrt{N}}.\label{eq:sum1}}
 Note that, by the assumptions of the Lemma it holds that
 \EQ{
 \sum_{i \in S} \sqrt{\pi_i} +  \sum_{i \in S^C} \sqrt{\pi_i} \leq N^{1/4}, \label{contr}
 }
 and, as we have seen,  $\sum_{i \in S} \sqrt{\pi_i} >0$.
 
 Now, consider the renormalized distribution $\tilde{\pi},$ where all probabilities corresponding to elements in $S$ are set to zero. By Eq. (\ref{eq:max1}), the renormalization factor is below 2.
 Then, since $\max_{i\in S^C} \pi_i < \dfrac{1}{4 \sqrt{N}}$ it holds that $\max_i \tilde{\pi}_i < \dfrac{1}{2 \sqrt{N}}.$ 
 Finally, we proceed analogously to the proof of the second direction of the first Lemma (Eq.~(\ref{Eq-first}) to Eq.~(\ref{Eq-last})) to find a bound on the $f(\tilde{\pi})$ function under the constraint that $\max_i \tilde{\pi}_i \leq \dfrac{1}{2 \sqrt{N}}.$ 
 We obtain 
 \EQ{
 f(\tilde{\pi}) \geq \dfrac{1}{\sqrt{1/(2\sqrt{N})}} = \sqrt{2 \sqrt{N}},
 }
 
which implies that $\sum_{i \in S^C} \sqrt{\pi_i} \geq \dfrac{1}{\sqrt{2}}  f(\tilde{\pi})  \geq N^{-1/4}.$
 
Since $f(\pi^{S})>0$ (strict inequality) we have the desired contradiction with Eq. (\ref{contr}) since $N^{1/4} + f(\pi^{S})$  is  strictly larger than $N^{1/4}$. $\qed$


\paragraph{Analysis for imperfect reflection operators}
Here we consider the propagation of errors when the reflection operator over the stationary distribution, and the $\ket{\pi}$ projective measurement, are approximate.  
Recall that both in the cases of the preparation from the uniform distribution, and in the cases of preparation from a given sampled element $i$, the precision of the approximation of the target state comes into play only logarithmically. More precisely, if $\epsilon$ is the desired bound on the trace distance between the realized distribution and the targeted distribution, and if $\xi$ is the fidelity between the initial state (uniform distribution or the given sample state $\ket{i}$), and the target state, then the total cost of the preparation procedure is given with $O\left(\sqrt{\delta^{-1}} \sqrt{\rho^{-1}} \left( \log\left(\epsilon^{-1}\right) + \log\left( \sqrt{\xi^{-1}} \right) \right) \right).$ In the last expression, the second log term compensates for the fact that an imperfect reflector will be applied $ \sqrt{\xi^{-1}}$ times, accumulating errors\footnote{We note that the errors stemming from the iterations of the approximate reflection operator can be further suppressed using more elaborate techniques, see \cite{2011_Magniez_SIAM} for further details.}.

Thus, the precision of the approximation contributes only logarithmically in the overall complexity, even  in the iterated setting. However, we must make sure that the inductive steps of our protocol, going from one time step to another, are not overly sensitive to small imperfections. There are two moments where the imperfections can cause problems. First, except for the first time-step, the $c$ samples we have stem not from the exact distribution, but rather the approximation. Second, in the generation of the $c$ samples at step $t$ we used an approximate projective measurement to go from an approximation of $\ket{\pi(t-1)}$ to an approximation of $\ket{\pi(t)}$, which succeeds with probability $\eta$ (the fidelity between the two states), only in the exact case.
For the second problem, a simple way to bound the deviation on the success probability is by considering the ideal $\ket{\pi}$ projective measurement as a completely positive trace-preserving (CPTP) map $\mathcal{E}_{\ket{\pi}}$ which outputs just the success or failure status (since we care only about the perturbations of the success probabilities). 
So
 \EQ{
 \mathcal{E}_{\ket{\pi(t)}} ( \dm{\pi(t-1)}) = \eta \dm{\textup{ok}} + (1-\eta) \dm{\textup{fail}}.
 }
The approximate projective measurement (precise within $\epsilon$) can be represented in the same way by the map  $\mathcal{E}^{\epsilon}_{\ket{\pi}},$
and we have that
\EQ{
1/2 || \mathcal{E}^{\epsilon}_{\ket{\pi}} (\rho) - \mathcal{E}_{\ket{\pi}} (\rho)|| \leq \epsilon
}
for any state $\rho$, where $||\cdot ||$ represents the standard trace norm on quantum states. 
The above holds for any pure state $\rho,$ so we get the above by triangle inequalities for arbitrary states. We point out that the claim holds when complete maps (which also output the heralded quantum state, not just the success/failure bit) are considered, but as tracing out only reduces trace distances this claim also holds.
Note that we do not need to consider purified systems (nor completely bounded norms on the maps), for our problem.
Then if $\mathcal{E}^{\epsilon}_{\ket{\pi(t)}} ( \dm{\pi(t-1)}) = \sigma \dm{\textup{ok}} + (1-\sigma) \dm{\textup{fail}},$ we have that
\EQ{
 1/2|| \mathcal{E}_{\ket{\pi(t)}} ( \dm{\pi(t-1)}) -  \mathcal{E}^{\epsilon}_{\ket{\pi(t)}} ( \dm{\pi(t-1)}) || =  |\eta - \sigma|
}
but then also $|\eta -\sigma| \leq \epsilon.$
In the following, let $\rho_{\pi(t-1)}$ denote the $\epsilon-$close approximation of $\ket{\pi(t-1)}$ (in the trace distance), and let  $\eta'$ be the success probability of the approximate projection measurement on the approximation $\rho_{\pi(t-1)},$ so
\EQ{
\mathcal{E}^{\epsilon}_{\ket{\pi(t)}} ( \rho_{\pi(t-1)}) = \eta' \dm{\textup{ok}} + (1-\eta') \dm{\textup{fail}}
}
Then we have that
\EQ{
|\eta - \eta'| = 1/2||\mathcal{E}^{\epsilon}_{\ket{\pi(t)}} ( \rho_{\pi(t-1)})  - \mathcal{E}_{\ket{\pi(t)}} ( \dm{\pi(t-1)})     ||
}
and then by adding and subtracting $\mathcal{E}^{\epsilon}_{\ket{\pi(t)}} ( \dm{\pi(t-1)}) $, and by the triangle inequality we obtain
\EQ{
|\eta - \eta'| \leq \epsilon + 1/2||\mathcal{E}^{\epsilon}_{\ket{\pi(t)}} ( \rho_{\pi(t-1)})  - \mathcal{E}^{\epsilon}_{\ket{\pi(t)}} ( \dm{\pi(t-1)})     ||,
}
which by the contractivity of CPTP maps yields $|\eta - \eta'| \leq 2 \epsilon$.
Then by setting $\epsilon$ to $\eta/4$ we get that if $\eta' < \eta$ ( which is the problematic case) then $\eta' \geq \eta/2.$
In other words, as long as we make sure the error is below $\eta/4$ (which is still a constant), we are sure that the success probability of the approximate measurement on the approximate state is in the worse case halved. This constitutes only a  a constant multiplicative increase in the run-time of our protocol, so the overall complexity expression is unchanged.

The other problem we face in the light of the approximate nature of the operators we use, is that the $c$ sampled elements we obtain do not stem from the distribution $\pi,$ but an $\epsilon-$close approximation (in terms of the trace distance). 
To analyze the worst case scenario how this influences our protocol, we shall employ similar arguments as above. Note that the``preparation from $c$ samples" subroutine can be viewed as a CPTP map applied on $c$ mixed states, all encoding the underlying probability distribution, which outputs success (heralds that the preparation succeeded) , except with probability $2^{-c},$ if the target distribution is in the right regime, i.e. far from uniform.
The $c$ mixed states are obtained by computational basis measurements of the ideal coherent encoding of the target probability distribution $\ket{\pi(t)}.$
In the non-ideal case, we have as input $c$ mixed states obtained by a computational-basis measurement of $c$ approximations, which are within $\epsilon$ distance from the ideal states. 
Since the trace distance can only decrease by measurements, and by its subaditivity w.r.t. tensor products, the total inputs, in the ideal and non-ideal case, differ by at most $c \epsilon$ (in the trace distance).
But then the output of the procedures (hence, also the success probability) cannot differ by more than $c \epsilon.$ Thus we obtain that the failure probability for the non-ideal case is no greater than $2^{-c} + c\epsilon$. If we set $\epsilon = 2^{-2c},$ the failure probability is lower bounded by $2^{-c+1},$ which is obeys the same scaling. Since the error term $\epsilon$ appears logarithmically in the overall complexity, we get an additional multiplicative pre-factor of $\log(2^{2c})$ which is in $O(c)$.

Then, the worst case complexity of our approach is given with $\tilde{O}(c^3\,\sqrt{\delta^{-1}} N^{1/4} ),$ with failure probability $2^{-c+1}.$ By adding one to all confidence parameters of the protocol, since $(c+1)^3 \in O(c^3)$, we obtain the cost in $\tilde{O}(c^3\, \sqrt{\delta^{-1}} N^{1/4} )$ and the same failure probability, as for the ideal reflectors case, of $2^{-c}$.
 



%\subsection{Classical cost lower bounds}
%In the section above we have shown how by employing quantum walk operators we can generate stationary distributions of sequences of Markov chains, provided the neighboring Markov chains have close stationary distributions.
%The protocol resolved the problem in time $\tilde{O}(N^{1/4}/\sqrt{\delta(t)})$ by resorting to either the measurement approach (if the stationary distribution is close to uniform) or to unsearching otherwise. In the latter case, to perform the unsearching, we first generated $c$ samples from the target distribution, and we have shown that with probability $1-2^{-c},$ at least one of the samples was a state which occurs with probability at least $1/(4 \sqrt{N})$ in the target distribution. 
%
%In the context of hitting times, the quadratic speed-up obtained by employing quantum walks, rather than classical walks is provable based on the lower bounds of classical mixing times which hold for time-reversible Markov chains.
%
%For completeness, we remind the reader of the basic results in the theory of mixing Markov chains.
%
%Let $P$ be an $N \times N$ left-stochastic matrix, which is a transition matrix of an aperiodic, irreducible time -reversible Markov chain. 
%As $P$ is time-reversible, one can show $P$ is similar to a symmetric matrix, which then implies that $P$ has real eigenvalues, and by Perron-Frobenius theorem, of absolute value no greater than 1. As the MC is also aperiodic and irreducible, it holds that there is exactly one eigenvalue of absolute value 1, namely $+1$, corresponding to the stationary distribution probability vector..
%
%Let $\delta = ( 1 - \lambda_{2}) >0$, where $\lambda_2$ is the second-largest eigenvalue in absolute value of $P$, be the spectral gap of $P$.
%The quantity $t_{rel} = 1/\delta$ is often referred to as the relaxation time of $P$.
%
%Let $\pi$ and $\sigma$ be two distributions over $N$ (represented as probability vectors). Then with $\|\pi - \sigma \|_{tr} = \dfrac{1}{2} \sum_{i} | \pi_i -\sigma_i  | $ we denote the total variation distance on distributions. Note that the definition of total variation distance coincides with the notion of trace distance, when distributions are encoded as mixed states w.r.t. a fixed basis. 
%Then the mixing time (within $\epsilon$) of the Markov chain $P$, $t_{mix}(\epsilon)$ is defined as
%\EQ{
%t_{mix}(\epsilon) = \min \{ t | \max_{\sigma} \| P^t \sigma - \pi \|_{tr}  \leq \epsilon \}.
%}
%Let $\pi_{min} = \min_i \pi_i$ be the smallest probability occurring in the stationary distribution $\pi$ (note, this is always strictly greater than zero for ergodic Markov chains). Then we have the following bounds:
%\EQ{
%(t_{rel} - 1 ) \log \left(\dfrac{1}{2 \epsilon} \right)\leq t_{mix}(\epsilon) \leq  t_{rel} \log \left( \dfrac{1}{\epsilon \pi_{min}} \right) 
%}
%
%where $\sigma$ is any distribution over $N$ states \footnote{Often, the maximization in the definition of mixing times is over all $\sigma$ distributions which have support only on one state (a Kronecker-$\delta$ distribution). It can be proven that these two definitions are equivalent.}, and $\pi$ is the stationary distribution of $P$.
% Here we can see that, for any distance $\epsilon$, the lower bound of the mixing time is governed by $t_{rel} -1$ so is in $\Omega(t_{rel}) = \Omega(1/\delta).$
% 
%





\bibliographystyle{unsrt}

\begin{thebibliography}{10}
\expandafter\ifx\csname url\endcsname\relax
  \def\url#1{\texttt{#1}}\fi
\expandafter\ifx\csname urlprefix\endcsname\relax\def\urlprefix{URL }\fi
\providecommand{\bibinfo}[2]{#2}
\providecommand{\eprint}[2][]{\url{#2}}

%\item[]{{\normalsize \textbf{References:\\}}}
%\bibitem{1985_Deutsch}
%\bibinfo{author}{Deutsch, D.}
%\newblock \bibinfo{title}{Quantum theory, the {C}hurch-{T}uring principle and
%  the universal quantum computer}.
%\newblock \emph{\bibinfo{journal}{Proceedings of the Royal Society of London
%  A}} \textbf{\bibinfo{volume}{400}}, \bibinfo{pages}{97--117}
%  (\bibinfo{year}{1985}).
%\newblock \urlprefix\url{http://www.qubit.org/oldsite/resource/deutsch85.pdf}.
%
%\bibitem{1992_Deutsch}
%\bibinfo{author}{Deutsch, D.} \& \bibinfo{author}{Jozsa, R.}
%\newblock \bibinfo{title}{Rapid solution of problems by quantum computation}.
%\newblock \emph{\bibinfo{journal}{Proc Roy Soc Lond A}}
%  \textbf{\bibinfo{volume}{439}}, \bibinfo{pages}{553--558}
%  (\bibinfo{year}{1992}).
%
%\bibitem{1996_Grover}
%\bibinfo{author}{Grover, L.~K.}
%\newblock \emph{\bibinfo{journal}{Proceedings, 28th Annual ACM Symposium on the
%  Theory of Computing (STOC)}} \bibinfo{pages}{212} (\bibinfo{year}{1996}).
%
%\bibitem{1994_Shor}
%\bibinfo{author}{Shor, P.~W.}
%\newblock \bibinfo{title}{Algorithms for quantum computation: discrete
%  logarithms and factoring}.
%\newblock In \emph{\bibinfo{booktitle}{Proceedings of the 35th symposium on
%  foundations of computer science, FOCS~'94}}, \bibinfo{pages}{124--134}
%  (\bibinfo{publisher}{IEEE}, \bibinfo{year}{1994}).
%
%\bibitem{2000_NC}
%\bibinfo{author}{Nielsen, M.~A.} \& \bibinfo{author}{Chuang, I.~L.}
%\newblock \emph{\bibinfo{title}{Quantum Computation and Quantum Information}}
%  (\bibinfo{publisher}{Cambridge University Press}, \bibinfo{year}{2000}).
%
%\bibitem{2000_Bennet}
%\bibinfo{author}{Charles H.~Bennett, D. P.~D.}
%\newblock \bibinfo{title}{Quantum information and computation}.
%\newblock \emph{\bibinfo{journal}{Nature}} \bibinfo{pages}{247?255}
%  (\bibinfo{year}{2000}).
%\newblock
%  \urlprefix\url{http://www.nature.com/nature/journal/v404/n6775/full/404247a0.html}.
%
%\bibitem{2002_Sasaki}
%\bibinfo{author}{Sasaki, M.} \& \bibinfo{author}{Carlini, A.}
%\newblock \bibinfo{title}{Quantum learning and universal quantum matching
%  machine}.
%\newblock \emph{\bibinfo{journal}{Phys. Rev. A}} \textbf{\bibinfo{volume}{66}},
%  \bibinfo{pages}{022303} (\bibinfo{year}{2002}).
%\newblock \urlprefix\url{http://link.aps.org/doi/10.1103/PhysRevA.66.022303}.
%
%\bibitem{2008_Neven}
%\bibinfo{author}{Neven, H.}, \bibinfo{author}{Denchev, V.~S.},
%  \bibinfo{author}{Rose, G.} \& \bibinfo{author}{Macready, W.~G.}
%\newblock \bibinfo{title}{Training a binary classifier with the quantum
%  adiabatic algorithm}  (\bibinfo{year}{2008}).
%\newblock \eprint{arXiv/0811.0416}.
%
%\bibitem{2013_Lloyd}
%\bibinfo{author}{Lloyd, S.}, \bibinfo{author}{Mohseni, M.} \&
%  \bibinfo{author}{Rebentrost, P.}
%\newblock \bibinfo{title}{Quantum algorithms for supervised and unsupervised
%  machine learning}.
%\newblock \emph{\bibinfo{journal}{ArXiv:1307.0411}}  (\bibinfo{year}{2013}).
%
%\bibitem{2009_Brukner}
%\bibinfo{author}{Manzano, D.}, \bibinfo{author}{Paw{\l}owski, M.} \&
%  \bibinfo{author}{Brukner, {\v{C}}.}
%\newblock \bibinfo{title}{The speed of quantum and classical learning for
%  performing the k th root of not}.
%\newblock \emph{\bibinfo{journal}{New Journal of Physics}}
%  \textbf{\bibinfo{volume}{11}}, \bibinfo{pages}{113018}
%  (\bibinfo{year}{2009}).
%\newblock \urlprefix\url{http://stacks.iop.org/1367-2630/11/i=11/a=113018}.
%
%\bibitem{2013_Lidar}
%\bibinfo{author}{Pudenz, K.~L.} \& \bibinfo{author}{Lidar, D.~A.}
%\newblock \bibinfo{title}{Quantum adiabatic machine learning}.
%\newblock \emph{\bibinfo{journal}{Quantum Information Processing}}
%  \textbf{\bibinfo{volume}{12}}, \bibinfo{pages}{2027--2070}
%  (\bibinfo{year}{2013}).
%\newblock \urlprefix\url{http://dx.doi.org/10.1007/s11128-012-0506-4}.
%
%\bibitem{2013_Aimeur}
%\bibinfo{author}{A{\"{i}}meur, E.}, \bibinfo{author}{Brassard, G.} \&
%  \bibinfo{author}{Gambs, S.}
%\newblock \bibinfo{title}{Quantum speed-up for unsupervised learning}.
%\newblock \emph{\bibinfo{journal}{Machine Learning}}
%  \textbf{\bibinfo{volume}{90}}, \bibinfo{pages}{261--287}
%  (\bibinfo{year}{2013}).
%\newblock \urlprefix\url{http://dx.doi.org/10.1007/s10994-012-5316-5}.
%
%\bibitem{1986_Braitenberg}
%\bibinfo{author}{Braitenberg, V.}
%\newblock \emph{\bibinfo{title}{Vehicles: Experiments in Synthetic Psychology}}
%  (\bibinfo{publisher}{MIT Press}, \bibinfo{address}{Cambridge Massachusetts},
%  \bibinfo{year}{1986}).
%
%\bibitem{1999_Brooks}
%\bibinfo{author}{Brooks, R.}
%\newblock \emph{\bibinfo{title}{Cambrian intelligence: The early history of the
%  new AI}} (\bibinfo{publisher}{The MIT Press}, \bibinfo{address}{Cambridge,
%  MA}, \bibinfo{year}{1999}).
%
%\bibitem{1999_Pfeifer}
%\bibinfo{author}{Pfeifer, R.} \& \bibinfo{author}{Scheier, C.}
%\newblock \emph{\bibinfo{title}{Understanding Intelligence}}
%  (\bibinfo{publisher}{MIT Press}, \bibinfo{address}{Cambridge, MA, USA},
%  \bibinfo{year}{1999}).
%
%\bibitem{2006_Pfeifer}
%\bibinfo{author}{Pfeifer, R.} \& \bibinfo{author}{Bongard, J.~C.}
%\newblock \emph{\bibinfo{title}{How the Body Shapes the Way We Think: A New
%  View of Intelligence (Bradford Books)}} (\bibinfo{publisher}{The MIT Press},
%  \bibinfo{year}{2006}).
%
%\bibitem{2008_Floreano}
%\bibinfo{author}{Floreano, D.} \& \bibinfo{author}{Mattiussi, C.}
%\newblock \emph{\bibinfo{title}{Bio-inspired artificial intelligence :
%  theories, methods, and technologies}} (\bibinfo{publisher}{The MIT Press},
%  \bibinfo{year}{2008}).
%
%\bibitem{2008_Barsalou}
%\bibinfo{author}{Barsalou, L.~W.}
%\newblock \bibinfo{title}{Grounded cognition}.
%\newblock \emph{\bibinfo{journal}{Annual Review of Psychology}}
%  \textbf{\bibinfo{volume}{59}}, \bibinfo{pages}{617--645}
%  (\bibinfo{year}{2008}).
%


%\bibitem{2003_Russel}
%\bibinfo{author}{Russel, S.~J.} \& \bibinfo{author}{Norvig, P.}
%\newblock \emph{\bibinfo{title}{Artificial intelligence - A modern approach}}
%  (\bibinfo{publisher}{Prentice Hall}, \bibinfo{address}{New Jersey},
%  \bibinfo{year}{2003}), \bibinfo{edition}{second edition} edn.
%
%\bibitem{SuttonBarto98}
%\bibinfo{author}{Sutton, R.~S.} \& \bibinfo{author}{Barto, A.~G.}
%\newblock \emph{\bibinfo{title}{Reinforcement learning: An introduction}}
%  (\bibinfo{publisher}{MIT Press, Cambridge Massachusetts},
%  \bibinfo{year}{1998}), \bibinfo{edition}{first} edn.
%

\bibitem{2003_Kempe_Contemp_Phys}
\bibinfo{author}{Kempe, J.} 
\newblock \bibinfo{title}{Quantum random walks - an introductory overview}.
\newblock \emph{\bibinfo{journal}{Contemp. Phys.}} \textbf{\bibinfo{volume}{44(4)}},
  \bibinfo{pages}{307} (\bibinfo{year}{2003}).
  

\bibitem{2010_Krovi}
\bibinfo{author}{Krovi, H.}, \bibinfo{author}{Magniez, F.},  \bibinfo{author}{Ozols, M.} and \bibinfo{author}{Roland, J.}
\newblock \bibinfo{title}{Quantum walks can find a marked element on any graph}
\newblock \emph{\bibinfo{journal}{arXiv:1002.2419v2}}  (\bibinfo{year}{2014}).





\bibitem{2004_Ambainis}
\bibinfo{author}{Ambainis, A.}
\newblock \bibinfo{title}{Quantum walk algorithms for element distinctness}.
\newblock In \emph{\bibinfo{booktitle}{45th Annual IEEE Symposium on  
 Foundations of Computer Science, OCT 17-19, 2004. IEEE Computer Society
  Press, Los Alamitos, CA}}, \bibinfo{pages}{22--31} (\bibinfo{year}{2004}).
  
\bibitem{2004_Szegedy_IEEE}
\bibinfo{author}{Szegedy, M.}
\newblock \bibinfo{title}{Quantum speed-up of markov chain based algorithms}.
\newblock In \emph{\bibinfo{booktitle}{Foundations of Computer Science, 2004.
  Proceedings. 45th Annual IEEE Symposium on}}, \bibinfo{pages}{32 -- 41}
  (\bibinfo{year}{2004}).
 

\bibitem{2005_Magniez}
\bibinfo{author}{Magniez, F.}, \bibinfo{author}{Santha, M.} and  \bibinfo{author}{Szegedy, M.}
\newblock \bibinfo{title}{Quantum Algorithms for the Triangle Problem}.
\newblock \emph{\bibinfo{journal}{Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms}}
\emph{\bibinfo{series}{SODA '05}}, \bibinfo{pages}{1109--1117}
  (\bibinfo{year}{2005}).
  
  
  
\bibitem{1999_Newman}
\bibinfo{author}{Newman, M. E. J.} and \bibinfo{author}{Barkema, G. T.}
\newblock \emph{\bibinfo{title}{Monte Carlo Methods in Statistical Physics}}, 
  (\bibinfo{publisher}{Oxford University Press, Oxford, UK}, \bibinfo{year}{1999}).
  







 \bibitem{2007_Richter}
\bibinfo{author}{Richter, P. C.} 
\newblock \bibinfo{title}{ Quantum speedup of classical mixing processes}.
\newblock \emph{\bibinfo{journal}{Phys. Rev. A}} \textbf{\bibinfo{volume}{76}},
  \bibinfo{pages}{042306} (\bibinfo{year}{2007}).
\newblock \urlprefix\url{http://journals.aps.org/pra/abstract/10.1103/PhysRevA.76.042306}.

\bibitem{2007_Richter_NJP}
 \bibinfo{author}{Richter, P. C.} 
\newblock \bibinfo{title}{Almost uniform sampling via quantum walks}.
\newblock \emph{\bibinfo{journal}{New J. Phys.}} \textbf{\bibinfo{volume}{9}},
  \bibinfo{pages}{73} (\bibinfo{year}{2007}).


\bibitem{2011_Temme_Nature}
\bibinfo{author}{Temme, K.}, \bibinfo{author}{Osborne, T.~J.},
  \bibinfo{author}{Vollbrecht, K. G.~H.}, \bibinfo{author}{Poulin, D.} \&
  \bibinfo{author}{Verstraete, F.}
\newblock \bibinfo{title}{Quantum metropolis sampling}
  \textbf{\bibinfo{volume}{471}}, \bibinfo{pages}{87--90}
  (\bibinfo{year}{2011}).

\bibitem{2012_Yung}
\bibinfo{author}{Yung, M.-H.} \& \bibinfo{author}{Aspuru-Guzik, A.}
\newblock \bibinfo{title}{A quantum quantum metropolis algorithm}.
\newblock \emph{\bibinfo{journal}{Proceedings of the National Academy of
  Sciences}}  (\bibinfo{year}{2012}).

\bibitem{2008_Somma_PRL}
\bibinfo{author}{Somma, R.~D.}, \bibinfo{author}{Boixo, S.},
  \bibinfo{author}{Barnum, H.} \& \bibinfo{author}{Knill, E.}
\newblock \bibinfo{title}{Quantum simulations of classical annealing
  processes}.
\newblock \emph{\bibinfo{journal}{Phys. Rev. Lett.}}
  \textbf{\bibinfo{volume}{101}}, \bibinfo{pages}{130504}
  (\bibinfo{year}{2008}).
\newblock
  \urlprefix\url{http://link.aps.org/doi/10.1103/PhysRevLett.101.130504}.

\bibitem{2008_Wocjan}
\bibinfo{author}{Wocjan, P.} and \bibinfo{author}{Abeyesinghe, A.}
\newblock \bibinfo{title}{Speedup via quantum sampling}.
\newblock \emph{\bibinfo{journal}{Phys. Rev. A}} \textbf{\bibinfo{volume}{78}},
  \bibinfo{pages}{042336} (\bibinfo{year}{2008}).
\newblock \urlprefix\url{http://link.aps.org/doi/10.1103/PhysRevA.78.042336}.


\bibitem{2011_Magniez_SIAM}
\bibinfo{author}{Magniez, F.}, \bibinfo{author}{Nayak, A.},
  \bibinfo{author}{Roland, J.} \& \bibinfo{author}{Santha, M.}
\newblock \bibinfo{title}{Search via quantum walk}.
\newblock \emph{\bibinfo{journal}{SIAM Journal on Computing}}
  \textbf{\bibinfo{volume}{40}}, \bibinfo{pages}{142--164}
  (\bibinfo{year}{2011}).
\newblock \urlprefix\url{http://epubs.siam.org/doi/abs/10.1137/090745854}.

\bibitem{2001_Aharonov}
 \bibinfo{author}{Aharonov, D.}, \bibinfo{author}{Ambainis, A.}, \bibinfo{author}{Kempe, J.} and \bibinfo{author}{Vazirani, U.} 
\newblock \bibinfo{title}{Quantum walks on graphs}.
\newblock In \emph{\bibinfo{booktitle}{Proceedings of the thirty-third annual ACM symposium on Theory of computing, ACM, New York, NY, USA}}, \bibinfo{pages}{50--59} (\bibinfo{year}{2001}).

\bibitem{2000_Nayak}
\bibinfo{author}{Nayak, A.} and  \bibinfo{author}{Vishwanath, A.}\newblock \bibinfo{title}{Quantum walk on the line}
\newblock \emph{\bibinfo{journal}{arXiv:quant-ph/0010117}}  (\bibinfo{year}{2000}).

\bibitem{2001_Ambainis}
\bibinfo{author}{Ambainis, A.}, \bibinfo{author}{Bach, E.}, \bibinfo{author}{Nayak, A.}, \bibinfo{author}{Vishwanath, A.} and \bibinfo{author}{Watrous, J.}
\newblock \bibinfo{title}{One-dimensional quantum walks}.
\newblock In \emph{\bibinfo{booktitle}{Proceedings of the thirty-third annual ACM symposium on Theory of computing}}, \bibinfo{pages}{37--49} (\bibinfo{year}{2001}).



\bibitem{2002_Moore}
\bibinfo{author}{Moore, C.} and \bibinfo{author}{Russell, A.}
\newblock \bibinfo{title}{Quantum Walks on the Hypercube}.
\newblock \emph{\bibinfo{journal}{Randomization and Approximation Techniques in Computer Science}}
\emph{\bibinfo{series}{Lecture Notes in Computer Science}}
  \textbf{\bibinfo{volume}{2483}}, \bibinfo{pages}{164--178}
  (\bibinfo{year}{2002}).


\bibitem{2011_Reitzner}
\bibinfo{author}{Reitzner, D.}, \bibinfo{author}{Nagaj, D.} and \bibinfo{author}{Bu{\v{z}ek}, V.}
\newblock \bibinfo{title}{Quantum Walks}.
\newblock \emph{\bibinfo{journal}{Acta Phys. Slovaca}}
  \textbf{\bibinfo{volume}{61}}, \bibinfo{number}{6}, \bibinfo{pages}{603--725}
  (\bibinfo{year}{2011}).




\bibitem{2009_Wocjan}
\bibinfo{author}{Wocjan, P.}, \bibinfo{author}{Chiang, C.}, \bibinfo{author}{Nagaj, D.},  and \bibinfo{author}{Abeyesinghe, A.}
\newblock \bibinfo{title}{Quantum algorithm for approximating partition functions}.
\newblock \emph{\bibinfo{journal}{Phys. Rev. A}} \textbf{\bibinfo{volume}{80}},
  \bibinfo{pages}{022340} (\bibinfo{year}{2009}).



\bibitem{2014_Paparo}
\bibinfo{author}{Paparo, G. D.}, \bibinfo{author}{Dunjko, V.}, \bibinfo{author}{Makmal, A.}, \bibinfo{author}{Matrin-Delgado, MA.}, \bibinfo{author}{Briegel, H. J.}
\newblock \bibinfo{title}{Quantum speedup for active learning agents}.
\newblock \emph{\bibinfo{journal}{Phys. Rev. X}} \textbf{\bibinfo{volume}{4}},
  \bibinfo{pages}{031002} (\bibinfo{year}{2014}).
\newblock \urlprefix\url{http://journals.aps.org/prx/abstract/10.1103/PhysRevX.4.031002}.



\bibitem{2012_Briegel}
\bibinfo{author}{Briegel, H.~J.} \& \bibinfo{author}{De~las Cuevas, G.}
\newblock \bibinfo{title}{Projective simulation for artificial intelligence}.
\newblock \emph{\bibinfo{journal}{Sci. Rep.}} \textbf{\bibinfo{volume}{2}}
  (\bibinfo{year}{2012}).




\bibitem{Julian12}
\bibinfo{author}{Mautner, J.}, \bibinfo{author}{Makmal, A.},
  \bibinfo{author}{Manzano, D.}, \bibinfo{author}{Tiersch, M.} \&
  \bibinfo{author}{Briegel, H.~J.}
\newblock \bibinfo{title}{Projective simulation for classical learning agents:
  a comprehensive investigation.} \bibinfo{journal}{New Generat. Comput.}
  (\bibinfo{year}{2015}).
 \textbf{ \bibinfo{volume}{33}}, 
   \bibinfo{issue}{1},
  \bibinfo{pages}{69--114}.

  \bibitem{1997_Aldous}
\bibinfo{author}{Aldous, D.} ,  \bibinfo{author}{L{\'{a}}szl{\'{o}}, L} and  \bibinfo{author}{Winkler, P.}
\newblock \bibinfo{title}{Mixing times for uniformly ergodic Markov chains}
\newblock \emph{\bibinfo{journal}{Stochastic Processes and their Applications}}  (\bibinfo{year}{1995}).
\bibinfo{volume}{2}
\bibinfo{pages}{165--185}


\bibitem{1998_Norris}
\bibinfo{author}{Norris, J. R.}
\newblock \emph{\bibinfo{title}{Markov chains}}
  (\bibinfo{publisher}{Cambridge University Press}, 
  \bibinfo{year}{1998}).

\bibitem{1996_Kitaev}
\bibinfo{author}{Kitaev, A. Y.} 
\newblock \bibinfo{title}{Quantum measurements and the Abelian Stabilizer Problem}.
\newblock In \emph{\bibinfo{booktitle}{Electronic Colloquium on Computational Complexity (ECCC) 3}},  (\bibinfo{year}{1996}).


\bibitem{2000_Brassard}
\bibinfo{author}{Brassard, G.}, \bibinfo{author}{Hoyer, P.},  \bibinfo{author}{Mosca, M.} and \bibinfo{author}{Tapp, A.}
\newblock \bibinfo{title}{Quantum Amplitude Amplification and Estimation}
\newblock \emph{\bibinfo{journal}{arXiv:quant-ph/0005055}}  (\bibinfo{year}{2000}).


\bibitem{2004_Childs}
\bibinfo{author}{Childs, A.} \newblock \bibinfo{title}{Quantum information processing in continuous time}. \bibinfo{note}{Ph. D. Thesis, Massachusetts Institute of Technology, (2004).} 
  



\bibitem{2015_Dunjko2}
\bibinfo{author}{Dunjko, V.} and  \bibinfo{author}{Briegel, H. J.}
\newblock \bibinfo{title}{Quantum mixing of Markov chains for special distributions}.
\newblock \bibinfo{note}{Preprint: arXiv:1502.05511}


\bibitem{1998_Boyer}
\bibinfo{author}{Boyer, M.}, \bibinfo{author}{Brassard, G.},  \bibinfo{author}{H{\o}yer, P.} and \bibinfo{author}{Tapp, A.}
\newblock \bibinfo{title}{Tight Bounds on Quantum Searching}
\newblock \emph{\bibinfo{journal}{Fortschritte der Physik}}  
 \textbf{\bibinfo{volume}{46}}, \bibinfo{pages}{493--505}(\bibinfo{year}{1998}).





  


%\bibitem{1995_Kohonen}
%\bibinfo{author}{Kohonen, T.}
%\newblock \bibinfo{title}{Self-organizing maps}
%  (\bibinfo{publisher}{Springer-Verlag}, \bibinfo{year}{1995}).
%
%\bibitem{2006_Toussaint}
%\bibinfo{author}{Toussaint, M.}
%\newblock \bibinfo{title}{A sensorimotor map: Modulating lateral interactions
%  for anticipation and planning}.
%\newblock \emph{\bibinfo{journal}{Neural Comput.}}
%  \textbf{\bibinfo{volume}{18}}, \bibinfo{pages}{1132--1155}
%  (\bibinfo{year}{2006}).
%\newblock \urlprefix\url{http://dx.doi.org/10.1162/089976606776240995}.
%
%\bibitem{2005_Magniez}
%\bibinfo{author}{Magniez, F.}, \bibinfo{author}{Santha, M.} \&
%  \bibinfo{author}{Szegedy, M.}
%\newblock \bibinfo{title}{Quantum algorithms for the triangle problem}.
%\newblock In \emph{\bibinfo{booktitle}{Proceedings of the Sixteenth Annual
%  ACM-SIAM Symposium on Discrete Algorithms}}, SODA '05,
%  \bibinfo{pages}{1109--1117} (\bibinfo{publisher}{Society for Industrial and
%  Applied Mathematics}, \bibinfo{address}{Philadelphia, PA, USA},
%  \bibinfo{year}{2005}).
%\newblock \urlprefix\url{http://dl.acm.org/citation.cfm?id=1070432.1070591}.
%

%
%\bibitem{2012_Magniez_Algorithmica}
%\bibinfo{author}{Magniez, F.}, \bibinfo{author}{Nayak, A.},
%  \bibinfo{author}{Richter, P.~C.} \& \bibinfo{author}{Santha, M.}
%\newblock \bibinfo{title}{On the hitting times of quantum versus random walks}.
%\newblock \emph{\bibinfo{journal}{Algorithmica}} \textbf{\bibinfo{volume}{63}},
%  \bibinfo{pages}{91--116} (\bibinfo{year}{2012}).
%\newblock \urlprefix\url{http://dx.doi.org/10.1007/s00453-011-9521-6}.
%


 


%\bibitem{1993_Sinclair}
%\bibinfo{author}{Sinclair, A.}
%\newblock \emph{\bibinfo{title}{Algorithms for random generation and counting:
%  a Markov chain approach}}, vol.~\bibinfo{volume}{7}
%  (\bibinfo{publisher}{Springer}, \bibinfo{year}{1993}).



%\bibitem{2012_paparo_google}
%\bibinfo{author}{Paparo, G.~D.} \& \bibinfo{author}{Martin-Delgado, M.}
%\newblock \bibinfo{title}{Google in a quantum network}.
%\newblock \emph{\bibinfo{journal}{Scientific reports}}
%  \textbf{\bibinfo{volume}{2}} (\bibinfo{year}{2012}).
%
%\bibitem{2013_paparo_complex}
%\bibinfo{author}{Paparo, G.}, \bibinfo{author}{Mueller, M.},
%  \bibinfo{author}{Comellas, F.} \& \bibinfo{author}{Martin-Delgado, M.}
%\newblock \bibinfo{title}{Quantum google in a complex network}.
%\newblock \emph{\bibinfo{journal}{Scientific reports}}
%  \textbf{\bibinfo{volume}{3}} (\bibinfo{year}{2013}).
%
%\bibitem{1998_Boyer}
%\bibinfo{author}{Boyer, M.}, \bibinfo{author}{Brassard, G.},
%  \bibinfo{author}{Hoeyer, P.} \& \bibinfo{author}{Tapp, A.}
%\newblock \bibinfo{title}{Tight bounds on quantum searching}.
%\newblock \emph{\bibinfo{journal}{Fortsch. Phys.}}
%  \textbf{\bibinfo{volume}{46}}, \bibinfo{pages}{493--506}
%  (\bibinfo{year}{1996}).
%\newblock \eprint{arXiv:quant-ph/9605034}.
%
%\bibitem{2012_Aspuru}
%\bibinfo{author}{Aspuru-Guzik, A.} \& \bibinfo{author}{Walther, P.}
%\newblock \bibinfo{title}{{Photonic quantum simulators}}.
%\newblock \emph{\bibinfo{journal}{Nature Physics}}
%  \textbf{\bibinfo{volume}{8}}, \bibinfo{pages}{285--291}
%  (\bibinfo{year}{2012}).
%\newblock \urlprefix\url{http://dx.doi.org/10.1038/nphys2253}.
%
%\bibitem{2012_Roos}
%\bibinfo{author}{Blatt, R.} \& \bibinfo{author}{Roos, C.~F.}
%\newblock \bibinfo{title}{{Quantum simulations with trapped ions}}.
%\newblock \emph{\bibinfo{journal}{Nature Physics}}
%  \textbf{\bibinfo{volume}{8}}, \bibinfo{pages}{277--283}
%  (\bibinfo{year}{2012}).
%\newblock \urlprefix\url{http://dx.doi.org/10.1038/nphys2252}.
%
%\bibitem{2013_Schaetz}
%\bibinfo{author}{Schaetz, T.}, \bibinfo{author}{Monroe, C.~R.} \&
%  \bibinfo{author}{Esslinger, T.}
%\newblock \bibinfo{title}{Focus on quantum simulation}.
%\newblock \emph{\bibinfo{journal}{New Journal of Physics}}
%  \textbf{\bibinfo{volume}{15}}, \bibinfo{pages}{085009}
%  (\bibinfo{year}{2013}).
%\newblock \urlprefix\url{http://stacks.iop.org/1367-2630/15/i=8/a=085009}.
%
%\bibitem{1996_Wolpert}
%\bibinfo{author}{Wolpert, D.~H.}
%\newblock \bibinfo{title}{The lack of a priori distinctions between learning
%  algorithms}.
%\newblock \emph{\bibinfo{journal}{Neural Comput.}}
%  \textbf{\bibinfo{volume}{8}}, \bibinfo{pages}{1341--1390}
%  (\bibinfo{year}{1996}).
%\newblock \urlprefix\url{http://dx.doi.org/10.1162/neco.1996.8.7.1341}.
%
%\bibitem{1997_Droste}
%\bibinfo{author}{Droste, S.}, \bibinfo{author}{Jansen, T.} \&
%  \bibinfo{author}{Wegener, I.}
%\newblock \bibinfo{title}{Optimization with randomized search heuristics -- the
%  (a)nfl theorem, realistic scenarios, and difficult functions}.
%\newblock \emph{\bibinfo{journal}{Theoretical Computer Science}}
%  \textbf{\bibinfo{volume}{287}}, \bibinfo{pages}{2002} (\bibinfo{year}{1997}).
%
%\bibitem{NFLorg}
%\bibinfo{title}{Introduction to discussions regarding the no free lunch
%  theorems, and their interpretations, can be found at the following web page}.
%\newblock \bibinfo{howpublished}{\url{http://no-free-lunch.org/}}.
%
%\bibitem{1993_Sinclair}
%\bibinfo{author}{Sinclair, A.}
%\newblock \emph{\bibinfo{title}{Algorithms for random generation and counting:
%  a Markov chain approach}}, vol.~\bibinfo{volume}{7}
%  (\bibinfo{publisher}{Springer}, \bibinfo{year}{1993}).
%

  




%\bibitem{Briegel2_2012}
%\bibinfo{author}{Briegel, H.}
%\newblock \bibinfo{title}{{On creative machines and the physical origins of
%  freedom.}}
%\newblock \emph{\bibinfo{journal}{Scientific reports}}
%  \textbf{\bibinfo{volume}{2}}, \bibinfo{pages}{522} (\bibinfo{year}{2012}).
%\newblock \urlprefix\url{http://dx.doi.org/10.1038/srep00522}.
%
%\bibitem{2007_Magniez_SIAM}
%\bibinfo{author}{Magniez, F.}, \bibinfo{author}{Santha, M.} \&
%  \bibinfo{author}{Szegedy, M.}
%\newblock \bibinfo{title}{Quantum algorithms for the triangle problem}.
%\newblock \emph{\bibinfo{journal}{SIAM Journal on Computing}}
%  \textbf{\bibinfo{volume}{37}}, \bibinfo{pages}{413--424}
%  (\bibinfo{year}{2007}).
%\newblock \urlprefix\url{http://epubs.siam.org/doi/abs/10.1137/050643684}.
%
%
%\bibitem{1993_Vazirani}
%\bibinfo{author}{Bernstein, E.} \& \bibinfo{author}{Vazirani, U.}
%\newblock \bibinfo{title}{Quantum complexity theory}.
%\newblock In \emph{\bibinfo{booktitle}{in Proc. 25th Annual ACM Symposium on
%  Theory of Computing, ACM}}, \bibinfo{pages}{11--20} (\bibinfo{year}{1993}).

\end{thebibliography}







%\subsection{Further tweaks}
%\begin{enumerate}
%\item What fidelity threshold can I reach if I use simulated annealing to go from distribution to distribution.
%\item did not write the theorem in full form. What if I let certain things scale logarithmically, rather than have a constant.
%\item can I use probability amplification? I WANT MY ALGORITHM IIIINNNN
%\item Do I actually need to sample from the distribution to get the $k$ good candidates? Suppose I start from a random candidate, and apply a few Grover-iterations. Maybe $k.$ What is the overall weight of the rest of the distribution compared to the element $k$? If that thing is constant, and obeys the distribution correctly (CAREFUL! There are errors, and the overall weight of the rest may be small so error can be relatively big) then sampling from such a distribution, post-selected on not sampling $k$ will follow the same statistics as sampling from the real steady state, postselected on not-$k.$ In log attempts I can sample out the good candidates (actually I think this really will work, it seems to me the worst case number of attempts will be $log{1/\epsilon_k}$) as ensured by Lemma \ref{minlemma}. Now, I will still need the guarantee that the entropy/fidelity between uniform and whateverthehell I have is bounded. But this could eliminate the need for having the distribution to start with.
%\item I really need to generalize Lemma \ref{minlemma}, and see when this thing becomes truly efficient, as in log(k). I doubt I can get it to be a constant. Why would a log appear. A log appears if I iterate crap, and i only need one to succeed. 
%\item One could further improve on the unsearch protocol maybe? What if I start from two elements? Doesn't sound too promising.
%\item What about the fidelity approach? If indeed I only have a problem with worst-case distributions, then starting not from a uniform, but uniform over a half-sized subset, through iteration may lead to a log-search (binary tree search?)
%\item Try to formally show that the general worst case scenario for classical mixing, even if you have the mode, still scales with $O(1/delta)$ - idea: use a symmetric MC - diagonalize - then you see that the powering has nothing to do with the initial state, that becomes only a multiplicative improvement in the error (overlap does.) But error only comes as a log term in it so you get improvement by a constant? Hmm...
%
%\end{enumerate}
%Can I make the preparation efficient in any annealing setting...need to go from fourth root to log.....
%
\end{document}

1503.01334.extracted_bib
{1985_Deutsch %\bibinfo{author{Deutsch, D. %\newblock \bibinfo{title{Quantum theory, the {Church-{Turing principle and % the universal quantum computer. %\newblock \bibinfo{journal{Proceedings of the Royal Society of London % A \bibinfo{volume{400, \bibinfo{pages{97--117 % (\bibinfo{year{1985). %\newblock \urlprefix\url{http://www.qubit.org/oldsite/resource/deutsch85.pdf. % %
1503.01334.extracted_bib
{1992_Deutsch %\bibinfo{author{Deutsch, D. \& \bibinfo{author{Jozsa, R. %\newblock \bibinfo{title{Rapid solution of problems by quantum computation. %\newblock \bibinfo{journal{Proc Roy Soc Lond A % \bibinfo{volume{439, \bibinfo{pages{553--558 % (\bibinfo{year{1992). % %
1503.01334.extracted_bib
{1996_Grover %\bibinfo{author{Grover, L.~K. %\newblock \bibinfo{journal{Proceedings, 28th Annual ACM Symposium on the % Theory of Computing (STOC) \bibinfo{pages{212 (\bibinfo{year{1996). % %
1503.01334.extracted_bib
{1994_Shor %\bibinfo{author{Shor, P.~W. %\newblock \bibinfo{title{Algorithms for quantum computation: discrete % logarithms and factoring. %\newblock In \bibinfo{booktitle{Proceedings of the 35th symposium on % foundations of computer science, FOCS~'94, \bibinfo{pages{124--134 % (\bibinfo{publisher{IEEE, \bibinfo{year{1994). % %
1503.01334.extracted_bib
{2000_NC %\bibinfo{author{Nielsen, M.~A. \& \bibinfo{author{Chuang, I.~L. %\newblock \bibinfo{title{Quantum Computation and Quantum Information % (\bibinfo{publisher{Cambridge University Press, \bibinfo{year{2000). % %
1503.01334.extracted_bib
{2000_Bennet %\bibinfo{author{Charles H.~Bennett, D. P.~D. %\newblock \bibinfo{title{Quantum information and computation. %\newblock \bibinfo{journal{Nature \bibinfo{pages{247?255 % (\bibinfo{year{2000). %\newblock % \urlprefix\url{http://www.nature.com/nature/journal/v404/n6775/full/404247a0.html. % %
1503.01334.extracted_bib
{2002_Sasaki %\bibinfo{author{Sasaki, M. \& \bibinfo{author{Carlini, A. %\newblock \bibinfo{title{Quantum learning and universal quantum matching % machine. %\newblock \bibinfo{journal{Phys. Rev. A \bibinfo{volume{66, % \bibinfo{pages{022303 (\bibinfo{year{2002). %\newblock \urlprefix\url{http://link.aps.org/doi/10.1103/PhysRevA.66.022303. % %
1503.01334.extracted_bib
{2008_Neven %\bibinfo{author{Neven, H., \bibinfo{author{Denchev, V.~S., % \bibinfo{author{Rose, G. \& \bibinfo{author{Macready, W.~G. %\newblock \bibinfo{title{Training a binary classifier with the quantum % adiabatic algorithm (\bibinfo{year{2008). %\newblock \eprint{arXiv/0811.0416. % %
1503.01334.extracted_bib
{2013_Lloyd %\bibinfo{author{Lloyd, S., \bibinfo{author{Mohseni, M. \& % \bibinfo{author{Rebentrost, P. %\newblock \bibinfo{title{Quantum algorithms for supervised and unsupervised % machine learning. %\newblock \bibinfo{journal{ArXiv:1307.0411 (\bibinfo{year{2013). % %
1503.01334.extracted_bib
{2009_Brukner %\bibinfo{author{Manzano, D., \bibinfo{author{Paw{\lowski, M. \& % \bibinfo{author{Brukner, {\v{C. %\newblock \bibinfo{title{The speed of quantum and classical learning for % performing the k th root of not. %\newblock \bibinfo{journal{New Journal of Physics % \bibinfo{volume{11, \bibinfo{pages{113018 % (\bibinfo{year{2009). %\newblock \urlprefix\url{http://stacks.iop.org/1367-2630/11/i=11/a=113018. % %
1503.01334.extracted_bib
{2013_Lidar %\bibinfo{author{Pudenz, K.~L. \& \bibinfo{author{Lidar, D.~A. %\newblock \bibinfo{title{Quantum adiabatic machine learning. %\newblock \bibinfo{journal{Quantum Information Processing % \bibinfo{volume{12, \bibinfo{pages{2027--2070 % (\bibinfo{year{2013). %\newblock \urlprefix\url{http://dx.doi.org/10.1007/s11128-012-0506-4. % %
1503.01334.extracted_bib
{2013_Aimeur %\bibinfo{author{A{\"{imeur, E., \bibinfo{author{Brassard, G. \& % \bibinfo{author{Gambs, S. %\newblock \bibinfo{title{Quantum speed-up for unsupervised learning. %\newblock \bibinfo{journal{Machine Learning % \bibinfo{volume{90, \bibinfo{pages{261--287 % (\bibinfo{year{2013). %\newblock \urlprefix\url{http://dx.doi.org/10.1007/s10994-012-5316-5. % %
1503.01334.extracted_bib
{1986_Braitenberg %\bibinfo{author{Braitenberg, V. %\newblock \bibinfo{title{Vehicles: Experiments in Synthetic Psychology % (\bibinfo{publisher{MIT Press, \bibinfo{address{Cambridge Massachusetts, % \bibinfo{year{1986). % %
1503.01334.extracted_bib
{1999_Brooks %\bibinfo{author{Brooks, R. %\newblock \bibinfo{title{Cambrian intelligence: The early history of the % new AI (\bibinfo{publisher{The MIT Press, \bibinfo{address{Cambridge, % MA, \bibinfo{year{1999). % %
1503.01334.extracted_bib
{1999_Pfeifer %\bibinfo{author{Pfeifer, R. \& \bibinfo{author{Scheier, C. %\newblock \bibinfo{title{Understanding Intelligence % (\bibinfo{publisher{MIT Press, \bibinfo{address{Cambridge, MA, USA, % \bibinfo{year{1999). % %
1503.01334.extracted_bib
{2006_Pfeifer %\bibinfo{author{Pfeifer, R. \& \bibinfo{author{Bongard, J.~C. %\newblock \bibinfo{title{How the Body Shapes the Way We Think: A New % View of Intelligence (Bradford Books) (\bibinfo{publisher{The MIT Press, % \bibinfo{year{2006). % %
1503.01334.extracted_bib
{2008_Floreano %\bibinfo{author{Floreano, D. \& \bibinfo{author{Mattiussi, C. %\newblock \bibinfo{title{Bio-inspired artificial intelligence : % theories, methods, and technologies (\bibinfo{publisher{The MIT Press, % \bibinfo{year{2008). % %
1503.01334.extracted_bib
{2008_Barsalou %\bibinfo{author{Barsalou, L.~W. %\newblock \bibinfo{title{Grounded cognition. %\newblock \bibinfo{journal{Annual Review of Psychology % \bibinfo{volume{59, \bibinfo{pages{617--645 % (\bibinfo{year{2008). % %
1503.01334.extracted_bib
{2003_Russel %\bibinfo{author{Russel, S.~J. \& \bibinfo{author{Norvig, P. %\newblock \bibinfo{title{Artificial intelligence - A modern approach % (\bibinfo{publisher{Prentice Hall, \bibinfo{address{New Jersey, % \bibinfo{year{2003), \bibinfo{edition{second edition edn. % %
1503.01334.extracted_bib
{SuttonBarto98 %\bibinfo{author{Sutton, R.~S. \& \bibinfo{author{Barto, A.~G. %\newblock \bibinfo{title{Reinforcement learning: An introduction % (\bibinfo{publisher{MIT Press, Cambridge Massachusetts, % \bibinfo{year{1998), \bibinfo{edition{first edn. %
1503.01334.extracted_bib
{2003_Kempe_Contemp_Phys \bibinfo{author{Kempe, J. \newblock \bibinfo{title{Quantum random walks - an introductory overview. \newblock \bibinfo{journal{Contemp. Phys. \bibinfo{volume{44(4), \bibinfo{pages{307 (\bibinfo{year{2003).
1503.01334.extracted_bib
{2010_Krovi \bibinfo{author{Krovi, H., \bibinfo{author{Magniez, F., \bibinfo{author{Ozols, M. and \bibinfo{author{Roland, J. \newblock \bibinfo{title{Quantum walks can find a marked element on any graph \newblock \bibinfo{journal{arXiv:1002.2419v2 (\bibinfo{year{2014).
1503.01334.extracted_bib
{2004_Ambainis \bibinfo{author{Ambainis, A. \newblock \bibinfo{title{Quantum walk algorithms for element distinctness. \newblock In \bibinfo{booktitle{45th Annual IEEE Symposium on Foundations of Computer Science, OCT 17-19, 2004. IEEE Computer Society Press, Los Alamitos, CA, \bibinfo{pages{22--31 (\bibinfo{year{2004).
1503.01334.extracted_bib
{2004_Szegedy_IEEE \bibinfo{author{Szegedy, M. \newblock \bibinfo{title{Quantum speed-up of markov chain based algorithms. \newblock In \bibinfo{booktitle{Foundations of Computer Science, 2004. Proceedings. 45th Annual IEEE Symposium on, \bibinfo{pages{32 -- 41 (\bibinfo{year{2004).
1503.01334.extracted_bib
{2005_Magniez \bibinfo{author{Magniez, F., \bibinfo{author{Santha, M. and \bibinfo{author{Szegedy, M. \newblock \bibinfo{title{Quantum Algorithms for the Triangle Problem. \newblock \bibinfo{journal{Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms \bibinfo{series{SODA '05, \bibinfo{pages{1109--1117 (\bibinfo{year{2005).
1503.01334.extracted_bib
{1999_Newman \bibinfo{author{Newman, M. E. J. and \bibinfo{author{Barkema, G. T. \newblock \bibinfo{title{Monte Carlo Methods in Statistical Physics, (\bibinfo{publisher{Oxford University Press, Oxford, UK, \bibinfo{year{1999).
1503.01334.extracted_bib
{2007_Richter \bibinfo{author{Richter, P. C. \newblock \bibinfo{title{ Quantum speedup of classical mixing processes. \newblock \bibinfo{journal{Phys. Rev. A \bibinfo{volume{76, \bibinfo{pages{042306 (\bibinfo{year{2007). \newblock \urlprefix\url{http://journals.aps.org/pra/abstract/10.1103/PhysRevA.76.042306.
1503.01334.extracted_bib
{2007_Richter_NJP \bibinfo{author{Richter, P. C. \newblock \bibinfo{title{Almost uniform sampling via quantum walks. \newblock \bibinfo{journal{New J. Phys. \bibinfo{volume{9, \bibinfo{pages{73 (\bibinfo{year{2007).
1503.01334.extracted_bib
{2011_Temme_Nature \bibinfo{author{Temme, K., \bibinfo{author{Osborne, T.~J., \bibinfo{author{Vollbrecht, K. G.~H., \bibinfo{author{Poulin, D. \& \bibinfo{author{Verstraete, F. \newblock \bibinfo{title{Quantum metropolis sampling \bibinfo{volume{471, \bibinfo{pages{87--90 (\bibinfo{year{2011).
1503.01334.extracted_bib
{2012_Yung \bibinfo{author{Yung, M.-H. \& \bibinfo{author{Aspuru-Guzik, A. \newblock \bibinfo{title{A quantum quantum metropolis algorithm. \newblock \bibinfo{journal{Proceedings of the National Academy of Sciences (\bibinfo{year{2012).
1503.01334.extracted_bib
{2008_Somma_PRL \bibinfo{author{Somma, R.~D., \bibinfo{author{Boixo, S., \bibinfo{author{Barnum, H. \& \bibinfo{author{Knill, E. \newblock \bibinfo{title{Quantum simulations of classical annealing processes. \newblock \bibinfo{journal{Phys. Rev. Lett. \bibinfo{volume{101, \bibinfo{pages{130504 (\bibinfo{year{2008). \newblock \urlprefix\url{http://link.aps.org/doi/10.1103/PhysRevLett.101.130504.
1503.01334.extracted_bib
{2008_Wocjan \bibinfo{author{Wocjan, P. and \bibinfo{author{Abeyesinghe, A. \newblock \bibinfo{title{Speedup via quantum sampling. \newblock \bibinfo{journal{Phys. Rev. A \bibinfo{volume{78, \bibinfo{pages{042336 (\bibinfo{year{2008). \newblock \urlprefix\url{http://link.aps.org/doi/10.1103/PhysRevA.78.042336.
1503.01334.extracted_bib
{2011_Magniez_SIAM \bibinfo{author{Magniez, F., \bibinfo{author{Nayak, A., \bibinfo{author{Roland, J. \& \bibinfo{author{Santha, M. \newblock \bibinfo{title{Search via quantum walk. \newblock \bibinfo{journal{SIAM Journal on Computing \bibinfo{volume{40, \bibinfo{pages{142--164 (\bibinfo{year{2011). \newblock \urlprefix\url{http://epubs.siam.org/doi/abs/10.1137/090745854.
1503.01334.extracted_bib
{2001_Aharonov \bibinfo{author{Aharonov, D., \bibinfo{author{Ambainis, A., \bibinfo{author{Kempe, J. and \bibinfo{author{Vazirani, U. \newblock \bibinfo{title{Quantum walks on graphs. \newblock In \bibinfo{booktitle{Proceedings of the thirty-third annual ACM symposium on Theory of computing, ACM, New York, NY, USA, \bibinfo{pages{50--59 (\bibinfo{year{2001).
1503.01334.extracted_bib
{2000_Nayak \bibinfo{author{Nayak, A. and \bibinfo{author{Vishwanath, A.\newblock \bibinfo{title{Quantum walk on the line \newblock \bibinfo{journal{arXiv:quant-ph/0010117 (\bibinfo{year{2000).
1503.01334.extracted_bib
{2001_Ambainis \bibinfo{author{Ambainis, A., \bibinfo{author{Bach, E., \bibinfo{author{Nayak, A., \bibinfo{author{Vishwanath, A. and \bibinfo{author{Watrous, J. \newblock \bibinfo{title{One-dimensional quantum walks. \newblock In \bibinfo{booktitle{Proceedings of the thirty-third annual ACM symposium on Theory of computing, \bibinfo{pages{37--49 (\bibinfo{year{2001).
1503.01334.extracted_bib
{2002_Moore \bibinfo{author{Moore, C. and \bibinfo{author{Russell, A. \newblock \bibinfo{title{Quantum Walks on the Hypercube. \newblock \bibinfo{journal{Randomization and Approximation Techniques in Computer Science \bibinfo{series{Lecture Notes in Computer Science \bibinfo{volume{2483, \bibinfo{pages{164--178 (\bibinfo{year{2002).
1503.01334.extracted_bib
{2011_Reitzner \bibinfo{author{Reitzner, D., \bibinfo{author{Nagaj, D. and \bibinfo{author{Bu{\v{zek, V. \newblock \bibinfo{title{Quantum Walks. \newblock \bibinfo{journal{Acta Phys. Slovaca \bibinfo{volume{61, \bibinfo{number{6, \bibinfo{pages{603--725 (\bibinfo{year{2011).
1503.01334.extracted_bib
{2009_Wocjan \bibinfo{author{Wocjan, P., \bibinfo{author{Chiang, C., \bibinfo{author{Nagaj, D., and \bibinfo{author{Abeyesinghe, A. \newblock \bibinfo{title{Quantum algorithm for approximating partition functions. \newblock \bibinfo{journal{Phys. Rev. A \bibinfo{volume{80, \bibinfo{pages{022340 (\bibinfo{year{2009).
1503.01334.extracted_bib
{2014_Paparo \bibinfo{author{Paparo, G. D., \bibinfo{author{Dunjko, V., \bibinfo{author{Makmal, A., \bibinfo{author{Matrin-Delgado, MA., \bibinfo{author{Briegel, H. J. \newblock \bibinfo{title{Quantum speedup for active learning agents. \newblock \bibinfo{journal{Phys. Rev. X \bibinfo{volume{4, \bibinfo{pages{031002 (\bibinfo{year{2014). \newblock \urlprefix\url{http://journals.aps.org/prx/abstract/10.1103/PhysRevX.4.031002.
1503.01334.extracted_bib
{2012_Briegel \bibinfo{author{Briegel, H.~J. \& \bibinfo{author{De~las Cuevas, G. \newblock \bibinfo{title{Projective simulation for artificial intelligence. \newblock \bibinfo{journal{Sci. Rep. \bibinfo{volume{2 (\bibinfo{year{2012).
1503.01334.extracted_bib
{Julian12 \bibinfo{author{Mautner, J., \bibinfo{author{Makmal, A., \bibinfo{author{Manzano, D., \bibinfo{author{Tiersch, M. \& \bibinfo{author{Briegel, H.~J. \newblock \bibinfo{title{Projective simulation for classical learning agents: a comprehensive investigation. \bibinfo{journal{New Generat. Comput. (\bibinfo{year{2015). \bibinfo{volume{33, \bibinfo{issue{1, \bibinfo{pages{69--114.
1503.01334.extracted_bib
{1997_Aldous \bibinfo{author{Aldous, D. , \bibinfo{author{L{\'{aszl{\'{o, L and \bibinfo{author{Winkler, P. \newblock \bibinfo{title{Mixing times for uniformly ergodic Markov chains \newblock \bibinfo{journal{Stochastic Processes and their Applications (\bibinfo{year{1995). \bibinfo{volume{2 \bibinfo{pages{165--185
1503.01334.extracted_bib
{1998_Norris \bibinfo{author{Norris, J. R. \newblock \bibinfo{title{Markov chains (\bibinfo{publisher{Cambridge University Press, \bibinfo{year{1998).
1503.01334.extracted_bib
{1996_Kitaev \bibinfo{author{Kitaev, A. Y. \newblock \bibinfo{title{Quantum measurements and the Abelian Stabilizer Problem. \newblock In \bibinfo{booktitle{Electronic Colloquium on Computational Complexity (ECCC) 3, (\bibinfo{year{1996).
1503.01334.extracted_bib
{2000_Brassard \bibinfo{author{Brassard, G., \bibinfo{author{Hoyer, P., \bibinfo{author{Mosca, M. and \bibinfo{author{Tapp, A. \newblock \bibinfo{title{Quantum Amplitude Amplification and Estimation \newblock \bibinfo{journal{arXiv:quant-ph/0005055 (\bibinfo{year{2000).
1503.01334.extracted_bib
{2004_Childs \bibinfo{author{Childs, A. \newblock \bibinfo{title{Quantum information processing in continuous time. \bibinfo{note{Ph. D. Thesis, Massachusetts Institute of Technology, (2004).
1503.01334.extracted_bib
{2015_Dunjko2 \bibinfo{author{Dunjko, V. and \bibinfo{author{Briegel, H. J. \newblock \bibinfo{title{Quantum mixing of Markov chains for special distributions. \newblock \bibinfo{note{Preprint: arXiv:1502.05511
1503.01334.extracted_bib
{1998_Boyer \bibinfo{author{Boyer, M., \bibinfo{author{Brassard, G., \bibinfo{author{H{\oyer, P. and \bibinfo{author{Tapp, A. \newblock \bibinfo{title{Tight Bounds on Quantum Searching \newblock \bibinfo{journal{Fortschritte der Physik \bibinfo{volume{46, \bibinfo{pages{493--505(\bibinfo{year{1998). %
1503.01334.extracted_bib
{1995_Kohonen %\bibinfo{author{Kohonen, T. %\newblock \bibinfo{title{Self-organizing maps % (\bibinfo{publisher{Springer-Verlag, \bibinfo{year{1995). % %
1503.01334.extracted_bib
{2006_Toussaint %\bibinfo{author{Toussaint, M. %\newblock \bibinfo{title{A sensorimotor map: Modulating lateral interactions % for anticipation and planning. %\newblock \bibinfo{journal{Neural Comput. % \bibinfo{volume{18, \bibinfo{pages{1132--1155 % (\bibinfo{year{2006). %\newblock \urlprefix\url{http://dx.doi.org/10.1162/089976606776240995. % %
1503.01334.extracted_bib
{2005_Magniez %\bibinfo{author{Magniez, F., \bibinfo{author{Santha, M. \& % \bibinfo{author{Szegedy, M. %\newblock \bibinfo{title{Quantum algorithms for the triangle problem. %\newblock In \bibinfo{booktitle{Proceedings of the Sixteenth Annual % ACM-SIAM Symposium on Discrete Algorithms, SODA '05, % \bibinfo{pages{1109--1117 (\bibinfo{publisher{Society for Industrial and % Applied Mathematics, \bibinfo{address{Philadelphia, PA, USA, % \bibinfo{year{2005). %\newblock \urlprefix\url{http://dl.acm.org/citation.cfm?id=1070432.1070591. % % %
1503.01334.extracted_bib
{2012_Magniez_Algorithmica %\bibinfo{author{Magniez, F., \bibinfo{author{Nayak, A., % \bibinfo{author{Richter, P.~C. \& \bibinfo{author{Santha, M. %\newblock \bibinfo{title{On the hitting times of quantum versus random walks. %\newblock \bibinfo{journal{Algorithmica \bibinfo{volume{63, % \bibinfo{pages{91--116 (\bibinfo{year{2012). %\newblock \urlprefix\url{http://dx.doi.org/10.1007/s00453-011-9521-6. % %
1503.01334.extracted_bib
{1993_Sinclair %\bibinfo{author{Sinclair, A. %\newblock \bibinfo{title{Algorithms for random generation and counting: % a Markov chain approach, vol.~\bibinfo{volume{7 % (\bibinfo{publisher{Springer, \bibinfo{year{1993). %
1503.01334.extracted_bib
{2012_paparo_google %\bibinfo{author{Paparo, G.~D. \& \bibinfo{author{Martin-Delgado, M. %\newblock \bibinfo{title{Google in a quantum network. %\newblock \bibinfo{journal{Scientific reports % \bibinfo{volume{2 (\bibinfo{year{2012). % %
1503.01334.extracted_bib
{2013_paparo_complex %\bibinfo{author{Paparo, G., \bibinfo{author{Mueller, M., % \bibinfo{author{Comellas, F. \& \bibinfo{author{Martin-Delgado, M. %\newblock \bibinfo{title{Quantum google in a complex network. %\newblock \bibinfo{journal{Scientific reports % \bibinfo{volume{3 (\bibinfo{year{2013). % %
1503.01334.extracted_bib
{1998_Boyer %\bibinfo{author{Boyer, M., \bibinfo{author{Brassard, G., % \bibinfo{author{Hoeyer, P. \& \bibinfo{author{Tapp, A. %\newblock \bibinfo{title{Tight bounds on quantum searching. %\newblock \bibinfo{journal{Fortsch. Phys. % \bibinfo{volume{46, \bibinfo{pages{493--506 % (\bibinfo{year{1996). %\newblock \eprint{arXiv:quant-ph/9605034. % %
1503.01334.extracted_bib
{2012_Aspuru %\bibinfo{author{Aspuru-Guzik, A. \& \bibinfo{author{Walther, P. %\newblock \bibinfo{title{{Photonic quantum simulators. %\newblock \bibinfo{journal{Nature Physics % \bibinfo{volume{8, \bibinfo{pages{285--291 % (\bibinfo{year{2012). %\newblock \urlprefix\url{http://dx.doi.org/10.1038/nphys2253. % %
1503.01334.extracted_bib
{2012_Roos %\bibinfo{author{Blatt, R. \& \bibinfo{author{Roos, C.~F. %\newblock \bibinfo{title{{Quantum simulations with trapped ions. %\newblock \bibinfo{journal{Nature Physics % \bibinfo{volume{8, \bibinfo{pages{277--283 % (\bibinfo{year{2012). %\newblock \urlprefix\url{http://dx.doi.org/10.1038/nphys2252. % %
1503.01334.extracted_bib
{2013_Schaetz %\bibinfo{author{Schaetz, T., \bibinfo{author{Monroe, C.~R. \& % \bibinfo{author{Esslinger, T. %\newblock \bibinfo{title{Focus on quantum simulation. %\newblock \bibinfo{journal{New Journal of Physics % \bibinfo{volume{15, \bibinfo{pages{085009 % (\bibinfo{year{2013). %\newblock \urlprefix\url{http://stacks.iop.org/1367-2630/15/i=8/a=085009. % %
1503.01334.extracted_bib
{1996_Wolpert %\bibinfo{author{Wolpert, D.~H. %\newblock \bibinfo{title{The lack of a priori distinctions between learning % algorithms. %\newblock \bibinfo{journal{Neural Comput. % \bibinfo{volume{8, \bibinfo{pages{1341--1390 % (\bibinfo{year{1996). %\newblock \urlprefix\url{http://dx.doi.org/10.1162/neco.1996.8.7.1341. % %
1503.01334.extracted_bib
{1997_Droste %\bibinfo{author{Droste, S., \bibinfo{author{Jansen, T. \& % \bibinfo{author{Wegener, I. %\newblock \bibinfo{title{Optimization with randomized search heuristics -- the % (a)nfl theorem, realistic scenarios, and difficult functions. %\newblock \bibinfo{journal{Theoretical Computer Science % \bibinfo{volume{287, \bibinfo{pages{2002 (\bibinfo{year{1997). % %
1503.01334.extracted_bib
{NFLorg %\bibinfo{title{Introduction to discussions regarding the no free lunch % theorems, and their interpretations, can be found at the following web page. %\newblock \bibinfo{howpublished{\url{http://no-free-lunch.org/. % %
1503.01334.extracted_bib
{1993_Sinclair %\bibinfo{author{Sinclair, A. %\newblock \bibinfo{title{Algorithms for random generation and counting: % a Markov chain approach, vol.~\bibinfo{volume{7 % (\bibinfo{publisher{Springer, \bibinfo{year{1993). % %
1503.01334.extracted_bib
{Briegel2_2012 %\bibinfo{author{Briegel, H. %\newblock \bibinfo{title{{On creative machines and the physical origins of % freedom. %\newblock \bibinfo{journal{Scientific reports % \bibinfo{volume{2, \bibinfo{pages{522 (\bibinfo{year{2012). %\newblock \urlprefix\url{http://dx.doi.org/10.1038/srep00522. % %
1503.01334.extracted_bib
{2007_Magniez_SIAM %\bibinfo{author{Magniez, F., \bibinfo{author{Santha, M. \& % \bibinfo{author{Szegedy, M. %\newblock \bibinfo{title{Quantum algorithms for the triangle problem. %\newblock \bibinfo{journal{SIAM Journal on Computing % \bibinfo{volume{37, \bibinfo{pages{413--424 % (\bibinfo{year{2007). %\newblock \urlprefix\url{http://epubs.siam.org/doi/abs/10.1137/050643684. % % %
1503.01334.extracted_bib
{1993_Vazirani %\bibinfo{author{Bernstein, E. \& \bibinfo{author{Vazirani, U. %\newblock \bibinfo{title{Quantum complexity theory. %\newblock In \bibinfo{booktitle{in Proc. 25th Annual ACM Symposium on % Theory of Computing, ACM, \bibinfo{pages{11--20 (\bibinfo{year{1993).