text:
\section{Introduction}

 How long it takes a lion to find its prey,
a particle to reach a domain or
an electric signal to cross a certain threshold?
These are all examples of the first passage time problem
\cite{Redner,Hughes,MOR,Benichou}.
A century ago Schr\"odinger showed  that a Brownian
particle in one dimension, i.e. the continuous  limit of
the classical random walk,  starting at $x_0$, will eventually reach
$x=0$,
with, however, a probability density function (PDF) of the first arrival
time that is fat tailed, in such a way that the mean first passage time diverges
\cite{Schro}.
Ever since, the
 classical first passage time has been a well studied field of research.
 More recently,
much work has been devoted to the analysis of  quantum walks  \cite{Aharonov1,Dorit,Ambainis,Childs,Konno}
(see  \cite{Blumen} for a review).
These exhibit interference patterns and ballistic scaling and in that
sense exhibit behaviors drastically different from the classical random
walk. While several variants of quantum walks exist \cite{Blumen},
 for example discrete time
walks, coin tossing walks, and tight-binding models,
one line of inquiry addresses a question generally
applicable to all these cases, namely
the statistics of first passage or detection times of a quantum particle
(to be defined precisely below).
Quantum walk search algorithms which are
supposed to perform better than classical walk search methods vitalized
this line of research in recent years.
A physical  example might be the statistics
of the time it takes a single electron, ion or atom
to reach a detection
device.
This question, which at first sight appears well-defined and physically
meaningful, has nevertheless been the subject of much controversy.
The Schr\"odinger Eqn. and the standard
postulates of quantum mechanics \cite{CT} do not give a ready-made
recipe for calculating these statistics.
There is no textbook  quantum
operators or wave function associated with the first passage time
measurements
(see \cite{Hauge,Muga,PHD}
for related historical accounts). Actually, time is a  non-quantum ingredient
of quantum mechanics and is treated as a object detached from
the probabilistic interpretation inherent to non-classical reality.
 From the non-deterministic nature of quantum mechanics,
we may expect that the time it takes a single particle
to reach a detection point or domain for a given
Hamiltonian and initial condition should be random
even in the absence of external noise,
 but how to precisely obtain
 the distribution of first detection times has remained in our opinion
 a controversial
matter.

The key to the solution  is that
 we must take into consideration the measurement process
\cite{Bach,Brun06,Brun07,Brun08,Dhar,Dhar1}.
For example consider a zebra sitting at the origin waiting for a lion
to arrive for the first and, unfortunately for her, the last time.
At some rate,  the zebra
records: did the lion arrive or did it not?
 The outcome is a string of answers:
e.g. no, no, no, .... and finally yes.
 If the lion is a quantum particle, then continuous attempts to detect it
by the zebra will maintain
the zebra's life, since the wave function of the lion is collapsed
in the vicinity of the zebra;
this is the famous  quantum Zeno effect \cite{Misra}
 (see more details below).
 On the other hand, if the
zebra samples the arrival of the lion at a finite constant rate,
its likelihood of death is much higher.
 In this sense the measurement of the time of  first detection,
which implies a
set of null
measurements for times prior to the final positive recording
is very different than  the familiar measurements of canonical variables
like position and momentum. There the system is prepared at time $t=0$ in
some initial state, it evolves free of measurement until time
$t$, at which point an instantaneous recording of some observable is made.
Furthermore, we must distinguish between first arrival or first
passage  problems \cite{Muga}
and first detection at a site.
Note that even classically the first detection does not imply
that the particle arrived at the site for the first time at the moment of
detection if the sampling is not continuous in time.
More importantly,   arrival
times are ill-defined in quantum problems \cite{Aharonov},  because we
cannot have a complete record of the trajectory of a quantum particle,
 whereas  the first detection problem under repeated
stroboscopic measurements is a well-defined problem,  and that is  what we treat in this manuscript.

 Here we investigate the first detection problem of quantum walks
following  Dhar et al. \cite{Dhar,Dhar1} who formulated the problem as a tight-binding
quantum walk, with projective local measurements every $\tau$
units of time (see also \cite{Brun06}).
 Specifically, we consider
a particle on a discrete graph, the  quantum evolution determined by the time
independent Hamiltonian $H$. Initially the particle is localized
so the state function is $|\psi \rangle=|x \rangle$ (some of our general results
are not limited to this initial condition, see below).
 Detection
attempts are performed locally at a site we call the origin which is
denoted with $|0\rangle$. Measurements on the origin are stroboscopic with the sampling time
$\tau$, and as mentioned the measurement stops once the particle
is detected after $n$ attempts, so $n \tau$ is the  random
first detection time. We investigate
the statistics of the random observable  $n$.
The questions are: is  the particle eventually detected?
what is the probability of detection after $n$ attempts?
what is the  average of number of attempts of detection before a successful measurement?
This we investigate both for closed systems and open ones.
 Below we present a physical derivation of the quantum  renewal equation describing
the probability amplitude of first detection for
the transition $|x \rangle\to |0 \rangle$. In classical stochastic theories
this corresponds to Schr\"odinger's  renewal equation \cite{Schro}
for the first  time  a particle
starting on $x$ reaches  $0$ (see details below).
We show
how the solution of Schr\"odinger's wave equation free of measurement
can be used to predict the quantum  statistics of the first detection time.
 Previously Gr\"unbaum et al. \cite{Grunbaum} considered the case where the starting
point is also the detection site $|x\rangle = |0\rangle$.
A topological interpretation of  the detection
process was provided for that initial condition and among other things they showed that
the expected time of first detection is an integer times $\tau$ or infinity.
This integer is the winding number of the so called Schur function of
the underlying scalar measure, the latter is determined by the initial state and
the unitary dynamics. Hence the expectation of the first detection time is
quantized \cite{Sinkovicz}.
 A vastly different behavior is found when we analyse the transition $|x \rangle \to |0 \rangle$ for
$x\ne 0$ \cite{Dhar1,Brun06}. The average of $n$  is not an integer, neither is detection finally
guaranteed.
 As demonstrated below for a ring geometry half dark states are observed in some cases
while in others the average of $n$  exhibits divergences and non-analytical behaviours,
for certain critical sampling times. Finally, we show that critical sampling,
including slowing down is found even for an infinite system.
Namely, for the quantum walk on the line,
the first detection probability decays like a power law, with additional
oscillations, where the amplitude of decay is not a continuous function of the sampling rate.
 Thus rich physical behaviors are found for the quantum
first detection problem, if compared with the known results of the classical
random walker.

The spatial  quantum first detection problem is a timely
subject.  Current
day experiments on quantum walks can be used to study these problems
in the laboratory \cite{Yaron,QWe2,QWe1,QWe,Xue}. First passage time
statistics in the classical domain
 are usually recorded  based on single particle analysis.
 Namely, one takes, say, a Brownian
particle, releases it from a certain position and then detects its time of arrival at
some other location.
This single particle experiment is repeated many times and then a
histogram of the first passage time is reported. While in principle one
could release simultaneously many particles from the same position,
 their mutual interaction will influence the statistics of first arrival
and similarly statistics of identical particles, either bosons or fermions,
 alter
the many particle statistics compared to the single particle case.
Hence, measurement
should be made on single particles, or in other words  at least classically
the first detection
time is a property of the single particle path and hence its history.
 The recent  advance
of single particle quantum tracking and measurement,
for systems where coherence is maintained for relatively long times,
is clearly a reason
to be optimistic with respect to possible first detection  measurements.
 Such measurements could test our predictions as well as those
of
a variety of
other theoretical approaches
\cite{Muga,Aharonov,Lumpkin,Grot,Stefanak,Shikano,Krap,Ranjith,Das,Miquel},
 some of which are compared with our results
towards the end of this manuscript.

The navigation map of this  manuscript is as follows.
We  start with the presentation of the  quantum walk model and
the measurement process in  Sec. \ref{secModel}.
In Sec. \ref{secFDA} the first detection wave function formalism
 is developed.
The main tool for actual solution of the problem is
based on the  generating function formalism
given in  Sec. \ref{secGF}
and in subsection
\ref{secRENEWAL}
the quantum renewal equation is discussed.
Sec. \ref{secRings} presents the example of first detection on rings,
with special emphasis on the peculiar statistics
found on a benzene-like ring.
In Sec. \ref{secFD} we obtain statistics of first detection times,
for a one-dimensional  quantum walk on an infinite lattice.
We end with further discussion of previous results (Sec.
\ref{secOTHER})
 and a summary.
A short account of part of our main results was recently published
\cite{FKB}.

\section{Model and Basic Formalism}
\label{secModel}

 We consider a particle whose evolution is described by a time independent
Hermitian Hamiltonian $H$ according to the Schr\"odinger Eqn.
$ i \hbar | \dot{\psi}\rangle = H \left| \psi\right\rangle$.
The initial condition is denoted  $|\psi(0)\rangle$.
 For simplicity, we consider a discrete $x$-space.
 As an  example we shall later consider the tight binding model
\begin{equation}
H = - \gamma \sum_{x=-\infty}^{\infty} \left(|x\rangle \langle x+1 | +
|x+1  \rangle \langle x| \right)
\label{eq01aa}
\end{equation}
on a lattice, though our general results are not limited to
a specific Hamiltonian.
 We denote a subset of lattice points $X$,
and loosely speaking we are interested in
 the statistics of first passage times from the
initial state to any site $x\in X$ in the subset. More generally, $X$ could be any subset of orthogonal states.
An example  is when $X$
consists of  a single lattice point, say $x=0$ and initially the
particle is localized at some other lattice
point $|\psi(0)\rangle = |x'\rangle$. We then investigate the
distribution of the first detection times. For that we must define the
measurement process following \cite{Dhar,Bach,Ambainis}.

Measurements on the subset $X$ are made at discrete times
$\tau,2 \tau, \cdots, n \tau \cdots$ and hence
clearly the first  recorded detection
time is either $t_f =\tau$ or $2 \tau$ etc.
The measurement provides two possible outcomes:
either the particle is in $x \in X$ or it is not.
Consider the first
measurement at time $\tau$. At time $\tau^{-}= \tau - \epsilon$ with
$\epsilon \to 0$ being positive, the wave function is
\begin{equation}
|\psi(\tau^{-}) \rangle = U(\tau) |\psi(0)\rangle
\label{eq01abc}
\end{equation}
and $U(\tau)= \exp( - i H \tau /\hbar)$ as usual. In what follows,
we set $\hbar=1$.
 The probability of finding the
particle in $x\in X$ is, according to the standard interpretation,
\begin{equation}
P_1 = \sum_{x \in X} |\langle x | \psi(\tau^{-})\rangle|^2 .
\label{eq02}
\end{equation}
If the outcome of the measurement is positive, namely the particle is found in $x \in X$,
the first detection time is $t_f=\tau$. On the other hand, if the  particle
is not detected, which occurs with probability $1-P_1$,
 the evolution of the quantum state will
resume. According to collapse theory, following the measurement
 the particle's wave function in $x\in X$ is zero. Namely, a null
measurement alters the wave function in such a way
that  the probability of detecting the
particle in $x \in X$ at time $\tau + \epsilon$ vanishes.
In this sense we are considering projective measurements whose  duration
is very short, while between the measurements the evolution is according to
the  Schr\"odinger Eqn. Mathematically the measurement is a projection \cite{CT},
so that at time $\tau^{+} = \tau + \epsilon$ we have
\begin{equation}
| \psi(\tau^{+}) \rangle = N \left( \mathbb{1} - \sum_{x \in X} | x \rangle \langle x |\right)| \psi(\tau^{-}) \rangle,
\label{eq03}
\end{equation}
where $\mathbb{1}$ is the identity operator,
and the constant $N$ is determined from the normalization condition.
Here we have used the assumption of a perfect projective measurement
that does not alter  either the relative phases
or  magnitudes of the wave
function not interacting with the measurement device, i.e.,
outside the observation domain the wave function is left unchanged beyond a global renormalization.
This is the fifth postulate of quantum mechanics \cite{CT},
though clearly it should be the subject to
continuing  experimental tests.
Since just prior to
measurement the probability
of finding the particle in $x$ not belonging to $X$ is $1-P_1$
we get
\begin{equation}
\begin{array}{c}
| \psi(\tau^{+}) \rangle =
{ \mathbb{1} - \sum_{x \in X} |x \rangle \langle x| \over \sqrt{ 1 - P_1}} |\psi(\tau^{-} \rangle = \\
\\
{ \mathbb{ 1} - \sum_{x \in X} |x\rangle \langle x | \over \sqrt{1 - P_1}} U(\tau) |\psi(0)\rangle.
\end{array}
\label{eq04}
\end{equation}
In sum, the measurement nullifies the wave functions on $x\in X$
but maintains the relative amplitudes of finding the particles outside
the spatial domain of measurement device,  modifying only the normalization.

 We now proceed in the same way to the second measurement. Between the
first and second detection attempts we have
$ | \psi(2 \tau^{-}) \rangle = U(\tau) |\psi(\tau^{+})\rangle$.
The probability of finding the particle
 in $x \in X$ at the second measurement,
conditioned  on the quantum walker not having been
 found in the first attempt is
\begin{equation}
P_2= \sum_{x \in X} | \underbrace{\langle x}_{\text{Projection}} | \underbrace{U(\tau)}_{\text{Evolution \ \ }} \underbrace{| \psi(\tau^{+})\rangle}_{\text{  Null\ X \  state} } |^2.
\label{eq05}
\end{equation}
We define the projection operator
\begin{equation}
\hat{D} = \sum_{x \in X} | x \rangle \langle x |
\label{eq06}
\end{equation}
and using Eqs. (\ref{eq04},\ref{eq05})
\begin{equation}
P_2 = { \sum_{x \in X} | \langle x | U(\tau)(1-\hat{D}) U(\tau)|\psi(0)\rangle|^2 \over 1- P_1}.
\label{eq07}
\end{equation}
\begin{widetext}
This iteration procedure  is continued to find the
probability of first  detection in the $n$-th measurement, conditioned on
prior measurements  not having detected the particle
\begin{equation}
P_n = \sum_{x \in X} { | \langle x | \left[U(\tau) (1 - \hat{D} )\right]^{n-1} U(\tau) | \psi(0)\rangle|^2 \over (1 - P_1 ) .... (1- P_{n-1}) }.
\label{eq08}
\end{equation}
\end{widetext}
In the numerator the operator  $1 - \hat{D}$ appears  $n-1$ times
corresponding to the $n-1$ prior measurements. Similarly, in the
denominator we find
$n-1$ probabilities of null measurements $1-P_j$.
Following \cite{Dhar,Dhar1} we define the first detection wave function
\begin{equation}
|\theta_n \rangle = U(\tau) \left[ \left( 1 - \hat{D} \right) U\left( \tau \right) \right]^{n-1} |\psi(0)\rangle
\label{eq09}
\end{equation}
or equivalently
$|\theta_n \rangle=[U(\tau)(1-\hat{D})]^{n-1}|\theta_1\rangle$
with the initial condition
$|\theta_1\rangle = U(\tau)| \psi(0)\rangle$.
The bra $|\theta_n\rangle$ is defined only for the moments of detection
$n=1,2,\cdots$,
unlike $|\psi(t)\rangle$ which is a function of continuous time.
With this definition
\begin{equation}
P_n = { \langle \theta_n| \hat{D} | \theta_n \rangle \over \Pi_{j=1} ^{n-1} (1 - P_i) } .
\label{eq10}
\end{equation}

The main focus of this work is on the probability of first detection
in the  $n$-th measurement, denoted $F_n$. This is of course not the same as
$P_n$ which as mentioned is a conditional probability, namely the
 probability of detection on
 the $n$-th attempt given no previous detection.
The conceptual measurement  process  for the calculation
of $F_n$ is as follows. We start with an initial spatial wave function
$|\psi(0)\rangle$ and evolve it until time $\tau$ when the
detection of the particle in $x\in X$ is attempted, and  with probability
$P_1$ the first measurement is also the first detection. Hence to simulate this process  on a
computer we toss a coin using an uniform random number generator and if
the particle is detected the measurement time is $\tau$.
 If the particle
is not detected we compute $P_2$.
Then at time $2 \tau$  either the particle is
detected with probability $P_2$
 or not.
This process is repeated  until a measurement is recorded (see remark below)
 and that
measurement constitutes the random  first detection event.
 In order to gain statistics of the first detection time we
return to the initial step and restart the process with the
same initial condition.
In this way, repeating this many times,
 we construct the
first detection probability
\begin{equation}
F_n = (1-P_1)(1-P_2)... (1 - P_{n-1}) P_n .
\label{eq11}
\end{equation}
Using Eq. (\ref{eq10}) we obtain
\begin{equation}
F_n = \langle \theta_n | \hat{D} | \theta_n \rangle .
\label{eq12}
\end{equation}
We see that the first detection probability $F_n$ is the expectation value
of the projection  operator $\hat{D}$
with respect to
$|\theta_n\rangle$, which we term
 the first detection wave function.

{\bf Remark.} We shall see that not all sequences of
measurements, generated on a computer or in the lab,
 yield a detection  in the long-time limit.
This is not problematic since also
classical random walks in say three dimensions are not recurrent and hence
the total
probability of detection is not necessarily  unity.
In many works one defines the survival probability, i.e.,
 the probability that
the particle is not detected
in the first $n$ attempts,
\begin{equation}
S_n = 1- \sum_{n=1}^n F_n.
\label{eqSur}
\end{equation}
 The eventual  survival probability
$S_\infty$
can be equal zero or not. If the initial condition and the detection location
are identical and $S_\infty=0$ the quantum walk is called recurrent.
We will later investigate whether or not the
quantum walk is recurrent, both  for the cases of an infinite lattice and
a finite ring.

\section{First detection amplitude}
\label{secFDA}

In this section, we solve the first detection time problem
 for quantum dynamics
with a single detection site, which we label $x=0$, so
$\hat{D} = | 0 \rangle \langle 0|$.
 We define the amplitude of the first detection
as
\begin{equation}
\phi_n= \langle 0| \theta_n \rangle
\label{eq13}
\end{equation}
so that $F_n = |\phi_n|^2$.
Using Eq. (\ref{eq09})  $\phi_1= \langle 0| U(\tau) | \psi(0)\rangle$,
$\phi_2= \langle 0 | U( 2 \tau)|\psi(0)\rangle - \phi_1 \langle 0 | U(\tau) | 0\rangle$ and a short calculation yields
\begin{equation}
\phi_3 = \langle 0| U(3 \tau) | \psi(0)\rangle -\phi_1 \langle 0| U(2 \tau) |0\rangle  - \phi_2 \langle 0| U(\tau)|0\rangle.
\label{eq14}
\end{equation}
In Appendix \ref{AppITGM}, using induction we find our first main equation
\begin{equation}
\phi_n = \langle 0 | U(n \tau) | \psi(0)\rangle -
\sum_{j=1} ^{n-1} \phi_j \langle 0 | U\left[\left(n-j\right) \tau\right] | 0 \rangle.
\label{eq15}
\end{equation}
We call this iteration rule
 the quantum renewal equation.
It yields the amplitude $\phi_n$ in terms
of a propagation free of measurement; i.e.,
$ \langle 0 | U(n \tau) | \psi(0)\rangle $ is the amplitude for being at
 the origin at time $n \tau$ in the absence of measurements, from which we
subtract $n-1$ terms related to the previous history of the system.
The physical interpretation of Eq. (\ref{eq15})
 is
that the condition of non-detection in previous measurements translates into
subtracting  wave sources (hence the minus sign)
 at the detection site $|0\rangle$ following the $j$th detection attempt.
This is due to the nullification of the wave function at the
 detection site
in the $j$th  measurement.
 The evolution of that wave source from the $j$th
measurement onward  is described by the free Hamiltonian, hence
$\langle 0| U[(n-j)\tau]|0\rangle$ which gives the amplitude of return back
to the origin, in the time interval $(j \tau,n \tau)$.

We now consider the formal solution to the first detection problem for
an initial condition on the origin hence $|\psi(0)\rangle=|0\rangle$
and
as mentioned the origin is also the point at which we perform the detection trials.
Clearly in this case $\phi_1=\langle 0|U(\tau)|0\rangle$ and since
$U(0)=\mathbb{1}$ we get $\phi_1=1$ when $\tau \rightarrow 0$ which is
expected. For $\phi_2= \langle 0|U(2)|0\rangle - \langle 0|U(1)0\rangle^2$
where we use the short-hand notation
$U(n)\equiv U(n \tau)$.
Similarly
$\phi_3=\langle 0| U(3)   |0\rangle
-2\langle 0| U(2) |0\rangle \langle 0| U(1) |0\rangle +
\langle 0| U(1)   |0\rangle^3$.
 The general solution is obtained by iteration
using Eq.
(\ref{eq15}),
\begin{equation}
\phi_n = \sum_{i=1} ^n \sum_{\{m_1,\cdots,m_i\}} (-1)^{i+1} \langle 0| U(m_1)|0\rangle \cdots \langle 0| U(m_i) |0 \rangle.
\label{eq16}
\end{equation}
The double  sum is over all partitions of $n$, i.e. all
 $i$-tuples of positive integers
$\{m_1, ....m_i\}$
satisfying $m_1+\cdots+m_i=n$. For example for $n=5$ we have five
partitions
corresponding to $i=1, \cdots, 5$, for $i=1$ the set in the second sum is
 $\{ 5 \}$, for $i=2$ we sum over $\{2,3\},\{3,2\},\{1,4\}$ and $\{4,1\}$,
for $i=3$ we use  $\{1,1,3\},\{1,3,1\},\{3,1,1\},\{2,2,1\},\{2,1,2\},\{1,2,2\}$,
for $i=4$,  $\{1,1,1,2\},\{1,1,2,1\},\{1,2,1,1\},\{2,1,1,1\}$
and for $i=5$ we have one term $\{1,1,1,1,1\}$.
Hence
\begin{equation}
\begin{array}{l}
\phi_5 = \langle 0|U(5)|0\rangle- 2 \langle 0 | U(4) | 0\rangle\langle 0|U(1) |0\rangle+ \\
3 \langle 0|U(1)|0\rangle^2 \langle 0 |U(3) |0\rangle-
4 \langle 0|U(1) |0\rangle^3 \langle 0|U(2)|0\rangle +\\
3 \langle 0 | U(2) | 0\rangle^2 \langle 0| U(1) | 0 \rangle-
2 \langle 0 | U(3)| 0  \rangle \langle 0 | U(2) | 0 \rangle +\\
\langle 0 | U(1) | 0\rangle^5.
\end{array}
\label{eq17}
\end{equation}
With a
symbolic  program
like Mathematica one can obtain similar  exact expressions for intermediate
values of $n$. However, to gain some insight
 we
turn now to the generating function approach \cite{Brown}.

\section{Generating function Approach}
\label{secGF}

The $Z$ transform,  or discrete Laplace transform,
of $\phi_n$ is by definition \cite{Brown,remark1}
\begin{equation}
\hat{\phi}(z) = \sum_{n=1}^\infty z^n  \phi_n.
\label{eq18}
\end{equation}
$\hat{\phi}(z)$ is also called the generating function.
Multiplying  Eq. (\ref{eq15}) by $z^n$ and summing over $n$
\begin{multline}
\hat{\phi}(z) = \sum_{n=1}^\infty \langle 0 | z^n U(n) |\psi(0)\rangle - \\
\sum_{n=1} ^\infty \sum_{j=1}^{n-1} \phi_j z^j \langle 0| z^{n-j} U(n-j)|0\rangle.
\label{eq19}
\end{multline}
Evaluating  the first term on the right hand side we get
\begin{equation}
\hat{U}(z) = \sum_{n=1} ^\infty z^n U(n) = \sum_{n=1} ^\infty \exp( - i H \tau n) z^n={ z e^{ - i H \tau } \over 1 - z e^{ - i H \tau}}.
\label{eq20}
\end{equation}
The second term in Eq. (\ref{eq19}) is a convolution term and after
rearrangement we find one of our main results \cite{remark1}
\begin{equation}
\hat{\phi}(z) = { \langle 0 | \hat{U}(z) | \psi(0)\rangle \over 1 + \langle 0 | \hat{U}(z) |0 \rangle}
\label{eq21}
\end{equation}
or more explicitly
\begin{equation}
\hat{\phi}(z) =  {\langle 0| { 1  \over z^{-1}e^{i H \tau} - 1}  | \psi(0)\rangle \over 1  + \langle 0 | {1  \over z^{-1} e^{i H \tau}  - 1} | 0 \rangle}.
\label{eq22}
\end{equation}
This equation, relates  the generating function $\hat{\phi}(z)$ to
the Hamiltonian
evolution between the initial condition and the detection attempt.

This approach is also valid for
other types of  measurements, repeatedly performed at times
 $\tau,2 \tau, \cdots$.
For example the case where we  measure a set of points $x \in X$ is
given in Eq.
(\ref{eq:general_z_transform})
in  Appendix
\ref{AppITGM}.
 First detection  measurements
of general observables is also treated there.

\subsubsection{Relations between $\hat{\phi}(z)$ and
$\phi_n$, $S_\infty$ and  $\langle n \rangle$.}

As usual the amplitudes $\phi_n$ are given in terms of their
$Z$-transforms by the inversion formula
\begin{equation}
\phi_n = { 1 \over  n !} { d^n \over d z^n} \hat{\phi}(z)|_{z=0}
\label{eq22pn}
\end{equation}
or
\begin{equation}
\phi_n = { 1 \over 2 \pi i} \oint_C \hat{\phi}(z) z^{ - n -1} {\rm d} z
\label{eq23}
\end{equation}
where $C$ is a counter clockwise path that contains the origin and is
entirely within the radius of convergence of $\hat{\phi}(z)$.

The probability of being measured
is also related to the generating function $\hat{\phi}(z)$ by
$$ 1-S_\infty=  \sum_{n=1} ^\infty F_n = \sum_{n=1} ^\infty |\phi_n|^2 = $$
\begin{equation}
{1 \over 2 \pi} \int_0 ^{2 \pi} \sum_{k=1} ^\infty \phi_k  e^{ i \theta k}
\sum_{l=1} ^\infty  \phi_l ^{*}  e^{ - i \theta l} {\rm d} \theta=
{1\over 2 \pi} \int_0 ^{2 \pi} |\hat{\phi}(e^{i \theta})|^2 {\rm d} \theta.
\label{eqTot}
\end{equation}
Similarly
\begin{equation}
\langle n \rangle = \sum_{n=1} ^\infty n F_n =
{1 \over 2 \pi} \int_0 ^{2 \pi} \left[\hat{\phi}\left(e^{i \theta}\right)\right]^{*}
\left(- i {\partial \over \partial \theta} \right)\hat{\phi}(e^{i \theta}) {\rm d} \theta.
\label{eqAve}
\end{equation}
The latter is the average of $n$ only when the particle
is detected with probability one, namely when  $S_\infty=0$.
A shorthand notation of Eq. (\ref{eqAve})
is
$\langle n \rangle = \langle \hat{\phi}| -i \partial_{\theta} | \hat{\phi}\rangle$.

\subsection{Connection between first detection and spatial wave function}
\label{secRENEWAL}

 In classical random walk theory the key approach to the first passage time
problem is to relate it to occupation probabilities \cite{Redner}.
Let us unravel a similar relation in the quantum domain, connecting
between first detection statistics and the corresponding
wave packet, namely the time dependent
solution of the Schr\"odinger equation in the absence
of measurement  (see also
\cite{Grunbaum} for the $|0\rangle \rightarrow |0\rangle$ transition).
To that end,  we first  briefly review the classical random walk.

Consider a
classical random walk in discrete time
 $t=0,1,..$,
for example
a random walk on a cubic lattice in dimension $d$
with jumps to nearest neighbours. The main assumption is that
the random walk is Markovian.
Denote $P_{\rm cl}({\bf r},t)$ as the probability
that the walker
 is at ${\bf r}$ at time $t$ when initially the particle is at the origin
${\bf r} = 0$
and in the absence of any absorption.
Let $F_{\rm cl}({\bf r}, t)$ be the first passage probability:
 the probability
that the random walk visits site ${\bf r}$ for the first time
at time $t$ with the same initial condition.
Following  the first equation in
the  first chapter in \cite{Redner}, $P_{{\rm cl}}({\bf r}, t)$
and $F_{\rm cl}({\bf r},t)$ are related
by
\begin{equation}
P_{\rm cl}({\bf r}, t) = \delta_{{\bf r} 0} \delta_{t 0} +
\sum_{t'\le t} F_{\rm cl}( {\bf r}, t') P_{{\rm cl}}(0,t-t').
\label{eqRed01}
\end{equation}
This equation \cite{Schro,Montroll,MontrollW},
 sometimes called the renewal equation, is generally valid
for Markov processes in the sense
that it is not limited to discrete time and space models; in the  continuum
one needs only to replace summation with integration,
and probabilities by probability densities.
The idea
behind Eq. (\ref{eqRed01})
is that a particle on position ${\bf r}$ at time $t$ must have either arrived
there previously at time $t'$ {\em for the first time}
and then returned back or it arrived
at ${\bf r}$ exactly at time $t$ for the first time (the $t'=t$ term)
\cite{Schro,Redner}.
Using the $Z$ transform the following equations are derived \cite{Redner}
\begin{equation}
F_{\rm cl}( {\bf r} , z) = \left\{
\begin{array}{c l}
{P_{\rm cl}( {\bf r}, z) \over P_{\rm cl}(0, z) } & {\bf r} \neq 0 \\
1- {1  \over P_{\rm cl}(0, z) } \quad & {\bf r} = 0.
\end{array}
\right.
\label{eqRed02}
\end{equation}
From this formula, various basic properties of random walks
 can be derived. One example is
 the P\'olya theorem which
answers the question: does a particle eventually return to its origin;
i.e., whether the random walk is recurrent.
 A second
is that in  one dimension, for an open system
without bias, the famous law  $F_{\rm cl} (0,t) \sim t^{-3/2}$ is found
for large first passage time $t$  and hence the first
passage time has an infinite mean, as mentioned in the introduction.
We will later find the quantum analogue to this well known $t^{-3/2}$ behaviour.

 At first glance this classical picture might not seem related to ours.
However  consider the case where we detect the particle at the origin,
so $\hat{D}=|0\rangle \langle 0|$ and  initially
 $|\psi(0)\rangle=|0\rangle$.
Then Eq. (\ref{eq22}) reads
\begin{equation}
\hat{\phi}(z) = { \langle 0 | { 1 \over z^{-1} e^{i H \tau} -1} |0 \rangle
\over 1 +
 \langle 0 | { 1 \over z^{-1} e^{i H \tau} -1} |0 \rangle}.
\label{eqQuRed02}
\end{equation}
We add and subtract one in the numerator and use
$\langle 0 | 0 \rangle=1$
and
\begin{equation}
1 + {1 \over z^{-1} e^{i H \tau} - 1} = { 1 \over 1 - z e^{- i H \tau} }
\label{eqIdd}
\end{equation}
 to rewrite
Eq. (\ref{eqQuRed02})
 as
\begin{equation}
\hat{\phi}(z) = 1 - {1 \over \langle 0  | {1 \over 1 - z e^{-i H \tau}} | 0 \rangle},
\label{eqRed03}
\end{equation}
Expanding in $z$ we get  a geometric series
\begin{equation}
\hat{\phi}(z) = 1 - { 1 \over \langle 0 | \sum_{n=0} ^\infty z^n \exp( - i H \tau n) | 0 \rangle}.
\label{eqRed04}
\end{equation}
By definition the sum
$\langle 0|\sum_{n=0} ^\infty z^n \exp( - i H \tau n) | 0 \rangle$
 is the generating
function
of the amplitude of being at the origin
retrieved from the solution of the Schr\"odinger equation without detection.
Namely, let $|\psi_f(t)\rangle$ be the solution of the Schr\"odinger
equation for the same initial condition $|\psi_f(0)\rangle =|0\rangle$
(the subscript $f$ denotes a wave function free of measurement).
The amplitude of being at the
origin at time $t$  is
 $\langle 0|\psi_f(t)\rangle$ and
$|\psi_f(t)\rangle = \exp( - i H t) |0 \rangle$ as usual.
 We define the generating function
 of this amplitude, for the sequence of measurements under consideration
\begin{equation}
\langle 0 | \hat{\psi}_f(z)\rangle_0  \equiv  \sum_{n=0} ^\infty z^n \langle 0 | \psi_f( n \tau)\rangle
\label{eqRed05}
\end{equation}
and clearly $\langle 0 | \hat{\psi}_f(z)\rangle_0 =\sum_{n=0} ^\infty \langle 0 | z^n \exp( - i H \tau n) | 0 \rangle$, the subscript zero
denotes the initial condition.
Hence we get the appealing result
reported already in \cite{Grunbaum}
\begin{equation}
\hat{\phi}(z) = 1 - {1 \over \langle 0 | \hat{\psi}_f(z)\rangle_0} .
\label{eqRed06}
\end{equation}
Thus the generating function of the first detection time
is determined from the $Z$ transform
of the  spatial wave function at the point of detection $x=0$.
 This connection is  the quantum  analogue of the second
line in the classical expression Eq. (\ref{eqRed02})
since in both cases  we start and detect at the origin.

 Similarly for an initial condition initially localized at some site $x\neq 0$,
so $| \psi(0)\rangle=|x\rangle$ with detection at site $0$ we find
\begin{equation}
\hat{\phi}(z) = {\langle 0 |\hat{\psi}_f(z)\rangle_x \over \langle 0 | \hat{\psi}_f(z)\rangle_0}
\label{eqRed06aa}
\end{equation}
where $|\hat{\psi}_f(z)\rangle_x$ is the $Z$ transform of the wave function
free of measurements initially localized on site $x$,
$|\hat{\psi}_f(z)\rangle_x=\sum_{n=0} ^\infty z^n |\psi_f(n\tau)\rangle_x$
with
$|\psi_f(n \tau) \rangle_x = \exp(- i H n \tau)|x \rangle$.
We see that the ratio of the generating functions of the amplitudes
of finding the particle on $|0\rangle$ for initial condition on $x$
and the location of measurement site $0$,
obtained from the measurement-free evolution, yields the generating
function of the measurement process. This is the sought after quantum renewal
equation, namely the amplitude analogue of the upper line of the classical
Eq.
(\ref{eqRed02}).

{\bf Remark}
In Eq.
(\ref{eqRed05})
the lower limit of the sum is $n=0$, while
in Eq. (\ref{eq18}) the sum starts at $n=1$ as noted already \cite{remark1}.
Since $\phi_0=0$ one may of course use a summation from $0$ also in Eq.
(\ref{eq18}).

{\bf Remark} Our formalism is not limited to spatially
 homogeneous Hamiltonians. Note that in our classical discussion,
following the textbook treatment~\cite{Redner} and
for the sake of simplicity, we have assumed translation
invariant random walks. In non-translation invariant systems,
one should replace $P_{{\rm cl}}(0,t-t')$ in the left hand side
of  Eq.
(\ref{eqRed01})
with
$P_{{\rm cl}}({\bf r} , t- t'| {\bf r} ,0)$.
Since the convolution structure of the equation remains,
related to the Markovian
hypothesis, Eq.
(\ref{eqRed02})
can be easily modified to include non-homogeneous effects.

{\bf Remark} Sinkovicz et al. \cite{Sinkovicz1}
 found a quantum Kac-Lemma for recurrence
time, thus analogies between quantum and classical walks are not limited
to the renewal equation under investigation.

\subsection{Zeno Effect}

 As pointed out in \cite{Brun08,Dhar}
 when $\tau \rightarrow 0$ we find the Zeno effect
\cite{Misra,Patil}.
Since in that limit $\exp(-i H \tau) =1$ and $\hat{U}(z)=z/(1-z)$,
using Eq.
(\ref{eq21}) we get
\begin{equation}
\lim_{\tau\rightarrow 0} \hat{\phi}(z) = z \langle 0 |\psi(0)\rangle.
\label{eq27}
\end{equation}
The amplitude of finding the particle
at the origin in the first attempt, is given by the  initial wave function
projected on the origin, i.e. the probability amplitude of finding
the particle at the origin at $t=0$.
 Hence the above expression gives an obvious answer
for the first measurement;  the repeated measurements being very frequent
do not allow the wave function to be built up at the origin, and hence
$\phi_n=0$ for all $n>1$.
 This means that we may investigate the problem
for  $\tau$ small relative to the time scales of the Hamiltonian, but we cannot
take the limit $\tau \rightarrow 0$ if we wish to retain  information
on the measurement process beyond
the initial state.

\subsection{Energy representation}

Eq.
(\ref{eq20})
for a time-independent Hamiltonian
yields
\begin{equation}
\langle E_m | \hat{U}(z) | E_i \rangle
 = \left[ z^{-1} \exp\left(  i E_m \tau\right) -1\right]^{-1} \delta_{mi}
\label{eq25}
\end{equation}
 so that the operator $\hat{U}(z)$ is diagonal in the energy representation.
Here $|E_i \rangle$ is a stationary state of the Hamiltonian $H$,
namely $H|E_i\rangle = E_i |E_i \rangle$.
Clearly it is worthwhile presenting the solution in that basis.
Consider the example of the  measurement at the spatial origin corresponding
to state $|0\rangle$. This state can be expanded in the energy representation
$|0\rangle = \sum_{k} C_k | E_k \rangle$ with $C_k=\langle E_k | 0 \rangle$.
Here as usual $\langle E_m | E_k \rangle = \delta_{mk}$.
Similarly the initial condition is expanded
as $|\psi(0)\rangle = \sum_{k} A_k| E_k\rangle$. The matrix
element
\begin{equation}
\langle 0| \hat{U}(z) | \psi(0)\rangle =
\sum_k C_k ^{*} A_k\left[z^{-1}  \exp(i E_k \tau)-1\right]^{-1}
\label{eq28}
\end{equation}
together with
\begin{equation}
\langle 0 | \hat{U}(z) | 0 \rangle =
\sum_k  |C_k|^2 \left[z^{-1}  \exp(i E_k \tau)-1\right]^{-1}
\label{eq29}
\end{equation}
yields $\hat{\phi}(z)$ using Eq. (\ref{eq21}).
For the special case where $|\psi(0)\rangle = |0\rangle$ we get $A_k=C_k$ and
\begin{equation}
\hat{\phi}(z) = {\sum_k |C_k|^2 \left[ z^{-1} \exp(i E_k \tau) -1\right]^{-1}
\over
1+ \sum_k |C_k|^2 \left[ z^{-1} \exp(i E_k \tau) -1\right]^{-1} }
\label{eq30}
\end{equation}
Here as usual $\sum_k |C_k|^2 = 1$.
It is easy to check that when $\tau\rightarrow 0$ we get $F_1=|\phi_1|^2 =1$
since a particle starting at the origin is with probability one detected when
$\tau \rightarrow 0$.

\begin{figure}
\vspace*{-0.3in}
\begin{center}
\includegraphics[width=0.4\textwidth]{fig_benzen}
\end{center}
\vspace*{-0.2in}
\caption{
Schematic model of a benzene ring.
In the text measurement is performed on site $0$ and we discuss
several initial conditions.
}
\label{figBenzene}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=0.40\textwidth]{benzen_avg_n_N_10000_500}
\caption{
For a  quantum walk on a benzene ring, with initial condition
$|\psi(0)\rangle= |0\rangle$ and projective measurements on the origin,
the average number of detection attempts is, by Eq. (\ref{eqfour}), $4$ except for
the cases when $\gamma \tau$ is a multiple of $\pi/2$ or $2 \pi/3$.
 Here we plot $\langle n \rangle_N =\sum_{n=1} ^N n F_n$ for $N = 500$
and $N=10000$,
the results converging (not shown) as we increase $N$ further.
}
\label{fig2four}
\end{figure}

\section{Rings}
\label{secRings}
For our explicit calculations, we will focus
on tight binding models in one dimension~\cite{Blumen}. The first model
is a quantum walk on a ring of length $L$:
\begin{equation}
H = - \gamma \sum_{x=0}^{L-1} \left(|x\rangle \langle x+1 | +
|x+1  \rangle \langle x| \right).
\label{eqTBring}
\end{equation}
This  describes a quantum particle jumping between nearest neighbours
on the ring. We use periodic boundary conditions and thus from the site
 labeled $x=L-1$ one may
jump either to the origin $x=0$ or to the site labeled $x=L-2$.
In condensed matter physics the parameter $\gamma$ is called the
tunnelling rate.

\subsection{Benzene-Type Ring}

 As our first example we consider the tight-binding model on a hexagonal ring
presented in Fig.
\ref{figBenzene},
namely a structure similar to the benzene molecule \cite{CT,Feynman}.
We consider the influence of initial states $|\psi(0)\rangle=|x\rangle$ with
$x=0,1,..5$
on the statistics of first detection times for detection at site $0$
so $\hat{D} = |0\rangle\langle 0 |$.
According to our theory, to find the generating function we need
the energy levels of $H$ and its eigenstates.
 The six energy levels of the system
 are $E_k= - 2 \gamma \cos(\theta_k)$
with $k=0,...5$ and the eigenstates are $|E_k\rangle^{T}=(1,e^{i \theta_k},e^{2 i \theta_k},e^{i 3 \theta_k} , e^{ i 4 \theta_k},e^{i 5 \theta_k})/\sqrt{6}$
with $\theta_k=2 \pi k/6$ \cite{CT} ($\ ^T$ is the transpose).
Hence the coefficients
 $|C_k|^2=|\langle E_k|0\rangle|^2=1/6$, reflecting the symmetry of the problem.

\subsubsection{Starting at $x=0$}

We use Eq. (\ref{eq30}) and find
\begin{equation}
\hat{\phi}(z) = {{ 1 \over 6} \sum_{k=0} ^5 { 1 \over z^{-1} \exp( i E_k \tau)-1}
\over
1 + {1 \over 6} \sum_{k=0} ^5 { 1 \over z^{-1} \exp( i E_k \tau) -1}}.
\label{eq31}
\end{equation}
The nondegenerate energy levels  are $-2 \gamma$ and $2 \gamma$
while $-\gamma$ and $\gamma$ are doubly degenerate,  hence
for real $z$
\begin{equation}
\hat{\phi}(z)=
{
{1 \over 3} \left\{ \mbox{Re} \left[ { 1 \over z^{-1} e^{2 i \gamma \tau} -1} \right] +
2 \mbox{Re} \left[ {1 \over z^{-1} e^{i \gamma \tau} -1} \right] \right\}
\over
1+  {1 \over 3} \left\{ \mbox{Re} \left[ { 1 \over z^{-1} e^{2 i \gamma \tau} -1} \right] +
2 \mbox{Re} \left[ {1 \over z^{-1} e^{i \gamma \tau} -1} \right] \right\}
}.
\label{eqDel}
\end{equation}
It is interesting to note that
the generating function  satisfies the identity
\begin{equation}
\hat{\phi}(e^{i\theta})\hat{\phi}(e^{- i \theta}) = 1.
\label{ident1}
\end{equation}
an  identity we will return to below when discussing $\langle n \rangle$
and $S_\infty$.
Inserting Eq. (\ref{ident1}) in Eq.
(\ref{eqTot}) and integrating over $\theta$  gives $S_\infty=0$.
Thus the survival probability is zero in the long time
limit.
This  behavior is classical in the sense that
for  finite systems a classical random walker is always detected.
Note that for a quantum walker this conclusion is not generally valid.
 If we start at $|1\rangle$ for example and measure at $|0\rangle$,
and perform measurements on full revival periods,
the particle is never recorded (see further details
and other examples  below).
Hence, for a quantum particle
 the survival
probability $S_n$ does not generally decay to zero as $n\to\infty$, even for finite systems.

 For special values of $\gamma \tau$ we get exceptional
behaviors.
When $\gamma \tau$ is $2 \pi$ times  an integer we get
$\hat{\phi}(z)=z$ namely the
 measurement in the  first attempt is made with probability $1$,
so the first detection time is $\tau$, which is expected
since the wave function is fully revived at these $\tau$'s
 in its initial state at the origin
\cite{Blumen}.
If $\gamma \tau=\pi$ we get $\hat{\phi}(z) = z(3 z-1)/(3-z)$. Inverting
we find $\phi_1=-1/3$ and $\phi_n =8/3^n $ for $n \ge 2$,
thus the amplitude $\phi_n$ decays exponentially.
It follows that the first detection probabilities are
\begin{equation}
F_n = \left\{
\begin{array}{c c}
{1 \over 9} \ \ \ \ \ \ n=1 \\
 \ \ \\
{64 \over 9^n} \ \ \ \ \  n \ge 2 .
\end{array}
\right.
 \label{eq31b}
\end{equation}
The average number of detection attempts is $\sum_{n=1} ^\infty n F_n = 2$.
If $\gamma \tau =  \pi/2$ we find $\hat{\phi}(z)= -z(1+2 z  + 3z^2)/ (3 + 2z + z^2)$
 which has
simple poles and hence
\begin{equation}
F_n = \left\{
\begin{array}{c c}
{ 1/9}
 \ \ \ \ \ \ n=1 \\
{ 16/81}
 \ \ \ \ \ \ n=2 \\
{24\over3^n}\sin^2{\big(
\zeta_1 (n-2)
-
\zeta_2 \big)}
 \ \ \ \ \ \ n\ge3
\end{array}
\right.
 \label{eq31baa}
\end{equation}
where
$\zeta_1=\tan^{-1}(\sqrt{2})$ and
$\zeta_2=\tan^{-1}(\sqrt{2}/5)$.
For this case $\langle n \rangle = 3$. Similarly for $\gamma \tau=2 \pi/3 + 2 k \pi$
and $\gamma \tau = 4 \pi/3+ 2 k \pi$ we
get $\langle n \rangle = 2$.
The general feature of finite rings is an exponential decay of
$F_n$  with a superimposed oscillation determined by the poles of
the generating function.  However the sampling times
$\gamma \tau=0,\pi/2, 2 \pi/3, \pi\cdots$  considered so far
 exhibit behaviors
which are not typical, as we now show.

A surprising behavior is found for the average, with
\begin{equation}
\langle n \rangle = 4
\label{eqfour}
\end{equation}
for any sampling rate in the interval $(0, 2 \pi)$ besides
what we call the exceptional sampling times
  $\gamma \tau=0,\pi/2,2 \pi/3 ,\pi, \cdots $ where as mentioned
$\langle n \rangle=1,3,2,2, \cdots$ respectively,
 which is continued periodically (see Fig. \ref{fig2four}). This result is derived below.
 As mentioned in the introduction the fact that $\langle n \rangle$ is some integer was
already pointed out rather generally by \cite{Grunbaum} and this is related to topological
effects.
Except for the exceptional points, the variance of $n$ is
\begin{widetext}
\begin{equation}
\mbox{Var}(n) = -11 + {27\over 4 - 4 \cos \gamma \tau} + {1\over
6 \cos^2 \gamma \tau} + {3\over 4  + 4\cos \gamma \tau} + {3\over
(1 + 2 \cos\gamma \tau)^2}
\end{equation}
\end{widetext}
 so that the first detection time exhibits large fluctuations near these
 points.
Thus for the $0$ to $0$ transition
it is only the average $\langle n \rangle$ that is nearly always
 not sensitive to the sampling
rate, not the full distribution of first detection times.

There are numerous methods to  find $\langle n \rangle =\sum_{n=1} ^\infty
n F_n$.
 For the exceptional points we used the exact solution for $F_n$
 (as mentioned).
For other sampling times we use two approaches: the first using
Mathematica and is based on a Taylor expansion
of $\hat{\phi}(z)$  and the second is an analytic calculation.
The former approach is very general in the sense that it can be used
in principle for general initial conditions and other problems beyond the benzene ring.

Specifically, we calculate $F_n$ exactly using the expansion
of $\hat{\phi}(z)$ with
  symbolic programming on Mathematica. This is performed
up to some large $N$. We then calculate $\langle n \rangle_N = \sum_{n=1} ^N
n F_n$. Clearly $\langle n \rangle > \langle n \rangle_N$, and  increasing $N$
we see convergence towards $\langle n \rangle= 4$ except for the mentioned
exceptional points. An example is shown in Fig.
(\ref{fig2four}) for the cases $N= 500$ and $N=10000$.

Even better is to write $\hat{\phi}(z)= z^4 H(1/z) /H(z)$, which is the extension to general $z$ of the identity
Eq. (\ref{ident1})
that we used to show $S_\infty=0$.
To find $\langle n \rangle$ we use Eq.
(\ref{eq31}) to find
\begin{multline}
H(z) = [2\cos(\gamma\tau)+\cos(2\gamma\tau)]z^3-\\
[3+6\cos(\gamma\tau)\cos(2\gamma\tau)]z^2+ \\
[4\cos(\gamma\tau)+5\cos(2\gamma\tau)]z-3,
\label{eqnn}
\end{multline}
and with Eq. (\ref{eqAve})
\begin{multline}
\langle n \rangle= \\
\frac{1}{2\pi i}\int_0^{2\pi}\frac{e^{-4i\theta}H(e^{i\theta})}{H(e^{-i\theta})}
\frac{\partial}{\partial \theta}
\left(\frac{e^{4i\theta}H(e^{-i\theta})}{H(e^{i\theta})}\right)d\theta \\
=4-\frac{1}{i\pi}\int_0^{2\pi}\frac{\partial}{\partial \theta}\ln{H(e^{i\theta})}d\theta.
\end{multline}
Rewriting  $H(z)=a(z-z_1)(z-z_2)(z-z_3)$ we can proceed to
show that
\begin{equation}
\langle n \rangle=
4-\frac{1}{i \pi}\sum_{j=1}^{3}\int_{0}^{2\pi}\frac{\partial}{\partial \theta}\ln(e^{i\theta}-z_j)d\theta=4-2\alpha-\beta
\end{equation}
where $\alpha$ (or $\beta$) is the number of zeros of  $H(z)$  for $z$ within
(or on)  the unit
circle  respectively.  As explained in Appendix B,
 $\alpha=0$ for otherwise we would find $F_n>1$.
For the exceptional values of $\gamma\tau$ we find $\beta>0$, as follows:
\begin{equation}
\beta=
\begin{cases}
1&\gamma\tau=\frac{1}{2}\pi+\pi k\\
2&\gamma\tau=\frac{2}{3}\pi+2\pi k, \pi+2\pi k,\frac{4}{3}\pi+2\pi k\\
3&\gamma\tau=2\pi k\\
0&\text{otherwise}.
\end{cases}
\end{equation}
This agrees with the values of $\langle n \rangle$
we have found at the exceptional
points. This exercise shows that mathematically, at least for
this example,  the exceptional
points are those specific
values of $\tau$ where some of the zeros of the polynomial $H(z)$ are found  to lie on the unit circle in the complex plane.
 We will soon find a by far more physical
and explicit formula for these points, Eq. (\ref{eqET}) below.

$$ $$
\begin{table}[h!]
\begin{tabular}{ c | c | c | c | c | c | c | c | c}
\centering
 $x$ & $0<\gamma \tau < 2 \pi ^{*}$  &$ \gamma\tau=  0$ & $\frac{1}{2}\pi$ & $\frac{2}{3}\pi$ & $\pi$ & $\frac{4}{3}\pi$ & $\frac{3}{2}\pi$ & $2\pi$ \\
 \hline
  0 &  1  & 1 &  1  & 1 &  1  & 1 &  1  & 1\\
  1 & 1/2 & 0 & 1/6 & 0 &  0  & 0 & 1/6 & 0\\
  2 & 1/2 & 0 & 1/2 & 0 & 1/2 & 0 & 1/2 & 0\\
  3 &  1  & 0 & 2/3 & 1 &  0  & 1 & 2/3 & 0\\
\end{tabular}
\caption{Total detection probability $1- S_\infty$ for a quantum walker
on a benzene
ring, for different localized
 starting points $|\psi(0)\rangle = | x \rangle$. Measurements are performed at $x=0$ hence
initial conditions on sites $1$ and $2$ are equivalent to initial conditions
on $5$ and $4$ respectively. Values of the parameter
 $\gamma \tau$ are listed in
the first row, and $0<\gamma \tau<2 \pi ^{*}$ implies all values of
$\gamma \tau$ in the interval,
 besides the listed special cases, e.g. $\gamma\tau=\pi$.
}
\label{TableExcpetional}
\end{table}

\subsubsection{Half Dark states}

 Another peculiar behavior is found if the detection is at
the origin  $\hat{D} = |0\rangle\langle 0 |$ and the starting point is
$|i\rangle$ with $i=1,2,4,5$.
The total probability of detection is found to be, by the method explained in Appendix B,
\begin{equation}
1-S_\infty=1/2
\label{eqHalf}
\end{equation}
 for all
values of $0<\gamma \tau < 2 \pi$ besides exceptional
points which are listed in Table
\ref{TableExcpetional}.
The exceptions include the case  when $\tau$ is the
full revival time, for which case the probability of being detected
is of course $0$.
The behaviour  Eq. (\ref{eqHalf})  was observed in
\cite{Dhar,Dhar1} for even larger systems.
It is  remarkable that  for certain initial conditions, the detection
of the particle is not guaranteed, and only in half of the measurement
processes we detect the particle, hence we call these initial
conditions
half  dark
states.

\subsubsection{Starting on site $3$ measuring on $0$}

In contrast, if the  starting  state is $|3\rangle$
 the total probability of detection is found to be $1$, if the measurement
time $\tau$ is not the full revival time $\gamma \tau=2 \pi$,
 or  one of the exceptional
sampling times  listed in Table
\ref{TableExcpetional}.
In Appendix \ref{AppKessler},
we find
\begin{widetext}
\begin{equation}
\langle n \rangle =
{4 \over 9}+  { 9 \over 8 - 8  \cos\gamma \tau} + {1 \over 36 \cos^2 \gamma \tau} - {1 \over 9 \cos \gamma \tau} + {17 \over 72\left( 1 + \cos \gamma \tau \right)}
\label{eqDAVID}
\end{equation}
\end{widetext}
an equation valid for all $\gamma \tau$ besides the exceptional points.
The general behavior of $\langle n \rangle$
is  obviously quite different from the case when the
initial location is $0$,  compare Fig.
\ref{fig2four} and Fig. \ref{fig2three} indicating that the initial
condition plays a crucial rule.
As shown in Fig.
\ref{fig2three}
the average $\langle n \rangle$
exhibits nontrivial behavior as it diverges as it  approaches some of the
exceptional points. These singularities  are found near those
exceptional
sampling times where the total probability of measurement is not one.
Interestingly the values of $\langle n \rangle$, conditioned on return, are finite at the exceptional points
themselves.

An analytical calculation
for the exceptional sampling times $\gamma \tau = 2 \pi/3$ or $4 \pi/3$
 finds
$\langle n \rangle=4/3$.
This sampling time is unique since the average $\langle n \rangle$ exhibits
a discontinuity: for $\gamma \tau$ in the vicinity of $2 \pi/3$ and $4 \pi/3$
 we
find using
Eq. (\ref{eqDAVID})
$\langle n \rangle =2$ (so at these points the equation is not valid).
Similar to any discontinuity at a point,
the discontinuity  of  $\langle n \rangle$ at $\gamma \tau=2 \pi/3,4 \pi/3$
 might not be detectable in experiment. However  one finds
critical slowing down, namely
the  convergence of $\langle n \rangle$ for any point in the vicinity
of these exceptional points is very slow,
as demonstrated in Fig.
\ref{fig2three}.

\begin{figure}
\centering
\includegraphics[width=0.49\textwidth]{benzen_avg_n_3_to_0_comparison}
\caption{
The average $\langle n \rangle$ versus $\gamma \tau$ Eq. (\ref{eqDAVID}).
 When
$\tau \to 0$ we find
$\langle n \rangle \to \infty$ due to the Zeno effect, another
expected
divergence of $\langle n \rangle$ is found when the sampling time is the full
 revival
time $\gamma \tau =2 \pi$. In addition to these two points we find singularities
also for $\pi/2,\pi,3\pi/2$.
Notice the discontinuities of $\langle n \rangle$
 for  $\gamma \tau=2 \pi/3$ and
$\gamma \tau=4 \pi/3$  which are discussed in the text.
Here $|\psi(0)\rangle=|3\rangle$ and the detection is on the origin.
The plot of $\langle n \rangle$  for this choice of initial condition
is  vastly different from that presented in
Fig.
\ref{fig2four}.
}
\label{fig2three}
\end{figure}

\subsection{Rings of Size $L$}

 While the benzene ring is instructive, one must wonder how general
are the main results. In Appendix \ref{AppKessler}
 we derive the following
four results:
\begin{itemize}
\item[i.] For a ring of size $L$ and for a particle initially on
site $x=0$ where the measurements are performed, the particle is
detected with probability  unity, and in this sense the motion is
recurrent. We emphasize that this result
is a property of the specified initial condition.
\item[ii.] For the same initial condition, besides those isolated exceptional
sampling times $\tau$ listed below, the average number of
detection events is
\begin{equation}
\langle n \rangle =\left\{
\begin{array}{c c}
{ L + 2 \over 2} & \  \mbox{$L$ is even} \\
\ & \ \\
{ L + 1 \over 2} & \  \mbox{$L$ is odd}.
\end{array}
\right.
\label{eqKRSL}
\end{equation}
This result is remarkable since the average is independent of the sampling time $\tau$.
 Here we see that $\langle n \rangle$ is the number of distinct energy
levels of the system.
In the language of \cite{Grunbaum} it is the winding
number of the Schur function, or the effective dimension of the Hilbert space.
 For large systems $\langle n \rangle$ grows linearly with the size
of the system $L$, while from classical random walk
 theory we naively expect diffusive
scaling $\langle n \rangle \sim L^2$. In that sense the quantum
walk is more efficient (see below further remarks).
\item[iii.] The exceptional sampling times $\tau$ are given by the rule
\begin{equation}
\Delta E \tau = 2 \pi n
\label{eqET}
\end{equation}
where $n$ is an integer, and $\Delta E= E_i - E_j> 0$ is the energy
difference between pairs of eigenenergies of the underlying Hamiltonian
$H$. For example the stationary energies of the benzene ring
are $\{ - 2 \gamma, - \gamma , \gamma , 2 \gamma\}$ as mentioned,
and hence Eq.
(\ref{eqET}) predicts the exceptional sampling times
$0, \pi/2\gamma, 2 \pi/3\gamma , \pi/\gamma, ...$.
The condition Eq. (\ref{eqET}) implies a partial revival of the wave packet
free of measurement, namely  two   modes of the system
behave identically when strobed at the period $\tau$.
On these exceptional points the solution exhibits non-analytical behavior.
This is manifested in discontinuities or diverging behavior of $\langle n \rangle$
or the fluctuations of $n$ and also slow critical-like convergence
to the asymptotic theory.  The
exact nature of the non-analytical behavior depends on the initial
condition as we have demonstrated for the benzene ring.

\item[iv]  For a particle starting on $|0\rangle$
every time the condition
(\ref{eqET}) is met by a pair of energy levels
we reduce the value of
$\langle n \rangle$  by unity.
Thus Eq. (\ref{eqET}) is the upper limit of $\langle n \rangle$ for a system
of fixed size $L$. More specifically we find that
\begin{equation}
\langle n \rangle = \mbox{number of distinct phases
} \exp( -i E_k \tau)
\label{eqPHASES}
\end{equation}
where $E_k$ are the energy levels of the system.
For nearly any $\tau$ this is the same as the number of distinct
 energy levels,
but of course for special sampling times, this integer is less
than that.

\end{itemize}

\subsection{Bose-Einstein Distribution}

A curiosity is the fact that we may express the solution for the $0$ (starting point) to $0$ (measurement point) problem for a general ring with $L$ sites,  in terms
of a Bose-Einstein distribution. The latter is defined
as \cite{Reif}
\begin{equation}
\bar{n}_k = {1 \over e^{-\beta \mu + \beta E_k} -1}
\label{eq32}
\end{equation}
where $\beta$ is the inverse temperature and $\mu$ the chemical potential.
In our case $z^{-1} =\exp(- \beta \mu)$ and $\beta E_k= i \tau E_k$
with the energy spectrum  $E_k = - 2 \gamma \cos( 2 \pi k/L)$.
The generating function for a ring system with $L$ sites is
\begin{equation}
\hat{\phi}(z) ={ \sum_{k=0} ^{L-1} \bar{n}_k/L \over 1 + \sum_{k=0} ^{L-1} \bar{n}_k /L }.
\label{eq32a}
\end{equation}
The mathematical
 relation of the problem at hand to the Bose-Einstein distribution
is not limited to the specific energy spectrum under investigation
(see also \cite{Grunbaum}).
If the Hamiltonian is symmetric in the sense
that all lattice points
are equivalent, such that $|C_k|^2=1/L$, the above result is valid.
In the Bose-Einstein language
the sum $\sum_{k=0} ^{L-1} \bar{n}_k/L$,
is the spatially averaged
density. Thus the problem
of finding the generating function is mathematically equivalent to finding
the relation between chemical potential, temperature and the
average number
of particles, for a given energy spectrum of a system.
 The main conditions are that all sites
are equivalent and
that the initial and detection state are both on a single ring site.

\subsection{Revivals}

 The amplitude of detection at the first measurement $\phi_1$ is now
investigated
for a particle on a ring of size $L$ starting on the origin
which is also the detected site
\begin{equation}
\phi_1 = {1 \over L} \sum_{k=0} ^{L-1} e^{2 i \gamma \tau \cos\left( 2 \pi k /L\right)}.
\label{eq32b}
\end{equation}
In the limit $L\to \infty$ the sum is an integral
and  we find $\phi_1=J_0 (2 \gamma \tau)$ and $J_0(\cdot)$
is a Bessel function of the first kind \cite{ABR}.
  Unlike the
benzene,  $L=6$, case, for an infinite system
 with $\gamma \tau\neq 0$,
the probability of detecting the particle at
first measurement, $F_1=|\phi_1|^2$, is always less than unity
since $|J_0(2 \gamma \tau)|^2<1$.
This is to be expected, as the wave function in an infinite
system does not revive
at the origin. The question remains:
does a finite sized system always exhibit a special
choice or choices  of $\gamma \tau \neq 0$ such that $F_1=1$?
(and  then
 all $F_n$ for $n>1$ are zero). This corresponds
to a deterministic outcome of certainly  detecting
 at a single detection attempt.
This question put differently is the well-studied
 question of full revivals.
Namely, does there exist some $\tau$ such that a particle,
 in the absence
of measurement,  will fully return to its initial state.
If that is the case,
the first measurement detects the particle with probability
one if the measurement time is $\tau$. As mentioned, for $L=6$,
this effect is found  for $\gamma \tau = 2 \pi k$ for $k=0,1,2,\cdots$.

 According to \cite{Blumen} full revivals take place for $L=1,2,3,4,6$ only.
This can be verified using our formalism.
We checked this for $L=5,7,8,9,10$
finding that
 the absolute value squared of the  sum
Eq. (\ref{eq32b}) is never equal 1 unless $\tau=0$.
For example for $L=10$
\begin{equation}
\phi_1 = {1 \over 5} \left[ \cos \left( 2 \gamma \tau \right) +
4 \cos\left( {\gamma \tau\over 2} \right) \cos\left( \sqrt{5} \gamma \tau \over 2\right)\label{eq43aa}
\right],
\end{equation}
an expression which shows that $|\phi_1|< 1$ beyond the trivial
case $\gamma \tau=0$.

{\bf Remark}
For a ring with $4$ sites and sampling rate of $\gamma \tau=\pi$
one finds $\hat{\phi}(z)=z^2$  namely the quantum walker is
detected in the  second measurement with probability one.
Such a behavior is found when the  initial wave packet is localized
at the place of detection.
 In this example,  the first measurement is performed
when the wave function at the origin is zero, and
hence this measurement does not alter the wave function, while
in the second measurement we have full revival of the wave function
at the origin.

\section{First detection time for an unbounded quantum walker}
\label{secFD}

 In this section we consider the first detection problem for
a free particle in an infinite lattice.
We use the  tight-binding Hamiltonian
\begin{equation}
H = - \gamma \sum_{x=-\infty}^{\infty} \left(|x\rangle \langle x+1 | +
|x+1  \rangle \langle x| \right)
\label{eq01}
\end{equation}
  for a particle launched from the origin
$|\psi(0)\rangle = | 0 \rangle$ and
investigate the probability  of
first  detection $F_n$ with projective
measurements performed at the origin.

  Previously  Bach, et al. \cite{Bach}.
investigated a Hadamard quantum walk introduced in  \cite{Ambainis}
showing that the survival probability of a one dimensional
walker
exhibits a power-law decay, $F_n \propto n^{=3}$ in our terminology, namely
 a scaling
 exponent $3$ which is twice the classical
one, i.e., $3/2$.
 This was the topic of further, analytical \cite{Grunbaum} numerical
\cite{Das,Miquel} and perturbative approaches \cite{Dhar,Dhar1}.
 In this sense, it is known already that  quantum walks modify the
known classical  exponents of classical random walk theory, where the first
passage time PDF decays like $t^{-3/2}$  for large times.
What seems to be missed in previous literature, is that even in an infinite
system critical sampling effect takes place. On the more technical level we show how to use
the generating function formalism to find the large $n$ behavior of
the  first detection probability then finding non trivial behaviour of $S_\infty$.

\subsection{The generating function}

 The solution of the Schr\"odinger equation (\ref{eq01}) is
$|\psi_f(t)\rangle= \sum_{x=-\infty} ^\infty B_x |x\rangle$ and
the amplitudes satisfy $i \dot{B}_x=- \gamma(B_{x+1} + B_{x-1})$.
Using the Bessel function identity \cite{ABR}
 $2 J'_\nu(z) = J_{\nu-1} (z) - J_{\nu+1}(z)$
and the initial condition $B_x= \delta_{x,0}$
one finds
\begin{equation}
|\psi_f(t)\rangle =
 \sum_{x=-\infty} ^\infty i^{x} J_x (2 \gamma t) | x \rangle.
\label{eq33}
\end{equation}
This is of course the same as
 $|\psi_f(t)\rangle = \exp( - i H t) |0\rangle$.
To obtain the generating function we use Eq.
(\ref{eqRed06}), we have $\langle 0 |\hat{\psi}_f(z)\rangle= \sum_{n=0} ^\infty z^n J_0( 2 \gamma \tau n)$ so
\begin{equation}
\hat{\phi}(z) = 1 - {1 \over \langle 0 |\hat{\psi}_f(z)\rangle} =
1 - {1 \over \sum_{n=0} ^\infty z^n J_0 ( 2 \gamma \tau n)}.
\label{eq35Zan}
\end{equation}
Since $J_0(0)=1$ this can be rewritten as
\begin{equation}
\hat{\phi}(z) = { \sum_{n=1} ^\infty z^n J_0 \left( 2 \gamma n \tau\right) \over
1 +  \sum_{n=1} ^\infty z^n J_0 \left( 2 \gamma n \tau\right) }.
\label{eq35}
\end{equation}

Before analyzing Eq. (\ref{eq35}), we
derive it again  using the energy
spectrum.
 The energy levels of a tight-binding  ring system
(periodic boundary conditions)
determined from the time independent Schr\"odinger equation,  are
$E_k = - 2 \gamma \cos( 2 \pi k/L)$ and the
system size $L$ tends to infinity.
As we have seen,  $|C_k|^2 = 1/L$ in Eq. (\ref{eq30}),
since all lattice sites are equivalent with respect to the Hamiltonian.
Using Eq. (\ref{eq22}) or Eq. (\ref{eq32a})  with minor rearrangement
\begin{equation}
\hat{\phi}(z) = {
{ 1 \over L} \sum_{k=0} ^{L-1} { z \exp\left[ i 2 \gamma \tau \cos\left( { 2 \pi k \over L} \right)\right] \over 1 - z \exp\left[ i 2 \gamma \tau \cos\left(   2 \pi k \over L \right) \right]}
\over
1 +
 { 1 \over L} \sum_{k=0} ^{L-1} { z \exp\left[ i 2 \gamma \tau \cos\left( { 2 \pi k \over L} \right)\right] \over 1 - z \exp\left[  i 2 \gamma \tau \cos\left(   2 \pi k \over L \right) \right]}
}.
\label{eq36}
\end{equation}
This is exact for all $L$  and reduces to Eq. (\ref{eq31}) when $L=6$.
Let
\begin{equation}
I(z)\equiv
 \lim_{L \to \infty}
{ 1 \over L} \sum_{k=0} ^{L-1} { z \exp\left[ i 2 \gamma \tau \cos\left( { 2 \pi k \over L} \right)\right] \over 1 - z \exp\left[  i 2 \gamma \tau \cos\left(   2 \pi k \over L \right) \right]
}.
\label{eq37}
\end{equation}
where the sum is an integral in the limit.  Changing variables
$2 \pi n/L=y$
\begin{equation}
I(z) = {1\over  2 \pi} \int_0 ^{2 \pi}
{
z e^{ 2 i \gamma \tau \cos(y) } {\rm d} y \over
1 -  z e^{ 2 i \gamma \tau \cos(y) }
}
\label{eq38}
\end{equation}
and expanding to get a geometric series
gives
\begin{equation}
I(z) = { z \over 2 \pi }
 \int_0 ^{2 \pi} e^{  2 i \gamma \tau \cos(y)} \sum_{k=0} ^\infty \left[ z e^{ 2 i \gamma \tau \cos\left( y \right)} \right]^k {\rm d} y.
\label{eq38A}
\end{equation}
Integrating over $y$
using the identity
$\int_0 ^{2 \pi} \exp[ i z \cos(y)] {\rm d} y = 2 \pi J_0 (z)$
and shifting the summation by unity, we get
\begin{equation}
I(z) = \sum_{n=1} ^\infty z^n J_0 \left( 2 \gamma n \tau \right).
\label{eq39}
\end{equation}
Using
\begin{equation}
\hat{\phi}(z) = {I(z)\over 1 + I(z)}
\label{eq40}
\end{equation}
we find  the generating function Eq.
(\ref{eq35}). Note that $1+ I(z) = \langle 0|\hat{\psi}_f(z)\rangle$, and we use
it as a matter of convenience.

\subsection{Small $n$ behaviour}

 To analyze the small $n$ behavior of $\phi_n$, we expand the generating
function
as a power series of $z$ using
Eqs. (\ref{eq18},\ref{eq35}).
Such an expansion is easy to perform with a symbolic program like Mathematica,
which provides Table \ref{Table01}  giving explicit expressions
for  $\phi_n$ when  $n=1,\cdots,7$.
If we set $\gamma \tau$ to a fixed value, the expansion can be carried out
for relatively large $n$, and in this sense we may find
numerically exact results which are later presented in the figures.
Of course this information is the same as that found with the
exact solution Eqs.
(\ref{eq16},\ref{eq17}).

From Table \ref{Table01}, we see that
 when $\gamma \tau \to 0$ we have $\phi_n=\delta_{n1}$ since then
the particle is detected in the first attempt.
The Table also gives
the leading order corrections to this expected behavior
\begin{equation}
\phi_n \sim \left\{
\begin{array}{c l}
 1 - (\gamma \tau)^2 &  n = 1 \\
  - 2 (\gamma \tau)^2 &  n \geq 2.
\end{array}
\right.
\label{eqDEM}
\end{equation}
This can
be derived
from Eq. (\ref{eq35}) using $J_0(x) \simeq 1 - x^2/4$ for $x\ll 1$.
Eq. (\ref{eqDEM}) exhibits equal probability of detection
for $n>1$ which is merely an outcome of the Taylor expansion.

When
$\gamma \tau \to \infty$
the amplitudes
$\phi_n$ are zero for $n=1,2,3,\cdots$
since the wave packet spreads in an infinite system,
hence its probability of being detected on the origin is zero in this limit.
A close look at Table \ref{Table01} shows that
in this limit $\phi_n \simeq J_0 \left( 2 n \gamma \tau\right)$.
Using $F_n = |\phi_n|^2$ and the asymptotic behavior
of the Bessel function
\begin{equation}
F_n \sim
{ \cos^2\left( 2 \gamma \tau n - \pi/4\right)
\over \pi \gamma \tau n}
\label{eqPPHH}
\end{equation}
when $\gamma \tau \gg 1$.
Thus the probability of first detection decays like a $1/n$ power law,
when $\gamma \tau$ is large and $n$ is fixed and finite.
This approximation breaks down for sufficiently large $n$. For example,
using $\gamma \tau =80$,
by comparison with the numerically exact solution, we observe roughly
$30 \%$ deviation from theory already for $n=10$

\begin{widetext}

\begin{table}[h!]
\centering
\begin{tabular}{| >{$}c<{$} | >{$}l<{$}|}
\hline
n &\phi_n\\
\hline
1 &J_0(2 \gamma \tau )\\
\hline
2 &J_0(4 \gamma \tau )-J_0(2 \gamma \tau ){}^2\\
\hline
3 & J_0(2 \gamma \tau ){}^3-2 J_0(4 \gamma \tau ) J_0(2 \gamma \tau )+J_0(6\gamma \tau )\\
\hline
4 &-J_0(2 \gamma \tau ){}^4+3 J_0(4 \gamma \tau ) J_0(2 \gamma \tau ){}^2-2 J_0(6 \gamma \tau ) J_0(2 \gamma \tau )-J_0(4 \gamma\tau ){}^2+J_0(8 \gamma \tau )\\
\hline
5 &J_0(2 \gamma \tau ){}^5-4 J_0(4 \gamma \tau ) J_0(2 \gamma \tau ){}^3+3 J_0(6 \gamma \tau ) J_0(2 \gamma \tau){}^2+\\
  &+3 J_0(4 \gamma \tau ){}^2 J_0(2 \gamma \tau )-2 J_0(8 \gamma \tau ) J_0(2 \gamma \tau )-2 J_0(4 \gamma \tau ) J_0(6 \gamma \tau)+J_0(10 \gamma \tau )\\
\hline
6 &-J_0(2 \gamma \tau ){}^6+5 J_0(4 \gamma \tau ) J_0(2 \gamma \tau ){}^4-4 J_0(6 \gamma \tau ) J_0(2 \gamma \tau){}^3-6 J_0(4 \gamma \tau ){}^2 J_0(2 \gamma \tau ){}^2+3 J_0(8 \gamma \tau ) J_0(2 \gamma \tau ){}^2+\\
 &+6 J_0(4 \gamma \tau ) J_0(6 \gamma\tau ) J_0(2 \gamma \tau )-2 J_0(10 \gamma \tau ) J_0(2 \gamma \tau )+J_0(4 \gamma \tau ){}^3-J_0(6 \gamma \tau ){}^2-2 J_0(4 \gamma \tau )
J_0(8 \gamma \tau )+J_0(12 \gamma \tau )\\
\hline
7 &J_0(2 \gamma \tau ){}^7-6 J_0(4 \gamma \tau ) J_0(2 \gamma \tau ){}^5+5 J_0(6 \gamma \tau ) J_0(2\gamma \tau ){}^4+10 J_0(4 \gamma \tau ){}^2 J_0(2 \gamma \tau ){}^3-4 J_0(8 \gamma \tau ) J_0(2 \gamma \tau ){}^3-\\
 &-12 J_0(4 \gamma \tau ) J_0(6 \gamma \tau ) J_0(2 \gamma \tau ){}^2+3J_0(10 \gamma \tau ) J_0(2 \gamma \tau ){}^2-4 J_0(4 \gamma \tau ){}^3 J_0(2 \gamma \tau )+3J_0(6 \gamma \tau ){}^2 J_0(2 \gamma \tau )+\\
  &+6 J_0(4 \gamma \tau ) J_0(8 \gamma \tau ) J_0(2 \gamma \tau )-2 J_0(12 \gamma \tau ) J_0(2\gamma \tau )+3 J_0(4 \gamma \tau ){}^2 J_0(6 \gamma \tau )-2 J_0(6 \gamma \tau ) J_0(8 \gamma \tau )-\\
  &-2 J_0(4 \gamma \tau ) J_0(10 \gamma\tau )+J_0(14 \gamma \tau )\\
\hline
\end{tabular}
\caption{Amplitudes  of $\phi_n$ for an infinite system, the quantum walker
dispatched and detected at the origin.}
\label{Table01}
\end{table}

\begin{figure}
\centering
\includegraphics[width=0.40\textwidth]{integral_path_p2}
\caption{
Counter-clockwise integration path $C$ in Eq. (\ref{eq23})
 for evaluation of $\phi_n$ for an unbounded lattice with the sampling rate
$\gamma \tau = \pi/2$  Eq.
(\ref{eq46a}) avoids  the
branch cut along the negative real axis
when $|z|>1$. The outer radius approaches infinity.
}
\label{fig2path}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=0.40\textwidth]{inf_lattice_tau_05pi_comparison}
\caption{
First detection probability $F_n$  versus $n$ on a log log plot,
for an open system, detection is at the starting point and
the sampling rate is $\gamma \tau=\pi/2$. For large $n$ the exact result (dots)
 converges to the
asymptotic power law behavior  Eq.
(\ref{eq53}), $F_n =|\phi_n|^2 \sim 0.25 n^{-3}$ (straight line).
}
\label{figsingle}
\end{figure}

\end{widetext}

\subsection{Large $n$ behaviour}

 The large $n$ behaviour of $\phi_n$  is of particular
theoretical interest  since it is expected to exhibit universal features.
For ordinary random walks the transformation from $z$ back to $n$
 is performed
with machinery called the Tauberian and Abelian theorems \cite{Redner,Weiss}.
While the technique is widely applicable
the transformation method for the quantum problem
is slightly more involved as compared
with the corresponding  classical  problems, the
reason being that $\phi_n$ turns out to exhibit
a decay superimposed with oscillations, while in classical random walks
the first passage probability decays monotonically to zero for large $n$.

The analysis is performed by integration in the complex plane
using Eqs. (\ref{eq23},\ref{eq39},\ref{eq40}). In the large $n$ limit
the asymptotic behaviour of the Bessel function
\cite{ABR}
is
\begin{equation}
J_0 \left( 2 \gamma \tau n \right) \sim { \cos\left( 2 \gamma \tau n - \pi/4\right) \over \sqrt{ \pi \gamma \tau n } }.
\label{eq42}
\end{equation}
Since we are investigating the large $n$ limit we replace
the Bessel function
in Eq. (\ref{eq39})
with its asymptotic
behavior, hence we
define
\begin{equation}
I_{\gamma \tau} (z) = \sum_{n=1} ^\infty z^n
 { \cos\left( 2 \gamma \tau n - \pi/4\right) \over \sqrt{ \pi \gamma \tau n }}
.
\label{eq43}
\end{equation}
This expression works well for $|z| \simeq 1$ corresponding to large $n$
(only $|z|>1$ is actually important, see our integration path below).
The  large $n$ limit of $\phi_n$ is then given by the asymptotics
of the inverse $Z$-transform of
\begin{equation}
\hat{\phi}(z) \sim { I_{\gamma \tau} (z) \over 1 + I_{\gamma \tau}(z) }.
\label{eq44}
\end{equation}
We start with an example.

\begin{widetext}

\subsubsection{ Infinite system $\gamma \tau = \pi/2$}

 We consider the case $\gamma \tau = \pi/2$ and find
\begin{equation}
I_{\pi/2} (z) = { 1\over \pi} \mbox{Li}_{1/2}(-z),
\label{eq45}
\end{equation}
where $\mbox{Li}_{s}(z) =\sum_{k=1} ^\infty z^k/k^s$ is the polylogarithm
function.
Using Eq. (\ref{eq23})
\begin{equation}
\phi_n \sim {1 \over 2 \pi i} \oint_C z^{-n -1}
 {  {1 \over \pi}\mbox{Li}_{1/2}(-z)  \over 1 + {1 \over \pi} \mbox{Li}_{1/2}(-z) } {\rm d} z
\label{eq46a}
\end{equation}
in the large $n$ limit.
The integration path is shown in Fig. \ref{fig2path}.
A branch-cut is found in the complex plane of integration along the negative
real axis when
$|z|>1$  since there $z=-|x|$ and $\mbox{Li}_{1/2}(-z)=\sum_{k=1} ^\infty |x|^k /\sqrt{k}$ does not converge.
The radius of the outer
 path of integration is taken to be large
($r \to \infty$ in Fig. \ref{fig2path})
and then
\begin{equation}
\phi_n \sim  {{\cal I}_{+} + {\cal I}_{-} \over 2 \pi i } .
\label{eq46}
\end{equation}
The integration in the complex
plane reduces to two integrals running parallel to the
branch cut (see Fig.
\ref{fig2path}).
The first line integral ${\cal I}_{+}$
 to be evaluated is slightly above the negative
real axis  along  $z=x + i \epsilon$ with
$-\infty < x < -1$ and $0<\epsilon \to 0$.
The second integral follows in the opposite direction with $z=x-i \epsilon$
(see Fig. \ref{fig2path}).  We consider ${\cal I}_{+}$ using
$z^{-(n+1)} = \exp[-(n+1) \ln z]$
and Eq. (\ref{eq46a}):
\begin{equation}
{\cal I}_{+} = \int_{-\infty} ^{-1} \exp\left[ - \left( 1 + n \right) \ln \left(  x + i \epsilon \right) \right]
{ \mbox{Li}_{1/2} ( - x - i \epsilon) \over \pi + \mbox{Li}_{1/2} (-x-i \epsilon) }{\rm d} x.
\label{eq47}
\end{equation}
${\cal I}_{-}$ is similarly defined with a change of sign in $\epsilon$ and
the lower and upper integration limits switched.
Changing variables to $y$ with $x\equiv -1 -y$
\begin{equation}
{\cal I}_{+} = \int_0 ^\infty \exp\left[ - \left(1 + n\right)
\ln\left(-1 - y + i \epsilon\right)\right]
{ \mbox{Li}_{1/2} (1 + y - i \epsilon) \over
\pi + \mbox{Li}_{1/2} (1 + y - i \epsilon) } {\rm d} y.
\label{eq48}
\end{equation}
When $n \to \infty$ clearly the small $y$ limit of the
integration dominates.
Close to the singularity at $z=1$ \cite{MathematicaREF}
\begin{equation}
\mbox{Li}_{1/2}(z) \simeq \sqrt{ { \pi \over 1- z} } + \zeta(1/2) + \cdots,
\label{eq48zeta}
\end{equation}
where $\zeta(.)$ is the Riemann zeta function. Indeed
to obtain the leading term (which will eventually give the large $n$ limit of $\phi_n$)
  we replace the summation with integration in the definition of
the Polylog function $\mbox{Li}_{1/2}(z)$  using
\begin{equation}
\sum_{k=1} ^\infty { z^k \over  \sqrt{k}} \simeq \int_0 ^\infty {{\rm d} k \over \sqrt{k} }  e^{ k \ln (z) } = \sqrt{\pi}\left[-\ln(z)\right]^{-1/2}  \simeq \sqrt{ \pi \over 1 - z },
\label{eq48ll}
\end{equation}
where $z<1$.
We use $z=1 + y \pm i \epsilon$, where the choice of sign depends on the path evaluated, namely ${\cal I}_{\pm}$. In the limit of small $y$, corresponding to large $n$,
we find, using Eq. (\ref{eq48zeta}),
\begin{equation}
\mbox{Li}_{1/2} \left(1 + y \pm i \epsilon\right) \simeq
\sqrt{{ \pi \over - y \mp i \epsilon}}\sim \sqrt{{\pi \over y e^{\mp i \pi}}}=
 \pm i \sqrt{{\pi \over y}}.
\label{eq49}
\end{equation}
Given that $\ln( - 1 - y +i \epsilon) = \ln(1+y) + i \pi$ when $\epsilon \to 0$,
\begin{equation}
{\cal I}_{+} = \int_0 ^\infty \exp\left\{ - (1 + n) \left[\ln(1 + y) + i \pi\right]\right\}
{ -i \sqrt{\pi/y } \over
\pi  -i \sqrt{\pi/y } }
{\rm d} y .
\label{eq50}
\end{equation}
Clearly $\exp[ - (1 +n ) i \pi] = (-1)^{n+1}$, and  approximating
 $(1+n)\ln(1+y) \sim n y$
in the exponential in the integrand in Eq. (\ref{eq50}),
an approximation
 valid in the limit of large $n$ since then only small $y$ contributes
 to the integration, and finally Taylor
expanding
$ -i \sqrt{\pi/y } / [
\pi  -i \sqrt{\pi/y } ] \sim 1 - i \sqrt{\pi y}$ we find
\begin{equation}
{\cal I}_{+} \sim (-1)^{n+1}
\int_0 ^\infty \exp( - ny) \left( 1 - i \sqrt{ \pi y} + \cdots\right) {\rm d} y.
\label{eq51}
\end{equation}
The integral yields
\begin{equation}
{\cal I}_{+}  \sim (-1)^{n + 1} \left( {1 \over n} - i {\pi \over 2 n^{3/2} } \right).
\label{eq52}
\end{equation}
The calculation of ${\cal I}_{-}$ follows the same  steps
\begin{equation}
{\cal I}_{-} \sim (-1)^{n+1} \left(-{1\over n}  - i {\pi \over 2  n^{3/2}} \right).
\label{eq53a}
\end{equation}
Finally,
using Eq. (\ref{eq46})
\begin{equation}
\phi_n \sim{ (-1)^n \over 2 n^{3/2} }.
\label{eq53}
\end{equation}
This solution exhibits odd/even oscillations with an overall decay
of a power law. The probability of finding the particle
after $n$ attempts goes like $F_n\sim 4^{-1} n^{-3}$. Hence
it does not exhibit oscillations, but that is merely due to our
choice of sampling rate $\gamma \tau=\pi/2$ as we now show.
In Fig. \ref{figsingle}, a very nice agreement between
Eq. (\ref{eq53}) and the exact solution is seen
already for not too large
$n$.

\begin{figure}
\centering
\includegraphics[width=0.39\textwidth]{integral_path}
\caption{
Integration path for the calculation of $\phi_n$
in the complex plane
bypasses  two branch cuts (dashed lines).
Integration along four lines just above and below the two dashed lines
is explained in the text, while the integration around the outer circle does not
contribute in the limit of an  infinite radius.
 When $2 \gamma \tau= k \pi$ the two branch cuts merge $(k=0,1,\cdots)$.
}
\label{fig1path}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=0.49\textwidth]{inf_lattice_tau_03pi_comparison}
\caption{
$F_n$ versus $n$ for the rational  sampling time
$\gamma \tau /\pi=1/3$. Now the
detection probability $F_n$
 decays monotonically like $n^{-3}$ with a superimposed
periodic oscillation.  The lines are the asymptotic theory
Eq.
(\ref{eqGen11})
 which for large $n$
nicely match the exact expression (dots).
}
\label{fig1patha}
\end{figure}

\subsubsection{First detection statistics in $1d$ for an open system}

 We now investigate  $\phi_n$  for sampling time
 $0<\gamma \tau<\pi$ with $\gamma \tau\neq \pi/2$,
sticking to the case where
the origin of the quantum walk is also the location where the
particle is detected.  We find the large $n$ limit of
$\phi_n$  using
\begin{equation}
\phi_n \sim {1 \over 2 \pi i}
\oint_C z^{-n -1} {I_{\gamma \tau} (z) \over 1 + I_{\gamma \tau} (z) } {\rm d} z
\label{eqGen01}
\end{equation}
and similar to the previous sub-section the large argument limit of the Bessel
function
Eq. (\ref{eq42})
gives
\begin{equation}
I_{\gamma \tau} (z) = \sum_{n=1} ^\infty z^n { \cos\left( 2 \gamma \tau n - \pi/4\right) \over \sqrt{ \pi \gamma \tau n}} =
{1 \over 2 \sqrt{2 \gamma \tau}}
 \left[
e^{- i \pi/4} \sum_{n=1} {\left( z e^{2 i \gamma \tau}\right)^n \over \sqrt{n}} +
e^{ i \pi /4} \sum_{n=1} ^\infty  {\left( z e^{ - 2 i \gamma \tau}\right)^n \over \sqrt{n}} \right].
\label{eqGen02}
\end{equation}
Clearly for $z=r \exp(i \theta)$ with $\theta=2 \gamma \tau$ or $\theta=- 2 \gamma \tau$ and $r\geq 1$
either the second or first sums diverge respectively.
 Thus for $0<2 \gamma \tau<2 \pi$ we find two branch cuts
which are  shown in Fig. \ref{fig1path}. The exception is the case
treated in the previous sub-section  $2 \gamma \tau=\pi$
where the two branch cuts merge.
The integration path in the
 complex plane now avoids two branch cuts, but otherwise
the calculation is similar to the one we performed in the  previous section.
In Appendix \ref{AppSolve}
we find one of our main results
\begin{equation}
\phi_n \sim 2 \sqrt{ {\gamma \tau \over \pi n^3}} \cos\left( 2 \gamma \tau n + {\pi \over 4} \right) .
\label{eqGen10}
\end{equation}
Thus the probability of measuring the quantum walker returning to its
origin for the first time is
\begin{equation}
F_n \sim { 4 \gamma \tau \over \pi n^3} \cos^2 \left( 2 \gamma \tau n + {\pi \over 4} \right).
\label{eqGen11}
\end{equation}
This formula predicts that when $\gamma \tau/\pi$ is a rational number the
probability $F_n$ multiplied by $n^3$ is periodic. Such a behavior
is shown in Fig. \ref{fig1patha}.
In contrast, if $\gamma \tau/\pi$ is not rational, the asymptotic behavior
is quasiperiodic and appears noisy, the theory Eq. (\ref{eqGen11})
 perfectly matching the exact solution. This we demonstrate in Figs.
\ref{figNum}
for the  choice of  irrational $\gamma \tau /\pi=0.8/\pi$.

A strange aspect of Eq. (\ref{eqGen11})
is that in the limit of $2 \gamma\tau \rightarrow
\pi$ it
does not recover the result found for $2 \gamma\tau = \pi$
$F_n \sim 0.25 n^{-3}$ found in Eq.
(\ref{eq53}). Instead $\lim_{2 \gamma \tau \to \pi} F_n\sim n^{-3}$
so a factor four mismatch is found.
 This surprising result
is no doubt due to the presence of two branch cuts for the case under study,
while for $2 \gamma \tau=\pi$ we have only one.
This implies that the convergence to formula Eq. (\ref{eqGen11})
when $2 \gamma \tau \simeq \pi$  is very slow, and is reminiscent of the
behavior at the exceptional sampling time we saw for finite $L$.

 These calculations can be extended for $\gamma \tau> 2 \pi$
 and critical behavior is found
 for $\gamma \tau=k \pi/2$ with $k=1,2,\cdots$,
 since then the two branch cuts merge, and
one finds $F_n \sim k /(4 n^3)$. Otherwise  Eq.
(\ref{eqGen11}) is valid for all sampling periods $0<\gamma \tau$.

 Note that the energies on a finite  tight-binding  ring are given by
$E_k=-2 \gamma \cos(2 \pi k /L)$, as mentioned. Hence in the limit
of large $L$ we
find  a band of energies
of size $\Delta E=4 \gamma$. If we use this width in  Eq.
(\ref{eqET}) we find the exceptional sampling time $2 \gamma \tau= k\pi$.
This argument leads us to speculate that the width of the band, in an infinite system,
will determine the exceptional points that survive the $L\to \infty$ limit.

\end{widetext}

\begin{figure}
\centering
\includegraphics[width=0.49\textwidth]{semilog_tau08_line_dots_better.pdf}
\caption{
$F_n$  versus $n$ for the irrational choice of sampling rate $\gamma \tau/\pi =0.8/\pi$, for
a quantum walk on a one dimensional lattice (note the log linear scale).
The numerically exact solution (red circles)  nicely
matches the theory (the curve) already for moderate values
of $n$.
}
\label{figNum}
\end{figure}

\subsection{$1d$ Quantum walks are not recurrent, the survival
probability is highly irregular}

 The probability that the quantum walker
 will eventually be detected on its
origin is given by
$1-S_\infty=\sum_{n=1} ^\infty F_n$. Here
$S_\infty$ is the probability that the particle survived,
namely the probability that it was not detected.
For a one dimensional classical
 random walk on the integers, i.e. the binomial random walk, where the
 particle has probability $1/2$ to jump left or right,
the survival probability is zero, so eventually the
 particle is detected at its origin.
 The quantum walk in one dimension is generally non-recurrent
as previously pointed out \cite{Bach,Ambainis}.
The spreading is ballistic, not diffusive, and hence the return to the origin
is not guaranteed in an open system.

 We focus therefore on the non-trivial value of the survival
probability  $S_\infty$.
Using the  exact expressions for $F_n$ we have used Mathematica to obtain
estimation for $1-S_\infty$ using two methods.  The first is summing $F_n$
for a large value of $n$ using the exact expression for $F_n$.
More precisely, we expand
the generating function $\hat{\phi}(z)$
 in $z$ the coefficients giving $\phi_n$
up to some large vale of $n$, and hence also $F_n$.
Then we estimate the reminder using
our asymptotic large $n$ formulas.
The second method we numerically perform the integration in Eq.
(\ref{eqTot}), using Eq. (\ref{eq35}).
  Both
methods yield the same results.

 In Fig.
\ref{figFGInf} we show $1 - S_\infty$ versus $\gamma \tau$.
 For $\gamma \tau \to 0$ we get $S_\infty=0$ since
the particle starting at the origin is detected with
probability one if the measurement is made immediately
 after the release of the particle.
 Not surprisingly, when $\gamma \tau \to \infty$ $S_\infty\to 0$ (though it remains small
though finite for $\gamma \tau \simeq 10$). An unforeseen property is
the cusps in
 $1-S_\infty$, presented in the figure,
  found for $\gamma \tau = \pi k/2$ with $k=1, 2, \cdots$.
Mathematically these cusps must be related to the appearance of two branch
 cuts in the complex plane.
 The non-monotonic behavior of the probability of eventual measurement
is not something we
could have anticipated.

  For large $\gamma \tau$ we find  $F_n \propto 1/n$
for finite $n$ and $F_n \propto n^{-3}$ for large $n$,
Eqs.
(\ref{eqPPHH})
and
(\ref{eqGen11}). Matching these solutions we expect a transition to
found when  $n_{tr}= c \left(\gamma \tau\right)$ where $c$ is a constant
of order unity.
We may estimate the probability of detection as  $\sum_{n=1} ^{n_{tr}} F_n$.
Here we do not sum in the interval $(n_{tr},\infty)$ since here
$F_n$ decays like
$n^{-3}$ and hence negligible. Using Eq.
(\ref{eqPPHH}), switching from summation to integration,
we find
\begin{equation}
1 - S_\infty \simeq {\ln \gamma \tau \over 2 \pi \gamma \tau}
\label{eqSUMINT}
\end{equation}
when $\gamma \tau\gg 1$. In this rough estimation we used
$\ln \gamma \tau \gg  \ln c$. Further discussion on $S_\infty$ and a far better approximation
is provided
in Appendix D.

\begin{figure}
\centering
\includegraphics[width=0.49\textwidth]{FG_inf_Sn}
\caption{
For the one dimensional tight-binding quantum walk the
 probability that the particle
is eventually detected $1-S_\infty=\sum_{n=1} ^\infty F_n$
versus the sampling rate $\gamma \tau$ exhibits a non-monotonic behavior.
Unlike its classical random walk
counterpart, the quantum  walk is not recurrent,
 unless $\gamma \tau \to 0$, which is the
trivial case.
}
\label{figFGInf}
\end{figure}

\subsection{Transition to large system}

 For a large but finite ring of size $L$ we expect to see a
behavior similar
 to the infinite system, for intermediate times, where on the one
hand the asymptotic limit Eq.
(\ref{eqGen11})
is reached, but the particle still does
not sense the finiteness of the system. This behavior is presented
in Fig.
\ref{fig4} for a ring with $L=100$ sites. At first $F_n$ decays
as for the infinite system with the same sampling rate (see
 Fig. \ref{fig4ex}).
However, at least in this example, roughly at $n \simeq 70$ we see a sudden
increase in $F_n$. This is a non-classical behavior;
for a classical random walk on a large ring the survival probability has a power-law decay for intermediate times, crossing over to an exponential decay for long times.
 The significant increase in $F_n$ is due to a partial revival
at the origin, a non-classical effect, and is obviously related to the ballistic
nature of the quantum walk.
The precise nature of this transition merits further study.

\begin{figure}
\centering
\includegraphics[width=0.49\textwidth]{L_100_Fn}
\caption{
Quantum walk on a ring with
 $L=100$ sites for a sampling rate $\gamma \tau=0.6$ with detection at the
origin of the walk.
For small $n$ the system exhibits a behavior similar to that of an infinite system
(see Fig. \ref{fig4ex}). Roughly at $n=70$, there is a
sudden increase in $F_n$,
probably due to a partial revival of the packet at the origin.
}
\label{fig4}
\end{figure}

\begin{figure}
\centering
\includegraphics[width=0.49\textwidth]{L_inf_Fn}
\caption{
Same as Fig. \ref{fig4} for an infinite system.
}
\label{fig4ex}
\end{figure}

\section{Other approaches and some connections}
\label{secOTHER}

 Krovi and Brun \cite{Brun06,Brun07} derived a
general expression for the average hitting
time $\langle n \rangle$  for discrete quantum walks.
Their formalism is based on a trace formula for a density matrix, while we
relate the statistics of the first detection event to the
wave function free of measurements. They also point out to the possibility
of an  infinite average hitting times on finite graphs. This theme
is important in the context of the efficiency of search. A classical
random walker, on a finite graph, always finds the target (assuming the walk
is ergodic). In that sense a classical walk is very efficient since
it will always reach its target. On the other hand, a  classical walk
tends to explore territory previously visited, so the time it takes
to reach the target is relatively long. Quantum walks
are considered faster, if compared to classical walks, in the
sense that they scale ballistically. However, as we showed
for the simple benzene ring geometry,
the average hitting time (for specific initial conditions) may diverge.
It implies that
one cannot categorically say that quantum search, in the average
hitting time sense, is more efficient than the classical counterpart.
However,  for the ring geometry,
and for initial condition on the origin, Eq.
(\ref{eqKRSL})
 shows that the average $\langle n \rangle$  scales with the size of system,
which is a ballistic feature of the search, not a diffusive one.
It should be noted that diverging $\langle n \rangle$ for finite systems are found here for the stroboscopic measurement under investigation. The latter has
many advantages, for example in revealing quantum periodicities,
 but if the goal is to detect the particle with probability one,
 measurements
on times drawn from a Poisson process should be more efficient \cite{Brun08}.

As mentioned in the introduction the quantum first passage time question is controversial
in the sense that one has many approaches to the problem.
One way to treat the quantum first passage time problem,
is by adding a non-Hermitian term to the Hamiltonian \cite{Krap}.
 Briefly the non-Hermitian approach leads
to the non-conservation of the  normalization of the wave function,
which can be interpreted
as the survival probability of the particle.
This  approach  was shown to be related to the projective measurement
method in the limit of small finite $\tau$ \cite{Dhar,Dhar1}.
It is an interesting question however whether
the non-Hermitian approach can predict the behaviors found in this manuscript,
for example Eq. (\ref{eqGen11}).
Especially important is whether
the limits of large $n$  and small $\tau$ commute, an issue
left
to future research.

Dhar et al. \cite{Dhar,Dhar1}, after laying the
 general framework to the problem,
including introducing the fundamental concept of the wave function $\phi_n$,
 investigated
the limit of small $\tau$. In this sense
the problem is investigated close to the
Zeno limit. The stroboscopic sampling for finite
$\tau$  investigated herein allows for revivals, critical sampling, and other special quantum
effects which are  clearly missed in this Zeno limit.
They \cite{Dhar,Dhar1} use a perturbation theory
and  derive an effective Hamiltonian
where the effects of the failed prior detections
are  included as a non-Hermitian part of the Hamiltonian.
 That method together with numerical simulations
 predicts, for a specific initial
condition and a finite sized system,  that the survival probability has a power law decay of
$-1/2$ or $-3/2$. This is an interesting observation since it
shows that in some cases
 half integer exponents control the decay of the survival probability, while so far we have found only integer values.
 We have verified
 results obtained by Dhar et al. using the
generating function formalism with exact numerical method (not shown).
Oscillations or anomalous measurement periods are not apparent under the restriction of small $\tau$.
It might be possible,
to prove analytically,
that in the small $\tau$ limit, one detects transients different from
our prediction for $F_n$
Eqs.
(\ref{eq53},
\ref{eqGen10}). As mentioned, the oscillating power-law
 tails of $F_n$  vanish when $\tau\to 0$,
and hence correction terms become very important when $\tau$
is small. In other words, perhaps there are two universality classes
of exponents for quantum random walks. The current picture is that we have
four exponents $1$, $3$, $1/2$ and $3/2$ which depend on the initial
position, the value of $\tau$,  and the geometry.

Another approach suggests the use of the classical renewal equation, derived by
Schr\"odinger \cite{Schro} long before the appearance of wave mechanics in
the context of the first passage time of a Brownian motion, to investigate
also the
 quantum first passage time problem
 \cite{Lumpkin,Ranjith}.
This approach seems very different than ours,
since it does not take into consideration the effect of measurement,
and  it uses probabilities instead of amplitudes to
describe the quantum statistical aspects of the first passage  problem.

 In \cite{Stefanak} a discarding system  method
was used
for  the problem of recurrence of quantum walks.
These authors investigated
 an ensemble of identically prepared systems and suggested
the following measurement procedure. After one time step measure the occupancy
of the particle at the origin (the outcome is a binary yes/no answer)
 and then discard the system.
Take a second identically prepared second system
and let it evolve for two time steps, measure at the origin and again
discard the system. Continue similarly for a long time.
One then constructs the probability of measurement at the origin,
for times $t=1,2,...$. In this way one may define a P$\hat{\mbox{o}}$lya number,
which in classical random walks gives the criterion whether
a random walk
is transient or recurrent. This approach is of course very different than ours.
 As pointed out in Ref.  \cite{Stefanak},
one can imagine several approaches to the problem of recurrence
of a quantum random walker.

{\bf Historical remark.}
Eq. (10) in Ref.  \cite{Muga} is the renewal equation for classical
 random walks after which  the author writes:
``The equation was proposed by Schr\"odinger in terms of cumulative probabilities
."
A minor historical remark is that
a  close look at the original publication
 \cite{Schro} does not reveal an explicit equation.
However, translating the original work to English reveals that indeed
the origin of the renewal equation is in that classic paper.
In Appendix B of \cite{Muga}
Muga and Leavens mention
 a quantum renewal equation, their conclusion is that
this equation (which is not at all related to ours)
is not valid.

\section{Summary }

The quantum first detected passage time problem
 rests on two fundamental
postulates of quantum reality. The first is the
 Schr\"odinger equation and the second is the projective measurement
postulate. The latter is the fifth postulate listed in \cite{CT}
which states that immediately after the measurement the state of the
system is a normalized projection of $|\psi\rangle$, where
$|\psi\rangle$ is the state function of the system just prior to the measurement.
Without these assumptions, the first tested in many experiments but
the second in far fewer,  quantum theory is not complete.
Our goal, following \cite{Dhar}  was not to question basic physical
 assumptions,
but rather show how these postulates lead to the solution of the
first detection  problem.

The quantum renewal equation (\ref{eq15}) and the $Z$ transforms
Eqs. (\ref{eqRed06},
\ref{eqRed06aa})
give
a rather general relation between the amplitude of first detection $\phi_n$
and the wave function of the system free of measurement $|\psi_f\rangle$.
In that sense the problem of first detection
reduces to the solution of the
 Schr\"odinger
  equation,
e.g. the determination of the energy spectrum. In particular,
similar to the corresponding classical first passage  problems,
the generating function is a powerful
 tool with which we can attain many insights.

We have illustrated several surprising features, both for closed
systems, like rings and for open systems. Generally the quantum first detection problem exhibits behaviors very different than classical, but still some
relations remain. For example for a classical random walk on an infinite
line,  the first passage
PDF decays like $n^{-3/2}$, similarly the corresponding
quantum amplitude
(neglecting the oscillations) gives  $\phi_n \sim n^{-3/2}$ [see
Eqs.
(\ref{eq53},
\ref{eqGen10})].
However the quantum problem exhibits rich behaviors, which are related to the sampling rate $\gamma \tau$,
including oscillations of $F_n$ superimposed on the power law decay,
the Zeno effect when $\tau \to 0$ and a surprising critical behavior when
$\gamma \tau=k\pi/2$. Thus the
first detection problem is critically sensitive to the sampling rate even
for an infinite
system and even in the large $n$ limit. Of course for real systems
this conclusion can be reached only if the coherence is
maintained for long times.
Another notable result is the non-analytical behavior
of the survival probability $S_\infty$
 as we tune $\gamma \tau$,
see Fig. \ref{figFGInf}.
This should be compared
with the classical result where the final probability of detecting
the particle in one dimension is unity.

For a finite system like a ring, we find strong sensitivity to
the initial condition: for an initial
condition starting on the origin $x=0$,
which is also the detected site,
the  average number of detection attempts $\langle n \rangle$,
increases  linearly  with the system size $L$, see Eq.
(\ref{eqKRSL}).
Further $\langle n \rangle$ does not depend
 on the sampling time $\tau$, besides ever present exceptional
sampling,
see Eq.
(\ref{eqET}).
 Since $\langle n \rangle \propto L$ we find
ballistic scaling of $\langle n \rangle$ compared
with diffusive scaling for the corresponding classical problem.
 However,  when starting on other initial conditions, $\langle n \rangle$
 depends crucially
on the sampling time $\tau$, in fact  $\langle n \rangle$ may
diverge as $\tau$ is tuned.
The revivals, optimal detection times, exceptional points given
by the simple formula Eq.
(\ref{eqET}),
half
dark states,  and quantization of $\langle n \rangle$ for the
$|0\rangle\rightarrow |0\rangle$ transition \cite{Grunbaum},
 describe rich behaviors even in small systems.
They also point out the advantage of stroboscopic observation
of the system, since this captures underlying quantum features.
Even for a finite sized system,
 the probability of being eventually detected is not
always unity. However, we showed that at least when starting on the
origin which is also the location of the detection, the particle
is detected with probability unity for any sampling time $\tau$,
and in that sense the quantum
walk on a finite ring or more generally a graph \cite{Grunbaum}
is recurrent.
Finally, the tools developed in this
paper can serve as starting point for many other first detection problems
and the advance of single particle first detection theory.

{\bf Acknowledgement}  We thank the Israel Science Foundation, grant number 376/12, for funding and Janos Asboth for pointing out Ref. \cite{Grunbaum}.
EB thanks Abhishek Dhar for discussions and hospitality at ICTS Campus
in Bangalore.

\newpage

\newpage

redpajama_set_name: RedPajamaArXiv