^{†}Corresponding author. Email: lidansusu007@163.com
^{*}Project supported by the National Natural Science Foundation of China (Grant Nos. 61272057 and 61170270), the Higher Education Young Elite Teacher Project of Beijing, China (Grant No. YETP0475 and YETP0477), the BUPT Excellent Ph. D. Students Foundation (Grant Nos. CX201325 and CX201326), and the China Scholarship Council (Grant No. 201306470046).
In this paper, we discuss the properties of lazy quantum walks. Our analysis shows that the lazy quantum walks have O( t^{n}) order of the nth moment of the corresponding probability distribution, which is the same as that for normal quantum walks. The lazy quantum walk with a discrete Fourier transform (DFT) coin operator has a similar probability distribution concentrated interval to that of the normal Hadamard quantum walk. Most importantly, we introduce the concepts of occupancy number and occupancy rate to measure the extent to which the walk has a (relatively) high probability at every position in its range. We conclude that the lazy quantum walks have a higher occupancy rate than other walks such as normal quantum walks, classical walks, and lazy classical walks.
Due to the constructive quantum interference along the paths in the discrete or continuous version, quantum walks^{[1, 2]} provided a method to explore all possible paths in a parallel way. Recently, algorithms based on quantum walks have been established as a dominant technique in quantum computation. Up to now, the algorithms based on quantum walks have a great deal of applications, ranging from element distinctness^{[3]} to database searching, ^{[4– 7]} from constructing quantum Hash schemes^{[8, 9]} to graph isomorphism testing.^{[10, 11]}
There are many kinds of quantum walk models, such as singleparticle quantum walks, ^{[12– 15]} twoparticle quantum walks, ^{[16– 18]} threestate quantum walks, ^{[19]} controlled interacting quantum walks, ^{[8, 9]} indistinguishable particle quantum walks, ^{[20, 21]} disordered quantum walk, ^{[22, 23]} etc. Each type of quantum walk has its own special features and advantages.
Lazy quantum walks were presented by Childs to prove that the continuoustime quantum walk is a limit of the discretetime quantum walk.^{[24]} He constructed a lazy quantum walk, which only takes one step with a small probability, to obtain small eigenvalues. Hence, the discretetime quantum walk that reproduces the same properties as those of the continuoustime quantum walk is the appropriate limit. Much attention has been paid to onedimensional threestate quantum walks recently, ^{[19, 25– 29]} and the limit distribution of these walks has been discussed. In this paper, we will consider the general properties of discrete lazy quantum walks, i.e., threestate quantum walks, such as the order of the moments of the probability distribution, the probability distribution concentrated interval, and the entanglement between the coin and the position of the particle.
Quantum walks have special properties, such as ballistic evolution and high probability of reaching remote points. This is because quantum walks create a superposition of all potential routes, furthermore creating coherent states over these routes. For the Hadamard quantum walks on the line, the probability distribution concentrated interval is
This paper is structured as follows. In Section 2, we introduce the specific mathematical formalism for lazy quantum walks on the line. In Section 3, we study the probability distribution concentrated interval and the moments of the probability distribution for lazy quantum walks, and prove that these moments have the same orders as those for normal quantum walks. We define and analyze the occupancy number and occupancy rate in Section 4 and discuss the entanglement between the position and coin for lazy quantum walks in Section 5. Finally, a short conclusion is given in Section 6.
In general, quantum walks on the line have two directions to move, right and left. But lazy quantum walks have three choices, right, left, and stay put. This results in different behaviour compared to their nonlazy counterparts. In this section, we introduce the specific mathematical formalism for lazy quantum walks on the line.
Lazy quantum walks take place in the product space
Let  x, α ⟩ be a basis state, where x ∈ Ƶ represents the position of the particle and α ∈ { r, s, l} represents the coin state. The evolution of the whole system at each step of the walk can be described by the global unitary operator, denoted by U,
where S is defined as
Except for this coin operator, there are other kinds of 3 × 3 coin operators^{[25, 27]}
with the coin parameter ρ ∈ (0, 1). This coin operator is equal to the Grover operator when
The Fourier analysis is a powerful tool and the right tool to exploit the symmetry of quantum walks. To compare lazy quantum walks with normal quantum walks, in this section, we use Fourier analysis to analytically study the large t behavior of lazy quantum walks.
Firstly, we define the state of the walker, Ψ , at time t ∈ 𝒩 and position x ∈ Ƶ as a threedimensional vector. We denote this as
Let
with the inverse transform given by
In the momentum space, i.e., the space of
Therefore, the walker evolves following the relation
where
It is worth mentioning that
As a unitary matrix,
Next, we will study the large t behavior of lazy quantum walks, specifically the probability distribution concentrated interval and the moments of the probability distribution of the lazy quantum walk.
In Fig. 1, we show the probability distributions of the lazy quantum walk and the normal quantum walk. We choose the initial states
From Fig. 1, we can see that even though the two kinds of quantum walks have different probability distributions, the probability distribution concentrated intervals for the two quantum walks are close to each other. In Refs. [12] and [13], by using the stationary phase method, the authors reported that for the Hadamard quantum walks, the wave function is almost completely contained in the interval
In Fig. 2 we plot ⟨ x^{2}⟩ for the lazy quantum walk, normal quantum walk, lazy classical walk, and normal classical walk. We still use the states
From Fig. 2, we see that although the lazy quantum walk has lower values, the values of ⟨ x^{2}⟩ are of the same order of O(t^{2}), which will be proven later. Also, both classical walks have the same order of ⟨ x^{2}⟩ , which is O(t). Furthermore, whether quantum or not, lazy walks have lower values of ⟨ x^{2}⟩ than nonlazy ones. The behavior obviously comes from the lazy action, which stops the walk from going far.
Now we will prove that the probability distributions from lazy quantum walks and normal quantum walks have moments of the same order, defined by
where P(x) is the probability of finding the particle at position x∈ Ƶ .
Theorem 1 The nth moment of the probability distribution of a tstep lazy quantum walk behaves like O(t^{n}).
Proof Firstly,
Using the relation
where δ (· ) is the Dirac function, we obtain
Since
We now insert Eq. (10) into Eq. (16). Due to the unitarity of U, the eigenvalues of
By substituting the eigenvalues and eigenvectors of
In Fig. 1, we show the probability distribution of the lazy quantum walk and the normal quantum walk. From the figure, we see that the normal quantum walk has a very high probability of 0.1304 at the position of − 68. While at most positions, the lazy quantum walk has a higher probability. It is worth noting that the normal quantum walk has zero probability at half of the positions in its range. Therefore, normal quantum walks spread quickly, but do not occupy all positions. To measure this aspect of the walks we introduce the concept of occupancy number, always keeping in mind that one number cannot exhibit all properties of a probability distribution.
Firstly, we define the range of a quantum walk.
Definition 1 For a random walk with t steps, the range denoted by N(t) is the number of different positions that the walker could occupy.
In extreme situations, such as when the coin operator is the identity matrix, we note that the range does not change. In fact the range of a quantum walk is only dependent on the shift operator and the number of steps, and is independent of the coin operator and the initial state. For example, a normal quantum walk on the line with t steps has a range of N(t) = 2t + 1. However, a quantum walk whose move choice is to stay or move right has a range of N(t) = t + 1.
Now, we give the definition of occupancy number and occupancy rate.
Definition 2 For a quantum walker walking on a graph, if the walker has a range of N, we define the occupancy number as
where P(x, t) is the probability that the walker is at position x after t steps.
In Fig. 3, we show the dependence of the occupancy number on the number of steps t (the walker‚ s range is 2t + 1). The initial state is still
The lazy action of the quantum walker brings some new features to the walk. The lazy walker will not have a high probability of being found at a remote position. From another point of view, the lazy walker is more deliberate. The walker does not like to move, and once he moves, he does not like to move again. Hence, the walker has a higher probability (relative to the nonlazy case) of occupying positions that were previously occupied. Furthermore, quantum features, which bring coherence and decoherence, make the walker travel further and give the walker O(t^{n}) order for the moments. In summary, for a lazy quantum walk, the walker has
(i) O(t^{n}) order of the nth moment;
(ii) a high occupancy number (relative to the nonlazy case);
(iii) similar probability distribution concentrated interval to that of a normal quantum walk.
Because the occupancy number of a quantum walk increases linearly with t, for ease of comparison, we define the occupancy rate as the normalized occupancy number.
Definition 3 For a quantum walker walking on a graph, if the walker has range N, then we define the occupancy rate as
This definition means that the occupancy rate is the quotient of the occupancy number and the range.
In fact, the groupvelocity density has the form of
for lazy quantum walks with coin operator G(ρ ), while the normal quantum walks with a general coin operator
has the following density, known as Konno’ s density function
where d_{0}, d_{1}, and d_{2} are parameters dependent on the coin operator and the initial state. Because
with the groupvelocity density, by integrating the groupvelocity density on the intervals satisfying P(x, t) ≥ 1/ 2, we can obtain the approximate limit of the occupancy rate. Because the result of the integration is a constant number, OccRate has the order of O(1). OccRate(N, t) has the following properties:
(i) 1/ N ≤ OccRate(N, t) ≤ 1 for arbitrary N and t;
(ii) OccRate(N, t) = 1 when the probabilities at every position are identical (and equal to 1/ N);
(iii) OccRate(N, t) = 1/ N when all probabilities satisfy P(x, t) < 1/ N except at one position.
For example, after fifty steps, the occupancy number for the lazy quantum walk in Fig. 3 is 40, while the range is 2(50) + 1 = 101. Therefore, the occupancy rate for the quantum walk after fifty steps is 40/101 ≈ 0.396.
In Fig. 4, we show the dependence of the occupancy rate on the time t. For quantum walks, since the occupancy number increases linearly with t, the occupancy rate is O(1). Also, from Fig. 4, it is clear that the occupancy rate of the quantum walk fluctuates around a fixed value. In general, lazy quantum walks have a higher occupancy rate than other corresponding normal quantum walks on the line, and this behavior also holds for the occupancy number. This is because that for time t, all occupancy rates are the quotients of the respective occupancy numbers and the quantity (2t + 1). Thus, the features of the occupancy rate are the same as those of the occupancy number, except that the order becomes O(1). We should remind readers that the occupancy rate of a classical walk decreases asymptotically to 0 (see Appendix A).
We pose a further question: Do quantum walks with different coin operators all have a high occupancy rate?
In Fig. 5, we plot the occupancy rate versus the time t. In Fig. 5(a), we choose the matrix G in Eq. (4) (with
In more general scenarios, we may want to parameterize the threshold probability, beyond which a position is said to be “ occupied” . Hence, borrowing ideas from the fuzzy set theory, we define the general occupancy number and general occupancy rate using a parameter δ which satisfies 0 < δ ≤ N.
Definition 4 For a quantum walker walking in one dimension, if the walker has range N, then we define the general occupancy number as
Definition 5 For a quantum walker walking in one dimension, if the walker has range N, then we define the general occupancy rate as
The general occupancy rate has the following properties:
(i) 0 ≤ GenOccRate(δ , N, t) ≤ 1 for all δ , N, t;
(ii) If δ _{1} < δ _{2},
GenOccRate(δ _{1}, N, t) ≥ GenOccRate(δ _{2}, N, t).
In Fig. 6, we show the general occupancy rate of quantum walks and classical walks for different values of the parameter δ . Blue lines represent the general occupancy rates for quantum walks and classical walks with δ = 1, i.e., the occupancy rates previously considered in Fig. 4. From Fig. 6, we see that the properties of the general occupancy rate do not change with the parameter δ . For quantum walks, the general occupancy rate still converges, with small fluctuations, to a nonzero value, while for classical walks it decreases asymptotically to 0. In addition, the lazy classical walks and normal classical walks have identical orders for their occupancy rates, and the general occupancy rate for both quantum walks and classical walks is O(t). We show in Appendix A that for
normal classical walks, the occupancy rate is
Entanglement is believed to be the most important quantum resource, occurring only in quantum states. For a single particle quantum walk, the entanglement between position and coin is not negligible.^{[32, 33]} In this section, we study the entanglement between position and coin for lazy quantum walks on the line. We use the standard entanglement measure (von Neumann entropy) to measure the total entanglement between the two subsystems: position space and coin space.
The entanglement between the two subsystems of a bipartite pure quantum state  Ψ ⟩ can be quantified using the von Neumann entropy S of the reduced density matrix of either subsystem,
where ρ _{1} and ρ _{2} are, respectively, the reduced density matrices of systems 1 and 2, and 0 log_{2} = 0.
Numerical methods can then be used to calculate the entanglement E between position and coin. In Fig. 7, we show the entanglement for normal quantum walks and lazy quantum walks. The maximum value of the entanglement E between two subsystems is E_{max} = log_{2}(min(d_{1}, d_{2})), where d_{1} and d_{2} are the dimensions of the two subsystems. For normal singleparticle quantum walks on the line, E_{max} = log_{2}(2) = 1, while for lazy singleparticle quantum walks on the line E_{max} = log_{2}(3) ≈ 1.585. From Fig. 7, we see that the entanglement converges to the maximum value for the two kinds of quantum walks. Because the dimension of the coin space for lazy quantum walks is greater than that for normal quantum walks, the lazy quantum walks have a higher entanglement between position and coin. Although a higher entanglement is a quantum resource, it is achieved at the cost of constructing a threedimensional coin.
In this paper, we study the properties of discrete lazy quantum walks. We discuss the probability distribution concentrated interval and the moments of lazy quantum walks. We prove that lazy quantum walks and normal quantum walks have the same order for the moments of their probability distributions, O(t^{n}).
We introduce the occupancy number and occupancy rate to measure the extent to which the walk has a relatively high probability at every position in its range. From our study, we conclude that the lazy quantum walks have a higher occupancy rate than other walks such as normal quantum walks, classical walks, and lazy classical walks. We show that the DFT lazy quantum walks and Hadamard quantum walks have similar probability distribution concentrated intervals, but different dissimilar occupancy rates. We also discuss other coin operators. Among the coin operators we consider, the quantum walks with a DFT coin operator have the highest occupancy rate.
Finally, we study the entanglement between position and coin for lazy quantum walks. The entanglement for lazy quantum walks is higher than that for normal quantum walks, which benefits from the higher dimensional coin.
Based on the these properties of lazy quantum walks, we hope in future to find applications.
We acknowledge Marcelo Forets for finding the general 3 × 3 coin opertor.
1 

2 

3 

4 

5 

6 

7 

8 

9 

10 

11 

12 

13 

14 

15 

16 

17 

18 

19 

20 

21 

22 

23 

24 

25 

26 

27 

28 

29 

30 

31 

32 

33 
