TOPICS
Search

Quantum Walk


A discrete-time quantum walk is the evolution of a unit vector of amplitudes by repeated application of a unitary matrix U. Its state at integer time t>=0 is U^tpsi_0, and the probability of a coordinate outcome is the squared absolute value of the corresponding amplitude. Unlike a random walk, amplitudes can interfere (Guo and Schmeits 2026).

A two-reflection walk has

 U=(2P-I)(2Q-I),
(1)

where P=P^*=P^2 and Q=Q^*=Q^2 are projection matrices and I is the identity matrix. Choose a matrix N with orthonormal columns satisfying Q=NN^*, and set

 B_t=N^*U^tN,
(2)

where ^* denotes the conjugate transpose. Then

 B_t=T_t(B),
(3)

where B=B_1 and T_t is the Chebyshev polynomial of the first kind (Guo and Schmeits 2026).

For distinct states indexed by u,v and real B, write B=sum_(theta)thetaE_theta, where E_theta projects onto the eigenspace of eigenvalue theta. The transition amplitude satisfies

 |B_t(u,v)|<=sum_(theta)|E_theta(u,v)|<=1.
(4)

Guo and Schmeits (2026) call equality in the first bound, with a nonzero right side at a positive integer time, peak state transfer. More precisely, let Lambda={theta:E_theta(u,v)!=0} be nonempty. Peak state transfer occurs iff every theta in Lambda can be written as cos(p_thetapi/q_theta) with 0<=p_theta<=q_theta and integers p_theta,q_theta having greatest common divisor 1, and there is a common gamma in {-1,1} such that

 sgnE_theta(u,v)=gamma(-1)^(taup_theta/q_theta),
(5)

where tau is the least common multiple of the positive denominators q_theta for theta in Lambda (Guo and Schmeits 2026, Theorem 3.5). Transfer then occurs precisely at the odd multiples of tau. Perfect state transfer means that |B_t(u,v)|=1. When E_thetae_v=+/-E_thetae_u for every theta, the second bound is also an equality, and peak state transfer is perfect state transfer. They apply this criterion to strongly regular graphs, incidence graphs of block designs, and walks associated with toroidal grid graphs.


See also

Random Walk, Unitary Matrix

Explore with Wolfram|Alpha

References

Guo, K. and Schmeits, V. "State Transfer in Discrete-Time Quantum Walks via Projected Transition Matrices." Elec. J. Combin. 33, P4.4, 2026. https://doi.org/10.37236/13764.

Cite this as:

Weisstein, Eric W. "Quantum Walk." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/QuantumWalk.html

Subject classifications