1201/1201.4780.md

Noname manuscript No.
(will be inserted by the editor)

Quantum walks: a comprehensive review

Salvador Elías Venegas-Andraca

To my dear friend Carlos Fuentes. In Memoriam.

To my beloved daughter Renata, welcome to my life and to Planet Earth!

Abstract Quantum walks, the quantum mechanical counterpart of classical random walks, is an advanced tool for building quantum algorithms that has been recently shown to constitute a universal model of quantum computation. Quantum walks is now a solid field of research of quantum computation full of exciting open problems for physicists, computer scientists and engineers.

In this paper we review theoretical advances on the foundations of both discrete- and continuous-time quantum walks, together with the role that randomness plays in quantum walks, the connections between the mathematical models of coined discrete quantum walks and continuous quantum walks, the quantumness of quantum walks, a summary of papers published on discrete quantum walks and entanglement as well as a succinct review of experimental proposals and realizations of discrete-time quantum walks. Furthermore, we have reviewed several algorithms based on both discrete- and continuous-time quantum walks as well as a most important result: the computational universality of both continuous- and discrete-time quantum walks.

Keywords quantum walks · quantum algorithms · quantum computing · quantum and classical simulation of quantum systems

1 Introduction

Computer science and computer engineering are disciplines that have transformed every aspect of modern society. In these fields, cutting-edge research is about new models of computation, new materials and techniques for building computer hardware, novel methods for speeding-up algorithms, and building bridges between computer science and several other scientific fields that allow scientists to both think of natural phenomena as computational procedures as well as to employ novel models of computation to simulate natural processes (e.g. [138,377,246,420,370,57,6,318,51].) In particular, quantifying the resources required to process information and/or to compute a solution, i.e. to assess the complexity of

---

Quantum Information Processing Group at Tecnológico de Monterrey Campus Estado de México and Texia, SA de CV
E-mail: sva@mindsofmexico.org, sva@texia.mx, salvador.venegas-andraca@keble.oxon.orga computational process, is a prioritized research area as it allows us to estimate implementation costs as well as to compare problems by comparing the complexity of their solutions. Among the mathematical tools employed in advanced algorithm development, classical random walks, a subset of stochastic processes (that is, processes whose evolution involves chance), have proved to be a very powerful technique for the development of stochastic algorithms [335, 403]. In addition to the key role they play in algorithmics, classical random walks are ubiquitous in many areas of knowledge as physics, biology, finance theory, computer vision, and earthquake modelling [278, 72, 198, 177, 192, 451], to name a few.

Theoretical computer science, in its canonical form, does not take into account the physical properties of those devices used for performing computational or information processing tasks. As this characteristic could be perceived as a drawback because the behavior of any physical device used for computation or information processing must ultimately be predicted by the laws of physics, several research approaches have therefore concentrated on thinking of computation in a physical context (e.g. [66, 69, 68, 67, 155, 156, 154, 130, 131, 162, 315].) Among those physical theories that could be used for this purpose, quantum mechanics stands in first place.

Quantum computation can be defined as the interdisciplinary scientific field devoted to build quantum computers and quantum information processing systems, i.e. computers and information processing systems that use the quantum mechanical properties of Nature. Research on quantum computation heavily focuses on building and running algorithms which exploit the physical properties of quantum computers. Among the theoretical discoveries and promising conjectures that have positioned quantum computation as a key element in modern science, we find:

1. 1. The development of novel and powerful methods of computation that may allow us to significantly increase our processing power for solving certain problems (e.g. [342, 240, 15, 82].)
2. 2. The increasing number of quantum computing applications in several branches of science and technology (e.g. image processing and computational geometry [446, 447, 444, 281, 283, 284, 427, 285, 204, 205], pattern recognition [432, 434, 433, 196], quantum games [4], and warfare [279].)
3. 3. The simulation of complex physical systems and mathematical problems for which we know no classical digital computer algorithm that could efficiently simulate them [155, 225, 360, 224, 226, 412]. A detailed summary of scientific and technological applications of quantum computers can be found in [371, 141].

Building good quantum algorithms is a difficult task as quantum mechanics is a counterintuitive theory and intuition plays a major role in algorithm design and, for a quantum algorithm to be good, it is not enough to perform the task it is intended to: it must also do better, i.e. be more efficient, than any classical algorithm (at least better than those classical algorithms known at the time of developing corresponding quantum algorithms.) Examples of successful results in quantum computation can be found in [132, 412, 182, 116, 196, 52, 225, 360, 224, 226]. Good introductions and reviews of quantum algorithms can be found in [240, 185, 342, 78, 323, 206, 231, 441, 296, 324, 400, 280, 334, 30, 119, 58, 455, 375].

Quantum walks, the quantum mechanical counterpart of classical random walks, is an advanced tool for building quantum algorithms (e.g. [409, 27, 26, 116, 29, 330])that has been recently shown to constitute a universal model of quantum computation [115, 301, 437]. There are two kinds of quantum walks: discrete and continuous quantum walks. The main difference between these two sets is the timing used to apply corresponding evolution operators. In the case of discrete quantum walks, the corresponding evolution operator of the system is applied only in discrete time steps, while in the continuous quantum walk case, the evolution operator can be applied at any time.

Our approach in the development of this work has been to study those concepts of quantum mechanics and quantum computation relevant to the computational aspects of quantum walks. Thus, in the history of cross-fertilization between physics and computation, this review is meant to be situated as a contribution within the field of quantum walks from the perspective of a computer scientist. In addition to this paper, the reader may also find the scientific documents written by Kempe [230], Kendon [234], Konno [255], Ambainis [25, 26, 29, 30], Santha [400], and Venegas-Andraca [443] relevant to deepening into the mathematical, physical and algorithmic properties of quantum walks.

The following lines provide a summary of the main ideas and contributions of this review article.

Section 2. Fundamentals of Quantum Walks. In this section I offer a comprehensive yet concise introduction to the main concepts and results of discrete and continuous quantum walks on a line and other graphs. This section starts with a short and rigorous introduction to those properties of classical discrete random walks on undirected graphs relevant to algorithm development, including definitions for hitting time, mixing time and mixing rate, as well as mathematical expressions for hitting time on an unrestricted line and on a circle. I then introduce the basic components of a discrete-time quantum walk on a line, followed by a detailed analysis of the Hadamard quantum walk on an infinite line, using a method based on the Discrete Time Fourier Transform known as the Schrödinger approach. This analysis includes the enunciation of relevant theorems, as well as the advantages of the Hadamard quantum walk on an infinite line with respect to its closest classical counterpart. In particular, I explore the context in which the properties of the Hadamard quantum walk on an infinite line are compared with classical random walks on an infinite line and with two reflecting barriers. Also, I briefly review another method for studying the Hadamard walk on an infinite line: path counting approach. I then proceed to study a quantum walk on an infinite line with an arbitrary coin operator and explain why the study of the Hadamard quantum walk on an infinite line is enough as for the analysis of arbitrary quantum walks on an infinite line. Then, I present several results of quantum walks on a line with one and two absorbing barriers, followed by an analysis on the behavior of discrete-time coined quantum walks using many coins and a study of the effects of decoherence, a detailed review on limit theorems for discrete-time quantum walks, a subsection devoted to the recently founded subfield of localization on discrete-time quantum walks, and a summary of other relevant results.

I then focus on the properties of discrete-time quantum walks on graphs: we study discrete-time quantum walks on a circle, on the hypercube and some general properties of this kind of quantum walks on Cayley graphs, including a limit theorem of averaged probability distributions for quantum walks on graphs. I continue this section with a general introduction to continuous quantum walks together with several relevant results published in this field. Then, I present an analysis ofthe role that randomness plays in quantum walks and the connections between the mathematical models of coined discrete quantum walks and continuous quantum walks. The last part of this section focuses on issues about the quantumness of quantum walks that includes a brief summary of reports on discrete quantum walks and entanglement. Finally, I briefly summarize several experimental proposals and realizations of discrete-time quantum walks.

Section 3. Algorithms based on quantum walks and classical simulation of quantum algorithms-quantum walks. We review several links between computer science and quantum walks. We start by introducing the notions of oracle and hitting time, followed by a detailed analysis of quantum algorithms developed to solve the following problems: searching in an unordered list and in a hypercube, the element distinctness problem, and the triangle problem. I then provide an introduction to a seminal paper written by M. Szegedy in which a new definition of quantum walks based on quantizing a stochastic matrix is proposed. The second part of this section is devoted to analyzing continuous quantum walks. We start by reviewing the most successful quantum algorithm based on a continuous quantum walk known so far, which consists of traversing, in polynomial time, a family of graphs of trees with an exponential number of vertices (the same family of graphs would be traversed only in exponential time by any classical algorithm). We then briefly review a generalization of a continuous quantum walk, now allowed to perform non-unitary evolution, in order to simulate photosynthetic processes, and we finish by reviewing the state of the art on classical digital computer simulation of quantum algorithms and, particularly, quantum walks.

Section 4. Universality of quantum walks. I review in this last section a very recent and most important contribution in the field of quantum walks: computational universality of both continuous- and discrete-time quantum walks.

2 Fundamentals of Quantum Walks

Quantum walks are quantum counterparts of classical random walks. Since classical random walks have been successfully adopted to develop classical algorithms and one of the main topics in quantum computation is the creation of quantum algorithms which are faster than their classical counterparts, there has been a huge interest in understanding the properties of quantum walks over the last few years. In addition to their usage in computer science, the study of quantum walks is relevant to building methods in order to test the “quantumness” of emerging technologies for the creation of quantum computers as well as to model natural phenomena.

Quantum walks is a relatively new research topic. Although some authors have selected the name “quantum random walk” to refer to quantum phenomena [170, 187] and, in fact, in a seminal work by R.P. Feynman about quantum mechanical computers [156] we find a proposal that could be interpreted as a continuous quantum walk [106], it is generally accepted that the first paper with quantum walks as its main topic was published in 1993 by Aharonov et al [16]. Thus, the links between classical random walks and quantum walks as well as the utility of quantum walks in computer science, are two fresh and open areas of research (among scientific contributions on the links between classical and quantum walks, Konno has proposed in [256] solid mathematical connections between correlatedrandom walks and quantum walks using the PQRS matrix method introduced in [248,247].) Two models of quantum walks have been suggested:

• • The first model, called discrete quantum walks, consists of two quantum mechanical systems, named a walker and a coin, as well as an evolution operator which is applied to both systems only in discrete time steps. The mathematical structure of this model is evolution via unitary operator, i.e. $|\psi\rangle_{t_2} = \hat{U}|\psi\rangle_{t_1}$ .
• • The second model, named continuous quantum walks, consists of a walker and an evolution (Hamiltonian) operator of the system that can be applied with no timing restrictions at all, i.e. the walker walks any time. The mathematical structure of this model is evolution via the Schrödinger equation.

In both discrete and continuous models, the topology on which quantum walks have been performed and their properties computed are discrete graphs. This is mainly because graphs are widely used in computer science and building up quantum algorithms based on quantum walks has been a prioritized activity in this field.

The original idea behind the construction of quantum algorithms was to start by initializing a set of qubits and then to apply (one of more) evolution operators several times without making intermediate measurements, as measurements were meant to be performed only at the end of the computational process (for example, see the quantum algorithms reported in [78,342].) Not surprisingly, the first quantum algorithms based on quantum walks were designed using the same strategy: initialize qubits, apply evolution operators and measure only to calculate the final outcome of the algorithm. Indeed, this method has proved itself very useful for building several remarkable algorithms (e.g. [26,230].) However, as the field has matured, it has been reported that performing (partial) measurements on a quantum walk may lead to interesting mathematical properties for algorithm development, like the ‘top hat’ probability distribution (e.g. [312,234].) Moreover and expanding on the idea of using more sophisticated tools from the repertoire of quantum mechanics, recent reports have shown the effect of using weak measurements on the walker probability distribution of discrete quantum walks [169].

The rest of this section is organized as follows. I begin with a short introduction to those properties of classical discrete random walks on undirected graphs relevant to algorithm development, including definitions for hitting time, mixing time and mixing rate, as well as mathematical expressions for hitting time on an unrestricted line and on a circle. I then introduce the basic components of a discrete-time quantum walk on a line, followed by a detailed analysis of the Hadamard quantum walk on an infinite line, using a method based on the Discrete Time Fourier Transform known as the Schrödinger approach. This analysis includes the enunciation of relevant theorems, as well as the advantages of the Hadamard quantum walk on an infinite line with respect to its closest classical counterpart. In particular, I explore the context in which the properties of the Hadamard quantum walk on an infinite line are compared with classical random walks on an infinite line and with two reflecting barriers. Also, I briefly review another method for studying the Hadamard walk on an infinite line: path counting approach. I then proceed to study a quantum walk on an infinite line with an arbitrary coin operator and explain why the study of the Hadamard quantum walk on an infinite line is enough as for the analysis of arbitrary quantum walks on an infi-nite line. Then, I present several results of quantum walks on a line with one and two absorbing barriers, followed by an analysis on the behavior of discrete-time coined quantum walks using many coins and a study of the effects of decoherence, a detailed review on limit theorems for discrete-time quantum walks, a subsection devoted to the recently founded subfield of localization on discrete-time quantum walks, and a summary of other relevant results.

In addition to this review paper, the reader may also find the scientific documents written by Kempe [230], Kendon [234], Konno [255], Ambainis [25, 26, 29, 30], Santha [400], and Venegas-Andraca [443] relevant to deepening into the mathematical, physical and algorithmic properties of quantum walks. Finally, readers who are not yet acquainted with the mathematical and/or physical foundations of quantum computation may find the following references useful: [185, 342, 374, 323, 206, 324, 442, 280, 375].

2.1 Classical random walk on an unrestricted line

Classical discrete random walks were first thought as stochastic processes with no straightforward relation to algorithm development. Thus, in addition to references like [363, 418, 125, 136, 179, 343, 457, 392] in which the mathematical foundations of random walks can be found, references [335, 298, 299, 367] are highly recommendable for a deeper understanding of algorithm development based on classical random walks.

A classical discrete random walk on a line is a particular kind of stochastic process. The simplest classical random walk on a line consists of a particle (“the walker”) jumping to either left or right depending on the outcomes of a probability system (“the coin”) with (at least) two mutually exclusive results, i.e. the particle moves according to a probability distribution (Fig. (1).) The generalization to discrete random walks on spaces of higher dimensions (graphs) is straightforward. An example of a discrete random walk on a graph is a particle moving on a lattice where each node has 6 vertices, and the particle moves according to the outcomes produced by tossing a dice. Classical random walks on graphs can be seen as Markov chains ([335, 343].)

Now, let ${Z_n}$ be a stochastic process which consists of the path of a particle which moves along an axis with steps of one unit at time intervals also of one unit (Fig. (1).) At any step, the particle has a probability $p$ of going to the right and $q = 1 - p$ of going to the left. Each step is modelled by a Bernoulli-distributed random variable [125, 442] and the probability of finding the particle in position $k$ after $n$ steps and having as initial position $Z_0 = 0$ is given by the binomial distribution $T_n = \sum_{k=1}^n Y_i = \frac{1}{2}(Z_n + n) \Rightarrow$

Fig. (2) shows a plot of Eq. (1) with number of steps $n = 100$ and $p = \frac{1}{2}$ .

Since $T_n$ is $\text{Bin}(n, p)$ then the expected value is given by $E[T_n] = np$ and the variance is computed as $V[T_n] = npq$ . Thus,Fig. 1 An unrestricted classical discrete random walk on a line. The probability of going to the right is $p$ and the probability of going to the left is $q = 1 - p$ .

Fig. 2 Plot of $P_{ok}^{(n)} = \binom{n}{\frac{1}{2}(k+n)} p^{\frac{1}{2}(k+n)} q^{\frac{1}{2}(n-k)}$ for $n = 100$ and $p = \frac{1}{2}$ . The probability of finding the walker in position $k = 0$ is equal to 0.0795. Only probabilities corresponding to even positions are shown, as odd positions have probability equal to zero.

$$V[Z_n]=V[2T_n-n]=4npq\mathrm{.}\text{ In other words, }V[Z_n]=O(n)(2)V[Z\_n]\; =\; V[2T\_n\; -\; n]\; =\; 4npq.\; \backslash text\{\; In\; other\; words,\; \}\; V[Z\_n]\; =\; O(n)\; \backslash quad\; (2)$$

Eq. (2) will be used in the following sections to show one of the earliest results on comparing classical random walks to quantum walks.

Graphs that encode the structure of a group are called Cayley graphs. Cayley graphs are a vehicle for translating mathematical structures of scientific and engineering problems into forms amenable to algorithm development for scientific computing.

Definition 1 Cayley graph. Let $G$ be a finite group, and let $S = {s_1, s_2, \dots, s_k}$ be a generating set for $G$ . The Cayley graph of $G$ with respect to $S$ has a vertex for every element of $G$ , with an edge from $g$ to $gs \forall g \in G$ and $s \in S$ .

Cayley graphs are $k$ -regular, that is, each vertex has degree $k$ . Cayley graphs have more structure than arbitrary Markov graphs and their properties can be used for algorithm development [228]. Graphs and Markov chains can be put in an elegant framework which turns out to be very useful for the development of algorithmic applications:

Let $G = (V, E)$ be a connected, undirected graph with $|V| = n$ and $|E| = m$ . $G$ induces a Markov chain $M_G$ if the states of $M_G$ are the vertices of $G$ , and $\forall u, v \in V$

where $d(u)$ is the degree of vertex $u$ . Since $G$ is connected, then $M_G$ is irreducible and aperiodic [335]. Moreover, $M_G$ has a unique stationary distribution.Theorem 1 Let $G$ be a connected, undirected graph with $n$ nodes and $m$ edges, and let $M_G$ be its corresponding Markov chain. Then, $M_G$ has a unique distribution

$$\vec{\pi }=(d(v_i)\mathrm{/}2m)\backslash vec\{\backslash pi\}\; =\; (d(v\_i)/2m)$$

for all components $v_i$ of $\vec{\pi}$ .

Note that Theorem 1 holds even when the distribution ${d(v_i)}$ is not uniform. In particular, the stationary distribution of an undirected and connected graph with $n$ nodes, $m$ edges and constant degree $d(v_i) = r \forall v_i \in G$ , i.e. a Cayley graph, is $\vec{\pi} = (r/2m)$ , the uniform distribution.

We have established the relationship between Markov chains and graphs. We now proceed to define the concepts that make discrete random walks on graphs useful in computer science. We shall begin by formally describing a random walk on a graph: let $G$ be a graph. A random walk, starting from a vertex $u \in V$ is the random process defined by

s=u

repeat

    choose a neighbor $v$ of $u$ according to a certain probability distribution $P$

$u = v$

until (stop condition)

So, we start at a node $v_0$ and, if at $t^{\text{th}}$ step we are at a node $v_t$ , we move to a neighbour of $v_t$ with probability given by probability distribution $P$ . It is common practice to make $P_{uv} = \frac{1}{d(v_t)}$ , where $d(v_t)$ is the degree of vertex $v_t$ . Examples of discrete random walks on graphs are a classical random walk on a circle or on a 3-dimensional mesh.

We now introduce several measures to quantify the performance of discrete random walks on graphs. These measures play an important role in the quantitative theory of random walks, as well as in the application of this kind of Markov chains in computer science.

Definition 2 Hitting time. The hitting time $H_{ij}$ is the expected number of steps before node $j$ is visited, starting from node $i$ .

Definition 3 Mixing rate. The mixing rate is a measure of how fast the discrete random walk converges to its limiting distribution. The mixing rate can be defined in many ways, depending on the type of graph we want to work with. We use the definition given in [298].

If the graph is non-bipartite then $p_{ij}^t \rightarrow d_j/2m$ as $t \rightarrow \infty$ , and the mixing rate is given by

$$\mu =\underset{t\to \mathrm{\infty }}{\lim }\sup \max {\mid p_{ij}^{(t)}-\frac{d_j}{2m}\mid }^{1\mathrm{/}t}\backslash mu\; =\; \backslash lim\_\{t\; \backslash rightarrow\; \backslash infty\}\; \backslash sup\; \backslash max\; \backslash left|\; p\_\{ij\}^\{(t)\}\; -\; \backslash frac\{d\_j\}\{2m\}\; \backslash right|^\{1/t\}$$

As it is the case with the mixing rate, the mixing time can be defined in several ways. Basically, the notion of mixing time comprises the number of steps one must perform a classical discrete random walk before its distribution is close to its limiting distribution.Definition 4 Mixing time [31]. Let $M_G$ be an ergodic Markov chain which induces a probability distribution $P_u(t)$ on the states at time $t$ . Also, let $\vec{\pi}$ denote the limiting distribution of $M_G$ . The mixing time $\tau_\epsilon$ is then defined as

where $|P_u(t) - \vec{\pi}|$ is a standard distance measure. For example, we could use the total variation distance, defined as $|P_u(t) - \vec{\pi}| = \frac{1}{2} \sum_i |P_{u_i}(t) - \pi_i|$ . Thus, the mixing time is defined as the first time $t$ such that $P_u(t)$ is within distance $\epsilon$ of $\vec{\pi}$ at all subsequent time steps $t \geq T$ , irrespective of the initial state.

Let us now provide two examples of hitting times on graphs.

2.1.1 Hitting time of an unrestricted classical discrete random walk on a line

It has been shown in Eq. (1) that, for an unrestricted classical discrete random walk on a line with $p = q = \frac{1}{2}$ , the probability of finding the walker in position $k$ after $n$ steps is given by

Using Stirling's approximation $n! \approx \sqrt{2\pi n} \left(\frac{n}{e}\right)^n$ and after some algebra, we find

$$\text{pr}(Z_n=k\mathrm{\mid }{Z}_0=0)=\frac{1}{2^n}\left(\genfrac{}{}{0px}{}{n}{\frac{1}{2}(k+n)}\right)\approx \sqrt{\frac{2n}{{\pi }^2(n^2-k^2)}}\frac{n^n}{(n+k{)}^{\frac{n+k}{2}}(n-k{)}^{\frac{n-k}{2}}}(3)\backslash text\{pr\}(Z\_n\; =\; k\; |\; Z\_0\; =\; 0)\; =\; \backslash frac\{1\}\{2^n\}\; \backslash binom\{n\}\{\backslash frac\{1\}\{2\}(k+n)\}\; \backslash approx\; \backslash sqrt\{\backslash frac\{2n\}\{\backslash pi^2(n^2\; -\; k^2)\}\}\; \backslash frac\{n^n\}\{(n+k)^\{\backslash frac\{n+k\}\{2\}\}\; (n-k)^\{\backslash frac\{n-k\}\{2\}\}\}\; \backslash quad\; (3)$$

We know that Eq. (1) is a binomial distribution, thus it makes sense to study the mixing time in two different vertex populations: $k \ll n$ and $k \approx n$ (the first population is mainly contained under the bell-shape part of the distribution, while the second can be found along the tails of the distribution.) In both cases, we shall find the expected hitting time by calculating the inverse of Eq. (3) (i.e., the expected time of the geometric distribution):

$$\text{Case }k\ll n\mathrm{.}\text{ Since }\sqrt{\frac{2n}{{\pi }^2(n^2-k^2)}}\frac{n^n}{(n+k{)}^{\frac{n+k}{2}}(n-k{)}^{\frac{n-k}{2}}}\approx \sqrt{\frac{2n}{{\pi }^2{n}^2}}\frac{n^n}{n^{n\mathrm{/}2}{n}^{n\mathrm{/}2}}=\frac{c}{\sqrt{n}}\Rightarrow \backslash text\{Case\; \}\; k\; \backslash ll\; n.\; \backslash text\{\; Since\; \}\; \backslash sqrt\{\backslash frac\{2n\}\{\backslash pi^2(n^2\; -\; k^2)\}\}\; \backslash frac\{n^n\}\{(n+k)^\{\backslash frac\{n+k\}\{2\}\}\; (n-k)^\{\backslash frac\{n-k\}\{2\}\}\}\; \backslash approx\; \backslash sqrt\{\backslash frac\{2n\}\{\backslash pi^2\; n^2\}\}\; \backslash frac\{n^n\}\{n^\{n/2\}\; n^\{n/2\}\}\; =\; \backslash frac\{c\}\{\backslash sqrt\{n\}\}\; \backslash Rightarrow$$

$$\text{Hitting time }{H}_{0,k}=O(\sqrt{n})(4)\backslash text\{Hitting\; time\; \}\; H\_\{0,k\}\; =\; O(\backslash sqrt\{n\})\; \backslash quad\; (4)$$

$$\text{Case }k\approx n\mathrm{.}\text{ Let }n-k=C_1\text{ and }{n}^2-k^2=C_2,\text{ where }{C}_1\text{ and }{C}_2\text{ are small integer numbers. Since }\sqrt{\frac{2n}{{\pi }^2(n^2-k^2)}}\frac{n^n}{(n+k{)}^{\frac{n+k}{2}}(n-k{)}^{\frac{n-k}{2}}}\approx \sqrt{\frac{2n}{\pi C_2}}\frac{n^n}{2^n{n}^n{C}_1^{C_1\mathrm{/}2}}=\frac{1}{2^n}\sqrt{\frac{2n}{\pi C_1^{C_1}{C}_2}}\Rightarrow \backslash text\{Case\; \}\; k\; \backslash approx\; n.\; \backslash text\{\; Let\; \}\; n-k\; =\; C\_1\; \backslash text\{\; and\; \}\; n^2\; -\; k^2\; =\; C\_2,\; \backslash text\{\; where\; \}\; C\_1\; \backslash text\{\; and\; \}\; C\_2\; \backslash text\{\; are\; small\; integer\; numbers.\; Since\; \}\; \backslash sqrt\{\backslash frac\{2n\}\{\backslash pi^2(n^2\; -\; k^2)\}\}\; \backslash frac\{n^n\}\{(n+k)^\{\backslash frac\{n+k\}\{2\}\}\; (n-k)^\{\backslash frac\{n-k\}\{2\}\}\}\; \backslash approx\; \backslash sqrt\{\backslash frac\{2n\}\{\backslash pi\; C\_2\}\}\; \backslash frac\{n^n\}\{2^n\; n^n\; C\_1^\{C\_1/2\}\}\; =\; \backslash frac\{1\}\{2^n\}\; \backslash sqrt\{\backslash frac\{2n\}\{\backslash pi\; C\_1^\{C\_1\}\; C\_2\}\}\; \backslash Rightarrow$$

$$\text{Hitting time }{H}_{0,k}=O(2^n)(5)\backslash text\{Hitting\; time\; \}\; H\_\{0,k\}\; =\; O(2^n)\; \backslash quad\; (5)$$

Thus, the hitting time for a given vertex $k$ of an $n$ -step unrestricted classical discrete random walk on a line depends on which region vertex $k$ is located in. If $k \ll n$ then it will take $\sqrt{n}$ steps to reach $k$ , in average. However, if $k \approx n$ then it will take an exponential number of steps to reach $k$ , as one would expect from the properties of the binomial distribution.Fig. 3 Classical discrete random walk on a 10 nodes circle.

2.1.2 Hitting time of a classical discrete random walk on a circle

The definitions of discrete random walks on a circle and on a line with two reflecting barriers are very similar. In fact, the only difference is the behavior of the extreme nodes.

Let ${Z_n}$ be a stochastic process which consists of the path of a particle which moves along a circle with steps of one unit at time intervals also of one unit. The circle has $n$ different position sites (for an example with 10 nodes, see Fig. (3)). At any step, the particle has a probability $p$ of going to the right and $q = 1 - p$ of going to the left. If the particle is on $Z_t = 0$ at time $t$ then the particle will move to $Z_{t+1} = 1$ with probability $p$ and to $Z_{t+1} = n - 1$ with probability $q$ . Similarly, if the particle is on $Z_t = n - 1$ at time $t$ then at time $t + 1$ the particle will go to $Z_{t+1} = 0$ with probability $p$ and to $Z_{t+1} = n - 2$ with probability $q$ .

According to Theorem 1, the Markov chain defined by ${Z_n}$ has a stationary distribution given by

$$\vec{\pi }=\frac{1}{n}(6)\backslash vec\{\backslash pi\}\; =\; \backslash frac\{1\}\{n\}\; \backslash quad\; (6)$$

And a hitting time $H_{0,n}$ given by ([298])

$$H_{0,n}=O(n^2)(7)H\_\{0,n\}\; =\; O(n^2)\; \backslash quad\; (7)$$

2.2 Discrete quantum walk on a line

Discrete quantum walks on a line (DQWL) is the most studied model of discrete quantum walks. As its name suggests, this kind of quantum walks are performed on graphs $G$ composed of a set of vertices $V$ and a set of edges $E$ (i.e., $G = (V, E)$ ), and having each vertex two edges, i.e. $|V| = 2$ . Studying DQWL is important in quantum computation for several reasons, including:

1. 1. DQWL can be used to build quantum walks on more sophisticated structures like circles or general graphs.1. 2. DQWL is a simple model that can be exploited to explore, find and understand relevant properties of quantum walks for the development of quantum algorithms.
2. 3. DQWL can be employed to test the quantumness of experimental realizations of quantum computers.

In [326], Meyer made two contributions to the study of DQWL while working on models of Quantum Cellular Automata (QCA) and Quantum Lattice Gases:

1. 1. He proposed a model of quantum dynamics that would be used later on to analytically characterize DQWL.
2. 2. He showed that a quantum process in which, at each time step, a quantum particle (the walker) moves in superposition both to left and right with equal amplitudes, is physically impossible in general, the only exception being the trivial motion in a single direction.

In order to perform a discrete DQWL with non-trivial evolution, it was proposed in [31] and [340] to use an additional quantum system: a coin. Thus, a DQWL comprises two quantum systems, coin and walker, along with a unitary coin operator (“to toss a coin”) and a conditional shift operator (to displace the walker to either left or right depending on the accompanying coin state component.)

In a different perspective, Patel et al proposed in [356] to eliminate the use of coins by rearranging the Hamiltonian operator associated with the evolution operator of the quantum walk (however, there is a price to be paid on the translation invariance of the quantum walk.) Moreover, Hines and Stamp have proposed the development of quantum walk Hamiltonians [195] in order to reflect the properties of potential experimental realizations of quantum walks in their mathematical structure.

Motivated by [356], Hamada et al [189] wrote a general setting for QCA, developed a correspondence between DQWL and QCA, and applied this connection to show that the quantum walk proposed in [356] could be modelled as a QCA. The relationship between QCA and quantum walks has been indirectly explored by Meyer [326]. Additionally, Konno et al [265] have studied the relationship between quantum walks and cellular automata, Van Dam has shown [438] that it is possible to build a quantum cellular automaton capable of universal computation, and Gross et al have introduced a comprehensive mathematical setting for developing index theory of one-dimensional automata and cellular automata [180].

We now review the mathematical structure of a basic coined DQWL.

2.2.1 Structure of a basic coined DQWL

The main components of a coined DQWL are a walker, a coin, evolution operators for both walker and coin, and a set of observables:

Walker and Coin: The walker is a quantum system living in a Hilbert space of infinite but countable dimension $\mathcal{H}_p$ . It is customary to use vectors from the canonical (computational) basis of $\mathcal{H}_p$ as “position sites” for the walker. So, we denote the walker as $|\text{position}\rangle \in \mathcal{H}_p$ and affirm that the canonical basis states $|i\rangle_p$ that span $\mathcal{H}p$ , as well as any superposition of the form $\sum_i \alpha_i |i\rangle_p$ subject to $\sum_i |\alpha_i|^2 = 1$ , are valid states for $|\text{position}\rangle$ . The walker is usually initialized at the ‘origin’, i.e. $|\text{position}\rangle{\text{initial}} = |0\rangle_p$ .The coin is a quantum system living in a 2-dimensional Hilbert space $\mathcal{H}_c$ . The coin may take the canonical basis states $|0\rangle$ and $|1\rangle$ as well as any superposition of these basis states. Therefore $|\text{coin}\rangle \in \mathcal{H}_c$ and a general normalized state of the coin may be written as $|\text{coin}\rangle = a|0\rangle_c + b|1\rangle_c$ , where $|a|^2 + |b|^2 = 1$ .

The total state of the quantum walk resides in $\mathcal{H}_t = \mathcal{H}p \otimes \mathcal{H}c$ . It is customary to use product states of $\mathcal{H}t$ as initial states, that is, $|\psi\rangle{\text{initial}} = |\text{position}\rangle{\text{initial}} \otimes |\text{coin}\rangle{\text{initial}}$ .

Evolution Operators: The evolution of a quantum walk is divided into two parts that closely resemble the behavior of a classical random walk. In the classical case, chance plays a key role in the evolution of the system. In the quantum case, the equivalent of the previous process is to apply an evolution operator to the coin state followed by a conditional shift operator to the total quantum system. The purpose of the coin operator is to render the coin state in a superposition, and the randomness is introduced by performing a measurement on the system after both evolution operators have been applied to the total quantum system several times.

Among coin operators, customarily denoted by $\hat{C}$ , the Hadamard operator has been extensively employed:

$$\widehat{H}=\frac{1}{\sqrt{2}}(\mathrm{\mid }0{⟩}_c⟨0\mathrm{\mid }+\mathrm{\mid }0{⟩}_c⟨1\mathrm{\mid }+\mathrm{\mid }1{⟩}_c⟨0\mathrm{\mid }-\mathrm{\mid }1{⟩}_c⟨1\mathrm{\mid })(8)\backslash hat\{H\}\; =\; \backslash frac\{1\}\{\backslash sqrt\{2\}\}(|0\backslash rangle\_c\backslash langle\; 0|\; +\; |0\backslash rangle\_c\backslash langle\; 1|\; +\; |1\backslash rangle\_c\backslash langle\; 0|\; -\; |1\backslash rangle\_c\backslash langle\; 1|)\; \backslash quad\; (8)$$

For the conditional shift operator use is made of a unitary operator that allows the walker to go one step forward if the accompanying coin state is one of the two basis states (e.g. $|0\rangle$ ), or one step backwards if the accompanying coin state is the other basis state (e.g. $|1\rangle$ ). A suitable conditional shift operator has the form

$$\widehat{S}=\mathrm{\mid }0{⟩}_c⟨0\mathrm{\mid }\otimes \sum _i\mathrm{\mid }i+1{⟩}_p⟨i\mathrm{\mid }+\mathrm{\mid }1{⟩}_c⟨1\mathrm{\mid }\otimes \sum _i\mathrm{\mid }i-1{⟩}_p⟨i\mathrm{\mid }\mathrm{.}(9)\backslash hat\{S\}\; =\; |0\backslash rangle\_c\backslash langle\; 0|\; \backslash otimes\; \backslash sum\_i\; |i+1\backslash rangle\_p\backslash langle\; i|\; +\; |1\backslash rangle\_c\backslash langle\; 1|\; \backslash otimes\; \backslash sum\_i\; |i-1\backslash rangle\_p\backslash langle\; i|.\; \backslash quad\; (9)$$

Consequently, the operator on the total Hilbert space is $\hat{U} = \hat{S} \cdot (\hat{C} \otimes \hat{\mathbb{I}}_p)$ and a succinct mathematical representation of a discrete quantum walk after $t$ steps is

$$\mathrm{\mid }\psi {⟩}_t=(\widehat{U}{)}^t\mathrm{\mid }\psi {⟩}_{\text{initial}},(10)|\backslash psi\backslash rangle\_t\; =\; (\backslash hat\{U\})^t\; |\backslash psi\backslash rangle\_\{\backslash text\{initial\}\},\; \backslash quad\; (10)$$

where $|\psi\rangle_{\text{initial}} = |\text{position}\rangle_{\text{initial}} \otimes |\text{coin}\rangle_{\text{initial}}$ .

Observables: Several advantages of quantum walks over classical random walks are a consequence of interference effects between coin and walker after several applications of $\hat{U}$ (other advantages come from quantum entanglement between walker(s) and coin(s) as well as partial measurement and/or interaction of coins and walkers with the environment.) However, we must perform a measurement at some point in order to know the outcome of our walk. To do so, we define a set of observables according to the basis states that have been used to define coin and walker.

There are several ways to extract information from the composite quantum system. For example, we may first perform a measurement on the coin using the observable

$${\widehat{M}}_c={\alpha }_0\mathrm{\mid }0{⟩}_c⟨0\mathrm{\mid }+{\alpha }_1\mathrm{\mid }1{⟩}_c⟨1\mathrm{\mid }\mathrm{.}(11)\backslash hat\{M\}\_c\; =\; \backslash alpha\_0|0\backslash rangle\_c\backslash langle\; 0|\; +\; \backslash alpha\_1|1\backslash rangle\_c\backslash langle\; 1|.\; \backslash quad\; (11)$$

A measurement must then be performed on the position states of the walker by using the operator$$\hat{M}_p = \sum_i a_i |i\rangle_p \langle i|. \quad (12)$$

We show in Fig. (4) the probability distributions of two 100-steps DQWL. Coin and shift operators for both quantum walks are given by Eqs. (8) and (9) respectively. The DQWLs from plots (a) and (b) have corresponding initial quantum states $|0\rangle_c \otimes |0\rangle_p$ and $|1\rangle_c \otimes |0\rangle_p$ . The first evident property of these quantum walks is the skewness of their probability distributions, as well as the dependance of the symmetry of such a skewness from the coin initial quantum state ( $|0\rangle$ for plot (a) and $|1\rangle$ for plot (b).) This skewness comes from constructive and destructive interference due to the minus sign included in Eq. (8). Also, we notice a quasi-uniform behavior in the central area of both probability distributions, approximately in the interval $[-70, 70]$ . Finally, we notice that regardless their skewness, both probability distributions cover the same number of positions (in this case, even positions from -100 to 100. If the quantum walk had been performed an odd number of times, then only odd position sites could have non-zero probability.)

Two approaches have been extensively used to study DQWL:

1. Schrödinger approach. In this case, we take an arbitrary component $|\psi\rangle_n = (\alpha|1\rangle_c + \beta|0\rangle_c) \otimes |n\rangle_p$ of the quantum walk, the tensor product of coin and position components for a certain walker position. $|\psi\rangle_n$ is then Fourier-transformed in order to get a closed form of the coin amplitudes. Then, standard tools of complex analysis are used to calculate the statistical properties of the probability distribution computed from corresponding coin amplitudes.

2. Combinatorial approach. In this method we compute the amplitude for a particular position component $|n\rangle_p$ by summing up the amplitudes of all the paths which begin in the given initial condition and end up in $|n\rangle_p$ . This approach can be seen as using a discrete version of path integrals.

In addition, Fuss et al have proposed an analytic description of probability densities and moments for the one-dimensional quantum walk on a line [161], Bressler and Pemantle [81] as well as Zhang [470] have employed generating functions to asymptotically analyze position probability distributions in one-dimensional quantum walks, and Feldman and Hillery [150] have proposed an alternative formulation of discrete quantum walks based on scattering theory. In particular, [150] plays an increasingly important role on the foundations of the field of quantum walks for being an alternative formulation for discrete quantum walks as well as a key tool to describe and understand the proof of computational universality delivered by Childs in [115], this latter paper is to be reviewed in section 4.

In the following lines we review both Schrödinger and combinatorial approaches to analyze the Hadamard walk, a specific but very powerful DQWL with coin and shift operators given by Eqs. (8) and (9) respectively. Later on we show how the Hadamard walk is related to the more general case of a DQWL with arbitrary coin operator.

2.2.2 Schrödinger approach for the Hadamard walk

The analysis of DQWL properties using the Discrete Time Fourier Transform (DTFT) and methods from complex analysis was first made by Nayak and Vishwanath [340], followed by Ambainis et al [31], Košík [269] and Carteret et al [93,Fig. 4 Probability distributions of 100 steps DQWLs using coin and shift operators given by Eqs. (8) and (9) respectively. Plot (a) corresponds to a DQWL with total initial quantum state $|0\rangle_c \otimes |0\rangle_p$ , while plot (b) had total initial quantum state $|1\rangle_c \otimes |0\rangle_p$ . Two interesting properties of these quantum walks is the skewness of corresponding probability distributions, along with the dependance of the symmetry of such skewness from the coin initial state.

94]. Following [31,340], a quantum walk on an infinite line after $t$ steps can be written as $|\psi\rangle_t = \hat{U}^t |\psi\rangle_{\text{initial}}$ (Eq. (10)) or, alternatively, as

$$\sum _k[a_k\mathrm{\mid }0{⟩}_c+b_k\mathrm{\mid }1{⟩}_c]\mathrm{\mid }k{⟩}_p(13)\backslash sum\_k\; [a\_k\; |0\backslash rangle\_c\; +\; b\_k\; |1\backslash rangle\_c]\; |k\backslash rangle\_p\; \backslash quad\; (13)$$

where $|0\rangle_c$ , $|1\rangle_c$ are the coin state components and $|k\rangle_p$ are the walker state components. For example, let us suppose we have

$$\mathrm{\mid }\psi {⟩}_0=\mathrm{\mid }0{⟩}_c\otimes \mathrm{\mid }0{⟩}_p(14)|\backslash psi\backslash rangle\_0\; =\; |0\backslash rangle\_c\; \backslash otimes\; |0\backslash rangle\_p\; \backslash quad\; (14)$$

as the quantum walk initial state, with Eq.(8) and Eq.(9) as coin and shift operators. Then, the first three steps of this quantum walk can be written as:

$$\mathrm{\mid }\psi {⟩}_1=\frac{1}{\sqrt{2}}\mathrm{\mid }0{⟩}_c\mathrm{\mid }1{⟩}_p+\frac{1}{\sqrt{2}}\mathrm{\mid }1{⟩}_c\mathrm{\mid }-1{⟩}_p,|\backslash psi\backslash rangle\_1\; =\; \backslash frac\{1\}\{\backslash sqrt\{2\}\}\; |0\backslash rangle\_c\; |1\backslash rangle\_p\; +\; \backslash frac\{1\}\{\backslash sqrt\{2\}\}\; |1\backslash rangle\_c\; |\; -1\backslash rangle\_p\; ,$$$$|\psi\rangle_2 = \left(\frac{1}{2}|0\rangle_c + 0|1\rangle_c\right)|2\rangle_p + \left(\frac{1}{2}|0\rangle_c + \frac{1}{2}|1\rangle_c\right)|0\rangle_p + \left(0|0\rangle_c - \frac{1}{2}|1\rangle_c\right)|-2\rangle_p ,$$

and

$$\mathrm{\mid }\psi {⟩}_3=(\frac{1}{2\sqrt{2}}\mathrm{\mid }0{⟩}_c+0\mathrm{\mid }1{⟩}_c)\mathrm{\mid }3{⟩}_p+(\frac{1}{\sqrt{2}}\mathrm{\mid }0{⟩}_c+\frac{1}{2\sqrt{2}}\mathrm{\mid }1{⟩}_c)\mathrm{\mid }1{⟩}_p+(\frac{-1}{2\sqrt{2}}\mathrm{\mid }0{⟩}_c+0\mathrm{\mid }1{⟩}_c)\mathrm{\mid }-1{⟩}_p+(0\mathrm{\mid }0{⟩}_c+\frac{1}{2\sqrt{2}}\mathrm{\mid }1{⟩}_c)\mathrm{\mid }-3{⟩}_p\mathrm{.}|\backslash psi\backslash rangle\_3\; =\; \backslash left(\backslash frac\{1\}\{2\backslash sqrt\{2\}\}|0\backslash rangle\_c\; +\; 0|1\backslash rangle\_c\backslash right)|3\backslash rangle\_p\; +\; \backslash left(\backslash frac\{1\}\{\backslash sqrt\{2\}\}|0\backslash rangle\_c\; +\; \backslash frac\{1\}\{2\backslash sqrt\{2\}\}|1\backslash rangle\_c\backslash right)|1\backslash rangle\_p\; +\; \backslash \backslash \; \backslash left(\backslash frac\{-1\}\{2\backslash sqrt\{2\}\}|0\backslash rangle\_c\; +\; 0|1\backslash rangle\_c\backslash right)|-1\backslash rangle\_p\; +\; \backslash left(0|0\backslash rangle\_c\; +\; \backslash frac\{1\}\{2\backslash sqrt\{2\}\}|1\backslash rangle\_c\backslash right)|-3\backslash rangle\_p\; .$$

We now define

$$\mathrm{\Psi }(n,t)=\left(\begin{array}{c}{\mathrm{\Psi }}_R(n,t)\\ {\mathrm{\Psi }}_L(n,t)\end{array}\right)(15)\backslash Psi(n,\; t)\; =\; \backslash begin\{pmatrix\}\; \backslash Psi\_R(n,\; t)\; \backslash \backslash \; \backslash Psi\_L(n,\; t)\; \backslash end\{pmatrix\}\; \backslash quad\; (15)$$

as the two component vector of amplitudes of the particle being at point $n$ and time $t$ or, in operator notation

$$\mathrm{\mid }\mathrm{\Psi }(n,t)⟩={\mathrm{\Psi }}_L(n,t)\mathrm{\mid }1⟩+{\mathrm{\Psi }}_R(n,t)\mathrm{\mid }0⟩(16)|\backslash Psi(n,\; t)\backslash rangle\; =\; \backslash Psi\_L(n,\; t)|1\backslash rangle\; +\; \backslash Psi\_R(n,\; t)|0\backslash rangle\; \backslash quad\; (16)$$

We shall now analyze the behavior of a Hadamard walk at point $n$ after $t + 1$ steps. We begin by applying the Hadamard operator given by Eq. (8) to those coin state components in position $n - 1$ , $n$ and $n + 1$ :

$$\widehat{H}(\mathrm{\mid }\mathrm{\Psi }(n-1,t)⟩+\mathrm{\mid }\mathrm{\Psi }(n,t)⟩+\mathrm{\mid }\mathrm{\Psi }(n+1,t)⟩)=\frac{1}{\sqrt{2}}(\mathrm{\mid }{\mathrm{\Psi }}_L(n-1,t)⟩\mathrm{\mid }0⟩+\mathrm{\mid }{\mathrm{\Psi }}_R(n-1,t)⟩\mathrm{\mid }0⟩-\mathrm{\mid }{\mathrm{\Psi }}_L(n+1,t)⟩\mathrm{\mid }1⟩+\mathrm{\mid }{\mathrm{\Psi }}_R(n+1,t)⟩\mathrm{\mid }1⟩-\mathrm{\mid }{\mathrm{\Psi }}_L(n-1,t)⟩\mathrm{\mid }1⟩+\mathrm{\mid }{\mathrm{\Psi }}_R(n-1,t)⟩\mathrm{\mid }1⟩+\mathrm{\mid }{\mathrm{\Psi }}_L(n+1,t)⟩\mathrm{\mid }0⟩+\mathrm{\mid }{\mathrm{\Psi }}_R(n+1,t)⟩\mathrm{\mid }0⟩+\mathrm{\mid }{\mathrm{\Psi }}_L(n,t)⟩\mathrm{\mid }0⟩+\mathrm{\mid }{\mathrm{\Psi }}_R(n,t)⟩\mathrm{\mid }0⟩-\mathrm{\mid }{\mathrm{\Psi }}_L(n,t)⟩\mathrm{\mid }1⟩+\mathrm{\mid }{\mathrm{\Psi }}_R(n,t)⟩\mathrm{\mid }1⟩)(17)\backslash hat\{H\}(|\backslash Psi(n\; -\; 1,\; t)\backslash rangle\; +\; |\backslash Psi(n,\; t)\backslash rangle\; +\; |\backslash Psi(n\; +\; 1,\; t)\backslash rangle)\; =\; \backslash \backslash \; \backslash frac\{1\}\{\backslash sqrt\{2\}\}(|\backslash Psi\_L(n\; -\; 1,\; t)\backslash rangle|0\backslash rangle\; +\; |\backslash Psi\_R(n\; -\; 1,\; t)\backslash rangle|0\backslash rangle\; -\; |\backslash Psi\_L(n\; +\; 1,\; t)\backslash rangle|1\backslash rangle\; +\; |\backslash Psi\_R(n\; +\; 1,\; t)\backslash rangle|1\backslash rangle\; \backslash \backslash \; -\; |\backslash Psi\_L(n\; -\; 1,\; t)\backslash rangle|1\backslash rangle\; +\; |\backslash Psi\_R(n\; -\; 1,\; t)\backslash rangle|1\backslash rangle\; +\; |\backslash Psi\_L(n\; +\; 1,\; t)\backslash rangle|0\backslash rangle\; +\; |\backslash Psi\_R(n\; +\; 1,\; t)\backslash rangle|0\backslash rangle\; \backslash \backslash \; +\; |\backslash Psi\_L(n,\; t)\backslash rangle|0\backslash rangle\; +\; |\backslash Psi\_R(n,\; t)\backslash rangle|0\backslash rangle\; -\; |\backslash Psi\_L(n,\; t)\backslash rangle|1\backslash rangle\; +\; |\backslash Psi\_R(n,\; t)\backslash rangle|1\backslash rangle)\; \backslash quad\; (17)$$

Now, we apply the shift operator given by Eq. (9) to Eq. (17)

$$\widehat{U}(\widehat{H}(\mathrm{\mid }\mathrm{\Psi }(n-1,t)⟩+\mathrm{\mid }\mathrm{\Psi }(n,t)⟩+\mathrm{\mid }\mathrm{\Psi }(n+1,t)⟩))=\frac{1}{\sqrt{2}}(\mathrm{\mid }{\mathrm{\Psi }}_L(n,t)⟩\mathrm{\mid }0⟩+\mathrm{\mid }{\mathrm{\Psi }}_R(n,t)⟩\mathrm{\mid }0⟩-\mathrm{\mid }{\mathrm{\Psi }}_L(n,t)⟩\mathrm{\mid }1⟩+\mathrm{\mid }{\mathrm{\Psi }}_R(n,t)⟩\mathrm{\mid }1⟩-\mathrm{\mid }{\mathrm{\Psi }}_L(n-2,t)⟩\mathrm{\mid }1⟩+\mathrm{\mid }{\mathrm{\Psi }}_R(n-2,t)⟩\mathrm{\mid }1⟩+\mathrm{\mid }{\mathrm{\Psi }}_L(n+2,t)⟩\mathrm{\mid }0⟩+\mathrm{\mid }{\mathrm{\Psi }}_R(n+2,t)⟩\mathrm{\mid }0⟩-\mathrm{\mid }{\mathrm{\Psi }}_L(n-1,t)⟩\mathrm{\mid }1⟩+\mathrm{\mid }{\mathrm{\Psi }}_R(n-1,t)⟩\mathrm{\mid }1⟩+\mathrm{\mid }{\mathrm{\Psi }}_L(n+1,t)⟩\mathrm{\mid }0⟩+\mathrm{\mid }{\mathrm{\Psi }}_R(n+1,t)⟩\mathrm{\mid }0⟩)(18)\backslash hat\{U\}(\backslash hat\{H\}(|\backslash Psi(n\; -\; 1,\; t)\backslash rangle\; +\; |\backslash Psi(n,\; t)\backslash rangle\; +\; |\backslash Psi(n\; +\; 1,\; t)\backslash rangle))\; =\; \backslash \backslash \; \backslash frac\{1\}\{\backslash sqrt\{2\}\}(|\backslash Psi\_L(n,\; t)\backslash rangle|0\backslash rangle\; +\; |\backslash Psi\_R(n,\; t)\backslash rangle|0\backslash rangle\; -\; |\backslash Psi\_L(n,\; t)\backslash rangle|1\backslash rangle\; +\; |\backslash Psi\_R(n,\; t)\backslash rangle|1\backslash rangle\; \backslash \backslash \; -\; |\backslash Psi\_L(n\; -\; 2,\; t)\backslash rangle|1\backslash rangle\; +\; |\backslash Psi\_R(n\; -\; 2,\; t)\backslash rangle|1\backslash rangle\; +\; |\backslash Psi\_L(n\; +\; 2,\; t)\backslash rangle|0\backslash rangle\; +\; |\backslash Psi\_R(n\; +\; 2,\; t)\backslash rangle|0\backslash rangle\; \backslash \backslash \; -\; |\backslash Psi\_L(n\; -\; 1,\; t)\backslash rangle|1\backslash rangle\; +\; |\backslash Psi\_R(n\; -\; 1,\; t)\backslash rangle|1\backslash rangle\; +\; |\backslash Psi\_L(n\; +\; 1,\; t)\backslash rangle|0\backslash rangle\; +\; |\backslash Psi\_R(n\; +\; 1,\; t)\backslash rangle|0\backslash rangle)\; \backslash quad\; (18)$$

The bold font amplitude components of Eq. (18) are the amplitude components of $|\Psi(n, t + 1)\rangle$ , which can be written in matrix notation as

Let us label$$M_- = \begin{pmatrix} \frac{-1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \ 0 & 0 \end{pmatrix} \text{ and } M_+ = \begin{pmatrix} 0 & 0 \ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{pmatrix}$$

Thus

$$\mathrm{\Psi }(n,t+1)=M_{-}\mathrm{\Psi }(n+1,t)+M_{+}\mathrm{\Psi }(n-1,t)(20)\backslash Psi(n,\; t+1)\; =\; M\_-\; \backslash Psi(n+1,\; t)\; +\; M\_+\; \backslash Psi(n-1,\; t)\; \backslash quad\; (20)$$

Eq. (20) is a difference equation with $\Psi(0, 0) = \begin{pmatrix} 1 \ 0 \end{pmatrix}$ and $\Psi(n, 0) = \begin{pmatrix} 0 \ 0 \end{pmatrix}$ , $\forall n \neq 0$ as initial conditions (Eq. (14).)

Our objective is to find analytical expressions for $\Psi_L(n, t)$ and $\Psi_R(n, t)$ . To do so, we compute the Discrete Time Fourier transform of Eq. (20). The Discrete Time Fourier Transform is given by

Definition 5 Discrete Time Fourier Transform. Let $f : \mathbb{Z} \rightarrow \mathbb{C}$ be a complex function over the integers $\Rightarrow$ its Discrete Time Fourier Transform (DTFT) $\tilde{f} : [-\pi, \pi] \rightarrow \mathbb{C}$ is given by

$$\tilde{f}=\tilde{f}(e^{i\omega })=\sum _{n=-\mathrm{\infty }}^{\mathrm{\infty }}f(n)e^{-in\omega },\backslash tilde\{f\}\; =\; \backslash tilde\{f\}(e^\{i\backslash omega\})\; =\; \backslash sum\_\{n=-\backslash infty\}^\{\backslash infty\}\; f(n)\; e^\{-in\backslash omega\},$$

and its inverse is given by

$$f(n)=\frac{1}{2\pi }{\int }_{-\pi }^{\pi }\tilde{f}(e^{i\omega })e^{in\omega }d\omega f(n)\; =\; \backslash frac\{1\}\{2\backslash pi\}\; \backslash int\_\{-\backslash pi\}^\{\backslash pi\}\; \backslash tilde\{f\}(e^\{i\backslash omega\})\; e^\{in\backslash omega\}\; d\backslash omega$$

Ambainis et al [31] employ the following slight variant of the DTFT:

$$\tilde{f}(k)=\sum _{n}f(n)e^{ikn},(21)\backslash tilde\{f\}(k)\; =\; \backslash sum\_n\; f(n)\; e^\{ikn\},\; \backslash quad\; (21)$$

where $f : \mathbb{Z} \rightarrow \mathbb{C}$ and $\tilde{f} : [-\pi, \pi] \rightarrow \mathbb{C}$ . Corresponding inverse DTFT is given by

$$f(n)=\frac{1}{2\pi }{\int }_{-\pi }^{\pi }\tilde{f}(k)e^{-ikn}dk(22)f(n)\; =\; \backslash frac\{1\}\{2\backslash pi\}\; \backslash int\_\{-\backslash pi\}^\{\backslash pi\}\; \backslash tilde\{f\}(k)\; e^\{-ikn\}\; dk\; \backslash quad\; (22)$$

So, using Eq. (21) we have

$$\tilde{\mathrm{\Psi }}(k,t)=\sum _n\mathrm{\Psi }(n,t)e^{ikn}(23)\backslash tilde\{\backslash Psi\}(k,\; t)\; =\; \backslash sum\_n\; \backslash Psi(n,\; t)\; e^\{ikn\}\; \backslash quad\; (23)$$

Using Eq. (20) we obtain

$$\tilde{\mathrm{\Psi }}(k,t+1)=\sum _n(M_{-}\mathrm{\Psi }(n+1,t)+M_{+}\mathrm{\Psi }(n-1,t))e^{ikn}(24)\backslash tilde\{\backslash Psi\}(k,\; t+1)\; =\; \backslash sum\_n\; (M\_-\; \backslash Psi(n+1,\; t)\; +\; M\_+\; \backslash Psi(n-1,\; t))\; e^\{ikn\}\; \backslash quad\; (24)$$

After some algebra we get

Thus

$$\tilde{\mathrm{\Psi }}(k,t)=\left(\begin{array}{c}{\tilde{\mathrm{\Psi }}}_L(k,t)\\ {\tilde{\mathrm{\Psi }}}_R(k,t)\end{array}\right)=M_k^t\tilde{\mathrm{\Psi }}(k,0),\text{ where }\tilde{\mathrm{\Psi }}(k,0)=\left(\begin{array}{c}1\\ 0\end{array}\right)(26)\backslash tilde\{\backslash Psi\}(k,\; t)\; =\; \backslash begin\{pmatrix\}\; \backslash tilde\{\backslash Psi\}\_L(k,\; t)\; \backslash \backslash \; \backslash tilde\{\backslash Psi\}\_R(k,\; t)\; \backslash end\{pmatrix\}\; =\; M\_k^t\; \backslash tilde\{\backslash Psi\}(k,\; 0),\; \backslash text\{\; where\; \}\; \backslash tilde\{\backslash Psi\}(k,\; 0)\; =\; \backslash begin\{pmatrix\}\; 1\; \backslash \backslash \; 0\; \backslash end\{pmatrix\}\; \backslash quad\; (26)$$

Our problem now consists in diagonalizing the (unitary) matrix $M_k$ in order to calculate $M_k^t$ . If $M_k$ has eigenvalues ${\lambda_k^1, \lambda_k^2}$ and eigenvectors $|\Phi_k^1\rangle, |\Phi_k^2\rangle$ then

$$M_k={\lambda }_k^1\mathrm{\mid }{\mathrm{\Phi }}_k^1⟩⟨{\mathrm{\Phi }}_k^1\mathrm{\mid }+{\lambda }_k^2\mathrm{\mid }{\mathrm{\Phi }}_k^2⟩⟨{\mathrm{\Phi }}_k^2\mathrm{\mid }(27)M\_k\; =\; \backslash lambda\_k^1\; |\backslash Phi\_k^1\backslash rangle\; \backslash langle\; \backslash Phi\_k^1|\; +\; \backslash lambda\_k^2\; |\backslash Phi\_k^2\backslash rangle\; \backslash langle\; \backslash Phi\_k^2|\; \backslash quad\; (27)$$

Using the mathematical properties of linear operators, we then find:

$$M_k^t=({\lambda }_k^1{)}^t\mathrm{\mid }{\mathrm{\Phi }}_k^1⟩⟨{\mathrm{\Phi }}_k^1\mathrm{\mid }+({\lambda }_k^2{)}^t\mathrm{\mid }{\mathrm{\Phi }}_k^2⟩⟨{\mathrm{\Phi }}_k^2\mathrm{\mid }(28)M\_k^t\; =\; (\backslash lambda\_k^1)^t\; |\backslash Phi\_k^1\backslash rangle\; \backslash langle\; \backslash Phi\_k^1|\; +\; (\backslash lambda\_k^2)^t\; |\backslash Phi\_k^2\backslash rangle\; \backslash langle\; \backslash Phi\_k^2|\; \backslash quad\; (28)$$

It is shown in [340] and [31] that

$${\lambda }_k^1=e^{i{\omega }_k},{\lambda }_k^2=e^{i(\pi -{\omega }_k)},\text{ where }{\omega }_k\in [-\frac{\pi }{2},\frac{\pi }{2}]\text{ and }\sin ({\omega }_k)=\frac{\sin k}{\sqrt{2}}(29)\backslash lambda\_k^1\; =\; e^\{i\backslash omega\_k\},\; \backslash lambda\_k^2\; =\; e^\{i(\backslash pi-\backslash omega\_k)\},\; \backslash text\{\; where\; \}\; \backslash omega\_k\; \backslash in\; [-\backslash frac\{\backslash pi\}\{2\},\; \backslash frac\{\backslash pi\}\{2\}]\; \backslash text\{\; and\; \}\; \backslash sin(\backslash omega\_k)\; =\; \backslash frac\{\backslash sin\; k\}\{\backslash sqrt\{2\}\}\; \backslash quad\; (29)$$

and

$${\mathrm{\Phi }}_k^1=\frac{1}{\sqrt{2[(1+{\cos }^2(k))+\cos (k)\sqrt{1+{\cos }^{2}k}]}}\left(\begin{array}{c}{e}^{-ik}\\ \sqrt{2}{e}^{i{\omega }_k}+e^{-ik}\end{array}\right)(30a)\backslash Phi\_k^1\; =\; \backslash frac\{1\}\{\backslash sqrt\{2[(1\; +\; \backslash cos^2(k))\; +\; \backslash cos(k)\backslash sqrt\{1\; +\; \backslash cos^2\; k\}]\}\}\; \backslash begin\{pmatrix\}\; e^\{-ik\}\; \backslash \backslash \; \backslash sqrt\{2\}e^\{i\backslash omega\_k\}\; +\; e^\{-ik\}\; \backslash end\{pmatrix\}\; \backslash quad\; (30a)$$

$${\mathrm{\Phi }}_k^2=\frac{1}{\sqrt{2[(1+{\cos }^2(\pi -k))+\cos (\pi -k)\sqrt{1+{\cos }^2(\pi -k)]}}}\left(\begin{array}{c}{e}^{-ik}\\ -\sqrt{2}{e}^{-i{\omega }_k}+e^{-ik}\end{array}\right)(30b)\backslash Phi\_k^2\; =\; \backslash frac\{1\}\{\backslash sqrt\{2[(1\; +\; \backslash cos^2(\backslash pi\; -\; k))\; +\; \backslash cos(\backslash pi\; -\; k)\backslash sqrt\{1\; +\; \backslash cos^2(\backslash pi\; -\; k)]\}\}\}\; \backslash begin\{pmatrix\}\; e^\{-ik\}\; \backslash \backslash \; -\backslash sqrt\{2\}e^\{-i\backslash omega\_k\}\; +\; e^\{-ik\}\; \backslash end\{pmatrix\}\; \backslash quad\; (30b)$$

From Eqs. (29), (30a) and (30b) we compute the Fourier-transformed amplitudes $\tilde{\Psi}_L(n, t)$ and $\tilde{\Psi}_R(n, t)$

$${\tilde{\mathrm{\Psi }}}_L(n,t)=\frac{e^{-ik}}{2\sqrt{1+{\cos }^{2}k}}(e^{i{\omega }_{k}t}-(-1{)}^t{e}^{-i{\omega }_{k}t})(31a)\backslash tilde\{\backslash Psi\}\_L(n,\; t)\; =\; \backslash frac\{e^\{-ik\}\}\{2\backslash sqrt\{1\; +\; \backslash cos^2\; k\}\}\; (e^\{i\backslash omega\_k\; t\}\; -\; (-1)^t\; e^\{-i\backslash omega\_k\; t\})\; \backslash quad\; (31a)$$

$${\tilde{\mathrm{\Psi }}}_R(n,t)=\frac{1}{2}(1+\frac{\cos k}{\sqrt{1+{\cos }^{2}k}})e^{i{\omega }_{k}t}+\frac{(-1{)}^t}{2}(1-\frac{\cos k}{\sqrt{1+{\cos }^{2}k}})e^{-i{\omega }_{k}t}(31b)\backslash tilde\{\backslash Psi\}\_R(n,\; t)\; =\; \backslash frac\{1\}\{2\}\; \backslash left(1\; +\; \backslash frac\{\backslash cos\; k\}\{\backslash sqrt\{1\; +\; \backslash cos^2\; k\}\}\backslash right)\; e^\{i\backslash omega\_k\; t\}\; +\; \backslash frac\{(-1)^t\}\{2\}\; \backslash left(1\; -\; \backslash frac\{\backslash cos\; k\}\{\backslash sqrt\{1\; +\; \backslash cos^2\; k\}\}\backslash right)\; e^\{-i\backslash omega\_k\; t\}\; \backslash quad\; (31b)$$

Using Eq. (5) on Eqs. (31a) and (31b), it is possible to prove the following theorem:

Theorem 2 Let $|\Psi\rangle_0 = |0\rangle_p \otimes |0\rangle_c$ be the initial state of a discrete quantum walk on an infinite line with coin and shift operators given by Eqs. (8) and (9) respectively $\Rightarrow$

$${\mathrm{\Psi }}_L(n,t)=\frac{1}{2\pi }{\int }_{-\pi }^{\pi }\frac{-i{e}^{ik}}{2\sqrt{1+{\cos }^{2}k}}(e^{-i({\omega }_{k}t-kn)})dk\backslash Psi\_L(n,\; t)\; =\; \backslash frac\{1\}\{2\backslash pi\}\; \backslash int\_\{-\backslash pi\}^\{\backslash pi\}\; \backslash frac\{-ie^\{ik\}\}\{2\backslash sqrt\{1\; +\; \backslash cos^2\; k\}\}\; (e^\{-i(\backslash omega\_k\; t\; -\; kn)\})\; dk$$

$${\mathrm{\Psi }}_R(n,t)=\frac{1}{2\pi }{\int }_{-\pi }^{\pi }(1+\frac{\cos k}{\sqrt{1+{\cos }^{2}k}})(e^{-i({\omega }_{k}t-kn)})dk\backslash Psi\_R(n,\; t)\; =\; \backslash frac\{1\}\{2\backslash pi\}\; \backslash int\_\{-\backslash pi\}^\{\backslash pi\}\; \backslash left(1\; +\; \backslash frac\{\backslash cos\; k\}\{\backslash sqrt\{1\; +\; \backslash cos^2\; k\}\}\backslash right)\; (e^\{-i(\backslash omega\_k\; t\; -\; kn)\})\; dk$$

where $\omega_k = \sin^{-1}\left(\frac{\sin k}{\sqrt{2}}\right)$ and $\omega_k \in [-\frac{\pi}{2}, \frac{\pi}{2}]$ .The amplitudes for even $n$ (odd $n$ ) at odd $t$ (even $t$ ) are zero, as it can be inferred from the definition of the quantum walk. Now we have an analytical expression for $\Psi_L(n, t)$ and $\Psi_R(n, t)$ , and taking into account that $P(n, t) = |\Psi_L(n, t)|^2 + |\Psi_R(n, t)|^2$ , we are interested in studying the asymptotical behavior of $\Psi(n, t)$ and $P(n, t)$ . Integrals in Theorem 2 are of the form

$$I(\alpha ,t)=\frac{1}{2\pi }{\int }_{-\pi }^{\pi }g(k)e^{i\varphi (k,\alpha )t}dk,\text{ where }\alpha =n\mathrm{/}t\text{ (= position/number of steps)}I(\backslash alpha,\; t)\; =\; \backslash frac\{1\}\{2\backslash pi\}\; \backslash int\_\{-\backslash pi\}^\{\backslash pi\}\; g(k)\; e^\{i\backslash phi(k,\; \backslash alpha)t\}\; dk,\; \backslash text\{\; where\; \}\; \backslash alpha\; =\; n/t\; \backslash text\{\; (=\; position/number\; of\; steps)\}$$

The asymptotical properties of this kind of integral can be studied using the method of stationary phase ([65] and [77]), a standard method in complex analysis. Using such a method, the authors of [31] and [340] reported the following theorems and conclusions:

Theorem 3 Let $\epsilon > 0$ be any constant, and $\alpha$ be in the interval $(\frac{-1}{\sqrt{2}} + \epsilon, \frac{1}{\sqrt{2}} - \epsilon)$ . Then, as $t \rightarrow \infty$ , we have (uniformly in $n$ )

$$p_L(n,t)\sim \frac{2}{\pi \sqrt{1-2{\alpha }^{2}t}}{\cos }^2(-\omega t+\frac{\pi }{4}-\rho ),p\_L(n,\; t)\; \backslash sim\; \backslash frac\{2\}\{\backslash pi\backslash sqrt\{1-2\backslash alpha^2t\}\}\; \backslash cos^2(-\backslash omega\; t\; +\; \backslash frac\{\backslash pi\}\{4\}\; -\; \backslash rho),$$

$$p_R(n,t)\sim \frac{2(1+\alpha )}{\pi (1-\alpha )\sqrt{1-2{\alpha }^{2}t}}{\cos }^2(-\omega t+\frac{\pi }{4})p\_R(n,\; t)\; \backslash sim\; \backslash frac\{2(1+\backslash alpha)\}\{\backslash pi(1-\backslash alpha)\backslash sqrt\{1-2\backslash alpha^2t\}\}\; \backslash cos^2(-\backslash omega\; t\; +\; \backslash frac\{\backslash pi\}\{4\})$$

where $\omega = \alpha\rho + \theta$ , $\rho = \arg(-B + \sqrt{\Delta})$ , $\theta = \arg(B + 2 + \sqrt{\Delta})$ , $B = \frac{2\alpha}{1-\alpha}$ and $\Delta = B^2 - 4(B+1)$ .

Theorem 4 Let $n = \alpha t \rightarrow \infty$ with $\alpha$ fixed. In case $\alpha \in (-1, -1/\sqrt{2}) \cup (1/\sqrt{2}, 1) \Rightarrow \exists c > 1$ for which $p_L(n, t) = O(c^{-n})$ and $p_R(n, t) = O(c^{-n})$ .

Conclusions

1. Quasi-uniform behavior and standard deviation. The wave function $\Psi_L(n, t)$ and $\Psi_R(n, t)$ (Theorem 2) is almost uniformly spread over the region for which $\alpha$ is in the interval $[-1/\sqrt{2}, 1/\sqrt{2}]$ (Theorem 3), and shrinks quickly outside this region (Theorem 4). Furthermore, by integrating the probability functions from Theorem 3, it is possible to see that almost all of the probability is concentrated in the interval $[(-1/\sqrt{2} + \epsilon)t, (1/\sqrt{2} - \epsilon)t]$ . In fact, the exact probability value in that interval is $P = 1 - \frac{2\epsilon}{\pi} - \frac{O(1)}{t}$ .

Furthermore, the position probability distribution spreads as a function of $t$ , i.e. $[-t/\sqrt{2}, t/\sqrt{2}]$ , hence an evidence of

$${\sigma }_{\widehat{H}}=O(t)(32)\backslash sigma\_\{\backslash hat\{H\}\}\; =\; O(t)\; \backslash quad\; (32)$$

Konno [248] as well as Kendon and Tregenna [238] have computed the actual variance of the probability distribution given in Theorem 3. Furthermore, by introducing a novel method to compute the probability distribution $X$ of the unrestricted DQWL, it was shown in [248] that $\frac{\sigma(X)}{t} \rightarrow \sqrt{\frac{\sqrt{2}-1}{2}}$ as $t \rightarrow \infty$ . In any case, the standard deviation of the unrestricted Hadamard DQWL is $O(t)$ and that result is in contrast with the standard deviation of an unrestricted classical random walk on a line, which is $O(\sqrt{t})$ (cf. Eq. (2).)

2. Mixing time. It was shown in [31] and [340] that an unrestricted HadamardDQWL has a linear mixing time $\tau_\epsilon^{(q)} = O(t)$ , where $t$ is the number of steps. Furthermore, $\tau_\epsilon^{(q)}$ was compared with the corresponding mixing time of a classical random walk on a line, which is quadratic, i.e. $\tau_\epsilon^{(c)} = O(t^2)$ .

In order to properly bound and evaluate the impact of this result in the fields of quantum walks and quantum computation, a few clarifications are needed.

a) The mixing time measure used in this case is not the same as Eq. (4), the reason being that unitary Markov chains in finite state space (such as finite graph analogues of quantum walks) have no stationary distribution (section 2 of [31].) Instead, the mixing time measure proposed is given by

Definition 6 Instantaneous Mixing Time. $\tau_\epsilon = \max_u \min_t {t \mid |P_u(t) - \pi| \leq \epsilon}$

which is a more relaxed definition in the sense that it measures the first time that the current probability distribution $P_u(t)$ is $\epsilon$ -close to the stationary distribution, without the requirement of continuing being $\epsilon$ -close for all future steps.

b) The stationary distribution of an unrestricted classical random walk on a line is the binomial distribution, spread all over $\mathbb{Z}$ . The only difference between $P_t$ , the probability distribution of an unrestricted classical random walk on a line at step $t$ , and its limiting distribution $P$ is the numerical value of the probability assigned to each node, as the shape of the distribution is the same. Although the binomial distribution can be roughly approximated by a uniform distribution for large values of $t$ , depending on the precision we need for a certain task, that comparison is not accurate: as shown in our previous subsection on classical random walks, the hitting time of an unrestricted classical random walk on a line depends on the region we are looking into. Specifically, the hitting time is $O(\sqrt{t})$ for $k \ll t$ and $O(2^t)$ for $k \approx t$ (Eqs. (4) and (5).) Thus, to hit node $k$ with equal probabilities $P_{t_k} = P_k$ may depend on the region where $k$ is located. For example, it may take $O(\sqrt{t})$ if $k \ll t$ and $O(2^t)$ if $k \approx t$ .

So, comparing mixing and hitting times for quantum and classical unrestricted walks on a line is not necessarily clear and straightforward. In order to reduce complexity in the analysis of algorithms, the infiniteness property of unrestricted classical random walks can sometimes be relaxed and properties of classical random walks on finite lines could be used instead, as proposed by Rantanen in [367].

2.2.3 Discrete Path Integral Analysis of the Hadamard Walk

A different proposal to study the properties of quantum walks, based on combinatorics and the method to quantify quantum state amplitudes given by Meyer in [326], has been delivered by Ambainis et al in [31] as well as Carteret et al in [93, 94].) The main idea behind this approach is to count the number of paths that take a quantum walker from point $a$ to point $b$ . Thus, this approach can also be seen as a discrete path-integral method. Let us begin by stating the following lemma:

Lemma 1 [31] and [326]. Let $t \in [-n, n) \cap \mathbb{Z}$ and $l = \frac{t-n}{2}$ . The amplitudes of position $n$ after $t$ steps of the Hadamard walk are:

$${\psi }_L(n,t)=\frac{1}{\sqrt{2^t}}\sum _k\left(\genfrac{}{}{0px}{}{l-1}{k}\right)\left(\genfrac{}{}{0px}{}{t-l}{k}\right)(-1{)}^{l-k-1}(33a)\backslash psi\_L(n,\; t)\; =\; \backslash frac\{1\}\{\backslash sqrt\{2^t\}\}\; \backslash sum\_k\; \backslash binom\{l-1\}\{k\}\; \backslash binom\{t-l\}\{k\}\; (-1)^\{l-k-1\}\; \backslash quad\; (33a)$$$$\psi_R(n, t) = \frac{1}{\sqrt{2^t}} \sum_k \binom{l-1}{k-1} \binom{t-l}{k} (-1)^{l-k} \quad (33b)$$

It was shown in [31] that the probabilities computed from those amplitudes of Lemma (1) can be expressed using Jacobi polynomials. Furthermore, it was shown in [94] that both Schrödinger and combinatorial approaches are equivalent.

Theorem 5 Let $n \in \mathbb{N} \cup {0}$ and $J_\nu^{(a,b)}(z)$ be the normalised degree $\nu$ Jacobi polynomial with $J_\nu^{(a,b)}$ as its constant term. Let us also define $\nu = \frac{(t-n)}{2} - 1$ . Then

$$P_l(n,t)=2^{-n-2}(J_{\nu }^{(0,n+1)}{)}^2(34a)P\_l(n,\; t)\; =\; 2^\{-n-2\}\; (J\_\backslash nu^\{(0,n+1)\})^2\; \backslash quad\; (34a)$$

$$P_R(n,t)={\left(\frac{t+n}{t-n}\right)}^2{2}^{-n-2}(J_{\nu }^{(1,n)}{)}^2,(34b)P\_R(n,\; t)\; =\; \backslash left(\backslash frac\{t+n\}\{t-n\}\backslash right)^2\; 2^\{-n-2\}\; (J\_\backslash nu^\{(1,n)\})^2,\; \backslash quad\; (34b)$$

$$\text{with }{p}_L(-n,t)=p_L(n-2,t)\text{ and }{p}_R(-n,t)={\left(\frac{t-n}{t+n}\right)}^2{p}_R(n,t)\backslash text\{with\; \}\; p\_L(-n,\; t)\; =\; p\_L(n-2,\; t)\; \backslash text\{\; and\; \}\; p\_R(-n,\; t)\; =\; \backslash left(\backslash frac\{t-n\}\{t+n\}\backslash right)^2\; p\_R(n,\; t)$$

A slight variation of this approach has been given by Brun et al in [87]. An alternative and powerful method for building quantum walks, based on combinatorics and decompositions of unitary matrices, has been proposed by Konno in [248, 249, 251, 252]. Also, Katori et al proposed in [227] to apply Group Theory to analyze symmetry properties of quantum walks on a line and, along the same line of thought, Chandrashekar et al have proposed a generalized version of the discrete quantum walk with coins living in $SU(2)$ [105].

2.2.4 Unrestricted DQWL with a general coin

The study of the Hadamard walk is relevant to the field of quantum walks not only as an example but also because of the fact that some important properties shown by the Hadamard walk (for example, its standard deviation and mixing time) are shared by any quantum walk on the line. In [431], Tregenna et al showed that, for a general unbiased initial coin state

$$\mathrm{\mid }\psi (x,0)⟩=\sqrt{\eta }(\mathrm{\mid }0{⟩}_c+e^{i\alpha }\sqrt{1-\eta }\mathrm{\mid }1{⟩}_c)\otimes \mathrm{\mid }0{⟩}_p(35)|\backslash psi(x,\; 0)\backslash rangle\; =\; \backslash sqrt\{\backslash eta\}(|0\backslash rangle\_c\; +\; e^\{i\backslash alpha\}\backslash sqrt\{1-\backslash eta\}|1\backslash rangle\_c)\; \backslash otimes\; |0\backslash rangle\_p\; \backslash quad\; (35)$$

and a single step (in Fourier space) of the quantum walk

$$\mathrm{\mid }\tilde{\psi }(k,t+1)⟩={\tilde{C}}_k\mathrm{\mid }\tilde{\psi }(k,t)⟩|\backslash tilde\{\backslash psi\}(k,\; t+1)\backslash rangle\; =\; \backslash tilde\{C\}\_k\; |\backslash tilde\{\backslash psi\}(k,\; t)\backslash rangle$$

where

is the Fourier transformed version of the most general 2-dimensional coin operator

with $\theta, \phi \in [0, \pi]$ and $\rho \in [0, 1]$ , we can express a $t$ -step quantum walk on a line as$$|\tilde{\psi}(k, t+1)\rangle = \tilde{C}_k^t |\tilde{\psi}(k, 0)\rangle, \text{ where } |\tilde{\psi}(k, 0)\rangle = \left( e^{i\alpha} \frac{\sqrt{\eta}}{\sqrt{1-\eta}} \right) \otimes |k\rangle \quad (37)$$

If $\tilde{C}_k$ is expressed in terms of its eigenvalues $\lambda_k^\pm$ and eigenvectors $|\lambda_k^\pm\rangle$ then $\tilde{C}_k^t = (\lambda_k^+)^t |\lambda_k^+\rangle \langle \lambda_k^+| + (\lambda_k^-)^t |\lambda_k^-\rangle \langle \lambda_k^-|$ , and Eq. (37) can be written as

$$\mathrm{\mid }\tilde{\psi }(k,t+1)⟩=({\lambda }_k^{+}{)}^t\mathrm{\mid }{\lambda }_k^{+}⟩⟨{\lambda }_k^{+}\mathrm{\mid }\tilde{\psi }(k,0)⟩+({\lambda }_k^{-}{)}^t\mathrm{\mid }{\lambda }_k^{-}⟩⟨{\lambda }_k^{-}\mathrm{\mid }\tilde{\psi }(k,0)⟩(38)|\backslash tilde\{\backslash psi\}(k,\; t+1)\backslash rangle\; =\; (\backslash lambda\_k^+)^t\; |\backslash lambda\_k^+\backslash rangle\; \backslash langle\; \backslash lambda\_k^+|\; \backslash tilde\{\backslash psi\}(k,\; 0)\backslash rangle\; +\; (\backslash lambda\_k^-)^t\; |\backslash lambda\_k^-\backslash rangle\; \backslash langle\; \backslash lambda\_k^-|\; \backslash tilde\{\backslash psi\}(k,\; 0)\backslash rangle\; \backslash quad\; (38)$$

with

$$({\lambda }_k^{\pm }{)}^t⟨{\lambda }_k^{\pm }\mathrm{\mid }\tilde{\psi }(k,0)⟩=\frac{({\lambda }_k^{\pm }{)}^t}{n_k^{\pm }}{e}^{-ik}[\sqrt{\eta }-\sqrt{\frac{1-\eta }{1-\rho }}{e}^{i(\theta +\alpha )}(\sqrt{\rho }\mp e^{i(k-\delta )}{e}^{\mp i{\omega }_k})],(39)(\backslash lambda\_k^\backslash pm)^t\; \backslash langle\; \backslash lambda\_k^\backslash pm\; |\; \backslash tilde\{\backslash psi\}(k,\; 0)\backslash rangle\; =\; \backslash frac\{(\backslash lambda\_k^\backslash pm)^t\}\{n\_k^\backslash pm\}\; e^\{-ik\}\; \backslash left[\; \backslash sqrt\{\backslash eta\}\; -\; \backslash sqrt\{\backslash frac\{1-\backslash eta\}\{1-\backslash rho\}\}\; e^\{i(\backslash theta+\backslash alpha)\}\; (\backslash sqrt\{\backslash rho\}\; \backslash mp\; e^\{i(k-\backslash delta)\}\; e^\{\backslash mp\; i\backslash omega\_k\})\; \backslash right],\; \backslash quad\; (39)$$

where $\delta = (\theta + \phi)/2$ , $\sin(\omega_k) = \sqrt{\rho} \sin(k - \delta)$ , $\lambda_k^\pm = \pm e^{i\delta} e^{\pm i\omega_k}$ , $n_k = \sqrt{\frac{2[1 \mp \sqrt{\rho} \cos(k - \delta \mp \omega_k)]}{1-\rho}}$ , $\lambda^\pm = \pm e^{i\delta} e^{\pm i\omega_k}$ and $|\lambda^\pm\rangle = \frac{1}{n_k^\pm} \begin{pmatrix} e^{ik} \ e^{i\theta} (\lambda^\pm - \sqrt{\rho} e^{ik}) / \sqrt{1-\rho} \end{pmatrix}$ .

As in the Hadamard walk case, the properties of the quantum walk defined by Eqs. (39,37) may be studied by inverting the Fourier transform and using methods of complex analysis. Let us concentrate on the phase factors $\alpha \in \mathbb{R}$ of the coin initial state (Eq. (35)) and $\theta \in \mathbb{R}$ of the coin operator (Eq. (36).) Note that we can choose many pairs of values $(\alpha, \theta)$ for any phase factor $r = \alpha + \theta$ . So, if we fix a value for $\theta$ (i.e. if we use only one coin operator) we can always vary the initial coin state $|\psi(x, 0)\rangle$ (Eq. (35)) to get a value for $\alpha$ so that we can compute a quantum walk with a certain phase factor value $r$ . It is in this sense that we say that the study of a Hadamard walk suffices to analyze the properties of all unrestricted quantum walks on a line. In Fig. (5) we show the probability distributions of three Hadamard walks with different initial coin states.

On further studies of coined quantum walks on a line, Villagra et al [450] present a closed-form of the probability that a quantum walk arrives at a given vertex after $n$ steps, for a general symmetric $SU(2)$ coin operator.

2.2.5 Discrete Quantum walk with boundaries

The properties of discrete quantum walks on a line with one and two absorbing barriers were first studied in [31]. For the semi-infinite discrete quantum walk on a line, Theorem 6 was reported

Theorem 6 Let us denote by $p_\infty$ the probability that the measurement of whether the particle is at the location of the absorbing boundary (location 0 in [31]) $\Rightarrow p_\infty = \frac{2}{\pi}$ .

Theorem 6 is in stark contrast with its classical counterpart (Theorem 8 of [31]), as the probability of eventually being absorbed (in the classical case) is equal to unity. Furthermore, Yang, Liu and Zhang have introduced an interesting and relevant result in [295]: the absorbing probability of Theorem 6 decays faster than the classical case and, consequently, the conditional expectation of the quantum-mechanical case is finite (as opposed to the classical case in which the corresponding conditional expectation is infinite.)

The case of a quantum walk on a line with two absorbing boundaries was also studied in [31], and their main result is given in Theorem 7.Fig. 5 Graph (a) was computed using initial state $|\psi\rangle_0 = \frac{1}{\sqrt{2}}(|0\rangle_c + i|1\rangle_c) \otimes |0\rangle_p$ . Graphs (b) and (c) had $|\psi\rangle_0 = |0\rangle_c \otimes |0\rangle_p$ and $|\psi\rangle_0 = \sqrt{0.85}|0\rangle_c - \sqrt{0.15}|1\rangle_c \otimes |0\rangle_p$ as initial states, respectively. Notice that symmetry in the probability distribution can be achieved by using coin initial states with either complex or real relative phase factors [431]. All graphs were computed from 100-step Hadamard quantum walks on a line with Eq. (9) as shift operator.Theorem 7 For each $n > 1$ , let $p_n$ be the probability that the process eventually exits to the left. Also define $q_n$ to be the probability that the process exits to the right. Then

$$i)\mathrm{\forall }n>1\Rightarrow p_n+q_n=1i)\; \backslash forall\; n\; >\; 1\; \backslash Rightarrow\; p\_n\; +\; q\_n\; =\; 1$$

$$ii)\underset{n\to \mathrm{\infty }}{\lim }{p}_n=\frac{1}{\sqrt{2}}ii)\; \backslash lim\_\{n\; \backslash rightarrow\; \backslash infty\}\; p\_n\; =\; \backslash frac\{1\}\{\backslash sqrt\{2\}\}$$

In [55], Bach et al revisit Theorems 6 and 7 with detailed corresponding proofs using both Fourier transform and path counting approaches as well as prove some conjectures given in [468]. Moreover, in [54], Bach and Borisov further study the absorption probabilities of the two-barrier quantum walk. Finally, Konno studied the properties of quantum walks with boundaries using a set of matrices derived from a general unitary matrix together with a path counting method ([247, 266].)

2.2.6 Unrestricted quantum walks on a line with several coins

The effect of different and multiple coins has been studied by several authors. In [210], Inui and Konno have analyzed the localization phenomena due to eigenvalue degeneracies in one-dimensional quantum walks with 4-state coins (the results shown in [210] have some similarities with the quantum walks with maximally entangled coins reported by Venegas-Andraca et al in [445] in the sense that both quantum walks tend to concentrate most of their probability distributions about the origin of the walk, i.e. the localization phenomenon is present.) Moreover, in [338], Konno, Inui and Segawa have derived an analytical expression for the stationary distribution of one-dimensional quantum walks with 3-state coins that make the walker go either right or left or, alternatively, rest in the same position. Additionally, Ribeiro et al [372] have considered quantum walks with several biased coins applied aperiodically, D'Alessandro et al [126] have studied non-stationary quantum walks on a cycle using different coin operators at each computational step, and Feinsilver and Kocik [148] have proposed the use of Krawtchouk matrices (via tensor powers of the Hadamard matrix) for calculating quantum amplitudes.

Linden and Sharam have formally introduced a family of quantum walks, inhomogeneous quantum walks, being their main characteristic to allow coin operators to depend on both position and coin registers [288]. Shikano and Katsura [411] have studied the properties of self-duality, localization and fractality on a generalization of the inhomogeneous quantum walk model defined in [288], Konno has presented and proved a theorem on return probability for inhomogeneous walks which are periodic in position [258], Machida [303] has found that combining the action of two unitary operators in an inhomogeneous quantum walk will result in a limit distribution for $X_t/t$ that can be expressed as a $\delta$ function and a combination of density functions (for a detailed analysis of weak convergence $X_t/t$ please go to subsection 2.2.8), and Konno has proved that the return probability of a one-dimensional discrete-time quantum walk can be written in terms of elliptic integrals [259].

In [87], Brun et al analyzed the behavior of a quantum walk on the line using both $M$ 2-dimensional coins and single coins of $2^M$ dimension, and Sewagaet al [406] have computed analytical expressions for limit distributions of quantum walks driven by $M$ 2-dimensional coins as well as analyzed the conditions upon which applying $M$ 2-dimensional coins to a quantum walk leads to classical behavior. Furthermore, Bañuls et al [61] have studied the behavior of quantum walks with a time-dependent coin and Machida and Konno [305] have produced limit distributions for such quantum walks with $\hat{C} = \hat{C}(t)$ , Chandrashekar [95] has proposed a generic model of quantum walk whose dynamics is described by means of a Hamiltonian with an embedded coin, and Romanelli [383] has generalized the standard definition of a discrete quantum walk and shown that appropriate choices of quantum coin lead to obtaining a variety of wave-function spreading. Finally, Ahlbrecht et al have produced a comprehensive analysis of asymptotical behavior of ballistic and diffusive spreading, using Fourier methods together with perturbed and unperturbed operators [19].

2.2.7 Decoherence and other considerations on classical and quantum walks

The links between classical and quantum versions of random walks have been studied by several authors under different perspectives:

1. 1. Simulating classical random walks using quantum walks. Studies on this area (e.g. [453]) would provide us not only with interesting computational properties of both types of walks, but also with a deeper insight of the correspondences between the laws that govern computational processes in both classical and quantum physical systems.
2. 2. Transitions from quantum walks into classical random walks. This area of research is interesting not only for exploring computational properties of both kinds of walks, but also because we would provide quantum computer builders (i.e. experimental physicists and engineers) with some criteria and thresholds for testing the quantumness of a quantum computer. Moreover, these studies have allowed the scientific community to reflect on the quantum nature of quantum walks and some of their implications in algorithm development (in fact, we shall discuss the quantum nature of quantum walks in subsection 2.7.)

Decoherence is a physical phenomenon that typically arises from the interaction of quantum systems and their environment. Decoherence used to be thought of as an annoyance as it used to be equated with loss of quantum information. However, it has been found that decoherence can indeed play a beneficial role in natural processes (e.g. [330]) as well as produce interesting results for quantum information processing (e.g. [237, 390, 85].) In addition to these properties, decoherence via measurement or free interaction with a classical environment is a typical framework for studying transitions of quantum walks into classical random walks. Thus, for the sake of getting a deeper understanding of the physical and mathematical relations between quantum systems and their environment, together with searching for new paradigms for building quantum algorithms, studying decoherence properties and effects on quantum walks is an important field in quantum computation.

Tregenna and Kendon [237] have studied the impact of decoherence in quantum walks on a line, cycle and the hypercube, and have found that some of those decoherence effects could be useful for building quantum algorithms, Strauch [426] has also studied the effects of decoherence on continuous-time quantum walks onthe hypercube, and Fan et al [144] have proposed a convergent rescaled limit distribution for quantum walks subject to decoherence. Brun et al [86] have shown that the quantum-classical walk transition could be achieved via two possible methods, in addition to performing measurements: decoherence in the quantum coin and the use of higher-dimensional coins, Ampadu [44] has focused on generalizing the method of decoherent quantum walk proposed in [86] for two-dimensional quantum walks, and Annabestani et al have generalized the results of [86] by providing analytical expressions for different kinds of decoherence [49]. Moreover, by using a discrete path approach, it was shown by Konno that introducing a random selection of coins (that is, amplitude components for coin operators are chosen randomly, being under the unitarity constraint) makes quantum walks behave classically [252]. In [114], Childs et al make use of a family of graphs (e.g. Fig. (8(a))) to exemplify the different behavior of (continuous) quantum walks and classical random walks.

Several authors have addressed the physical and computational properties of decoherence in quantum walks: Ermann et al [142] have inspected the decoherence of quantum walks with a complex coin, where the coin is part of a larger quantum system, Chandrashekar et al [104] have studied symmetries and noise effects on coined discrete quantum walks, and Obuse and Kawakami [345] have studied one-dimensional quantum walks with spatial or temporal random defects as a consequence of interactions with random environments, having found that this kind of quantum walks can avoid complete localization. Also, Kendon et al [237, 236, 238] have extensively studied the computational consequences of coin decoherence in quantum walks, Alagić and Russell [20] have studied the effects of independent measurements on a quantum walker travelling along the hypercube (please see Def. 11 and Fig. 7), Košík et al [413] have studied the quantum to classical transition of a quantum walk by introducing random phase shifts in the coin particle, Romanelli [382] has studied one-dimensional quantum walks subjected to decoherence induced by measurements performed with timing provided by the Lévi waiting time distribution, Pérez and Romanelli [361] have analyzed a one-dimensional discrete quantum walk under decoherence, on the coin degree of freedom, with a strong spatial dependence (decoherence acts only when the walker moves on one half of the line), and Oliveira et al [348] have analyzed two-dimensional quantum walks under a decoherence regime due to random broken links on the lattice. Furthermore and taking as basis a global chirality probability distribution (GCD) independent of the walker's position proposed in [385], Romanelli has studied the behavior of one-dimensional quantum walks under two models of decoherence: periodic measurements of position and chirality as well as randomly broken links on the one-dimensional lattice [387]. Additionally, Chisaki et al [122] have studied both quantum to classical and classical to quantum transitions using discrete-time and classical random walks, and have also introduced a new kind of quantum walk entitled final-time-dependent discrete-time quantum walk (FD-DTQW) together with a limit theorem for FD-DTQW.

In [470], Zhang studied the effect of increasing decoherence (caused by measurements probabilistically performed on both walker and coin) in coined quantum walks and derived analytical expressions for position-related probability distributions, Annabestani et al have studied the impact of decoherence on the walker in one-dimensional quantum walks [50], Srikanth et al [419] have quantified the degree of 'quantumness' in decoherent quantum walks using measurement-induced distur-bance, Gönülol et al [163] have studied decoherence phenomena in two-dimensional quantum walks with traps, and Rao et al have analyzed noisy quantum walks using measurement-induced disturbance and quantum discord [368]. Moreover, Liu and Petulante have proposed a model for decoherence in an $n$ -site cycle together with a definition for decoherence time [291], as well as derived analytical expressions for i) the asymptotic dynamics of discrete quantum walks under decoherence on the coin degree of freedom [292] and on both coin and walker degrees of freedom running on $n$ -site cycles [293], ii) the order (big O) of the mixing time for the time-averaged probability of a quantum walk subject to decoherence on the coin quantum system [292], and iii) the limiting behavior of quantum entanglement between coin and walker under the same decoherence regime [293].

Schreiber et al [404] have analyzed the effect of decoherence and disorder in a photonic implementation of a quantum walk, and have shown how to use dynamic and static disorder to produce diffusive spread and Anderson localization, respectively. In addition, Ahlbrecht et al have produced a detailed manuscript in which several topics from the field of discrete quantum walks are analyzed, including ballistic and diffusive behavior, decoherent and invariance on translation, asymptotic behavior with perturbation, together with several examples [19].

2.2.8 Limit theorems for quantum walks

The central limit theorem plays a key role in determining many properties of statistical estimates. This key role has been a crucial motivation for members of the quantum computing community to derive limit distributions for quantum walks. Among the scientific contributions produced in this field, the seminal papers produced by Norio Konno and collaborators have been central to the effort of deriving analytical results and establishing solid grounds for quantum walk limit distributions.

Let us start this summary with a fundamental result for quantum walks on a line: Konno's weak limit theorem [248, 247, 251, 255] (following mathematical statements are taken verbatim from corresponding papers.)

Let $\Phi = {\varphi = (\alpha, \beta)^t \in \mathbb{C}^2 : |\alpha|^2 + |\beta|^2 = 1}$ be the set of initial qubit states of a one-dimensional quantum walk, and let $X_n^\varphi$ denote a one-dimensional quantum walk at time $n$ starting from initial qubit state $\varphi \in \Phi$ with evolution operator given by a $2 \times 2$ unitary matrix

Using a path integral approach, Konno proves the following theorem:

Theorem 8 [248, 251, 255] We assume $abcd \neq 0$ . If $n \rightarrow \infty$ , then

$$\frac{X_n^{\phi }}{n}\Rightarrow Z^{\phi }\backslash frac\{X\_n^\backslash varphi\}\{n\}\; \backslash Rightarrow\; Z^\backslash varphi$$

where $Z^\varphi$ has the following density, known as Konno's density function

$$f(x;{}^t[\alpha ,\beta ])=\frac{\sqrt{1-\mathrm{\mid }\alpha {\mathrm{\mid }}^2}}{\pi (1-x^2)\sqrt{\mathrm{\mid }\alpha {\mathrm{\mid }}^2-x^2}}\{1-(\mathrm{\mid }\alpha {\mathrm{\mid }}^2-\mathrm{\mid }\beta {\mathrm{\mid }}^2+\frac{a\alpha \bar{b}\bar{\beta }+\bar{a}\bar{\alpha }b\beta }{\mathrm{\mid }\alpha {\mathrm{\mid }}^2})x\}f(x;\; \{\}^t[\backslash alpha,\; \backslash beta])\; =\; \backslash frac\{\backslash sqrt\{1\; -\; |\backslash alpha|^2\}\}\{\backslash pi(1\; -\; x^2)\backslash sqrt\{|\backslash alpha|^2\; -\; x^2\}\}\; \backslash left\backslash \{\; 1\; -\; \backslash left(\; |\backslash alpha|^2\; -\; |\backslash beta|^2\; +\; \backslash frac\{a\backslash alpha\backslash bar\{b\}\backslash bar\{\backslash beta\}\; +\; \backslash bar\{a\}\backslash bar\{\backslash alpha\}b\backslash beta\}\{|\backslash alpha|^2\}\; \backslash right)\; x\; \backslash right\backslash \}$$for $x \in (-|a|, |a|)$ with

and $Y_n \Rightarrow Y$ means that $Y_n$ converges in distribution to a limit $Y$ .

That is, the quantity $\frac{X_n^\varphi}{n}$ , later on named a pseudovelocity, does converge to the limit distribution $Z$ . In [188], Hamada et al study the symmetric $\left[ \left( |\alpha|^2 - |\beta|^2 + \frac{a\alpha\bar{b}\beta + \bar{a}\alpha b\beta}{|a|^2} \right) = 0 \right]$ and asymmetric $\left[ \left( |\alpha|^2 - |\beta|^2 + \frac{a\alpha\bar{b}\beta + \bar{a}\alpha b\beta}{|a|^2} \right) \in \left[ \frac{-1}{r}, \frac{1}{r} \right], \text{ where } r \in (0, 1) \right]$ cases of Konno's density function.

A plethora of central results are published in [248, 247, 251, 255]. Among them, I mention the following:

• – Symmetry of probability distribution $P(X_n^\varphi)$ .

Let us define the following sets:

Definition 7

where $\mathbf{Z}_+$ is the set of the positive integers. Then,

Theorem 9 Let $\Phi_s, \Phi_0$ , and $\Phi_\perp$ be as in Def. (7). Suppose $abcd \neq 0$ . Then we have $\Phi_s = \Phi_0 = \Phi_\perp$ .

Theorem 9 is a generalization of the result given by [249] for the Hadamard walk, i.e. a one-dimensional quantum walk with the Hadamard operator (Def. 8) as evolution operator. Also, Nayak and Vishwanath [340] discussed the symmetry of distribution and showed that $[1/\sqrt{2}, \pm i/\sqrt{2}]^t \in \Phi_s$ for the Hadamard walk.

• – $m^{th}$ moment of $X_n^\varphi$ . A most interesting result from [248, 247, 251, 255] is the expected behavior of $(X_n^\varphi)^m$ : for $m$ even, $E((X_n^\varphi)^m)$ is independent of the initial qubit state $\varphi$ . In contrast, for $m$ odd, $E((X_n^\varphi)^m)$ does depend on the initial qubit state $\varphi$ .

Theorem 10 (i) Suppose $abcd \neq 0$ . When $m$ is odd, we have

When $m$ is even, we have

$$E((X_n^{\phi }{)}^m)=\mathrm{\mid }a{\mathrm{\mid }}^{2(n-1)}\{n^m+\sum _{k=1}^{\lfloor \frac{n-1}{2}\rfloor }\sum _{\gamma =1}^k\sum _{\delta =1}^k{(-\frac{\mathrm{\mid }b{\mathrm{\mid }}^2}{\mathrm{\mid }a{\mathrm{\mid }}^2})}^{\gamma +\delta }\frac{(n-2k{)}^m{\kappa }_{\gamma ,\delta ,n,k}{\nu }_{\gamma ,\delta ,n,k}}{\gamma \delta }\}\mathrm{.}E((X\_n^\backslash varphi)^m)\; =\; |a|^\{2(n-1)\}\; \backslash left\backslash \{\; n^m\; +\; \backslash sum\_\{k=1\}^\{\backslash lfloor\; \backslash frac\{n-1\}\{2\}\; \backslash rfloor\}\; \backslash sum\_\{\backslash gamma=1\}^k\; \backslash sum\_\{\backslash delta=1\}^k\; \backslash left(\; -\backslash frac\{|b|^2\}\{|a|^2\}\; \backslash right)^\{\backslash gamma+\backslash delta\}\; \backslash frac\{(n-2k)^m\; \backslash kappa\_\{\backslash gamma,\backslash delta,n,k\}\; \backslash nu\_\{\backslash gamma,\backslash delta,n,k\}\}\{\backslash gamma\; \backslash delta\}\; \backslash right\backslash \}.$$

(ii) Let $b = 0$ . Then we have

(iii) Let $a = 0$ . Then we have

where $\mu_{\alpha,\beta} = (|a|^2 - |b|^2) (|\alpha|^2 - |\beta|^2) + 2(a\alpha\bar{b}\bar{\beta} + \bar{a}\bar{\alpha}b\beta)$ .

– Hadamard walk case. Let the unitary matrix $U$ from Eq. (40) be the Hadamard operator given in Eq. (8). Then, the following result holds:

For any initial qubit state $\varphi = [\alpha, \beta]^t$ , Theorem 8 implies

$$\underset{n\to \mathrm{\infty }}{\lim }P(a\le X_n^{\phi }\mathrm{/}n\le b)={\int }_a^b\frac{1-(\mathrm{\mid }\alpha {\mathrm{\mid }}^2-\mathrm{\mid }\beta {\mathrm{\mid }}^2+\alpha \bar{\beta }+\bar{\alpha }\beta )x}{\pi (1-x^2)\sqrt{1-2x^2}}{1}_{(-\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})}(x)dx(41)\backslash lim\_\{n\; \backslash rightarrow\; \backslash infty\}\; P(a\; \backslash leq\; X\_n^\backslash varphi/n\; \backslash leq\; b)\; =\; \backslash int\_a^b\; \backslash frac\{1\; -\; (|\backslash alpha|^2\; -\; |\backslash beta|^2\; +\; \backslash alpha\backslash bar\{\backslash beta\}\; +\; \backslash bar\{\backslash alpha\}\backslash beta)x\}\{\backslash pi(1-x^2)\backslash sqrt\{1-2x^2\}\}\; 1\_\{(-\backslash frac\{1\}\{\backslash sqrt\{2\}\},\; \backslash frac\{1\}\{\backslash sqrt\{2\}\})\}(x)\; dx\; \backslash quad\; (41)$$

where $1_{(u,v)}(x)$ is the indicator function, that is, $1_{(u,v)}(x) = 1$ if $x \in (u, v)$ , and $1_{(u,v)}(x) = 0$ if $x \notin (u, v)$ .

Compare Eq. (41) with the corresponding result for the classical symmetric random walk $Y_n^o$ starting from the origin, Eq. (42):

$$\underset{n\to \mathrm{\infty }}{\lim }P(a\le Y_n^o\mathrm{/}\sqrt{n}\le b)={\int }_a^b\frac{e^{-x^2\mathrm{/}2}}{\sqrt{2\pi }}dx\mathrm{.}(42)\backslash lim\_\{n\; \backslash rightarrow\; \backslash infty\}\; P(a\; \backslash leq\; Y\_n^o/\backslash sqrt\{n\}\; \backslash leq\; b)\; =\; \backslash int\_a^b\; \backslash frac\{e^\{-x^2/2\}\}\{\backslash sqrt\{2\backslash pi\}\}\; dx.\; \backslash quad\; (42)$$

In addition to the scientific contributions already mentioned in previous sections, we now provide a summary of more results on limit distributions. Konno [250] has proved the following weak limit theorem for continuous quantum walks:

Theorem 11 Let us denote a continuous-time quantum walk on $\mathbb{Z}$ by $X_t$ whose probability distribution is defined by $P(k, t)$ for any location $k \in \mathbb{Z}$ and time $t \geq 0$ . Then, the following result holds for a continuous-time quantum walk on a line:

In [178], Grimmett et al used Fourier transform methods to also rigorously prove weak convergence theorems for one- and $d$ - dimensional quantum walks and, using the definition of pseudovelocities introduced by Konno [251], the Fourier transform method proposed in [178] and the one-parameter family of quantum walks proposed by Inui et al in [208], Watabe et al [452] have derived analyticalexpressions for the limit and localization distributions of walker pseudovelocities in two-dimensional quantum walks, while Sato et al [402] have derived limit distributions for qudits in one-dimensional quantum walks, Liu and Petulante have presented limiting distributions for quantum Markov chains [294], and Chisaki et al have also deduced limit theorems for $X_t$ (localization) and $\frac{X_t}{n}$ (weak convergence) for quantum walks on Cayley trees [120].

Furthermore and based on the Fourier transform approach developed by Grimmett et al [178], Machida and Konno have deduced a limit theorem for discrete quantum walks with 2-dimensional time-dependent coins [305]. In addition, Machida has produced analytical expressions for weak convergence as well as limit distributions for a localization model of a 2-state quantum walk [304], Konno has derived limit theorems using path counting methods for discrete-time quantum walks in random (both quenched and annealed) environments [257], and Liu [289] has derived a weak limit distribution as well as formulas for stationary probability distribution for quantum walks with two-entangled coins [445].

Motivated by the properties of quantum walks with many coins published by Brun et al in [86, 87], Segawa and Konno [406] have used the Wigner formula of rotation matrices for quantum walks published by Miyazaki et al in [329] to rigorously derive limit theorems for quantum walks driven by many coins. Also, Sato and Katori [401] have analyzed Konno's pseudovelocities within the context of relativistic quantum mechanics, di Molfetta and Debbasch have proposed a subset of quantum walks, named (1-jets), to study how continuous limits can be computed for discrete-time quantum walks [331]. In addition, based on definitions and concepts found in [251, 266, 248], Ampadu proposed a mathematical model for the localization and symmetrization phenomena in generalized Hadamard quantum walks as well as proposed conditions for the existence of localization [34]. Moreover, based on McGettrick's model of discrete quantum walks with memory [168] and using the Fourier-based approach proposed by Grimmett et al [178], Konno and Machida [263] have proved two new weak limit distribution theorems for that kind of quantum walk.

Finally, in [262] Konno et al have studied three kinds of measures (time averaged limit measure, weak limit measure and stationary measure) as well as studied conditions for localization in a family of inhomogeneous quantum walks, while Chisaki et al have produced limit theorems for discrete quantum walks running on joined half lines (i.e. lines with sites defined on $\mathbb{Z}^+ \cup {0}$ ) and (semi)homogeneous trees [121].

2.2.9 Localization in discrete quantum walks

In condensed-matter physics, localization is a well-studied physical phenomenon. According to Kramer and MacKinnon [271], it is likely that the first paper in which localization was discussed within the context of quantum mechanical phenomena is [45] by P. W. Anderson. Since then, localization has been extensively studied (see the compilation of textbooks and reviews on localization provided in [271]) and, consequently, different qualitative and mathematical definitions have been provided for this concept. Nevertheless, the essential idea behind localization is the absence of diffusion of a quantum mechanical state, which could be caused by random or disordered environments that break the periodicity in the dynamics ofthe physical system. Moreover, localization could also be produced by evolution operators that mimic the behavior of disordered media, as shown by Chandrashekar in [100]. As for quantum walks, localization phenomena has been detected as a result of either eigenvalue degeneracy (typically caused by using evolution operators that are all identical except for a few sites) or choosing coin operators that are site dependent [215].

In order to have a precise and inclusive introduction to localization in quantum walks, we direct the reader's attention to [216,217] by A. Joye, [218] by A. Joye and M. Merkli, and [191] by E. Hamza and A. Joye, and references provided therein. In addition to these references and those presented in previous sections in which we have incidentally addressed the topic of localization, we also mention the numerical simulations of quantum walks on graphs shown by Tregenna et al [431], in which the localization phenomenon, due to the use of Grover's operator (Def. (12)) in a 2-dimensional quantum walk, was detected. Inspired by this phenomenon, Inui et al proved in [208] that the key factor behind this localization phenomenon is the degeneration of the eigenvectors of corresponding evolution operator, Inui and Konno [210] have further studied the relationship between localization and eigenvalue degeneracy in the context of particle trapping in quantum walks on cycles, and Ide et al have computed the return probability of final-time dependent quantum walks [201]. Based on the study of aperiodic quantum walks given in [372], Romanelli [384] has proposed the computation of a trace map for Fibonacci quantum walks (this is a discrete quantum walk with two coin operators arranged in quasi-periodic sequences following a Fibonacci prescription) and Ampadu has shown that localization does not occur on Fibonacci quantum walks [35].

In [184], Grünbaum et al have studied recurrence processes on discrete-time quantum walks following a particle absorption monitoring approach (i.e. a projective measurement strategy), Štefaňák et al have analyzed the Pólya number (i.e. recurrence without monitoring particle absorption) for biased quantum walks on a line [424] as well as for $d$ -dimensional quantum walks [422,423], and Daráz and Kiss [127] have also proposed a Pólya number for continuous-time quantum walks. In [422], Štefaňák et al have proposed a criterion for localization and Kollár et al [245] found that, when executing a discrete-time quantum walk on a triangular lattice using a three-state Grover operator, there is no localization in the origin.

Furthermore, Chandrashekar has found that one-dimensional discrete coined quantum walks fail to fully satisfy the quantum recurrence theorem but succeed at exhibiting a fractional recurrence that can be characterized using the quantum Pólya number [98], Ampadu has analyzed the motion of $M$ particles on a one-dimensional Hadamard walk and has presented a theoretical criterion for observing quantum walkers at an initial location with high probability [36], has also studied the conditions upon which a biased quantum walk on the plane is recurrent [39], as well as studied the localization phenomenon in two-dimensional five-state quantum walks [37].

In [90], Cantero et al present an alternative method to formulate the theory of quantum walks based on matrix-valued Szegő orthogonal polynomials, known as the CGMV method, associated with a particular kind of unitary matrices, named CMV matrices, and Hamada et al have independently introduce the idea of employing orthogonal polynomials for deriving analytical expressions for limit distributions of one-dimensional quantum walks [188]. Based on the mathematical formalism delivered in [90], Konno and Segawa [268] have studied quantum walks