Hitting statistics from quantum jumps
A. Chia
1
, T. Paterek
2 3
, and L. C. Kwek
1 3 4 5
1
Centre for Quantum Technologies, National University of Singapore
2
Division of Physics and Applied Physics, School of Physical and Mathematical Sc iences, Nanyang Technological University, Singapore
3
Majulab, CNRS-UNS-NUS-NTU International Joint Research Unit, UMI 3654, Singapore
4
Institute of Advanced Studies, Nanyang Technological University, Singapore
5
National Institute of Education, Nanyang Technological University, Singapore
July 17, 2017
We define the hitting time for a model of continuous-time open quantum walks in terms of quantum
jumps. Our starting point is a master equation in Lindblad form, which can be taken as the quantum
analogue of the rate equation for a classical continuous-time Markov chain. The quantum jump method
is well known in the quantum optics community and has also been applied to simulate open quantum
walks in discrete time. This method however, is well-suited to continuous-time problems. It is shown
here that a continuous-time hitting problem is amenable to analysis via quantum jumps: The hitting
time can be defined as the time of the first jump. Using this fact, we derive the distribution of hitting
times and explicit exressions for its statistical moments. Simple examples are considered to illustrate
the final results. We then show that the hitting statistics obtained via quantum jumps is consistent
with a previous definition for a measured walk in discrete time [Phys. Rev. A 73, 032341 (2006)] (when
generalised to allow for non-unitary evolution and in the limit of small time steps). A caveat of the
quantum-jump approach is that it relies on the final state (the state which we want to hit) to share
only incoherent edges with other vertices in the graph. We propose a simple remedy to restore the
applicability of quantum jumps when this is not the case and show that the hitting-time statistics will
again converge to that obtained from the measured discrete walk in appropriate limits.
1 Introduction
With the advent of quantum information science and the desire to build a quantum computer, the study of quantum
algorithms have become an integral part of quantum information theory [1]. Quantum walks have played a special
role in quantum computing by providing a platform on which quantum algorithms may be analysed [2, 3]. Moreover,
they have served as a useful mechanism to describe and explain coherent transport processes in photosynthesis [4, 5]
and the breakdown of a driven system in an electric field [6]. This has in turn stimulated much experimental effort
to realise quantum walks, see e.g. Refs. [7, 8, 9, 10]. Theoretical quantum optics on the other hand has had fruitful
applications in the analyses of quantum technologies [11, 12, 13]. In this paper we will apply the well-known theory
of quantum jumps developed in quantum optics to define and calculate the distribution of hitting times in open
(i.e. non-unitary) quantum walks.
The paper is organised as follows. We first review quantum jumps and motivate its application to hitting
problems in quantum walks in Sec. 1.1. The theory of quantum walks and some existing works related to quantum
jumps are then reviewed in Sec. 1.2. We then introduce the necessary background in Sec. 2 with the presentation
of the quantum-jump formalism in Sec. 2.1, followed by our approach to continuous-time open quantum walks in
Sec. 2.2. In Sec. 3 we explain how the quantum-jump method is to be applied to quantum walks and obtain our first
result—the hitting-time distribution. Then in Sec. 4 we derive explicit expressions for the hitting-time statistics.
We then relate our result to a previous definition of the hitting time devised for a discrete-time measured walk in
Sec. 5. Here the hitting-time statistics of the discrete-time measured walk is shown to converge to the quantum-
jump approach in the continuous-time limit. A problem with the quantum-jump definition of hitting times is that
it becomes inaccurate when there are coherent transitions to the final state. We overcome this problem in Sec. 6,
1
arXiv:1608.05510v4 [quant-ph] 14 Jul 2017
SOURCE OF
PHOTONS
PHOTODETECTION
RECORD
TIME
JUMPS
NO JUMP
Figure 1: Typical scenario where quantum-jumps are applied in quantum optics. Usually an atomic system or an optical cavity
with a lossy end mirror acts as a source of photons. The output light is measured by a photodetector. It is well known in quantum
optics that the photodetection record contains information about the state of the light. The photodetection record can also be
used to gain information about the photoemissive source. References [21, 22, 23, 24] are some examples.
extending the quantum-jump approach to arbitrary graphs. We then conclude with a summary of our results
and analyses in Sec. 7 and also comment on the relationship of our work with other studies not mentioned in the
literature review of Secs. 1.1 and 1.2.
1.1 Quantum jumps—from photon counting to hitting times
The quantum-jump approach to dissipative quantum dynamics has traditionally been used for efficiently solving
master equations [14, 15, 16, 17], or calculating photon statistics in photon counting [18, 19]. It also goes by the
name of Monte Carlo wavefunctions or quantum trajectories due to the different contexts in which it was invented
(although quantum jumps correspond only to a subset of unravellings within quantum-trajectory theory
1
). We
refer the reader to Ref. [20] for a comprehensive review of how the quantum-jump method was developed. Figure
1 illustrates a typical scenario where quantum jumps are applied e.g. Refs. [21, 22, 23, 24]. There is usually a
system (described by a master equation [25]), say a lossy cavity or a two-level atom which dissipates energy into
the environment in the form of photons. The emitted photons are then measured by a photodetector. Each count,
or photodetector “click” appears as a spike in the photodetection record. The quantum-jump formalism then allows
one to compute the system evolution conditioned on a given photodetection record where each detector click is
associated with a “jump” in the system Hilbert space. Periods of no clicks then correspond to system evolution
with no jumps. The quantum-jump method states that an average over a large number of such conditioned states
will reproduce the solution to the master equation. Thus in solving the master equation, one also gains access
to the statistics of photon arrival times at the detector. Photon statistics are therefore often calculated using
the quantum-jump method [24, 26, 27]. In fact, Carmichael derived the quantum-jump method [18, 19] from the
photon-counting distribution due to Kelley and Kleiner [28]. It is this intuition between photodetector clicks and
quantum jumps that we will exploit for deriving the hitting-time statistics in quantum walks. To see this we need
to first explain what hitting times are: In quantum-walk theory the system, usually called the walker, has a Hilbert
space spanned by a countable set of orthonormal states {|ψ
n
i}
n
, called sites, nodes, or vertices. The hitting time
is defined as the time required for the walker to reach (or “hit”) some “final” state |ψ
N
i for the first time given that
initially it was at |ψ
m
i. The hitting time is a random variable since the first time that the walker arrives at |ψ
N
i
will vary from one realisation of the quantum walk to another. It therefore makes sense to speak of the average
hitting time and its higher-order statistics. We will often call the hitting-time distribution simply as the hitting
distribution for ease of reference. Similarly, hitting statistics (as in the title) refers to the statistics of hitting times.
It should be noted that the problem we have defined here has an analogue in classical Markov chains, where the
orthonormal set {|ψ
n
i}
n
is replaced by a set of probabilities. The temporal evolution of the classical walker is then
governed by a set of rate equations for the site probabilities [29] which plays the role of the master equation in
the quantum case. In fact, one of the quantum-walk models that we will discuss two paragraphs down is based on
this idea. We should also mention that hitting times are usually called first-passage times in the classical theory of
Markov chains and most areas of science where this concept appears, see e.g. Refs. [30, 31, 32].
The quantum-jump method lends itself naturally to a hitting problem because the question one is asking, starting
from the initial time, is whether the system has made a transition to the final state or not. This leads to a very
natural division of the system evolution into two types—either a transition to the final state occurred, or it has
1
We have devoted a separate discussion to the use of other unravellings in hitting problems in Sec. 7.2. If the reader is already
familiar with quantum-trajectory theory then this may be read now, but otherwise should be left till the end for the nonexperts.
2
PHOTODETECTION
RECORD
TIME
JUMPS TO
NO JUMPS
Figure 2: An example graph to illustrate the quantum-jump approach to hitting times. We place imaginary detectors that can
only detect transitions to |ψ
N
i along the edges connected to |ψ
N
i. We then lump all the detection records obtained from these
photodetectors into one record. A click in the superimposed record therefore corresponds to a transition to |ψ
N
i. This can be
described by a jump in the Hilbert space of the walker as prescribed by the quantum-jump method. When viewed as such, the
hitting time, labelled T , is therefore the time at which the first click occurs.
not, and this corresponds to a system evolution conditioned on “jumps” and “no jumps”. We illustrate this idea on
an arbitrarily chosen quantum walk in Fig. 2. The walker can move between any two vertices connected by a line,
usually called an edge (edges and vertices together form a graph as shown). We are not defining the edges precisely
for the moment but one may think of each edge as given by a completely-positive trace-preserving map, i.e. a Kraus
channel of some sort [1, 33]. Consider the hitting problem defined by the initial and final states shown as |ψ
1
i
and |ψ
N
i respectively on the graph. Imagine now that each transition on the graph emits a photon. Then we can
find out when the quantum walker will arrive at |ψ
N
i by associating photodetectors with the edges connected to
|ψ
N
i (assuming our photodetectors only measure photons emitted from transitions to |ψ
N
i). If we superimpose the
photodetection records from these detectors then we will observe an overall record shown on the right of Fig. 2. In
this case a photodetector click signifies that our walker is at |ψ
N
i, and the first such click provides the hitting time.
We will not be able to distinguish which channel the quantum walker took to reach |ψ
N
i but this does not matter
if we only care about when the walker visits |ψ
N
i. This analogy makes clear how the quantum-jump method can
be applied to calculate the distribution of hitting times in quantum walks. The theory of quantum walks is more
than two decades old so let us briefly review some of the key developments in this field and then discuss where our
work stands in relation to the literature on this topic.
1.2 Quantum walks and quantum trajectories
The concept of a quantum walk was first introduced by Aharonov and coworkers in 1993 [34]. Quantum walks can
be categorised into one of two classes—either a walk in discrete time, or a walk in continuous time [35]. Quantum
walks in discrete time follow the idea originally prosposed by Aharonov and colleagues where a quantum coin is
introduced. Classically, a random walk on a line involves a coin toss, the result of which determines whether the
walker moves one step to the left, or one step to the right. In the quantum version the coin is simply a two-state
system. The movement of the walker is then effected by a (quantum) coin toss implemented as a Hadamard gate
ˆ
C, followed by applying a shift operator
ˆ
S to change the walker’s position conditioned on the coin state [36]. Each
application of the unitary operator
ˆ
U ≡
ˆ
S
ˆ
C then evolves the walker in one time step. For a unitary quantum
walk, the notion of hitting becomes fuzzy due to the walker’s ability to be in a superposition of sites. As a result,
multiple definitions of hitting have been proposed [37, 38]. Among these, the definition of hitting based on repeated
measurements proposed by Krovi and Brun in Ref. [38] will be useful for our analysis. Applications of discrete-time
quantum walks include the design of search algorithms [39, 40], and implementing universal quantum computation
[41]. Continuous-time quantum walks on the other hand do not use a coin. Instead, the quantum walker evolves
according to a unitary operator generated by a Hamiltonian, i.e.
ˆ
U(t) = exp(−i
ˆ
Ht) with
ˆ
H parametrised by hopping
rates to adjacent nodes. Quantum walks in continuous time were first introduced by Farhi and Gutmann [42] in
close analogy to continuous-time Markov chains [42, 43]. Their hitting properties were then studied by Varbanov
and colleagues [44] who defined hitting times through jumplike weak measurements. The quantum-jump treatment
in the present paper can also be seen as a weak measurement of the walker position in that most of the time one gets
3
a null result (no jumps) which does not modify the walker state very much but once in a while a collapse (a jump)
happens which changes the walker state drastically [45]. As with the discrete-time case, continuous-time quantum
walks have also been shown to give rise to exponential speedups over classical algorithms for searching [46] and
solving black-box problems [47]. It has also been shown that universal quantum computation can be achieved using
continuous-time quantum walks [48]. Discrete-time quantum walks were then generalised to allow for non-unitary
evolution. These are known as open quantum walks and were first introduced by Attal and collaborators [49, 50].
Here the coin changes its state according to a completely-positive trace-preserving map and the evolution operator
ˆ
U for the unitary walk is also replaced by a completely-positive trace-preserving map. A continuous-time model
was subsequently proposed by Pellegrini as the continuous-time limit of the discrete-time open quantum walk [51].
Most recently, Liu and Balu proposed yet another continuous-time model of open quantum walks by starting with a
master equation in the Lindblad form [52]. This approach to defining quantum walks is in the same spirit as Farhi
and Gutmann’s for unitary walks as already alluded to above. They (Farhi and Gutmann) viewed the Schrödinger
equation as the analogue of the rate equation for probabilities in classical Markov chains. Generalising this to
allow for non-unitary dynamics naturally leads to a master equation. We also consider here continuous-time open
quantum walks described by a master equation.
Of particular interest for our work is the application of quantum trajectories in Refs. [49, 50, 51]. These works
were motivated by the fact that quantum trajectories offer an efficient means of simulating quantum walks and have
the advantage of providing a visualisation of the walk. Lardizabal and Souza have recently defined hitting times
using quantum trajectories [53], but for the discrete-time model due to Attal and colleagues [49, 50]. Given that
quantum trajectories were invented in the context of Lindblad-form master equations the latter is in fact the most
natural setting in which to consider them. For such non-unitary graphs one can therefore bypass the formalism
of positive operator-valued measures (as in Ref. [44] for example) and give a quantum-trajectory treatment of the
hitting problem. Our aim in this paper is to define the hitting time for open quantum walks as the time for the first
jump to occur and use this as the basis for calculating the distribution of hitting times and its statistical moments.
Our result also corrects Ref. [54] which claims to have calculated the average hitting time for continuous-time open
quantum walks. However, an inspection of Ref. [54] shows their model to be purely classical. A summary of the
relevant literature is given in Fig. 3.
2 Background
2.1 Quantum jumps
Here we will explain the method of quantum jumps as illustrated in Fig. 1, i.e. in the context of photon counting.
This makes the basic structure of the formalism intuitive. Assume for simplicity that the system in Fig. 1 is a
single-mode field in an optical cavity with one slightly lossy mirror. The lossy mirror allows the single-mode light to
couple to the field outside the cavity which we assume is in a vacuum state. This is described by a master equation
which has only one dissipative channel, given by
˙ρ(t) = Lρ(t) ≡ −i
ˆ
H, ρ(t)
+ ˆc ρ(t) ˆc
†
−
1
2
ˆc
†
ˆc, ρ(t)
, (1)
where ˆc =
√
γ ˆa with γ being a damping coefficient and ˆa a bosonic annihilation operator. We are using the notation
{
ˆ
A,
ˆ
B} for the anticommutator of any two operators
ˆ
A and
ˆ
B. The terms containing ˆc modify the usual unitary
dynamics (which conserves the system’s energy) to include a dissipative process (here being the loss of photons to
the vacuum outside the optical cavity). The quantum-jump formalism provides a way to understand these terms as
follows. The system state ρ(t) can evolve over an infinitesimal time interval dt conditioned on two types of detection
events—a count, and no count (Fig. 1). Given an initial state ρ(t), the probability of registering a count in the
interval [t, t + dt) is given by
℘
1
(dt) = Tr
Jρ(t)
dt = Tr
ˆc
†
ˆc ρ(t)
dt , (2)
where we have defined
Jρ ≡ ˆc ρ ˆc
†
. (3)
4
This is a natural setting to
apply quantum jumps
Aharanov + (1993)
Kempe (2003)
Krovi and Brun (2006)
Pellegrini (2014)
Liu and Balu (2017)
Our work
Attal + (2012)
Lardizabal and Souza (2016)
Farhi and Gutmann (1998)
Varbanov + (2008)
Discrete time
Continuous time
Classical
Quantum
(unitary)
Quantum
(non-unitary)
Quantum-walk model
Hitting time literature
Figure 3: Representative works of different quantum-walk models and their corresponding hitting-time proposals: Aharanov +
(1993) Ref. [34]; Kempe (2003) Ref. [37]; Krovi and Brun (2006) Ref. [38]; Farhi and Gutmann (1998) Ref. [42]; Varbanov +
(2008) Ref. [44]; Attal + (2012) Refs. [49, 50]; Lardizabal and Souza (2017) Ref. [53]; Liu and Balu (2017) Ref. [52]; Pelligrini
(2014) Ref. [51].
Here we are assuming our detector in Fig. 1 is ideal. The state change conditioned on observing a count (a spike in
the photodetection record in Fig. 1) is effected by
ρ
1
(t + dt) =
Jρ(t)
Tr
Jρ(t)
. (4)
Equation (4) is called a quantum jump and ˆc is referred to as a jump operator. A quantum jump causes ρ(t) to
change discontinuously in time.
The second type of evolution is conditioned on the event that no counts were registered in [t, t + dt). This is
commonly referred to as the no-jump evolution and occurs with probability
℘
0
(dt) = 1 − ℘
1
(dt) . (5)
The state at time t + dt conditioned on a no-count observation is
ρ
0
(t + dt) =
e
¯
Ldt
ρ(t)
Tr
e
¯
Ldt
ρ(t)
, (6)
where
¯
Lρ(t) ≡ −i
ˆ
H, ρ(t)
−
1
2
ˆc
†
ˆc, ρ(t)
. (7)
Note that ℘
0
(dt) can be written explicitly in terms of (7) as
℘
0
(dt) = Tr
e
¯
Ldt
ρ(t)
. (8)
It helps to consider two generalisations of the basic structure given by (2)–(7) for the application of quantum jumps
to quantum walks coming up later.
5
2.1.1 Generalisation 1: Non-unit detection efficiency
The above formulation assumes that every jump in the system is observed with probability one. Therefore the
first generalisation that we will consider is to allow for an non-ideal observation, or non-unit detection efficiency
where only a fraction η (between zero and one) of the jumps are actually detected [13]. This means that the
probablity of detecting a jump in time dt (when it occurs) should be (2) multiplied by η. This can be effected in
the quantum-jump approach by letting
Jρ(t) −→ J(η)ρ(t) ≡ η ˆc ρ(t) ˆc
†
. (9)
The probability of detecting a jump in the time interval [t, t + dt) is now
℘
1
(η; dt) = η Tr
ˆc
†
ˆc ρ(t)
dt . (10)
The remaining fraction of jumps that went unnoticed then contributes to the no-count evolution and we have
¯
Lρ(t) −→
¯
L(η) ρ(t) ≡ −i
ˆ
H, ρ(t)
−
1
2
ˆc
†
ˆc, ρ(t)
+ (1 − η) ˆc ρ(t) ˆc
†
. (11)
It is not difficult to show that this gives the probability of no counts in [t, t + dt) to be
℘
0
(η; dt) = Tr
e
¯
L(η)dt
ρ(t)
= 1 − ℘
1
(η; dt) , (12)
as one would expect.
2.1.2 Generalisation 2: Multiple decay channels
The second generalisation that we shall consider is to include the possibilility of multiple decay channels in the
system. Assuming there are L such channels, the master equation in (1) is generalised to
˙ρ(t) = −i
ˆ
H, ρ(t)
+
L
X
k=1
ˆc
k
ρ(t) ˆc
†
k
−
1
2
ˆc
†
k
ˆc
k
, ρ(t)
. (13)
If we now assume that each channel has a detection efficiency η
k
(k = 1, 2, . . . L), the new superoperator effecting
a jump conditioned on a detection in [t, t + dt) is given by
J(η) ρ(t) ≡
L
X
k=1
η
k
ˆc
k
ρ(t) ˆc
†
k
, (14)
where we have defined η ≡ (η
1
, η
2
, . . . , η
L
). The probability of observing a jump in any one of the L channels in
duration dt is
℘
1
(η; dt) =
L
X
k=1
η
k
Tr
ˆc
†
k
ˆc
k
ρ(t)
dt . (15)
The no-count superoperator is now
¯
L(η) ρ(t) ≡ −i
ˆ
H, ρ(t)
+
L
X
k=1
(1 − η
k
) ˆc
k
ρ(t) ˆc
†
k
−
1
2
ˆc
†
k
ˆc
k
, ρ(t)
, (16)
and the corresponding probability for no detections in the interval [t, t + dt) is
℘
0
(η; dt) = Tr
e
¯
L(η)dt
ρ(t)
= 1 − ℘
1
(η; dt) . (17)
The generalisation to multiple decay channels allows us to selectively tune the detection efficiency of channel k by
choosing a value for η
k
. In particular we can choose to ignore jumps for selected channels by setting the detection
efficiency for those channels to zero. The multichannel theory of quantum jumps with non-unit detection efficiency
has been used to show that quantum jumps are more robust to measurement inefficiencies in disproving the existence
of objective pure-state dynamical models [55]. The same formalism has also been used to study parameter estimation
from multichannel photon counting
2
[24].
2
Analogies between photon counting and quantum walks in connection to Ref. [24] are discussed further in Sec. 7.2.
6
Figure 4: Different types of edges considered in the quantum walk. (a) Coherent transition. (b) Incoherent transition. (c) Loop
(dephasing).
2.2 Open quantum walks
We now define the problem to which we would like to apply the quantum-jump formalism. Our problem can be set
up in analogous fashion to a classical Markov chain problem in continuous time. We are given a quantum system
that makes transitions between a set of discrete states
S
N
≡ {|ψ
1
i, |ψ
2
i, . . . , |ψ
N
i} . (18)
The set S
N
forms an orthonormal basis for the system. The space in which the system resides is thus spanned by
S
N
. In the language of quantum-walk theory, each state in S
N
is referred to as a vertex and the system is referred
to as a quantum walker. We shall also refer to the elements of S
N
as states, or sites.
We must therefore also define the exact manner in which the system makes transitions between different states
(analogous to specifying a transtion matrix in classical Markov chains). We assume that our system is undergoing
dynamics that can be composed from three basic processes. They are coherent transitions, incoherent population
transfer, and dephasing. These processes are represented schematically in Fig. 4 for two vertices and are explained
below.
2.2.1 Coherent transition
The ability to be in a superposition of states is what differentiates the random walk of a quantum system from a
classical one, so coherent evolution, i.e. any evolution that adds coherences to our system, is indispensable in our
theory. Coherent evolution between any two states |ψ
j
i and |ψ
k
i can be described by
d
dt
ρ(t) = −i
ˆ
H
jk
, ρ(t)
. (19)
This is the familiar unitary evolution with a Hamiltonian given by
ˆ
H
jk
= ω
j
ˆ
Q
j
+ ω
k
ˆ
Q
k
+ Ω
jk
ˆ
Q
jk
+
ˆ
Q
kj
, (20)
where ω
k
= hψ
k
|
ˆ
H
jk
|ψ
k
i is the expectation of
ˆ
H
jk
in the state |ψ
k
i, and
ˆ
Q
jk
= |ψ
j
ihψ
k
|,
ˆ
Q
j
= |ψ
j
ihψ
j
|. (21)
We are assuming
Ω
jk
= Ω
∗
jk
= Ω
kj
, (22)
so that
ˆ
H
jk
is represented by a real and symmetric matrix. We can define the rate at which coherent evolution
occurs by how quickly the transition probability varies in time under (19). The transition probability for a system
evolving according to (19) is
α
jk
(t) ≡
hψ
j
|e
−i
ˆ
H
jk
t
|ψ
k
i
2
. (23)
7
It can be shown, see e.g. [56], that this evaluates to
α
jk
(t) =
2 Ω
2
jk
ν
2
jk
1 − cos(ν
jk
t)
, (24)
where
ν
jk
=
q
(ω
j
− ω
k
)
2
+ 4Ω
2
jk
. (25)
An inspection of (24) suggests that we should define the frequency of a coherent transition between any two states
|ψ
j
i and |ψ
k
i to be ν
jk
. The symbol that we shall assign to coherent transitions is shown in Fig. 4(a).
2.2.2 Incoherent population transfer
This is a process which transfers a fraction of the population in one state to another. It is shown in Fig. 4(b) for
the case of two states with the direction of the arrow indicating the direction of population transfer. For a system
with N states, the incoherent population transfer between any two states, say |ψ
m
i and |ψ
n
i, occurring at a rate
k
mn
is described by
d
dt
ρ(t) = k
mn
D
mn
ρ(t) ≡ k
mn
ˆ
Q
mn
ρ(t)
ˆ
Q
†
mn
−
1
2
ˆ
Q
†
mn
ˆ
Q
mn
ρ(t) −
1
2
ρ(t)
ˆ
Q
†
mn
ˆ
Q
mn
. (26)
Note the order of the indices defines the direction of the process so D
mn
6= D
nm
for m 6= n. Equation (26) can be
understood by considering an arbitrary state and propagating it over an infinitesimal interval dt. For simplicity let
us consider the N = 2 scenario. The result is then most apparent if we use the matrix representation in the basis
S
2
. Assuming the process to occur with a rate k
21
and in the direction shown in Fig. 4(b) we have
ρ(t + dt) =
ρ
11
(t) − k
21
ρ
11
(t) dt
√
1 − k
21
dt ρ
12
(t)
√
1 − k
21
dt ρ
21
(t) ρ
22
(t) + k
21
ρ
11
(t) dt
, (27)
where the matrix elements of ρ(t) are abbreviated by
ρ
mn
(t) = hψ
m
|ρ(t)|ψ
n
i . (28)
From (27) we can see that a fraction of the population in |ψ
1
i has been transferred to |ψ
2
i and that this amount is
given by k
21
ρ
11
(t) dt. We can interpret ρ
11
(t) as the prior probability of finding the system in state |ψ
1
i at time
t and k
21
dt as the probability that the system will transition to |ψ
2
i during dt given that it is in |ψ
1
i at time
t. Notice that in transferring the population from |ψ
1
i to |ψ
2
i we also drive the system to a less coherent state.
This is seen in (27) as the off-diagonal terms of ρ(t + dt) are less than the off-diagonal terms in ρ(t) by a factor
of
√
1 − k
21
dt . This is the sense in which we call the process modelled by (26) incoherent population transfer.
The usual rate-equation model of continuous-time Markov chains appears as a special case of incoherent population
transfer with ρ
21
(t) = ρ
12
(t) = 0.
2.2.3 Loop (dephasing)
We saw above that incoherent population transfer leads to a reduction of the system coherences. However, a system
can also lose coherences without the simultaneous loss of populations. Such processes are called dephasing. In
general we can control how classical (or quantum) a state |ψ
n
i is by tuning its ability to share coherences with
other states in the graph. Assuming a dephasing rate of q
n
for |ψ
n
i, the corresponding equation of motion for this
process is
d
dt
ρ(t) = q
n
D
n
ρ(t) ≡ q
n
ˆ
Q
n
ρ(t)
ˆ
Q
n
−
1
2
ˆ
Q
n
ρ(t) −
1
2
ρ(t)
ˆ
Q
n
. (29)
Again, we illustrate this process for the simplest case of a two-state graph shown in Fig. 4(c). Allowing state |ψ
1
i
to dephase with a rate of q
1
, we can show that (29) changes only the system coherences by looking at the matrix
representation of an arbitrary state in S
2
:
ρ(t + dt) =
ρ
11
(t)
√
1 − q
1
dt ρ
12
(t)
√
1 − q
1
dt ρ
21
(t) ρ
22
(t)
. (30)
8
It is clear that (30) has off-diagonal elements with the same form as the off-diagonal elements in (27), but now there
is no transfer of populations. In fact, (29) is a special case of (26) when n = m, and
k
nn
≡ q
n
. (31)
That is, the population transfer is from state |ψ
n
i back to itself so we expect the population of |ψ
n
i to be unchanged.
However, we saw above that incoherent population transfer also reduces the coherences in the graph so dephasing
can be viewed simply as a loop shown in Fig. 4(c).
3 Distribution of hitting times
We are now in position to apply the quantum-jump prescription to calculate the distribution of hitting times.
Consider now a graph where each state is connected to another by either one or all of the processes shown in
Fig. 4. The question that we would like to answer is how long it takes the system (or a quantum walker) to reach
a particular state ρ
f
∈ S
N
for the first time assuming some initial state ρ
i
. This length of time is called the hitting
time. However, each time we run the quantum walk the time taken to reach ρ
f
for the first time will be different,
so the hitting time is actually a random variable. We denote the hitting time by T (ρ
f
, ρ
i
). What we would like
to know is actually the distribution of hitting times if we were to run the quantum walk on the same graph many
times. Since the hitting time here is a continuous variable, its distribution is governed by a probability density. The
hitting probability density is a function h(t; ρ
f
, ρ
i
) such that
h(t; ρ
f
, ρ
i
) dt = Pr
n
ρ(τ) = ρ
f
for τ ∈ [t, t + dt) , ρ(τ) 6= ρ
f
for τ ∈ (0, t)
ρ(0) = ρ
i
o
. (32)
We are using the notation Pr{A|B} for the probability of event A occurring given that event B has occurred and
an equation like Pr{ρ(t) = ρ
0
} is to be read as the probability of finding the system in the state ρ
0
at time t. The
hitting distribution depends on the choice of ρ
i
and ρ
f
for a given graph but once chosen they are fixed so ρ
i
and
ρ
f
are to be thought of as parameters in (32). Without loss of generality we shall define the final state as the Nth
state in S
N
as it is just a matter of labelling whereas the initial state will be left unspecified. That is
ρ
f
= |ψ
N
ihψ
N
| =
ˆ
Q
N
. (33)
Since ρ
i
and ρ
f
are fixed we will not write these out explicitly as arguments of h unless it is helpful to do so.
3.1 Derivation without dephasing
We now derive a closed-form expression for the hitting time distribution on an arbitrary graph using quantum-jump
formalism. For simplicity we first consider a graph where there are no loops, i.e. no dephasing:
d
dt
ρ(t) = Lρ(t) ≡ −
i
2
N−1
X
m=1
N−1
X
n=1
m6=n
ˆ
H
mn
, ρ(t)
+
N
X
m=1
N
X
n=1
m6=n
k
mn
D
mn
ρ(t) . (34)
Note that we have divided the sum over commutators by half to compensate for double counting. This is because
ˆ
H
mn
=
ˆ
H
nm
. In general not every state will be connected to every other state via all possible processes. When this
is the case we can simply choose which processes to switch off in (34) by setting the relevant rates zero. One may
have also noticed that the sums over the coherent transitions (the commutator terms) do not include transitions to
the final state |ψ
N
i. This is because only the incoherent transitions to |ψ
N
i are detectable in the quantum-jump
formalism. Later on (in Sec. 6) we will show how the hitting probability density can be obtained when there are
coherent transitions to |ψ
N
i by introducing an artifical dissipative channel.
In order to apply the quantum-jump technique we first note that (32) can also be rewritten using Bayes’s rule
as
h(t) dt = Pr
n
ρ(τ) =
ˆ
Q
N
for τ ∈ [t, t + dt)
ρ(τ) 6=
ˆ
Q
N
for τ ∈ (0, t) , ρ(0) = ρ
i
o
× Pr
n
ρ(τ) 6=
ˆ
Q
N
for τ ∈ (0, t)
ρ(0) = ρ
i
o
. (35)
9
Each factor on the right-hand side in (35) can now be calculated using the prescription laid out in Sec. 2.1. To do
this we map (13) directly to (34) by making the following identification
ˆc
q
q
=
p
k
mn
ˆ
Q
mn
m,n
, (36)
ˆ
H =
1
2
N−1
X
m=1
N−1
X
n=1
m6=n
ˆ
H
mn
. (37)
In terms of the multichannel theory of quantum jumps in Sec. 2.1.2, each channel is now labelled by an ordered
pair (m, n) where m = 1, 2, . . . N , and n = 1, 2, . . . N, and a quantum jump is simply the detection of a transition
between any two nodes, say |ψ
m
i and |ψ
n
i. The measurement efficiency for this quantum jump can then be labelled
by η
mn
, and is a number which corresponds to the fraction of jumps observed in the |ψ
n
i → |ψ
m
i incoherent
transition. The actual number of jumps from |ψ
n
i to |ψ
m
i will always be greater than the observed number of
jumps unless η
mn
= 1. We can then express the probability of finding the system in the final state |ψ
N
i using the
probability of detecting a jump to |ψ
N
i provided that all transitions to |ψ
N
i are monitored with unit efficiency.
This identification then dictates how we should set η
mn
for all m and n, namely that η
Nn
= 1 for any n. Transitions
to states other than |ψ
N
i are irrelevant so we simply do not monitor these transitions. Therefore we set η
mn
= 0
for every m 6= N. We must use this set of detection efficiencies in the formalism outlined in Sec. 2.1.2 in order for
it to be applicable for hitting-time calculations. This prompts us to assign a special label, η
?
, for the detection
efficiencies to be used:
η
?
⇐⇒ η
mn
= δ
mN
. (38)
The jump superoperator (14) on using (36) and (38), becomes
J(η
?
) ρ ≡
N−1
X
n=1
k
Nn
ˆ
Q
Nn
ρ
ˆ
Q
†
Nn
. (39)
An application of J(η
?
) effects an instantaneous collapse of the system to the state |ψ
N
i. From (15) and (36), the
probability of detecting a jump in time dt given ρ(t) is thus
℘
1
(η
?
; dt) = Tr
J(η
?
) ρ(t)
dt =
N−1
X
n=1
k
Nn
hψ
n
|ρ(t)|ψ
n
idt . (40)
If ρ(t) in (40) is a state where no transitions to |ψ
N
i are observed in the time interval [0, t) given some initial state
ρ(0), then (40) is exactly the first factor on the right-hand side of (35). Such a state can be directly obtained by
solving the no-jump evolution defined by (16), (36), and (37):
d
dt
¯ρ(t) ≡
¯
L(η
?
) ¯ρ(t) = −
i
2
N−1
X
m=1
N−1
X
n=1
m6=n
ˆ
H
mn
, ¯ρ(t)
+
N
X
m=1
N
X
n=1
m6=n
k
mn
(1 − δ
mN
)
ˆ
Q
mn
¯ρ(t)
ˆ
Q
†
mn
−
1
2
N
X
m=1
N
X
n=1
m6=n
k
mn
ˆ
Q
†
mn
ˆ
Q
mn
, ¯ρ(t)
. (41)
It helps to rewrite
¯
L(η
?
) ¯ρ(t) so that its meaning is more obvious. Expanding the sum containing (1 −δ
mN
) we get
¯
L(η
?
) ¯ρ(t) = −
i
2
N−1
X
m=1
N−1
X
n=1
m6=n
ˆ
H
mn
, ¯ρ(t)
+
N
X
m=1
N
X
n=1
m6=n
k
mn
ˆ
Q
mn
¯ρ(t)
ˆ
Q
†
mn
− J(η
?
) ¯ρ(t) −
1
2
N
X
m=1
N
X
n=1
m6=n
k
mn
ˆ
Q
†
mn
ˆ
Q
mn
, ¯ρ(t)
. (42)
10
It is simple to see that
N
X
m=1
N
X
n=1
m6=n
k
mn
ˆ
Q
mn
¯ρ(t)
ˆ
Q
†
mn
= J(η
?
) ¯ρ(t) +
N−1
X
m=1
N
X
n=1
m6=n
k
mn
ˆ
Q
mn
¯ρ(t)
ˆ
Q
†
mn
, (43)
and similarly
N
X
m=1
N
X
n=1
m6=n
k
mn
ˆ
Q
†
mn
ˆ
Q
mn
, ¯ρ(t)
=
N−1
X
n=1
k
Nn
ˆ
Q
†
Nn
ˆ
Q
Nn
, ¯ρ(t)
+
N−1
X
m=1
N
X
n=1
m6=n
k
mn
ˆ
Q
†
mn
ˆ
Q
mn
, ¯ρ(t)
. (44)
Substituting (43) and (44) into (42) gives
¯
L(η
?
) ¯ρ(t) = −
i
2
N−1
X
m=1
N−1
X
n=1
m6=n
ˆ
H
mn
, ¯ρ(t)
+
N−1
X
m=1
N
X
n=1
m6=n
k
mn
D
mn
¯ρ(t) +
N−1
X
n=1
k
Nn
¯
D
Nn
¯ρ(t) , (45)
where we have defined
¯
D
Nn
ρ = −
1
2
ˆ
Q
†
Nn
ˆ
Q
Nn
, ρ
. (46)
As already described at the outset, the first term in (45) describes coherent population transfer between states
other than the final state |ψ
N
i (recall Sec. 2.2.1). The second term in (45) describes incoherent transitions that
either move populations out of |ψ
N
i, or between any two states except for |ψ
N
i (see Sec. 2.2.2). The last term in
(45) is similar in form to D
mn
except that terms of the form
ˆ
Q
Nn
¯ρ(t)
ˆ
Q
†
Nn
have been removed. But these are the
terms which describe jumps to the final state. Therefore
¯
D
Nn
is a superoperator which describes how the system
evolves conditioned on no jumps to |ψ
N
i. Substituting the formal solution of (41) into (40) we thus obtain
Pr
n
ρ(τ) =
ˆ
Q
N
for τ ∈ [t, t + dt)
ρ(τ) 6=
ˆ
Q
N
for τ ∈ (0, t) , ρ(0) = ρ
i
o
=
N
X
n=1
k
Nn
hψ
n
|e
¯
L(η
?
) t
ρ
i
|ψ
n
i
Tr
e
¯
L(η
?
) t
ρ
i
dt . (47)
Note that (41) produces a trace-decreasing state, which is why we have used an overbar for the density operator
and the generator of time evolution. Following Sec. 2.1.2 we see that the norm of ¯ρ(t) is precisely the probability
of no jumps in the interval [0, t), given some initial state i.e.
Pr
n
ρ(τ) 6=
ˆ
Q
N
for τ ∈ [0, t)
ρ(0) = ρ
i
o
= Tr
e
¯
L(η
?
) t
ρ
i
. (48)
The product of (47) and (48) simply cancels the norm of ¯ρ(t) giving the final expression for the hitting probability
density as
h
t;
ˆ
Q
N
, ρ
i
=
N−1
X
n=1
k
Nn
hψ
n
|e
¯
L(η
?
) t
ρ
i
|ψ
n
i . (49)
This completes our derivation of the hitting distribution using the quantum-jump method.
3.2 Examples
We now illustrate (49) with a simple example. Consider the graph shown in Fig. 5(a). This is an example with
N = 4 so by our convention the final state is ρ
f
= |ψ
4
ihψ
4
|. We will let the initial state be ρ
i
= |ψ
1
ihψ
1
|. In Fig. 5(b),
(c), and (d), we plot the hitting distribution for various amounts of coherence between states |ψ
1
i and |ψ
2
i while
keeping other parameters constant (see figure caption for their values). We observe that as Ω
21
is increased from 5
[Fig. 5(b)] to 50 [Fig. 5(d)], the hitting distribution starts to show more and more oscillations due to the increased
11
Figure 5: Recall from Sec. 2.2.1 that a Hamiltonian, say
ˆ
H
21
is parameterised by the three numbers ω
1
, ω
2
, and Ω
21
, which
correspond to the diagonal and off-diagonal matrix elements of
ˆ
H
21
in the site basis. Here we set ω
1
= 1, ω
2
= 3, and ω
3
= 5
which are kept constant throughout. We then set the transition rates to be Ω
32
= k
42
= k
43
= 5 and change only Ω
21
whose
value is shown in the plot. Note that |ω
1
− ω
2
| 2Ω
21
, so according to (25) of Sec. 2.2.1 ν
21
≈ 2Ω
21
.
level of coherence. Classically, only incoherent transitions are permitted so hitting distributions do not exhibit
oscillations. We can see from Fig. 5(b) that for Ω
21
= 5 the oscillations in the hitting distribution are dying out and
the quantum walk is in transition to the classical regime. Furthermore, the oscillations in the hitting distribution
can actually reach zero (or near zero) at its minimum meaning that there are times at which it is impossible to find
the walker at |ψ
4
i. Again, such features would not appear in a purely classical walk since incoherent transitions
cannot produce any interference effects. For variation we show in Fig. 6 what happens when we change Ω
32
instead
of Ω
21
while keeping every other parameter constant (see the figure caption for the actual values). Like Fig. 5, the
amount of oscillations increases as Ω
32
is increased, but now this is accompanied by a lengthening of the tail of the
hitting distribution. The shape of the hitting distribution depends on the exact manner in which the probability
amplitudes for the different paths of the quantum walk interfere. A comparison of Fig. 5 with Fig. 6 illustrates that
hitting times of a given graph can be much more sensitive to one coherent transition but not others. We will have
more to say about this in Sec. 4.
3.3 Including dephasing
We obtained (49) based on (34) which does not have the dephasing processes defined in (29). The omission of
dephasing connections was simply to make the derivation easier to follow. If we include dephasing in L then the
dephasing terms will simply carry through to
¯
L(η
?
). The expression for the hitting-time probability density will still
be given by (49), just with an
¯
L(η
?
) that includes dephasing connections. Stated more formally, we can consider a
12
Figure 6: Hitting distributions for various values of Ω
32
(shown in the plots). We fix Ω
21
= 5 while keeping the remaining
parameters the same as in Fig. 5 (k
42
= k
43
= 5 and ω
1
= 1, ω
2
= 3, ω
3
= 5). Note that (c) and (d) are for identical parameters
just that (c) plots the hitting distribution for short times.
graph defined by
d
dt
ρ(t) = Lρ(t) ≡ −
i
2
N−1
X
m=1
N−1
X
n=1
m6=n
ˆ
H
mn
, ρ(t)
+
N
X
m=1
N
X
n=1
m6=n
k
mn
D
mn
ρ(t) +
N
X
n=1
q
n
D
n
ρ(t) . (50)
Note that the total number of incoherent channels in this case is given by L = N
2
and we can make the following
identification for the Lindblad operators in (13):
ˆc
q
N
2
−N
q=1
=
p
k
mn
ˆ
Q
mn
m,n
,
ˆc
q
N
2
q=N
2
−N+1
=
√
q
n
ˆ
Q
n
n
. (51)
The Hamiltonian in (13) is still given by (37). The detection efficiencies should now be set according to
η
?
⇐⇒ η
mn
= δ
mN
, n = 1, 2, . . . , L/2 . (52)
This then gives
¯
L(η
?
) ¯ρ(t) = −
i
2
N−1
X
m=1
N−1
X
n=1
m6=n
ˆ
H
mn
, ¯ρ(t)
+
N
X
n=1
q
n
D
n
¯ρ(t)
+
N−1
X
m=1
N
X
n=1
m6=n
k
mn
D
mn
¯ρ(t) +
N−1
X
n=1
k
Nn
¯
D
Nn
¯ρ(t) . (53)
13
Figure 7: Ω
32
= k
42
= k
43
= 5, Ω
21
= 50, ω
1
= 1, ω
2
= 3, and ω
3
= 5. See Fig. 5(d) for comparison.
Replacing
¯
L(η
?
) in (49) with (53) then gives the distribution of hitting times for the general graph.
The reason why adding dephasing connections to the graph does not change the form of hitting distribution as
a function of
¯
L(η
?
) is because the quantum-jump method works by detecting transitions to the final state |ψ
N
i.
Of the three types of connections that we consider, only two can induce transitions between states—coherent and
incoherent population transfer. The third type, i.e dephasing, changes only the coherences in the system. Of course
changing coherences in the graph does affect how quickly the final state is reached. That is to say, the distribution of
hitting times for a state diagram with dephasing will be a different function of t compared to one without dephasing
but otherwise identical in all respects.
For illustration we include in Fig. 7 hitting distributions for the graph with dephasing of |ψ
2
i, see Fig. 7(a). The
plots in Fig. 7 are identical to Fig. 5(d) except with various amounts of dephasing added as indicated in the plots.
Here the dephasing rate is q
2
and as we increase this rate the quantum walk becomes more classical. This can be
seen in passing from Fig. 7(b) to (d) where the oscillations which we attributed to the quantum-mechanical nature
of the walk in Fig. 5 gradually die out. This is to be expected since by increasing q
2
we are making the walk more
classical, in other words, making it more and more difficult to share coherences between |ψ
2
i and other nodes in
the graph. Next we calculate the moments of h
t;
ˆ
Q
N
, ρ
i
.
4 Hitting statistics
4.1 The nth moment
The nth raw statistical moment of the hitting time T(
ˆ
Q
N
, ρ
i
) is defined as
E
T
n
(
ˆ
Q
N
, ρ
i
)
=
Z
∞
0
dt t
n
h(t;
ˆ
Q
N
, ρ
i
) , (54)
14
where we are using the notation E[X] to mean the ensemble average of an arbitrary random variable X. Although
having the hitting-time distribution is formally equivalent to knowing the statistics of T (
ˆ
Q
N
, ρ
i
), deriving a closed-
form expression for (54) is still a nontrivial task. We will show in Sec. 4.2 that (54) evaluates to
E
T
n
(
ˆ
Q
N
, ρ
i
)
= (−1)
n+1
n!
N−1
X
m=1
k
Nm
hψ
m
|
¯
L
+
?
(n+1)
ρ
i
|ψ
m
i (55)
where we have defined the shorthand
¯
L
?
=
¯
L(η
?
) , (56)
and
¯
L
+
?
is the Moore–Penrose pseudoinverse of
¯
L
?
, defined by
¯
L
+
?
¯
L
?
¯
L
+
?
=
¯
L
+
?
,
¯
L
?
¯
L
+
?
¯
L
?
=
¯
L
?
,
¯
L
+
?
¯
L
?
†
=
¯
L
+
?
¯
L
?
,
¯
L
?
¯
L
+
?
†
=
¯
L
?
¯
L
+
?
. (57)
Note the superoperator Hermitian conjugate in (57) is defined with respect to the Hilbert–Schmidt inner product
Tr[
ˆ
X
†
ˆ
Y ] between any two bounded operators
ˆ
X and
ˆ
Y . We say an arbitrary superoperator A is Hermitian,
i.e. A = A
†
if and only if
Tr
ˆ
X
†
A
ˆ
Y
∗
= Tr
ˆ
Y
†
A
ˆ
X
∀
ˆ
X ,
ˆ
Y . (58)
The Moore–Penrose pseudoinverse always exists, is unique, and recovers the standard inverse when
¯
L
?
is invertible.
One may wonder how
¯
L
+
?
can actually be computed for a given graph. To find the pseudoinverse it will be most
convenient to use a matrix representation for
¯
L
?
. This can be accomplished by using {
ˆ
Q
mn
}
m,n
as an operator
basis, in which case the Hilbert–Schmidt inner product allows us to represent an arbitrary state ρ by a vector ρ
whose elements are ρ
mn
. Note in this representation each row of ρ is labelled by two indices so ρ is a N
2
×1 vector.
Similarly
¯
L
?
can be represented by an N
2
× N
2
matrix (
¯
L
?
) whose elements are
(
¯
L
?
)
jk,mn
= Tr
ˆ
Q
†
jk
¯
L
?
ˆ
Q
mn
. (59)
The superoperator pseudoinverse
¯
L
+
?
will then be faithfully represented by the Moore–Penrose pseudoinverse of
(
¯
L
?
), i.e. (
¯
L
+
?
) = (
¯
L
?
)
+
. Equation (59) will be useful in Sec. 4.3 when we consider simple examples. There, we will
consider one example where
¯
L
−1
?
does not exist and another where it does. This will explicitly illustrate the use of
the Moore–Penrose pseudoinverse in (55).
The two most considered hitting statistics are the average and variance. We therefore pay special attention to
these two quantities. On setting n = 1 in (55) we obtain the average hitting time:
E[T (
ˆ
Q
N
, ρ
i
)] =
N−1
X
m=1
k
Nm
hψ
m
|
¯
L
+
?
2
ρ
i
|ψ
m
i . (60)
Setting n = 2 in (55) and using the result for the average we arrive at an expression for the variance
V
T (
ˆ
Q
N
, ρ
i
)
= −2
N−1
X
m=1
k
Nm
hψ
m
|
¯
L
+
?
3
ρ
i
|ψ
m
i −
N−1
X
m=1
k
Nm
hψ
m
|
¯
L
+
?
2
ρ
i
|ψ
m
i
!
2
. (61)
Our expression for the nth moment makes the evaluation of the hitting statistics a simple and efficient procedure
given
¯
L
?
. For example, evaluating the average hitting time by setting n = 1 in (54) and evaluating the resulting
integral requires the determination of an optimal upper limit to truncate the integral in order to balance the amount
of simulation time and numerical precision. In particular, when h(t) has a long tail, the calculation of the average
hitting time via (54) can be cumbersome. Equation (60) has the advantage that it avoids these issues.
4.2 Proof of the nth moment
To derive (55) we consider the moment-generating function M
T
(x) defined by
M
T
(x) = E
e
xT
. (62)
15
Given M
T
(x), all higher-order moments of T can be calculated as
E
T
n
=
d
n
dx
n
M
T
(x)
x=0
. (63)
A formula for M
T
(x) is simple to derive by substituting the expression for h(t;
ˆ
Q
N
, ρ
i
) from (49) into (62). We
obtain
M
T
(x) =
N−1
X
m=1
k
Nm
hψ
m
|
Z
∞
0
dt e
(x +
¯
L
?
)t
ρ
i
|ψ
m
i (64)
=
N−1
X
m=1
k
Nm
hψ
m
|
x +
¯
L
?
−1
h
e
(x +
¯
L
?
)t
∞
0
ρ
i
|ψ
m
i (65)
=
N−1
X
m=1
k
Nm
hψ
m
|
x +
¯
L
?
−1
lim
t→∞
e
xt
e
¯
L
?
t
−
ρ
i
|ψ
m
i . (66)
Here we are using for the superoperator identity. We now need to evaluate the t −→ ∞ limit in (66). To do so
we first note that
lim
t→∞
e
¯
L
?
t
ρ
i
= 0 . (67)
This simply says that the steady state for the dynamics defined by the generator
¯
L
?
is the zero state (represented
by a matrix with all elements equal to zero). We can prove this by showing that (45) produces a trace-decreasing
density operator. It is simple to check from (26) that D
mn
is a traceless superoperator:
Tr
D
mn
ρ
= 0 , ∀ m, n . (68)
It is also simple to see that the trace of a commutator is always zero. Therefore taking the trace of (45) we get
d
dt
Tr
¯ρ(t)
=
N−1
X
m=1
k
Nm
Tr
¯
D
Nm
¯ρ(t)
(69)
= −
1
2
N−1
X
m=1
k
Nm
Tr
ˆ
Q
†
Nm
ˆ
Q
Nm
¯ρ(t)
. (70)
The traces on the right-hand side are positive since they are averages of positive operators in the state ¯ρ(t). They
are in fact just the diagonal elements of the unnormalised density operator ¯ρ(t). Since the rates k
Nm
must also be
positive for every value of m, Tr[¯ρ(t)] has a negative rate of change, which means that ¯ρ(t) will eventually decay
to zero. We now assume the evolution under exp(
¯
L
?
t) dominates over exp(xt) [i.e. the approach to zero under
exp(
¯
L
?
t) is faster than the rise of exp(xt)] then the t −→ ∞ limit can be dropped to give
M
T
(x) = −
N−1
X
m=1
k
Nm
hψ
m
|
x +
¯
L
?
−1
ρ
i
|ψ
m
i . (71)
It is easy to see that
d
n
dx
n
x +
¯
L
?
−1
= (−1)
n
n!
x +
¯
L
?
−(n+1)
. (72)
Using (63) we therefore arrive at
E
T
n
(
ˆ
Q
N
, ρ
i
)
= (−1)
n+1
n!
N−1
X
m=1
k
Nm
hψ
m
|
¯
L
−(n+1)
?
ρ
i
|ψ
m
i . (73)
16
We assumed that
¯
L
?
has an inverse in our proof and it is natural to ask what if
¯
L
−1
?
does not exist? If the inverse
of
¯
L
?
does not exist then one can replace
¯
L
−1
?
by
¯
L
+
?
, the Moore–Penrose pseudoinverse. As mentioned in Sec. 4.1,
¯
L
+
?
always exists, is unique, and coincides with
¯
L
−1
?
if it can be found. The replacement of
¯
L
−1
?
by
¯
L
+
?
in (73) then
gives (55). Equations (60) and (61) are obtained from (55) which we have derived using the moment-generating
function but they should also be derivable by directly doing the integral in (54) with n = 1 and n = 2 respectively.
We show that this is indeed possible in Appendices A and B, which serve as independent proofs for the mean and
variance of the hitting time. Let us now illustrate how these results work with a few simple examples below. We
consider only the mean and variance of T .
4.3 Examples
4.3.1 Example 1: An absorbing state for N = 2
For our first example we consider the case of a simple incoherent transition between two states shown in Fig. 8 with
k
12
= 0. It is clear that |ψ
2
i is an absorbing state and we will see that our hitting statistics says so as well. The
graph is defined by
Lρ(t) = k
21
ˆ
Q
21
ρ(t)
ˆ
Q
†
21
−
1
2
ˆ
Q
1
ρ(t) −
1
2
ρ(t)
ˆ
Q
1
, (74)
where we have used
ˆ
Q
†
21
ˆ
Q
21
=
ˆ
Q
1
. The average and variance of T(
ˆ
Q
2
, ρ
i
) according to (60) and (61) are thus
E[T (
ˆ
Q
2
, ρ
i
)] = k
21
hψ
1
|
¯
L
+
?
2
ρ
i
|ψ
1
i , (75)
V[T (
ˆ
Q
2
, ρ
i
)] = −2 k
21
hψ
1
|
¯
L
+
?
3
ρ
i
|ψ
1
i −
k
21
hψ
1
|
¯
L
+
?
2
ρ
i
|ψ
1
i
2
. (76)
This then gives
¯
L
?
as
¯
L
?
ρ(t) = −
k
21
2
ˆ
Q
1
ρ(t) + ρ(t)
ˆ
Q
1
. (77)
Using (59) the matrix representing
¯
L
?
reads:
(
¯
L
?
) =
−k
21
0 0 0
0 −k
21
/2 0 0
0 0 −k
21
/2 0
0 0 0 0
. (78)
This is clearly not an invertible matrix since the last row has only zeros. However, it has a Moore–Penrose
pseudoinverse given by the same matrix with the first three diagonal entries inverted. In operator form we have
¯
L
+
?
ρ = −k
−1
21
ˆ
Q
1
ρ
ˆ
Q
1
+ 2
ˆ
Q
1
ρ
ˆ
Q
2
+ 2
ˆ
Q
2
ρ
ˆ
Q
1
. (79)
Repeated application of (79) then gives
¯
L
+
?
2
ρ
i
= k
−2
21
ˆ
Q
1
ρ
i
ˆ
Q
1
+ 4
ˆ
Q
1
ρ
i
ˆ
Q
2
+ 4
ˆ
Q
2
ρ
i
ˆ
Q
1
, (80)
¯
L
+
?
3
ρ
i
= − k
−3
21
ˆ
Q
1
ρ
i
ˆ
Q
1
+ 8
ˆ
Q
1
ρ
i
ˆ
Q
2
+ 8
ˆ
Q
2
ρ
i
ˆ
Q
1
. (81)
Taking the average of (80) and (81) against |ψ
1
i we get
hψ
1
|
¯
L
+
?
2
ρ
i
|ψ
1
i =
1
k
2
21
ρ
11
, hψ
1
|
¯
L
+
?
3
ρ
i
|ψ
1
i = −
1
k
3
21
ρ
11
, (82)
where we have defined ρ
mn
= hψ
m
|ρ
i
|ψ
n
i. The average and variance of T (
ˆ
Q
2
, ρ
i
) according to (75) and (76) are
thus
E
T (
ˆ
Q
2
, ρ
i
)
=
1
k
21
ρ
11
, (83)
V
T (
ˆ
Q
2
, ρ
i
)
=
1
k
2
21
(2ρ
11
− ρ
2
11
) . (84)
17
PHOTODETECTION
RECORD
TIME
Figure 8: A simple example with N = 2. We are concerned with the hitting time for state |ψ
2
i so we are only detecting the
|ψ
1
i −→ |ψ
2
i transition.
Note the mean and variance are independent of any initial coherences in the graph so the random walk is classical.
This can be expected because incoherent transitions do not couple the site populations to its coherences [see (27)
of Sec. 2.2.2]. For ρ
i
= |ψ
1
ihψ
1
| we have ρ
11
= 1 and
E
T (
ˆ
Q
2
,
ˆ
Q
1
)
=
1
k
21
, V
T (
ˆ
Q
2
,
ˆ
Q
1
)
=
1
k
2
21
. (85)
This says the average amount of time we would have to wait to see the walker reach |ψ
2
i starting at |ψ
1
i is the
inverse of the incoherent transition rate and this has a spread equal to the square of the mean as expected. If on
the other hand ρ
i
= |ψ
2
ihψ
2
|, then ρ
11
= 0, and we obtain
E[T (
ˆ
Q
2
,
ˆ
Q
2
)] = V
T (
ˆ
Q
2
,
ˆ
Q
2
)
= 0 . (86)
When the initial and final states coincide, i.e. ρ
f
= ρ
i
, the quantity T (ρ
i
, ρ
i
) is known as the recurrence time of ρ
i
[29]. It is the time taken by a walker starting at ρ
i
to return to it. If ρ
i
has an infinite recurrence time then it is
referred to as a null-recurrent state, and positive recurrent if its recurrence time is finite. An absorbing state ρ
i
can
thus be seen as a special case of a positive-recurrent state with zero recurrence time since the walker never leaves
ρ
i
. This is precisely what (86) says. The variance should also be zero as there should be no spread in the recurrence
time of an absorbing state. Although simple, this example illustrates the fact that we actually just require the
inverse of the nonzero block in
¯
L
?
that describes the transitions between |ψ
1
i and |ψ
2
i. The reason why the last
row (and column) in
¯
L
?
is zero is simply because there are no transitions out of |ψ
2
i.
4.3.2 Example 2: A recurrent state for N = 2
We contrast the example above with the graph shown in Fig. 8 where another incoherent transition from |ψ
2
i to
|ψ
1
i has been added. In this case we modify (77) to
¯
L
?
ρ(t) = −
k
21
2
ˆ
Q
1
ρ(t) + ρ(t)
ˆ
Q
1
+ k
12
ˆ
Q
12
ρ(t)
ˆ
Q
†
12
−
1
2
ˆ
Q
2
ρ(t) −
1
2
ρ(t)
ˆ
Q
2
. (87)
The matrix representation of
¯
L
?
can be shown to be
(
¯
L
?
) =
−k
21
0 0 k
12
0 −(k
21
+ k
12
)/2 0 0
0 0 −(k
21
+ k
12
)/2 0
0 0 0 −k
12
. (88)
It is clear that (
¯
L
?
) has linearly independent columns. Therefore
¯
L
?
has a standard inverse which in operator form
is given by
¯
L
−1
?
ρ = −
k
−1
21
ˆ
Q
1
+ 2 (k
12
+ k
21
)
−1
ˆ
Q
1
ρ
ˆ
Q
2
+ 2 (k
12
+ k
21
)
−1
ˆ
Q
2
ρ
ˆ
Q
1
+ k
−1
12
ˆ
Q
2
ρ
ˆ
Q
2
. (89)
18
As before, repeated application of (89) gives
¯
L
−2
?
ρ
i
= −
k
−2
21
ˆ
Q
1
+ (k
12
k
21
)
−1
ˆ
Q
12
ρ
i
ˆ
Q
†
12
+ 4 (k
12
+ k
21
)
−2
ˆ
Q
1
ρ
i
ˆ
Q
2
+ 4 (k
12
+ k
21
)
−2
ˆ
Q
2
ρ
i
ˆ
Q
1
+ k
−2
12
ˆ
Q
2
ρ
i
ˆ
Q
2
, (90)
¯
L
−3
?
ρ
i
= −
k
−3
21
ˆ
Q
1
+ (k
−1
12
k
−2
21
+ k
−2
12
k
−1
21
)
ˆ
Q
12
ρ
i
ˆ
Q
†
12
+ 8 (k
12
+ k
21
)
−2
ˆ
Q
1
ρ
i
ˆ
Q
2
+ 8 (k
12
+ k
21
)
−2
ˆ
Q
2
ρ
i
ˆ
Q
1
+ k
−3
12
ˆ
Q
2
ρ
i
ˆ
Q
2
. (91)
Substituting these into (75) and (76) and simplifying we get
E
T (
ˆ
Q
2
, ρ
i
)
=
1
k
21
ρ
11
+
1
k
21
+
1
k
12
ρ
22
, (92)
V
T (
ˆ
Q
2
, ρ
i
)
=
1
k
2
12
2ρ
22
− ρ
2
22
+
1
k
2
21
. (93)
Looking at Fig. 8, we can see that if ρ
i
= |ψ
1
ihψ
1
| then we would expect the average hitting time to be identical to
the case without the transition from |ψ
2
i to |ψ
1
i. This is indeed what we find on setting ρ
11
= 1 and ρ
22
= 0 in
(92) and (93). If instead we now set ρ
i
= |ψ
2
ihψ
2
| so that ρ
11
= 0 and ρ
22
= 1, we obtain the mean and variance
for the recurrence time of |ψ
2
i,
E
T (
ˆ
Q
2
,
ˆ
Q
2
)
=
1
k
21
+
1
k
12
, V
T (
ˆ
Q
2
,
ˆ
Q
2
)
=
1
k
2
21
+
1
k
2
12
. (94)
Intuitively we would say the round trip time T (
ˆ
Q
2
,
ˆ
Q
2
) should be the sum of the hitting times for each direction:
T (
ˆ
Q
2
,
ˆ
Q
2
) = T (
ˆ
Q
1
,
ˆ
Q
2
) + T (
ˆ
Q
2
,
ˆ
Q
1
) . (95)
Taking the average of (95) then reproduces the average in (94). Physically we also expect T (
ˆ
Q
1
,
ˆ
Q
2
) to be inde-
pendent of T (
ˆ
Q
2
,
ˆ
Q
1
), so taking the variance of (95) we get V[T (
ˆ
Q
1
,
ˆ
Q
2
)] + V[T (
ˆ
Q
2
,
ˆ
Q
1
)] which is precisely the
variance seen in (94).
4.3.3 Example 3: Effects of coherence for N = 4
So far we have only illustrated our formula for the average hitting time for the simplest of examples—graphs
with only incoherent transitions and with the minimum number of nodes. Although they are oversimplified, these
examples allow us to get a handle on (60) by using our intuition from classical random walks. Now that we are
somewhat more comfortable with (60) we consider a more nontrivial example. We return to the graph discussed in
Fig. 5(a) and examine how different amounts of coherence in the graph can change the average of T (
ˆ
Q
4
,
ˆ
Q
1
). We
have deliberately chosen the graph parameters so they match those used in Fig. 5. The parameters which are held
constant have their values shown in the caption of Fig. 9.
In Fig. 9(a) we plot the average hitting time as a function of Ω
21
for three different values of Ω
32
[corresponding
to the three values chosen in Fig. 5(b), (c), and (d)]. It can be seen from Fig. 9(a) that the average hitting times
all behave, qualitatively the same as Ω
21
is varied for the three values of Ω
32
considered: They all start at infinity
at Ω
21
= 0, decay to some minimum, and then increase again to some constant value. From Fig. 5(a) we see
that if Ω
21
= 0 then |ψ
1
i becomes an absorbing state and the quantum walker stays at its initial position forever.
This is why E[T (
ˆ
Q
4
,
ˆ
Q
1
)] −→ ∞ as Ω
21
−→ 0. Thus as we increase Ω
21
from zero, we allow the quantum walker
to access the rest of the graph and the average hitting time must drop from infinity. In particular it reaches the
minimum when there is non-negligible population in both states |ψ
2
i and |ψ
3
i. Increasing Ω
21
further makes the
|ψ
1
i ←→ |ψ
2
i transition dominant which leads to a small probability of finding the walker in |ψ
3
i. Hence when
Ω
21
Ω
32
, essentially all first transitions to the final state are from |ψ
2
i and the hitting time becomes independent
of the actual values of Ω
21
and Ω
32
.
A much less trivial feature is present in Fig. 9(b). This time we fix the value of Ω
21
and plot the hitting time
as a function of Ω
32
. Again, all the curves are qualitatively the same and show that Ω
32
Ω
21
also increases
the hitting time and can even make it diverge. We emphasise that diverging hitting times are a purely quantum
phenomenon as a classical walker always reaches the final state in a finite time (assuming of course that there are
19
Figure 9: The average hitting time for the graph in Fig. 5 with the parameter values k
42
= k
43
= 5, ω
1
= 1, ω
2
= 3, and ω
3
= 5.
(a) We set Ω
32
= 5, 20, 50 as shown and change only Ω
21
. (b) Ω
21
= 5, 20, 50.
no absorbing states). We can shed some light on this quantum effect by solving the eigenvalue problem of the
Hamiltonian driving the |ψ
1
i ←→ |ψ
2
i and |ψ
2
i ←→ |ψ
3
i transitions. Since ω
1
, ω
2
, and ω
3
are of the same order,
let us assume they are all equal to zero for simplicity. In this case one can easily show that for Ω
32
Ω
21
the state
|ψ
1
i becomes the eigenstate of the Hamiltonian and hence it is a stationary state. In other words, by increasing
the rate of coherent transitions |ψ
2
i ←→ |ψ
3
i we are trapping the population in the initial state |ψ
1
i, and thereby
increasing the hitting time. This new mechanism leading to diverging hitting times should be contrasted with two
other mechanisms known previously in the context of measured quantum walks [44]: (i) When the measurement
frequency tends to zero (since the walk is essentially not measured at all the hitting time tends to infinity); (ii)
when the measurement frequency tends to infinity (quantum Zeno effect freezes the population in the initial state).
5 Comparison with a discrete-time measured walk
5.1 Generalised Krovi–Brun definition
There are a few noteworthy differences between what we have considered thus far and what is usually considered in
the standard theory of quantum walks: First, much of quantum-walk theory considers only closed systems i.e. sys-
tems undergoing unitary evolution whereas the theory presented here allows for non-unitary evolution (although
open quantum walks are starting to attract some attention recently as already mentioned in Sec. 1). Second, time
is often discrete. In this case the hitting time is simply measured in the number of steps that the system takes to
reach the final state. The hitting probability is then defined analogously to (32) to be
f(n; ρ
f
, ρ
i
) ≡ Pr
ρ(t
n
) = ρ
f
, ρ(t
m
) 6= ρ
f
∀ m ≤ n − 1 |ρ(0) = ρ
i
. (96)
Lastly, as we said already for quantum walks with only unitary dynamics, the notion of a quantum walker actually
being in a particular state is not well defined. One way around this issue is to introduce a measurement of the final-
state population at the end of every step. Given that our hitting distribution is founded on measurement theory,
it is most natural to compare our calculation with this version of the hitting distribution from the quantum-walk
literature. In particular, we use the definition stated in Krovi and Brun’s paper [38] but replace, in their definition
of the hitting distribution, the unitary time-evolution operator by a non-unitary map K(t). Taking ρ
f
=
ˆ
Q
N
as
before, the expression for f(n; ρ
f
, ρ
i
) from Ref. [38] gives
f(n;
ˆ
Q
N
, ρ
i
) = Tr
Q
N
K(δt)
P
N
K(δt)
n−1
ρ
i
(97)
where the quantum-walk is defined by K(δt) = exp(Lδt). The superoperators Q
N
and P
N
are defined by
Q
N
ρ =
ˆ
Q
N
ρ
ˆ
Q
N
, P
N
ρ =
ˆ
P
N
ρ
ˆ
P
N
, (98)
20
and
ˆ
P
N
=
ˆ
1 −
ˆ
Q
N
. (99)
The effect of Q
N
is thus to project the system into |ψ
N
i while P
N
projects the system into the subspace
¯
H
N
≡ Span
¯
S
N
, (100)
where
¯
S
N
≡ S
N
− {|ψ
N
i}. Their effects on an arbitrary state ρ can most easily be seen when (98) are in their
matrix representations
Q
N
ρ =
0 0 ··· 0 0
0 0 ··· 0 0
.
.
.
.
.
.
.
.
.
.
.
.
0 0 ··· 0 0
0 0 ··· 0 ρ
NN
, P
N
ρ =
ρ
11
ρ
12
··· ρ
1,N−1
0
ρ
21
ρ
22
··· ρ
2,N−1
0
.
.
.
.
.
.
.
.
.
.
.
.
ρ
N−1,1
ρ
N−1,2
··· ρ
N−1,N−1
0
0 0 ··· 0 0
, (101)
where we have made use of (28) for the matrix elements of ρ (sometimes with a comma in the subscript when
the indices of ρ are otherwise difficult to differentiate). Note that we have written the time step in (97) as a
small but finite number δt to remind ourselves that (97) was derived in discrete time. Therefore the comparison of
h(t; ρ
f
, ρ
i
) to f(n; ρ
f
, ρ
i
) has to be made in the limit of δt −→ 0. As a matter of fact, we will show next that the
two distributions converge in the continuous-time limit, expressed as
lim
δt→0
f(n;
ˆ
Q
N
, ρ
i
) = h(t
n−1
) δt . (102)
5.2 Convergence of the generalised Krovi–Brun and quantum-jump distributions
To show the equivalence between the two hitting distributions in the δt −→ 0 limit it helps to separate the full
generator for the Markov chain into jump and no-jump terms:
L =
¯
L
?
+ J
?
, (103)
where
¯
L
?
is given by (53) and we have also defined the shorthand
J
?
≡ J(η
?
) . (104)
Recall that we defined J(η
?
) in (39). We will assume that initially there is no population in the final state,
hψ
N
|ρ
i
|ψ
N
i = 0 . (105)
This condition then implies that |ψ
N
i cannot share coherences with the remaining states in
¯
S
N
. The initial state
is thus confined to be in
¯
H
N
, which can be formally expressed as
P
N
ρ
i
= ρ
i
. (106)
The idea of writing L as the sum of
¯
L
?
and J
?
is that the no-jump and jump superoperators have the following
useful properties which can be used to show the consistency between the discrete-time and continuous-time hitting
distributions. The first thing to note is that the no-jump evolution of an ρ
i
defined by (106) is confined to
¯
H
N
.
This automatically means that any future evolution of ρ
i
under
¯
L
?
has zero projection onto |ψ
N
i. We can express
these observations formally as
Q
N
¯
L
?
= 0 , P
N
¯
L
?
=
¯
L
?
P
N
=
¯
L
?
. (107)
Remember that these are superoperator identities assuming they act on states satisfying (106). Jumps, on the other
hand, take the system state out of its confinement in
¯
H
N
and into |ψ
N
i. This means that
Q
N
J
?
= J
?
, P
N
J
?
= 0 . (108)
21
We then have, in the limit of δt −→ 0,
P
N
K(δt) = P
N
e
Lδt
(109)
= P
N
+
¯
L
?
δt + J
?
δt
(110)
=
+
¯
L
?
δt
P
N
. (111)
On rewriting the expansion in δt back in exponential form we arrive at
P
N
K(δt) ρ
i
= e
¯
L
?
δt
ρ
i
. (112)
This then permits us to write
¯ρ(t
n−1
) =
P
N
K(δt)
n−1
ρ
i
= e
¯
L
?
(n−1)δt
ρ
i
. (113)
This is again a state which satisfies (106) [with ρ
i
replaced by ¯ρ(t
n−1
)] so the superoperator identities (107) and
(108) still apply and we have
Q
N
K(δt)
P
N
K(δt)
n−1
ρ
i
= Q
N
K(δt) ¯ρ(t
n−1
) (114)
= Q
N
+
¯
L
?
δt + J
?
δt
¯ρ(t
n−1
) (115)
= J
?
¯ρ(t
n−1
) δt , (116)
where we have also noted that Q
N
¯ρ(t
n−1
) = 0. Taking the trace then gives
f(n) = Tr
J
?
¯ρ(t
n−1
)
δt , (117)
which we recognise as the jump probability (40) with an unnormalised state, but we showed in (47) and (48) that
this is precisely the hitting distribution. The only difference is that time is discretised. Substituting the definition
of J
?
from (39) into (117) we get
f(n) = Tr
"
N−1
X
m=1
k
Nm
ˆ
Q
Nm
¯ρ(t
n−1
)
ˆ
Q
†
Nm
#
δt (118)
=
N−1
X
m=1
k
Nm
hψ
m
|e
¯
L
?
(n−1)δt
ρ
i
|ψ
m
iδt = h(t
n−1
) δt . (119)
Note that f(n) corresponds to the quantum-jump distribution evaluated at time t
n−1
. This makes sense since there
are only n time steps so what we want is the probability that a jump occurs in the interval from t
n−1
to t
n
and
that none occurred from t
0
to t
n−1
—which is precisely h(t
n−1
) δt.
6 Including coherent transitions to the final state
6.1 The N + 1 model
The theory above does not allow for coherent transitions to |ψ
N
i in the graph. The quantum-jump approach works
by detecting transitions to the final state but only incoherent transitions can be detected. That is to say, if there
are coherent transitions from
¯
H
N
to |ψ
N
i, then the hitting statistics calculated from the quantum-jump approach
will not reflect the true statistics, which contains a contribution from the coherent transitions to the final state.
On the other hand the Krovi–Brun formula (97) works by detecting the on-site populations and therefore applies
to arbitrarily complicated graphs. We will now remedy this problem so that the quantum-jump approach can be
applied to arbitrarily complicated graphs as well.
Let us introduce one extra state, a fictitious state, to the quantum walk. We will denote this extra state as
|ψ
N+1
i. By introducing an incoherent transition from |ψ
N
i to |ψ
N+1
i we can expect to recover the original hitting
time (i.e. the time to reach |ψ
N
i for the first time) by making the transition rate k
N+1,N
large in the extended graph.
22
Since the rate k
N+1,N
is an important quantity in this section, and is also a bit cumbersome to write repeatedly,
we shall set
v ≡ k
N+1,N
. (120)
It is then intuitive to see that
lim
v→∞
T
ˆ
Q
N+1
, ρ
i
= T
ˆ
Q
N
, ρ
i
, (121)
since in the limit of large v, the time taken to go from |ψ
N
i to |ψ
N+1
i becomes negligible. In fact, in the limit of
large v, we can also expect T (
ˆ
Q
N+1
, ρ
i
) and T (
ˆ
Q
N
, ρ
i
) to be identically distributed. This is because as we make
v larger and larger, we are also making the probability of reaching |ψ
N+1
i from |ψ
N
i tend to one. When this
probability is one, the quantum walker is as likely to be in |ψ
N+1
i as |ψ
N
i, or more formally,
lim
v→∞
h(t;
ˆ
Q
N+1
, ρ
i
) dt = lim
δt→0
f(n;
ˆ
Q
N
, ρ
i
) . (122)
Note the hitting distribution to reach |ψ
N
i is written using the Krovi–Brun formula since the existence of coherent
transitions to |ψ
N
i limits the use of the quantum-jump method. We refer to the Krovi–Brun formula f(n;
ˆ
Q
N
, ρ
i
)
simply as the N model and the quantum-jump formula h(t;
ˆ
Q
N+1
, ρ
i
) dt in the limit of large v as the N + 1 model.
We prove (122) below.
6.2 Convergence of the N and N + 1 models
By adding one extra state and an incoherent connection from |ψ
N
i to |ψ
N+1
i we may decompose the dynamics of
the N + 1 graph into jump and no-jump terms as we have been doing,
L =
¯
L
?
+ J
?
. (123)
Note that (123) now acts on density operators in an N + 1-dimensional space where
¯
L
?
describes the evolution
of the quantum walk constrained to the original N -dimensional subspace. The superoperator J
?
now describes a
jump from |ψ
N
i to |ψ
N+1
i, defined by
J
?
ρ = v
ˆ
Q
N+1,N
ρ
ˆ
Q
†
N+1,N
. (124)
In order to make the connection with the N model, it helps to introduce
L = L
N+1
,
¯
L
?
= L
N
. (125)
The proof of (122) can be made easier if we discretise time into steps of size δt and express h(t) dt in the limit of
δt −→ 0. In this case an arbitrary t is equivalent to t
n
≡ n δt for an arbitrary n. The hitting distribution calculated
using quantum jumps is thus
h(t
n
,
ˆ
Q
N+1
, ρ
i
) δt = Tr
n
J
?
e
¯
L
?
δt
n
ρ
i
o
δt (126)
= Tr
n
J
?
e
¯
L
?
δt
e
¯
L
?
δt
n−1
ρ
i
o
δt (127)
= Tr
n
J
?
e
L
N
δt
P
N+1
e
L
N+1
δt
n−1
ρ
i
o
δt , (128)
where P
N+1
is defined in the same way as (98), (99), and (101) with N −→ N + 1 [recall also that we have defined
ˆ
Q
n
= |ψ
n
ihψ
n
|]. The last line simply makes use of the proof in Sec. 5 to express the conditional evolution in terms
of P
N+1
and L
N+1
. As we will be taking the limit of large v it makes sense to plug in the definition of J
?
to make
v explicit in the hitting distribution:
h(t
n
,
ˆ
Q
N+1
, ρ
i
) δt = v δt Tr
n
Q
N
e
L
N
δt
P
N+1
e
L
N+1
δt
n−1
ρ
i
o
. (129)
There are in fact two places where v appears in (129): One in the product v δt, and the other implicitly in
exp(L
N+1
δt). The first limit is simple to see. All we have to do is note that (129) is already in the δt −→ 0 limit
23
and that v −→ ∞ must be consistent with the interpretation of v δt as the probability to jump from |ψ
N
i to |ψ
N+1
i
in δt. This means that v δt −→ 1 as we make v ever so large but δt ever so small. This immediately gives
lim
v→∞
h(t
n
,
ˆ
Q
N+1
, ρ
i
) δt = Tr
n
Q
N
e
L
N
δt
h
P
N+1
lim
v→∞
e
L
N+1
δt
i
n−1
ρ
i
o
. (130)
The only nontrivial part now resides in what happens to the evolution of the N + 1 graph for large v: The larger
we make v, the more difficult it is for the population of |ψ
N
i to build up. Then, as v tends to infinity there is
simply no appreciable population in |ψ
N
i for all time. Since hψ
N
|ρ(t)|ψ
N
i = 0 implies no coherences can be shared
between |ψ
N
i and any other state, we can write, in the v −→ ∞ limit,
e
L
N+1
δt
= P
N
e
L
N+1
δt
. (131)
This simply says that the N
th
row and N
th
column of the density operator at all times is zero when v −→ ∞. Now
we note that the only sensible initial state is one satisfying
P
N+1
ρ
i
= ρ
i
, (132)
since the original hitting problem is defined only for the N-state graph. From this initial condition it is easy to see
that
P
N+1
L
N
= L
N
P
N+1
= L
N
, P
N+1
J
?
= 0 . (133)
The properties in (133) are simple to see since the action of P
N+1
just says that we find the system to be in a state
in the subspace spanned by S
N
. The first condition in (133) then follows since L
N
only evolves the system within
the subspace spanned by S
N
. The second condition in (133) is true because J
?
puts the quantum walker in the
state |ψ
N+1
i so that one finds the population of every other state to be zero. These are the same conditions as
those appearing in (107) and (108), just extended to N + 1 states. We can use (133) to simplify the limit in (130)
by noting that
P
N+1
P
N
= P
N
P
N+1
. (134)
We therefore have, upon using (133) and (134),
P
N+1
P
N
e
L
N+1
δt
= P
N
P
N+1
+ L
N
δt + J
?
δt
(135)
= P
N
e
L
N
δt
P
N+1
. (136)
Since P
N+1
can be commuted through P
N
and L
N
, it is simple to see that
P
N+1
P
N
e
L
N+1
δt
n−1
=
P
N
e
L
N
δt
n−1
P
N+1
. (137)
Substituting this back into (130) then gives, for v −→ ∞ and δt −→ 0,
h(t
n
,
ˆ
Q
N+1
, ρ
i
) δt = Tr
n
Q
N
e
L
N
δt
P
N
e
L
N
δt
n−1
ρ
i
o
. (138)
As this equation already assumes δt −→ 0, this is precisely the right-hand side of (122). This therefore shows the
equivalence between the N and N + 1 models.
We now illustrate (122) for the graph in Fig. 10(a) where we are interested in the hitting time for vertex |ψ
4
i
starting at |ψ
1
i. All the graph parameters except for v are fixed and have values stated in the figure caption. In
this case we consider the hitting-time distribution for |ψ
5
i under the quantum-jump approach and compare it to
the generalised Krovi–Brun distribution taking the final state to be |ψ
4
i. The hitting distribution calculated from
the quantum-jump approach is shown as the (blue) solid line while the generalised Krovi–Brun approach is shown
as (red) dots. The value of v is gradually increased as we pass from Fig. 10(b) to (d), and as can be seen, the hitting
distribution from the quantum-jump approach (solid curve) changes until it eventually coincides exactly with the
generalised Krovi–Brun hitting distribution (dots).
24
Figure 10: Hitting-time distributions for the N + 1 and N models for the N = 4 graph shown in (a) (|ψ
5
i being a fictitious state).
The parameter values are Ω
43
= Ω
32
= k
42
= k
43
= 5, Ω
21
= 50, ω
1
= 1, ω
2
= 3, and ω
3
= 5. The convergence between the
N + 1 and N models is clearly seen as v is increased from v = 5 in (b) to v = 500 in (d).
7 Discussion
The most essential result of this paper is the explicit expression for the statistics of hitting times for a model
of continuous-time open quantum walks given in (55). This is a finite sum and in principle can be entered into a
computer to extract meaningful quantities about the quantum walk such as the average hitting time and its variance.
Below we summarise our results in conjunction with other findings obtained in this paper. We also explain the
relationship between our work and some other literature which we have not mentioned so far but are nevertheless
worthy of a discussion.
7.1 Summary
We have shown here how the quantum-jump method lends itself naturally to the hitting problem in continuous
open quantum walks. In this language the hitting time for the walker to reach a prescribed state ρ
f
from some
fixed ρ
i
in an N-state graph is defined by the time of the first jump. Based on this, the hitting distribution is just
the distribution of times for the first jump, given in (49). Simple examples of this result were considered. We then
derived expressions for the statistical moments of the hitting time in terms of the graph dynamics. The results are
given by (60), (61), and (55). Again, some simple examples were used to illustrate the final results. In the process
we showed analytically how the quantum expression simplifies to the expected classical result when the graph has
only incoherent transitions. We then generalised the hitting distribution for the discrete-time unitary quantum walk
in Ref. [38] to allow for non-unitary evolution and showed that this is equivalent to the quantum-jump distribution
if the time step of the discrete walk approached zero. A caveat of the quantum-jump method is that it assumes the
edges connected to ρ
f
are incoherent. The hitting time becomes much less straightforward to define when coherent
transitions to ρ
f
are present. Thus open quantum walks have an intrinsic advantage over unitary walks in that there
25
is a set of graphs for which hitting times can be unambiguously defined (i.e. graphs where ρ
f
only shares incoherent
edges with other nodes). We then proposed a solution to this problem by adding one fictitious state to the graph
giving us a model with N + 1 states. We then proved that our N + 1 model predicts the same hitting statistics as
the N model according to the generalised definition of Ref. [38]. This is illustrated for a simple graph where the
convergence of the N + 1 model to the N model can be seen “explicitly” (Fig. 10). It is interesting to point out
that the N and N + 1 models differ qualitatively in that the former decides if the final state has been hit or not by
detecting the walker’s presence at the final state, whereas the N + 1 model works by detecting if the walker is in
transit to the final state.
7.2 Relation to other work and possible future explorations
Our appeal to photon counting as a way of thinking about quantum jumps for the hitting problem raises another
interesting question related to the use of measurements in quantum walks. This is related to our allusion to
other unravellings made earlier in Sec. 1.1. In general, an unravelling is a specific decomposition of the master
equation into stochastic trajectories such that the ensemble average of them recovers the dynamics of the master
equation. Two classes of unravellings have special significance in quantum optics—the jump unravellings used in our
paper, and the so-called diffusive unravellings—because they turn out to have concrete interpretations in terms of
quantum optical measurements (as already seen with the jump unravellings in our work) [13]. Canonical examples
of quantum-optical measurements that give rise to (or essentially realise) diffusive unravellings are the homodyne
and heterodyne detection schemes [57, 58]. Since we are defining the graph of a continuous-time open quantum walk
by a master equation, and we know that a master equation can be unravelled in different ways, one might wonder if
another type of unravelling can be used to study a hitting problem. Given that diffusive unravellings form the second
major class of unravellings in quantum optics we might then ask if they can be used for the hitting problem in this
paper. The short answer is that there is not much motivation to do so because they are unhelpful for solving hitting
problems with discrete-state quantum walks. To understand this we recall that in our quantum-jump approach we
imagined the incoherent transitions in the graph gave off photons which were measured by photodetectors. Using
a diffusive unravelling is equivalent to superimposing the stream of photons coming from an incoherent transition
with a local-oscillator field (a laser in a coherent state) on a beam splitter before it is detected by the photodetector.
In this case the photodetector actually measures a quadrature of the stream of photons determined by the phase
of the local oscillator. A diffusive unravelling thus gives us information about a continuous variable that does not
directly reveal to us if the walker has reached a prescribed state or not. To get around this one can then try to
introduce the fidelity between ρ
f
(here taken to be a parameter) and the walker’s state to define when ρ
f
is reached
or not. As one can see, this already introduces an extra step into the analysis, not to mention that the fidelity for a
fixed ρ
f
is a nonlinear function of the density operator. The jump unravelling on the other hand does give us direct
information about whether the walker has reached ρ
f
, and is much more natural for our quantum-walk problem. If
one wants to think about applying diffusive unravellings one could start with a completely different quantum-walk
model altogether where diffusive unravellings would appear to be natural. A suitable quantum-walk model would
be one in which the state space is continuous. To this end, it might be interesting to use quantum Brownian motion
as a model. A diffusive unravelling of this can then be expected to reveal the walker’s position directly.
There is in fact an example of a hitting-time calculation for a diffusively unravelled quantum master equation
in the context of rapid purification [59, 60, 61]. The basic idea is to purify qubits as quickly as possible by using
a continuous diffusive measurement and feedback. There are two approaches to rapid purification—one can either
maximize the average purity of a qubit in a fixed time, or minimize the average time for a qubit to reach a fixed
purity [62]. It is the latter approach that is a hitting problem where the hitting time is simply the time to reach
a predefined purity. In this case, the average time to reach a predefined purity (i.e. the average hitting time) is
calculated by first converting the qubit dynamics under a diffusive measurement into a set of stochastic Bloch
equations, and then from these, the equivalent classical Fokker–Planck equation. Once the classical Fokker–Planck
equation is known, standard techniques for calculating the average time to reach a given purity can be applied
[63] (where the hitting time is known as the first-passage time). Aside from the difference in the unravelling
that is employed, there is another difference between the calculation of the average first-passage time in the rapid
purification work and our results here: Our average hitting-time calculation (and in fact all higher statistics) uses
a quantum method—quantum jumps—and hence our results are expressed explicitly in terms of the quantum
evolution equation of the random process. The rapid-purification work on the other hand re-expresses the evolution
of the random process in terms of the equivalent classical equation first (the Fokker–Planck equation), from which
26
Hitting problem Photon counting
Hitting time Time of first count
Recurrence time Waiting time
Table 1: Analogies between different quantities in a hitting problem of quantum walks and photon counting in quantum optics.
the average hitting/first-passage time can then be obtained using a method invented for classical diffusive processes.
In light of this, a noteworthy point of our paper is that the nature of our problem, and the ensuing method used,
allows us to bypass the extra step of making a quantum-classical correspondence as in rapid purification before the
hitting problem can be solved.
We have seen that in the language of photon counting, the hitting time is the analogue of the time of the first
count. In fact, our calculation of the hitting-time distribution follows much the same strategy as what a quantum
optician would do to derive the distribution of waiting times (the time interval between successive photon counts).
Is the hitting-time distribution in our quantum-walk problem therefore equivalent to the waiting-time distribution
of photon counting? The answer is no, and to see this we just have to refer back to Fig. 2. If we look at the record
of jumps shown on the right in Fig. 2, the waiting time is the interval between successive jumps. However, from
the graph on the left we can see that this is the amount of time the walker spends being away from the final state
before returning to it again. The time taken for a random walker to start in a given node and return to it turns
out to be an interesting quantity as well. It is known as the recurrence time (recall Examples 1 and 2 in Sec. 4.3).
The recurrence time in a hitting problem is thus the quantity that one should regard as analogous to the waiting
time of quantum optics and it is not difficult to see that it is different to the hitting time. It is in fact simple to
construct a graph for which the hitting time is very different to the recurrence time. We summarise this in Table 1.
It is then interesting to ask whether there is additional knowledge from photodetection statistics that one might
be able to borrow for quantum walks. One potential application is the use of the waiting-time distribution for
estimating an unknown parameter in a quantum emitter that one is interested in characterising [24, 64]. The
simplest model being a driven two-level atom whose Rabi frequency is not known to an experimenter. Kiilerich and
Mølmer have shown that the waiting-time distribution of the photodetection record obtained from monitoring the
atomic fluorescence is useful for estimating the Rabi frequency [64]. This idea may have applications to quantum
walks where one has only a partially characterised graph—e.g. the frequency of one of the coherent transitions in the
graph is not known. It might then be possible to identify a recurrent state whose distribution of recurrence times
can be used for identifying the unknown transition frequency. Clearly, one will need the multichannel extension
of this idea described in Ref. [24]. A successful application of this theory would then extend the quantum-walk–
quantum-optics analogy further.
8 Acknowledgements
We would like to thank an anonymous referee who stimulated us into thinking about continuous-time quantum
walks. This paper is an outgrowth of the exchange we had with the referee. We thank also many others who we
have discussed this project with in the past: Itai Arad, Marcin Karczewski, Dagomir Kaszlikowski, Paweł Kurzyński,
Zakarya Lasmar, Gerard Milburn, Ranjith Nair, Changsuk Noh, and Miklos Santha. This research is supported
by the MOE grant number RG 127/14, and the National Research Foundation, Prime Minister’s Office, Singapore
under its Competitive Research Programme (CRP Award No. NRF-CRP-14-2014-02).
References
[1] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University
Press, United Kingdom, 2000).
[2] S. E. Venegas-Andraca, Quantum Walks for Computer Scientists (Morgan and Claypool, 2008).
[3] R. Portugal, Quantum Walks and Search Algorithms (Springer, New York, Heidelberg, Dordrecht, London,
2013).
27
[4] G. S. Engel, T. R. Calhoun, E. L. Read, T.-K. Ahn, T. Manˇcal, Y.-C. Cheng, R. E. Blankenship, and G.
R. Fleming, Evidence for wavelike energy transfer through quantum coherence in photosynthetic systems,
Nature 446, 782 (2007).
[5] M. Mohseni, P. Rebentrost, S. Lloyd, and A. Aspuru-Guzik, Environment-assisted quantum walks in photo-
synthetic energy transfer, J. Chem. Phys. 129, 174106 (2008).
[6] T. Oka, N. Konno, R. Arita, and H. Aoki, Breakdown of an electric-field driven system: A mapping to a
quantum walk, Phys. Rev. Lett. 94, 100602 (2005).
[7] H. B. Perets, Y. Lahini, F. Pozzi, M. Sorel, R. Moran-Dotti, and Y. Silberberg. Realization of quantum walks
with negligible decoherence in waveguide lattices, Phys. Rev. Lett. 100, 170506 (2008).
[8] M. Karski, L. Förster, J. M. Choi, A. Steffen, W. Alt, D. Meschede, and A. Widera, Quantum walk in position
space with single optically trapped atoms, Science 325, 174 (2009).
[9] H. Schmitz, R. Matjeschk, Ch. Schneider, J. Glueckert, M. Enderlein, T. Huber, and T. Schaetz, Quantum
walk of a trapped ion in phase space, Phys. Rev. Lett. 103, 090504 (2009).
[10] F. Zähringer, G. Kirchmair, R. Gerritsma, E. Solano, R. Blatt, and C. F. Roos, Realization of a quantum
walk with one and two trapped ions, Phys. Rev. Lett. 104, 100503 (2010).
[11] D. Bouwmeester, A. Ekert, and A. Zeilinger (Eds.), The Physics of Quantum Information (Springer-Verlag,
Berlin, Heidelberg, New York, 2001).
[12] P. Kok and B. W. Lovett, Introduction to Optical Quantum Information Processing (Cambridge University
Press, New York, 2010).
[13] H. M. Wiseman and G. J. Milburn, Quantum Measurement and Control (Cambridge University Press, New
York, 2010).
[14] J. Dalibard, Y. Castin, and K. Mølmer, Wave-function approach to dissipative processes in quantum optics,
Phys. Rev. Lett. 68, 580 (1992).
[15] R. Dum, P. Zoller, and H. Ritsch, Monte Carlo simulation of the atomic master equation for spontaneous
emission, Phys. Rev. A 45, 4879 (1992).
[16] R. Dum, A. S. Parkins, P. Zoller, and C. W. Gardiner, Monte Carlo simulation of master equations in quantum
optics for vacuum, thermal, and squeezed reservoirs, Phys. Rev. A 46, 4382 (1992).
[17] K. Mølmer, Y. Castin, and J. Dalibard, Monte Carlo wave-function method in quantum optics, J. Opt. Soc.
Am. B 10, 524 (1993).
[18] H. J. Carmichael, S. Singh, R. Vyas, and P. R. Rice, Photoelectron waiting times and atomic state reduction
in resonance fluorescence, Phys. Rev. A 39, 1200 (1989).
[19] H. J. Carmichael, An Open Systems Approach to Quantum Optics (Springer-Verlag, Berlin, Heidelberg, 1993).
[20] M. B. Plenio and P. L. Knight, The quantum-jump approach to dissipative dynamics in quantum optics, Rev.
Mod. Phys. 70, 101 (1998).
[21] D. B. Horoshko and S. Ya. Kilin, Direct detection feedback for preserving quantum coherence in an open
cavity, Phys. Rev. Lett. 78, 840 (1997).
[22] J. Gambetta and H. M. Wiseman, State and dynamical parameter estimation for open quantum systems,
Phys. Rev. A 64, 042105 (2001).
[23] C. Di Fidio, W. Vogel, M. Khanbekyan, and G.-G. Welsch, Photon emission by an atom in a lossy cavity,
Phys. Rev. A 77, 043822 (2008).
[24] A. H. Kiilerich and K. Mølmer, Parameter estimation by multichannel photon counting, Phys. Rev. A 91,
012119 (2015).
[25] H. J. Carmichael, Statistical Methods in Quantum Optics 2 (Springer, Berlin, Heidelberg, New York, 2008).
[26] B. Jones, S. Ghose, J. P. Clemens, P. R. Rice, and L. M. Pedrotti, Photon statistics of a single atom laser,
Phys. Rev. A 60, 3267 (1999).
[27] A. Kronwald, M. Ludwig, and F. Marquadt, Full photon statistics of a light beam transmitted through an
optomechanical system, Phys. Rev. A 87, 013847 (2013).
28
[28] P. L. Kelley and W. H. Kleiner, Theory of electromagnetic field measurement and photoelectron counting,
Phys. Rev. 136, A316 (1964).
[29] H. Kobayashi, B. L. Mark, and W. Turin, Probability, Random Processes, and Statistical Analysis (Cambridge
University Press, New York, 2012).
[30] S. Redner, A Guide to First-Passage Processes, (Cambridge University Press, United States of America,
2001).
[31] T. Taillefumier and M. O. Magnasco, A phase transition in the first passage of a Brownian process through
a fluctuating boundary with implications for neural coding, Proc. Natl. Acad. Sci. 110, E1438 (2013).
[32] S. Condamin, O. Bénichou, V. Tejedor, R. Voituriez, and J. Klafter, First-passage times in complex scale-
invariant media, Nature 450, 77 (2007).
[33] K. Kraus, General state changes in quantum theory, Ann. Phys. 64, 311 (1971).
[34] Y. Aharanov and L. Davidovich and N. Zagury, Quantum random walks, Phys. Rev. A 48, 1687 (1993).
[35] S. E. Venegas-Andraca, Quantum walks: a comprehensive review, Quantum Inf. Process. 12, 1015 (2012).
[36] J. Kempe, Quantum walks: an introductory overview, Contemp. Phys. 44, 307 (2003).
[37] J. Kempe, Discrete quantum walks hit exponentially faster, Proceedings of the 7th International Workshop
on Randomization and Approximation Techniques in Computer Science (RANDOM03), 354 (2003).
[38] H. Krovi and T. A. Brun, Hitting time for quantum walks on the hypercube, Phys. Rev. A 73, 032341 (2006).
[39] N. Shenvi, J. Kempe, and K. B. Whaley, Quantum random-walk search algorithm, Phys. Rev. A 67, 052307
(2003).
[40] A. Ambainis, J. Kempe, and A. Rivosh, Coins make quantum walks faster, Proc. 16th ACM-SIAM Symposium
on Discrete Alogrithms, 1099 (2005) (http://dl.acm.org/citation.cfm?id=1070432.1070590).
[41] N. B. Lovett, S. Cooper, M. Everitt, M. Trevers, and V. Kendon, Universal quantum computation using the
discrete-time quantum walk, Phys. Rev. A 81, 042330 (2010).
[42] E. Farhi and S. Gutmann, Quantum computation and decision trees, Phys. Rev. A 58, 915 (1998).
[43] A. M. Childs, E. Farhi, and S. Gutmann, An example of the difference between quantum and classical random
walks, Quant. Inf. Process. 1, 35 (2002).
[44] M. Varbanov, H. Krovi, and T. A. Brun, Hitting time for the continuous quantum walk, Phys. Rev. A 78,
022324 (2008).
[45] T. A. Brun, A simple model of quantum trajectories, Am. J. Phys. 70, 719 (2002).
[46] A. M. Childs and J. Goldstone, Spatial search by quantum walk, Phys. Rev. A 70, 022314 (2004).
[47] A. M. Childs, R. Cleve, E. Deotto, E. Farhi, S. Gutmann, and D. A. Spielman, Exponential algorithmic
speedup by a quantum walk, Proc. of the 35th Annual ACM Symposium on Theory of Computing, 59 (2003).
[48] A. M. Childs, Universal computation by quantum walk, Phys. Rev. Lett. 102, 180501 (2009).
[49] S. Attal, F. Petruccione, and I. Sinayskiy, Open quantum walks on graphs, Phys. Lett. A 376, 1545 (2012).
[50] S. Attal, F. Petruccione, C. Sabot, and I. Sinayskiy, Open quantum random walks, J. Stat. Phys. 147, 832
(2012).
[51] C. Pellegrini, Continuous time open quantum random walks and non-Markovian Lindblad master equations,
J. Stat. Phys. 154, 838 (2014).
[52] C. Liu and R. Balu, Steady states of continuous-time open quantum walks, C. Liu and R. Balu, Steady states
of continuous-time open quantum walks, Quantum Inf. Process. 16, 173 (2017).
[53] C. F. Lardizabal and R. R. Souza, Open quantum random walks: Ergodicity, hitting times, gambler’s ruin
and potential theory, J. Stat. Phys. 164, 1122 (2016).
[54] R.-T. Qiu, W.-S. Dai, and M. Xie, Mean-first passage time of quantum transition processes, Physica A, 4748
(2012).
[55] S. Daryanoosh and H. M. Wiseman, Quantum jumps are more quantum than quantum diffusion, New. J.
Phys. 16, 063028 (2014).
29
[56] A. Chia, A. Górecka, P. Kurzyński, T. Paterek, D. Kaszlikowski, Coherent chemical kinetics as quantum
walks. II. Radical-pair reactions in Arabidopsis thaliana, Phys. Rev. E 93, 032408 (2016).
[57] H. M. Wiseman and L. Diósi, Complete parameterization, and invariance, of diffusive quantum trajectories
for Markovian open systems, Chem. Phys. 268, 91 (2001).
[58] A. Chia and H. M. Wiseman, Complete parameterizations of diffusive quantum monitorings, Phys. Rev. A
84, 012119 (2011).
[59] K. Jacobs, How to project qubits faster using quantum feedback, Phys. Rev. A 67, 030301(R) (2003).
[60] K. Jacobs, Optimal feedback control for rapid preparation of a qubit, Proc. SPIE 5468, 355 (2004).
[61] J. Combes and K. Jacobs, Rapid state reduction of quantum systems using feedback control, Phys. Rev. Lett.
96, 010504 (2006).
[62] H. M. Wiseman and J. F. Ralph, Reconsidering rapid qubit purification by feedback, New J. Phys. 8, 90
(2006).
[63] C. W. Gardiner, Handbook of Stochastic Methods Third Edition (Springer-Verlag, Berlin, Heidelberg, New
York, 2004).
[64] A. H. Kiilerich and K. Mølmer, Estimation of atomic interaction parameters by photon counting, Phys. Rev.
A. 89, 052110 (2014).
A Independent derivation of the average hitting time
The goal here is to provide a derivation of the average of hitting times that is independent of the moment-generating
function used in Sec. 4.2. This will add further confidence in our result. The ensemble average of T (ρ
f
, ρ
i
) with
ρ
f
=
ˆ
Q
N
is defined by
E
T (
ˆ
Q
N
, ρ
i
)
=
Z
∞
0
dt t h(t;
ˆ
Q
N
, ρ
i
) , (139)
We will again suppress the dependence of T and h on the initial and final states in the following. We integrate
(139) by parts directly, in which case it will be convenient to define the indefinite integral
H(t) =
Z
dt h(t) . (140)
We may then write
E[T ] =
h
t H(t)
∞
0
−
Z
∞
0
dt H(t) . (141)
The first term is given by
h
t H(t)
∞
0
= lim
t→∞
t H(t) − lim
t→0
t H(t) . (142)
We can get some insight into this function by actually doing the indefinite integral in (140). The function H(t) is
H(t) =
Z
dt
N−1
X
m=1
k
Nm
hψ
m
|e
¯
L
?
t
ρ
i
|ψ
m
i (143)
=
N−1
X
m=1
k
Nm
hψ
m
|
Z
dt e
¯
L
?
t
ρ
i
|ψ
m
i (144)
=
N−1
X
m=1
k
Nm
hψ
m
|
¯
L
−1
?
e
¯
L
?
t
ρ
i
|ψ
m
i . (145)
30
Assuming that
¯
L
?
is invertible we can see that
lim
t→0
H(t) =
N−1
X
m=1
k
Nm
hψ
m
|
¯
L
−1
?
lim
t→0
e
¯
L
?
t
ρ
i
|ψ
m
i (146)
=
N−1
X
m=1
k
Nm
hψ
m
|
¯
L
−1
?
ρ
i
|ψ
m
i , (147)
which in general has a value between zero and some finite number. Therefore we obtain
lim
t→0
t H(t) = 0 . (148)
As for the first term in (142), we need to see how H(t) behaves as t −→ ∞. This is given by
lim
t→∞
H(t) =
N−1
X
m=1
k
Nm
hψ
m
|
¯
L
−1
?
lim
t→∞
e
¯
L
?
t
ρ
i
|ψ
m
i = 0 , (149)
where we have used (67), stated here again for ease of reference,
lim
t→∞
e
¯
L
?
t
ρ
i
= 0 . (150)
This means that H(t) −→ 0 as t −→ ∞, which in turn implies that the first term in (142) has an indeterminate
form of the type ∞ × 0. We can therefore use L’Hˆopital’s rule to calculate the limit, giving
lim
t→∞
t H(t) = lim
t→∞
H(t)
t
−1
(151)
= − lim
t→∞
˙
H(t)
t
−2
(152)
= − lim
t→∞
t
2
h(t) = 0 , (153)
where the third equality is obtained from (140). For the final equality we assume that h(t) is decaying faster than
t
2
in the limit t −→ ∞, which is the case for most physically relevant probability densities. We note here that it is
not always the case that h(t) is such a “nice” distribution as this depends on the actual graph defining the quantum
walk (e.g. a graph containing absorbing states may give rise to infinite hitting times). We will not consider such
cases in this paper. Equation (142) thus vanishes completely and the average hitting time becomes
E[T ] = −
Z
∞
0
dt H(t) . (154)
From (145) we have
F (t) ≡
Z
dt H(t) (155)
=
N−1
X
m=1
k
Nm
hψ
m
|
¯
L
−1
?
Z
dt e
¯
L
?
t
ρ
i
|ψ
m
i (156)
=
N−1
X
m=1
k
Nm
hψ
m
|
¯
L
−1
?
2
e
¯
L
?
t
ρ
i
|ψ
m
i . (157)
The definite integral in (154) is thus given by
E[T ] = −
h
lim
t→∞
F (t) − lim
t→0
F (t)
i
(158)
Using again the fact that
¯
L
?
produces a zero steady state we have
lim
t→∞
F (t) = 0 . (159)
31
This gives E[T (
ˆ
Q
N
, ρ
i
)] = lim
t→0
F (t) which evaluates to
E[T (
ˆ
Q
N
, ρ
i
)] =
N−1
X
m=1
k
Nm
hψ
m
|
¯
L
−2
?
ρ
i
|ψ
m
i . (160)
Replacing
¯
L
−1
?
by the Moore–Penrose pseudoinverse
¯
L
+
?
then reproduces (60).
B Independent derivation of the variance of the hitting time
The variance of the hitting time reads
V
T (
ˆ
Q
N
, ρ
i
)
≡ E
T
2
(
ˆ
Q
N
, ρ
i
)
−
E
T (
ˆ
Q
N
, ρ
i
)
2
. (161)
All we have to do is to calculate E
T
2
(ρ
f
, ρ
i
)
which is given by
E
T
2
(
ˆ
Q
N
, ρ
i
)
=
Z
∞
0
dt t
2
h(t; ρ
f
, ρ
i
) . (162)
We can proceed in a similar manner as we have done with the average. Integrating (162) by parts we get
E
T
2
(
ˆ
Q
N
, ρ
i
)
=
h
t
2
H(t)
∞
0
− 2
Z
∞
0
dt t H(t) , (163)
where we defined H(t) in (145). Repeated application of the L’Hˆopital rule gives
lim
t→∞
t
2
H(t) = − lim
t→∞
t
3
h(t) = 0 . (164)
We have assumed again that h(t) is a normalisable function. Using again the fact that H(t) is a continuous function
and finite at t = 0 we get
lim
t→0
t
2
H(t) = 0 . (165)
This means that we are left with only the integral in (163).
E
T
2
(
ˆ
Q
N
, ρ
i
)
= −2
Z
∞
0
dt t H(t) = −2
h
t F (t)
∞
0
−
Z
∞
0
dt F (t)
. (166)
where we have introduced
F (t) =
Z
dt H(t) =
N−1
X
m=1
k
Nm
hψ
m
|
¯
L
−2
?
e
¯
L
?
t
ρ
i
|ψ
m
i . (167)
The finiteness of F (0) and L’Hˆopital’s rule give once again
h
t F (t)
∞
0
= − lim
t→∞
t
2
H(t) − F (0) lim
t→0
t = 0 . (168)
We thus have
E
T
2
(
ˆ
Q
N
, ρ
i
)
= 2
Z
∞
0
dt F (t) (169)
= 2
N−1
X
m=1
k
Nm
hψ
m
|
¯
L
−2
?
Z
∞
0
dt e
¯
L
?
t
ρ
i
|ψ
m
i (170)
= 2
N−1
X
m=1
k
Nm
hψ
m
|
¯
L
−3
?
h
e
¯
L
?
t
ρ
i
∞
0
|ψ
m
i = −2
N−1
X
m=1
k
Nm
hψ
m
|
¯
L
−3
?
ρ
i
|ψ
m
i , (171)
32
where we have again used the fact that the dynamics under
¯
L
?
vanishes in the long-time limit. Subtracting off the
square of E[T (
ˆ
Q
N
, ρ
i
)] we finally arrive at
V
T (
ˆ
Q
N
, ρ
i
)
= −2
N−1
X
m=1
k
Nm
hψ
m
|
¯
L
−3
?
ρ
i
|ψ
m
i −
N−1
X
m=1
k
Nm
hψ
m
|
¯
L
−2
?
ρ
i
|ψ
m
i
!
2
. (172)
As with the average, we can replace
¯
L
−1
?
by
¯
L
+
?
to obtain (61).
33