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.
Revised:
Accepted:
Published online:
Keywords: quantum walks, graph embeddings, graph eigenvalues
Guo, Krystal 1; Schmeits, Vincent 2
CC-BY 4.0
@article{ALCO_2024__7_3_713_0,
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 = {https://alco.centre-mersenne.org/articles/10.5802/alco.353/}
}
TY - JOUR 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 - https://alco.centre-mersenne.org/articles/10.5802/alco.353/ 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 %U https://alco.centre-mersenne.org/articles/10.5802/alco.353/ %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. https://alco.centre-mersenne.org/articles/10.5802/alco.353/
[1] Spatial search on grids with minimum memory, Quantum Inf. Comput., Volume 15 (2015) no. 13-14, pp. 1233-1247 | MR
[2] 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] 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] 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] Hamiltonians of Bipartite Walks, 2022 | arXiv
[6] 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] 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] Regular maps and hypermaps of Euler characteristic to , J. Combin. Theory Ser. B, Volume 99 (2009) no. 2, pp. 455-459 | DOI | MR | Zbl
[9] Rotary maps (on orientable or non-orientable surfaces) with up to 1000 edges, 2012 https://www.math.auckland.ac.nz/~conder/RotaryMapsWithUpTo1000Edges.txt
[10] Perfect state transfer on distance-regular graphs and association schemes, Linear Algebra Appl., Volume 478 (2015), pp. 108-130 | DOI | MR | Zbl
[11] 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] Quantum Search on the Spatial Grid, 2013 | arXiv
[13] Quantum walks on regular graphs and eigenvalues, Electron. J. Combin., Volume 18 (2011) no. 1, Paper no. 165, 9 pages | DOI | MR | Zbl
[14] 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] Number-theoretic nature of communication in quantum spin systems, Phys. Rev. Lett., Volume 109 (2012) no. 5, Paper no. 050502
[16] Discrete-time quantum walks and graph structures, J. Combin. Theory Ser. A, Volume 167 (2019), pp. 181-212 | DOI | MR | Zbl
[17] 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] 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] Array programming with NumPy, Nature, Volume 585 (2020) no. 7825, pp. 357-362 | DOI
[20] Multidimensional Quantum Walks, with Application to -Distinctness, 2023 | arXiv
[21] 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] Search via quantum walk, SIAM J. Comput., Volume 40 (2011) no. 1, pp. 142-164 | DOI | MR | Zbl
[23] Graphs on surfaces, Johns Hopkins Studies in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 2001, xii+291 pages | DOI | MR
[24] 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] Quantum walks and search algorithms, Quantum Science and Technology, Springer, Cham, 2018, xiv+308 pages | DOI | MR
[26] The Chebyshev polynomials, Pure and Applied Mathematics, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1974, vi+186 pages | MR
[27] 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] 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] SageMath, the Sage Mathematics Software System (Version 9.0) (2020) (https://www.sagemath.org)
[30] -trails of embedded graphs and twisted duals, Ars Math. Contemp., Volume 22 (2022) no. 2, Paper no. 6, 16 pages | DOI | MR | Zbl
[31] Quantum walks on embeddings, J. Algebraic Combin., Volume 53 (2021) no. 4, pp. 1187-1213 | DOI | MR | Zbl
Cited by Sources: