Symmetry, Integrability and Geometry: Methods and Applications (SIGMA)

SIGMA 22 (2026), 063, 22 pages      arXiv:2509.26243      https://doi.org/10.3842/SIGMA.2026.063

Symmetric Quantum Walks on Hamming Graphs and Their Limit Distributions

Robert Griffiths a and Shuhei Mano b
a) School of Mathematics, Monash University, Clayton, Victoria 3800, Australia
b) The Institute of Statistical Mathematics, Tachikawa, Tokyo 190-8562, Japan

Received November 07, 2025, in final form June 20, 2026; Published online July 03, 2026

Abstract
We study a class of symmetric coined quantum walks on Hamming graphs, where the distance between vertices specifies the transition probability. A special model is the simple quantum walk on the hypercube, which has been discussed in the literature. Eigenvalues of the unitary operator of the quantum walks are zeros of certain self-reciprocal polynomials. We obtain a spectral representation of the wave vector, where our systematic treatment relies on the coin space isomorphic to the state space and the commutative association scheme. The Grover coin is extended to the reflection about a vector in an invariant subspace of the Terwilliger algebra. The limit distributions of several quantum walks are obtained.

Key words: association scheme; hypercube; random walk; self-reciprocal polynomial; spectral representation.

pdf (458 kb)   tex (31 kb)  

References

  1. Aharonov D., Ambainis A., Kempe J., Vazirani U., Quantum walks on graphs, in Proceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing, ACM, New York, 2001, 50-59, arXiv:quant-ph/0012090.
  2. Bannai E., Bannai E., Ito T., Tanaka R., Algebraic combinatorics, De Gruyter Ser. Discrete Math. Appl., Vol. 5, De Gruyter, Berlin, 2021.
  3. Bannai E., Ito T., Algebraic combinatorics. I. Association schemes, The Benjamin/Cummings Publishing Co., Inc., Menlo Park, CA, 1984.
  4. Best A., Kliegl M., Mead-Gluchacki S., Tamon C., Mixing of quantum walks on generalized hypercubes, Int. J. Quantum Inf. 6 (2008), 1135-1148, arXiv:0808.2382.
  5. Chen W., On the polynomials with all their zeros on the unit circle, J. Math. Anal. Appl. 190 (1995), 714-724, arXiv:1995.1105.
  6. Collevecchio A., Griffiths R.C., A class of random walks on the hypercube, in In and out of Equilibrium 3. Celebrating Vladas Sidoravicius, Progr. Probab., Vol. 77, Birkhäuser, Cham, 2021, 265-298.
  7. Diaconis P., Group representations in probability and statistics, IMS Lecture Notes Monogr. Ser., Vol. 11, Institute of Mathematical Statistics, Hayward, CA, 1988.
  8. Diaconis P., Griffiths R., Exchangeable pairs of Bernoulli random variables, Krawtchouck polynomials, and Ehrenfest urns, Aust. N. Z. J. Stat. 54 (2012), 81-101, arXiv:2012.00654.
  9. Feinsilver P., Fitzgerald R., The spectrum of symmetric Krawtchouk matrices, Linear Algebra Appl. 235 (1996), 121-139.
  10. Ho C.-L., Ide Y., Konno N., Segawa E., Takumi K., A spectral analysis of discrete-time quantum walks related to the birth and death chains, J. Stat. Phys. 171 (2018), 207-219, arXiv:1706.01005.
  11. Hora A., The cut-off phenomenon for random walks on Hamming graphs with variable growth conditions, Publ. Res. Inst. Math. Sci. 33 (1997), 695-710.
  12. Koekoek R., Swarttouw R.F., The Askey-scheme of hypergeometric orthogonal polynomials and its $q$-analogue, Department of Technical Mathematics and Informatics, Delft University of Technology, Report 98-17, 1998, arXiv:math.CA/9602214.
  13. Lakatos P., Losonczi L., Self-inversive polynomials whose zeros are on the unit circle, Publ. Math. Debrecen 65 (2004), 409-420, arXiv:2004.3250.
  14. Marquezino F.L., Portugal R., Abal G., Donangelo R., Mixing times in quantum walks on the hypercube, Phys. Rev. A 77 (2008), 042312, 8 pages, arXiv:0712.0625.
  15. Moore C., Russell A., Quantum walks on the hypercube, in Randomization and Approximation Techniques in Computer Science, Lecture Notes in Comput. Sci., Vol. 2483, Springer, Berlin, 2002, 164-178, arXiv:quant-ph/0104137.
  16. Shenvi N., Kempe J., Whaley K.B., Quantum random-walk search algorithm, Phys. Rev. A 67 (2003), 052307, 11 pages, arXiv:quant-ph/0210064.
  17. Szegedy M., Quantum speed-up of Markov chain based algorithms, in 45th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Piscataway, NJ, 2004, 32-41.

Previous article  Next article  Contents of Volume 22 (2026)