Quantum walk
Quantum walks are considered to be quantum analogs of random walks. The study of quantum walks started to get attention around 2000 in relation to a quantum computer.
Contents
Discrete-time quantum walk on the line o
Probability amplitude o
The whole system of a discrete-time 2-state quantum walk on the line is described by probability amplitudes. The probability amplitude at position at time is expressed as a 2-component complex vector , as shown in the following figure.
Time evolution o
Assuming is a unitary matrix, the time evolution is determined by a reccurence
where
and are complex numbers.
Probability disribution o
The probability that the walker can be observed at position at time is defined by
where is a random variable and denotes the position of the quantum walker.
- Example
- Quantum walk v.s. Random walk
Limit theorem o
For complex numbers , we take initial conditions to be
under the condition . The symbol means the transposed operator.
If we assume that the unitary matrix satisfies the condition , then we have
where
and
- Example
In the case of a simple random walk, we have
where
Continuous-time quantum walk on the line o
Probability amplitude o
The whole system of a continuous-time quantum walk on the line is also described by probability amplitudes. The probability amplitude at position at time is expressed as a complex number , as shown in the following figure.
Time evolution o
The time evolution is defined by a discrete-space Schrödinger equation,
where , and is a positive constant.
Probability distribution o
The quantum walker can be observed at position at time with probability
- Example
Limit theorem o
We take the initial conditions
Then we have
where
and
- Example
Interesting probability distributions of quantum walks o
QIC, 15(13&14), 1248-1258 (2015)
QIC, 10(11&12), 1004-1017 (2010)
IWNC 2009 Proc. ICT, 2, 226-235 (2010)
See also o
Further reading o
- Julia Kempe (2003). Quantum random walks – an introductory overview. Contemporary Physics 44 (4): 307–327. DOI:10.1080/00107151031000110776.
- Viv Kendon (2007). Decoherence in quantum walks – a review. Mathematical Structures in Computer Science 17 (6): 1169–1220. DOI:10.1017/S0960129507006354.
- Norio Konno (2008). Quantum Walks. Volume 1954 of Lecture Notes in Mathematics. Springer-Verlag, (Heidelberg) pp. 309–452. DOI:10.1007/978-3-540-69365-9.
- Salvador Elías Venegas-Andraca (2008). Quantum Walks for Computer Scientists. Morgan & Claypool Publishers. DOI:10.2200/S00144ED1V01Y200808QMC001.
- Salvador Elías Venegas-Andraca (2012). Quantum walks: a comprehensive review. Quantum Information Processing 11 (5): 1015–1106. DOI:10.1007/s11128-012-0432-5.