Instruction


FACTA UNIVERSITATIS  
Series: Electronics and Energetics Vol. 27, N

o
 1, March 2014, pp. 103 - 112 

DOI: 10.2298/FUEE1401103K 

MULTIPLE QUANTUM WALKERS ON THE LINE USING 

HYBRID COINS: A POSSIBLE TOOL FOR QUANTUM SEARCH

 

Ioannis G. Karafyllidis
1
, Paul Isaac Hagouel

2
 

1
Democritus University of Thrace, Department of Electrical and Computer Engineering,  

671 00 Xanthi, Greece 
2
Optelec, 11 Chrysostomou Smyrnis Street, 54 622 Thessaloniki, Greece 

Abstract. In this paper discrete quantum walks with different coins used for odd and 

even time steps are studied. These coins are called hybrid. The calculation results are 

compared with the most frequently used coin, the Hadamard transform. Furthermore, 

quantum walks on the line which involve two or more quantum walkers with hybrid 

coins are studied. Quantum walks with entangled walkers and hybrid coins are also 

studied. The results of these calculations show that the proposed types of quantum 

walks can be used for quantum search, because the walker can be directed towards 

preferred directions and can also be confined in certain segments of the line. 

Key words: Quantum walk, quantum computing, simulation max 

1. INTRODUCTION 

Quantum walks are quantum versions of classical random walks. They were first 

introduced in 1993 [1] and since then considerable work has been done on this subject. 

Quantum walks are useful models for physical processes such as Brownian motion and may 

serve as a basis for the development of new quantum algorithms [2], [3].  Furthermore, 

quantum walk is a natural model for quantum search using parallel quantum computer 

architectures [4], [5]. Quantum walks may also become an effective tool for studying 

biological systems [6]. Several studies of continuous-time and discrete-time quantum walks 

on the line [7], [8], and some implementation proposals have been published [9]-[11].  The 

effect of noise on the discrete-time quantum walk has also been studied [12].  

Recently, a study of a quantum walk on the line with one walker and several coins has 

been published [13]. On the other hand, in [14] a quantum walk on the line with two 

entangled walkers and one coin, the Hadamard transform, is studied. In this paper a study 

of discrete quantum walks in which multiple walkers use hybrid coins is presented. 

"Hybrid coin" means the use of two different coins, one for odd and one for even time 

steps. The question to be answered by this study is: Is it possible to use multiple quantum 

                                                           

 Received January 9, 2014 
Corresponding author: Ioannis G. Karafyllidis 

Democritus University of Thrace, Department of Electrical and Computer Engineering,  

671 00 Xanthi, Greece 
(e-mail: ykar@ee.duth.gr) 

mailto:ykar@ee.duth.gr


104 I. G. KARAFYLLIDIS, P. I. HAGOUEL 

walkers and hybrid coins to direct the search towards a desired direction and, furthermore, 

is it possible to confine the search in a desirable segment of the line? Calculation results 

show that this is possible. 

2. QUANTUM WALK ON THE LINE WITH HYBRID COINS  

In discrete quantum walk a walker (which can be a particle or a state) moves on a 

one-dimensional periodic lattice. The sites of this lattice are numbered by: 

 0, 1, 2,i n     (1) 

The Hilbert space of the discrete quantum walk comprises two subspaces, the location 

subspace HL, which is spanned by the basis: 

 , 2 , 1 , 0 , 1 , 2 ,i n n     (2) 

and the two-dimensional coin subspace, HC, which is spanned by the two coin basis states 

0 and 1 .  The Hilbert space, H, of the quantum walk is: 

 
L C

H H H   (3) 

The state of the quantum walker found at location  j  with coin in state 0  is , 0j . 

The quantum walk usually starts with the walker in state 0 , 0 . At each step of the 

walk two operations are applied to the walker state.  The coin toss operation, C, which 

acts on the coin state, is applied first: 

 

0,0 0,1

1,0 1,1

, 0 , 0 , 1

, 1 , 0 , 1

C j c j c j

C j c j c j

 

 

 (4) 

Any two-dimensional unitary transformation can by used as a coin toss operation. 

Usually, the Hadamard transform, H, is used. In this case: 

 

0,0 0,1

1,0 1,1

1 1
1

2
1 1

c c

H

c c

   
   

    
     

 (5) 

The second operation applied is the walker shit operation, S, which acts on the location 

state and is given by: 

 1 1 1 0 0 1
n

j n

S j j j j
 

       (6) 

This operation shifts the walker to the right (towards +n) if the coin state is 1  and to the 

left  if the coin state is 0 . The probability distribution for a discrete quantum walk with 

initial walker state 0 , 0 , in which the Hadamard transform is used as coin, is shown in 



 Multiple Quantum Walkers on the Line using Hybrid Coins: A Possible Tool for Quantum Search 105 

Figure 1. The probability distribution is biased towards left because of quantum interference. 

The initial walker state 0 , 1  results in probability distribution biased towards right. 

 

Fig. 1 Probability distribution for a quantum walk after 40 steps. The initial state is 0 , 0   

and the Hadamard transform is used for coin toss 

The dependence of the probability distribution on the coin initial state leads naturally 

to the question: What is the probability distribution in the case where two coins are used 

alternatively? 

The case where the coin used in odd steps is the Hadamard transform and the coin 

used in even time steps is a phase shift, P, is considered first. The phase shift is given by: 

 

1 1

1
i

P

e


 
 


 
  

 (7) 

Figure 2 shows the probability distribution in this case. The initial walker state is 

0 , 0  and the phase angle, ф, is 60
o
. The probability distribution is biased towards left 

as in the case where only the Hadamard transform was used, but the probability to find 

the walker in certain locations, which are periodically distributed, is larger. On the other 

hand, there is a zero probability to find the walker in much more locations that the case 

where only the Hadamard transform was used. This is an expected result for all phase 

angles, in the case of a single walker. Phase shift is important in the case of multiple 

walkers, because it affects quantum interference.  



106 I. G. KARAFYLLIDIS, P. I. HAGOUEL 

 

Fig. 2 Probability distribution for a quantum walk after 40 steps in the case where two 

coins are used alternatively, namely H and P. The initial walker state is 0 , 0  

The case where the coin used in odd steps is the Hadamard transform and the coin 

used in even time steps is a more general transform, G, is considered next. The transform 

G is given by: 

 

cos ( ) sin ( )

sin ( ) cos ( )

G

 

 

 
 


 
  

 (8) 

Figure 3(a) shows the probability distribution after 40 steps in this case where φ = 

30
o
. The initial walker state is 0 , 0 . The walker is localized between in the region [-10, 

+10]. The order of magnitude of the probability to find the walker in locations outside 

this region is 10
-3

. It is therefore acceptable to say that using the aforementioned hybrid 

coin we can confine the walker within a certain segment of the line. This walker can be 

confined in any segment of the line [x-10, x+10] by setting the initial walker state to 

, 0x . Different values of φ result in walker confinement in regions with different sizes. 

For example, Figure 3(b) shows the probability distribution after 40 steps in this case 

where φ = 55
o
 and initial walker state 20 , 0 . In this case the walker is confined in the 

region [18, 22] or [20-2, 20+2], that is ±2 around its initial location. 



 Multiple Quantum Walkers on the Line using Hybrid Coins: A Possible Tool for Quantum Search 107 

 
(a) 

 
(b) 

Fig. 3 Probability distribution for a quantum walk after 40 steps in the case where the 

coins H and P are used alternatively. (a) Initial walker state 0 , 0  and φ=30
o
.  (b) 

Initial walker state 20 , 0  and φ=55
o
. 



108 I. G. KARAFYLLIDIS, P. I. HAGOUEL 

3. MULTIPLE WALKERS ON THE LINE 

More that one walker can be used in order to exploit quantum interference. A number of 

w walkers can be used. These walkers can be distinct particles each one with a different 

initial state. In this case the initial state of the quantum walk, 
in

w , is given by:  

 1 1 1 2 2 2 3 3 3, , , ,in w w ww a w c a w c a w c a w c      (9) 

with 

 
2 2 2 2

1 2 3
1

w
a a a a      (10) 

Multiple walkers can also be states of the same particle located initially at different 

locations. In this case: 

 
2 2 2 2

1 2 3
1

w
a a a a      (11) 

Figure 4 shows the probability distribution after 40 steps of quantum walk. A hybrid 

coin H and P with ф = 40
o
 is used. The initial state for this walk is: 

 
1 1

14 , 0 12 , 0
2 2

in
w      (12) 

The calculation results show that the walk is directed towards left. 

 

Fig. 4 Probability distribution after 40 steps of quantum walk with a hybrid coin H and P 

with ф = 40
o
. The initial state for this walk is given by equation (12). 



 Multiple Quantum Walkers on the Line using Hybrid Coins: A Possible Tool for Quantum Search 109 

Figure 5 shows the probability distribution after 40 steps of quantum walk in which a 

hybrid coin H and G with φ = 30
o
 is used. The initial state for this walk is: 

 
1 1

18 , 0 18 , 1
2 2

in
w     (13) 

The walkers are confined into two segments of the line. From Figure 5 it is evident that 

the two probability patterns are located symmetrically to the left and to the right of the 

origin and are exactly the same. This walk results in two probability patterns which are 

the same and are displaced by 36 line sites.  

 

Fig. 5 Probability distribution after 40 steps of quantum walk with a hybrid coin H and G 

with φ = 30
o
. The initial state for this walk is given by equation (13). 

A quantum walk with two entangled walkers will be considered next. The initial state 

of the walk is:  

 
1 1

6 , 0 5 , 1
2 2

in
w     (14) 

Α hybrid coin H and G with φ = 50
o
 is used. The calculation results are shown in Figure 

6. The probability distribution pattern has mirror symmetry with respect to the origin.  

More than two walkers can be used. Let us examine the case of a quantum walk with 

three walkers in which a hybrid coin H and G with φ = 30
o
 is used. The initial state is: 

 
1 1 1

10 , 1 5 , 1 11 , 0
2 2 2

in
w       (15) 



110 I. G. KARAFYLLIDIS, P. I. HAGOUEL 

 

Fig. 6 Probability distribution after 40 steps of quantum walk with a hybrid coin H and G 

with φ = 50
o
. The initial state for this walk is given by equation (14) 

The calculation results shown in Figure 7 indicate that the walkers are confined within 

the region [-20, 20]. There is a non-zero probability to locate a walker in every location 

within the region [-15, 1]. 

 

Fig. 7 Probability distribution after 40 steps of quantum walk with a hybrid coin H and G 

with φ = 30
o
. The initial state for this walk is given by equation (15) 



 Multiple Quantum Walkers on the Line using Hybrid Coins: A Possible Tool for Quantum Search 111 

The periodic structure of probability distribution shown in Figure 8 was obtained 

using four walkers with hybrid coin H and G (φ = 30
o
). The initial state was: 

 
1 1 1 1

20 , 0 10 , 1 10 , 0 20 , 1
2 2 2 2

in
w        (16) 

A periodic probability distribution with more periods can be obtained using more walkers. 

Figures 5 and 6 indicate that two periods correspond to two walkers. 

 

Fig. 8 Probability distribution after 40 steps of quantum walk with a hybrid coin H and G 

with φ = 30
o
. The initial state for this walk is given by equation (16) 

4. CONCLUSIONS 

In this paper the study of discrete quantum walks involving multiple walkers and hybrid 

coins was presented. An analytical study of these quantum walks is probably impossible 

because the probability distribution patterns depend on the choice of hybrid coins, the 

number of the walkers and the initial states. A large variety of patterns can be achieved 

including walker confinement, walker direction and periodic patterns. The results presented 

here indicate that quantum walk on the line with multiple walkers using hybrid coins is an 

effective tool for quantum search.  

REFERENCES 

[1] Y. Aharonov, L. Davidovich and N. Zagury, Quantum random walks, Physical Review A, 48, 1993, 1687. 
[2] A. Ambainis, Quantum walks and their algorithmic applications, quant-ph/0403120. 
[3] J. Kempe, Quantum random walks: an introductory overview, Contemporary Physics, 44, 2003, 302. 
[4] I. G. Karafyllidis, Simulation of entanglement generation and variation in quantum computation, Journal 

of Computational Physics,  200, 2004, 383. 



112 I. G. KARAFYLLIDIS, P. I. HAGOUEL 

[5] I. G. Karafyllidis, Definition and evolution of quantum cellular automata  with two qubits per cell, 
Physical Review A, 70, 2004, 044301. 

[6] Tai-Hsin Hsu and Su-Long Nyeo, Diffusion coefficients of two-dimensional viral DNA walks, Physical 
Review E, 67, 2003, 051911. 

[7] D. ben-Avraham, E. M. Bolt and C. Tamon, One-Dimensional Continuous-Time Quantum Walks, 
Quantum Information Processing, 3, 2004, 295. 

[8] O. Buerschper and K. Burnett, Stroboscopic quantum walks,quant-ph/0406039.  
[9] W. Dur, R. Raussendorf, V. M. Kendon and H.-J. Briegel, Quantum walks in optical lattices, Physical 

Review A, 66, 2002, 052319. 

[10] J. Du, H. Li, X. Xu, M. Shi, J. Wu, Z. Zhou and R. Han,  Experimental implementation of the quantum 
random-walk algorithm, Physical Review A, 67, 2003, 042316. 

[11] H. Jeong, M. Paternostro and M. S. Kim, Simulation of quantum random walks using the interference of 
a classical field,  Physical Review A, 69, 012310, 2004.  

[12] D. Shapira, O. Biham, A. J. Bracken and M. Hackett, One-dimensional quantum walk with unitary noise, 
Physical Review A, 68, 2003, 062315. 

[13] P. Ribeiro, P. Milman and R. Mosseri, Aperiodic Quantum Random Walks, Physical Review Letters, 93, 
2004, 190503. 

[14] Y. Omar, N. Paunkovic, L. Sheridan and S. Bose, Quantum Walk on a Line with Two Entangled 
Particles, quant-ph/0411065.