Perfect state transfer in quantum walks on orientable maps
Algebraic Combinatorics, Volume 7 (2024) no. 3, pp. 713-747.

A discrete-time quantum walk is the quantum analogue of a Markov chain on a graph. We show that the evolution of a general discrete-time quantum walk that consists of two reflections satisfies a Chebyshev recurrence, under a projection. We apply this to study perfect state transfer in a model of discrete-time quantum walk whose transition matrix is given by two reflections, defined by the face and vertex incidence relations of a graph embedded in an orientable surface, proposed by Zhan [J. Algebraic Combin. 53(4):1187–1213, 2020]. For this model, called the vertex-face walk, we prove results about perfect state transfer and periodicity and give infinite families of examples where these occur. In doing so, we bring together tools from algebraic and topological graph theory to analyze the evolution of this walk.

Published online:
DOI: 10.5802/alco.353
Classification: 05C50, 05C10, 81P45
Keywords: quantum walks, graph embeddings, graph eigenvalues

Guo, Krystal 1; Schmeits, Vincent 2

1 Korteweg-de Vries Institute for Mathematics University of Amsterdam Amsterdam The Netherlands and QuSoft (Research center for Quantum software & technology) Amsterdam The Netherlands
2 Korteweg-de Vries Institute for Mathematics University of Amsterdam Amsterdam The Netherlands
License: CC-BY 4.0
Copyrights: The authors retain unrestricted copyrights and publishing rights
     author = {Guo, Krystal and Schmeits, Vincent},
     title = {Perfect state transfer in quantum walks on orientable maps},
     journal = {Algebraic Combinatorics},
     pages = {713--747},
     publisher = {The Combinatorics Consortium},
     volume = {7},
     number = {3},
     year = {2024},
     doi = {10.5802/alco.353},
     language = {en},
     url = {}
AU  - Guo, Krystal
AU  - Schmeits, Vincent
TI  - Perfect state transfer in quantum walks on orientable maps
JO  - Algebraic Combinatorics
PY  - 2024
SP  - 713
EP  - 747
VL  - 7
IS  - 3
PB  - The Combinatorics Consortium
UR  -
DO  - 10.5802/alco.353
LA  - en
ID  - ALCO_2024__7_3_713_0
ER  - 
%0 Journal Article
%A Guo, Krystal
%A Schmeits, Vincent
%T Perfect state transfer in quantum walks on orientable maps
%J Algebraic Combinatorics
%D 2024
%P 713-747
%V 7
%N 3
%I The Combinatorics Consortium
%R 10.5802/alco.353
%G en
%F ALCO_2024__7_3_713_0
Guo, Krystal; Schmeits, Vincent. Perfect state transfer in quantum walks on orientable maps. Algebraic Combinatorics, Volume 7 (2024) no. 3, pp. 713-747. doi : 10.5802/alco.353.

[1] Ambainis, Andris; Portugal, Renato; Nahimov, Nikolay Spatial search on grids with minimum memory, Quantum Inf. Comput., Volume 15 (2015) no. 13-14, pp. 1233-1247 | MR

[2] Apers, Simon; Gilyén, András; Jeffery, Stacey A unified framework of quantum walk search, 38th International Symposium on Theoretical Aspects of Computer Science (LIPIcs. Leibniz Int. Proc. Inform.), Volume 187, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern (2021), Paper no. 6, 13 pages | MR

[3] Banchi, Leonardo; Coutinho, Gabriel; Godsil, Chris; Severini, Simone Pretty good state transfer in qubit chains—the Heisenberg Hamiltonian, J. Math. Phys., Volume 58 (2017) no. 3, Paper no. 032202, 9 pages | DOI | MR | Zbl

[4] Chan, Ada; Zhan, Hanmeng Pretty good state transfer in discrete-time quantum walks, J. Phys. A, Volume 56 (2023) no. 16, Paper no. 165305, 25 pages | MR | Zbl

[5] Chen, Qiuting; Godsil, Chris; Sobchuk, Mariia; Zhan, Harmony Hamiltonians of Bipartite Walks, 2022 | arXiv

[6] Childs, Andrew M. On the relationship between continuous- and discrete-time quantum walk, Comm. Math. Phys., Volume 294 (2010) no. 2, pp. 581-603 | DOI | MR | Zbl

[7] Conder, Marston; Dobcsányi, Peter Determination of all regular maps of small genus, J. Combin. Theory Ser. B, Volume 81 (2001) no. 2, pp. 224-242 | DOI | MR | Zbl

[8] Conder, Marston D. E. Regular maps and hypermaps of Euler characteristic -1 to -200, J. Combin. Theory Ser. B, Volume 99 (2009) no. 2, pp. 455-459 | DOI | MR | Zbl

[9] Conder, Marston D. E. Rotary maps (on orientable or non-orientable surfaces) with up to 1000 edges, 2012

[10] Coutinho, G.; Godsil, C.; Guo, K.; Vanhove, F. Perfect state transfer on distance-regular graphs and association schemes, Linear Algebra Appl., Volume 478 (2015), pp. 108-130 | DOI | MR | Zbl

[11] Ellingham, Mark N.; Ellis-Monaghan, Joanna A. A Catalog of Enumeration Formulas for Bouquet and Dipole Embeddings under Symmetries, Symmetry, Volume 14 (2022) no. 9, Paper no. 1793, 39 pages | DOI

[12] Falk, Matthew Quantum Search on the Spatial Grid, 2013 | arXiv

[13] Godsil, Chris; Guo, Krystal Quantum walks on regular graphs and eigenvalues, Electron. J. Combin., Volume 18 (2011) no. 1, Paper no. 165, 9 pages | DOI | MR | Zbl

[14] Godsil, Chris; Guo, Krystal; Kempton, Mark; Lippner, Gabor; Münch, Florentin State transfer in strongly regular graphs with an edge perturbation, J. Combin. Theory Ser. A, Volume 172 (2020), Paper no. 105181, 27 pages | DOI | MR | Zbl

[15] Godsil, Chris; Kirkland, Stephen; Severini, Simone; Smith, Jamie Number-theoretic nature of communication in quantum spin systems, Phys. Rev. Lett., Volume 109 (2012) no. 5, Paper no. 050502

[16] Godsil, Chris; Zhan, Hanmeng Discrete-time quantum walks and graph structures, J. Combin. Theory Ser. A, Volume 167 (2019), pp. 181-212 | DOI | MR | Zbl

[17] Godsil, Chris; Zhan, Hanmeng Discrete quantum walks on graphs and digraphs, London Mathematical Society Lecture Note Series, 484, Cambridge University Press, Cambridge, 2023, xii+138 pages | DOI | MR

[18] Gross, Jonathan L.; Tucker, Thomas W. Topological graph theory, Wiley-Interscience Series in Discrete Mathematics and Optimization, John Wiley & Sons, Inc., New York, 1987, xvi+351 pages (A Wiley-Interscience Publication) | MR

[19] Harris, Charles R.; Millman, K. Jarrod; van der Walt, Stéfan J.; Gommers, Ralf; Virtanen, Pauli; Cournapeau, David; Wieser, Eric; Taylor, Julian; Berg, Sebastian; Smith, Nathaniel J.; Kern, Robert; Picus, Matti; Hoyer, Stephan; van Kerkwijk, Marten H.; Brett, Matthew; Haldane, Allan; del Río, Jaime Fernández; Wiebe, Mark; Peterson, Pearu; Gérard-Marchant, Pierre; Sheppard, Kevin; Reddy, Tyler; Weckesser, Warren; Abbasi, Hameer; Gohlke, Christoph; Oliphant, Travis E. Array programming with NumPy, Nature, Volume 585 (2020) no. 7825, pp. 357-362 | DOI

[20] Jeffery, Stacey; Zur, Sebastian Multidimensional Quantum Walks, with Application to k-Distinctness, 2023 | arXiv

[21] Lovett, Neil B.; Cooper, Sally; Everitt, Matthew; Trevers, Matthew; Kendon, Viv Universal quantum computation using the discrete-time quantum walk, Phys. Rev. A (3), Volume 81 (2010) no. 4, Paper no. 042330, 7 pages | DOI | MR

[22] Magniez, Frédéric; Nayak, Ashwin; Roland, Jérémie; Santha, Miklos Search via quantum walk, SIAM J. Comput., Volume 40 (2011) no. 1, pp. 142-164 | DOI | MR | Zbl

[23] Mohar, Bojan; Thomassen, Carsten Graphs on surfaces, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2001, xii+291 pages | DOI | MR

[24] Patel, Apoorva; Raghunathan, K. S.; Rungta, Pranaw Quantum random walks do not need a coin toss, Phys. Rev. A (3), Volume 71 (2005) no. 3, Paper no. 032347, 6 pages | DOI | MR | Zbl

[25] Portugal, Renato Quantum walks and search algorithms, Quantum Science and Technology, Springer, Cham, 2018, xiv+308 pages | DOI | MR

[26] Rivlin, Theodore J. The Chebyshev polynomials, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974, vi+186 pages | MR

[27] Santha, Miklos Quantum walk based search algorithms, Theory and applications of models of computation (Lecture Notes in Comput. Sci.), Volume 4978, Springer, Berlin (2008), pp. 31-46 | DOI | MR | Zbl

[28] Szegedy, Mario Quantum speed-up of Markov chain based algorithms, 45th Annual IEEE Symposium on Foundations of Computer Science, IEEE, Los Alamitos CA (2004), pp. 32-41 | DOI

[29] The Sage Developers SageMath, the Sage Mathematics Software System (Version 9.0) (2020) (

[30] Yan, Qi; Jin, Xian’an A-trails of embedded graphs and twisted duals, Ars Math. Contemp., Volume 22 (2022) no. 2, Paper no. 6, 16 pages | DOI | MR | Zbl

[31] Zhan, Hanmeng Quantum walks on embeddings, J. Algebraic Combin., Volume 53 (2021) no. 4, pp. 1187-1213 | DOI | MR | Zbl

Cited by Sources: