Abstract
Quantum walks are quantum counterparts of random walks. While probability distributions of random walks diffusively spread out as the walkers are updating, quantum walks have ballistic behavior. Some of the ballistic behaviors have been revealed in long-time limit theorems and their probability distributions are all far away from the Gaussian distributions, which are known as limit distributions of random walks. In this chapter, we are going to be seeing limit distributions for a standard quantum walk on the line and two kinds of time-dependent quantum walk on the line.
Keywords
- Quantum walk
- limit theorem
- Fourier analysis
- time-dependent walk
- line
1. Introduction
Quantum walks (QWs) are mathematical models on graphs whose systems repeatedly update according to time-evolution rules. They have been in an emerging field which describes the quantum world. Experts in mathematics, physics, and information theory have been interested in them and to study QWs, and a lot of fascinating properties of QWs have been discovered. Historically, QWs were independently introduced in science from several view points; mathematics in 1988 [1], physics in 1993 [2], and computer science in 1996 [3]. After a while, they began to get attention around 2000. Since QWs can be considered as quantum counterparts of random walks in mathematics, they are also called quantum random walks. The dynamics of QWs are similar to those of random walks in mathematical terms. But, whereas a random walker moves on a graph at random, a quantum walker spreads out as a wave on a graph. Although random walks are stochastic processes, QWs are different. They are unitary processes because the systems of quantum walkers get updated with unitary operators. In quantum physics, the update rules of QWs are interpreted as discretized models of Dirac equations. High dimensional Dirac equations are hard to solve even in numerics due to their complexities, and then we expect QWs to become alternative systems to solve the equations on computer. QWs also play an important role in quantum computers because they are quantum algorithms themselves. Indeed, some quantum algorithms based on QWs show quadratic speed-up, compared to the corresponding classical algorithms [4]. Such algorithms imply that quantum computers could give rise to excellent performance.
In this chapter, we are going to be seeing mathematical aspects of the QWs, which will be described as limit theorems. We first observe a standard QW on the line in Sec.2 Then we shift our focus to time-dependent QWs on the line in Secs. 3 and 4.
2. A quantum walk on the line
We start off with the description of a standard QW on the line. The system of the QW is defined in a tensor space of two Hilbert spaces. One is a Hilbert space ℋ
Customarily,
with
where
and an initial state
assuming the complex numbers
where the random variable
The definition of the standard QW on the line has been done. So, what are we curious about? One of the major studies on QWs is to know how their probability distributions behave after they have updated a lot of times. For the probability distribution of the QW defined in this section, one can assert a limit theorem which tells us an approximate behavior of the probability distribution ℙ(
This limit theorem, to be exact which was a theorem for a general unitary operator
Oppositely, we can obtain the coin states by inverse Fourier transformation,
Equation (2) gives the evolution of the Fourier transform,
with
The iteration by Eq. (12) connects the system at time
To prove the theorem, we concentrate on a convergence
with
It is known from probability theory that the convergence guarantees Eq. (8). Before we compute the limit, let us depict the
Noting that
we have
Integrating Eq. (19) over the interval [−
from which the
Here, let
The Fourier transform at time
which also gives a description of the derivative
where
Equations (23) and (24) change the integral picture in Eq. (21),
Dividing Eq. (26) by
and obtain a convergence as
Now what we need more has made sense. It is the eigensystem of the operator
from which a matrix representation follows,
The matrix contains two different eigenvalues
in which
from which the function
The normalized eigenvector associated to the eigenvalue
with its normalized factor
Back in Eq. (28), we put
Equation (36) allows us to hold Eq. (8).
Now that we have obtained a limit theorem for the QW whose operator was defined by
Theorem 1 can be extended for the parameter
Since we already had the limit theorem for the parameter
The negative sign in front of the operator
We should remark that Eq. (40) holds under the condition
Figure 4 shows an example of the limit density function.
We see that the limit density function reproduces the features of the probability distribution shown in Figure 1.
3. Two-period time-dependent QW
In this section, we see a time-dependent QW whose coin-flip operator depends on time. The evolution of the QW is given by two unitary operators,
with
where
It is plane that the operators
Now, we are looking at examples of the probability distribution when the walker starts off with
The features, which we have seen in Figures 5 to 7 are caught by a limit theorem.
This limit theorem was proved by Fourier analysis in 2010 [7]. First, we find the time evolution of the Fourier transform
which comes from Eq. (44). We should recall
The eigensystem of the matrix
Arranging the
we obtain the representations of the
Dividing these equations by time 2
which are combined as
As a result, we have
The Hilbert space ℋ
and one can find its eigenvalues
The normalized eigenvector associated to the eigenvalue
with
Here we compute
from Eq. (61). Putting
For the same reason as the proof for Theorem 1, this convergence promises Theorem 3. As mentioned earlier, if the parameters
Given an initial state with
We confirm that the function has two singularities at the points ±
4. Three-period time-dependent QW
The standard QW in Sec.2 and the two-period time-dependent QW in Sec.3 have the same type of limit density function. In the final section, we see a three-period time-dependent QW and its limit density function. As a result, a different type of limit density function will be discovered. With a unitary operator
where
The 3-period time-dependent QW was studied by Grünbaum and Machida [8] when the unitary operator
with
We find a long-time limit theorem in the paper [8] and it asserts the convergence of a random variable rescaled by time
where
and ℜ (
This limit theorem can be derived by Fourier analysis as well. For the Fourier transform
Given an orthogonal normalized basis such as Eq. (29), the matrix
has two eigenvalues
A possible expression of the normalized eigenvector associated to the eigenvalue
where
With a decomposition
and compute their derivatives
The moments
and we see
which is put together as
where
Setting
which guarantees Theorem 4. Figure 12 shows the limit density function (
Acknowledgments
The author is supported by JSPS Grant-in-Aid for Young Scientists (B) (No. 16K17648).
References
- 1.
S. P. Gudder (1988), Quantum probability , Academic Press. Probability and Mathematical Statistics. - 2.
Y. Aharonov, L. Davidovich and N. Zagury (1993), Quantum random walks , Phys. Rev. A, 48(2), pp. 1687–1690. - 3.
D. A. Meyer (1996), From quantum cellular automata to quantum lattice gases , Journal of Statistical Physics, 85(5–6), pp. 551–574. - 4.
S. E. Venegas-Andraca (2012), Quantum walks: a comprehensive review , Quantum Information Processing, 11(5), pp. 1015–1106. - 5.
N. Konno (2002), Quantum random walks in one dimension , Quantum Information Processing, 1(5), pp. 345–354. - 6.
G. Grimmett, S. Janson and P.F. Scudo (2004), Weak limits for quantum random walks , Phys. Rev. E, 69(2), p. 026119. - 7.
T. Machida and N. Konno (2010), Limit theorem for a time-dependent coined quantum walk on the line , F. Peper et al. (Eds.): IWNC 2009, Proceedings in Information and Communications Technology, 2, pp. 226–235. - 8.
F. A. Grünbaum and T. Machida (2015), A limit theorem for a 3-period time-dependent quantum walk , Quantum Information and Computation, 15(1& 2), pp. 50–60.