Recurrence in discrete-time quantum stochastic walks

Martin Štefaňák1, Václav Potoček1, İskender Yalçınkaya1, Aurél Gábris1,2, and Igor Jex1

1Department of Physics, Faculty of Nuclear Sciences and Physical Engineering, Czech Technical University in Prague, Břehová 7, 115 19 Praha 1-Staré Město, Czech Republic
2Institute for Solid State Physics and Optics, HUN-REN Wigner Research Centre for Physics, 1525 P.O. Box 49, Hungary

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

Interplay between quantum interference and classical randomness can enhance performance of various quantum information tasks. In the present paper we analyze recurrence phenomena in the discrete-time quantum stochastic walk on a line, which is a quantum stochastic process that interpolates between quantum and classical walk dynamics. Surprisingly, we find that introducing classical randomness can reduce the recurrence probability – despite the fact that the classical random walk returns with certainty – and we identify the conditions under which this intriguing phenomenon occurs. Numerical evaluation of the first-return generating function allows us to investigate the asymptotics of the return probability as the step number approaches infinity. This provides strong evidence that the suppression of recurrence probability is not a transient effect but a robust feature of the underlying quantum-classical interplay in the asymptotic limit. Our results show that for certain tasks discrete-time quantum stochastic walks outperform both classical random walks and unitary quantum walks.

In the world of classical physics, a walker wandering randomly back and forth on a long line will always eventually return to its starting point—this is known as recurrence with certainty. In the quantum world, however, things are different; a quantum walker can use wave-like interference to spread out so quickly that it might never return.

In this paper we explore what happens when one mixes these two worlds using Discrete-Time Quantum Stochastic Walks (DTQSW). Intuitively, one might expect that adding even a little bit of classical randomness to a quantum walk would make it "more classical" and thus more likely to return home.

The Surprise: Our results demonstrate the contrary. Under certain conditions, adding classical noise actually decreases the probability of the walker returning. By interpolating between quantum and classical dynamics, we discovered a regime where the interplay of wave interference and random hopping creates a more efficient escape than either pure quantum or pure classical movement could achieve alone. This counterintuitive finding may have implications for designing more efficient quantum search algorithms and understanding how quantum information survives in noisy environments.

► BibTeX data

► References

[1] J. G. Morley, N. Chancellor, S. Bose, and V. Kendon. ``Quantum search with hybrid adiabatic-quantum-walk algorithms and realistic noise''. Phys. Rev. A 99, 022339 (2019).
https:/​/​doi.org/​10.1103/​PhysRevA.99.022339

[2] J. J. Wallman and J. Emerson. ``Noise tailoring for scalable quantum computation via randomized compiling''. Phys. Rev. A 94, 052325 (2016).
https:/​/​doi.org/​10.1103/​PhysRevA.94.052325

[3] S. Wang, S. McArdle, and M. Berta. ``Qubit-efficient randomized quantum algorithms for linear algebra''. PRX Quantum 5, 020324 (2024).
https:/​/​doi.org/​10.1103/​PRXQuantum.5.020324

[4] K. Wan, M. Berta, and E. T. Campbell. ``Randomized Quantum Algorithm for Statistical Phase Estimation''. Phys. Rev. Lett. 129, 030503 (2022).
https:/​/​doi.org/​10.1103/​PhysRevLett.129.030503

[5] T. Proctor, S. Seritan, K. Rudinger, E. Nielsen, R. Blume-Kohout, and K. Young. ``Scalable Randomized Benchmarking of Quantum Computers Using Mirror Circuits''. Phys. Rev. Lett. 129, 150502 (2022).
https:/​/​doi.org/​10.1103/​PhysRevLett.129.150502

[6] Y. Li and S. C. Benjamin. ``Efficient Variational Quantum Simulator Incorporating Active Error Minimization''. Phys. Rev. X 7, 021050 (2017).
https:/​/​doi.org/​10.1103/​PhysRevX.7.021050

[7] K. Temme, S. Bravyi, and J. M. Gambetta. ``Error Mitigation for Short-Depth Quantum Circuits''. Phys. Rev. Lett. 119, 180509 (2017).
https:/​/​doi.org/​10.1103/​PhysRevLett.119.180509

[8] Y. Kim, Ch. J. Wood, T. J. Yoder, S. T. Merkel, J. M. Gambetta, K. Temme, and A. Kandala. ``Scalable error mitigation for noisy quantum circuits produces competitive expectation values''. Nat. Phys. 19, 752–759 (2023).
https:/​/​doi.org/​10.1038/​s41567-022-01914-3

[9] E. Campbell. ``Random Compiler for Fast Hamiltonian Simulation''. Phys. Rev. Lett. 123, 070503 (2019).
https:/​/​doi.org/​10.1103/​PhysRevLett.123.070503

[10] V. Kendon and B. Tregenna. ``Decoherence can be useful in quantum walks''. Phys. Rev. A 67, 042315 (2003).
https:/​/​doi.org/​10.1103/​PhysRevA.67.042315

[11] S. Apers, A. Gilyén, and S. Jeffery. ``A Unified Framework of Quantum Walk Search''. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Pages 6:1–6:13. Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021).
https:/​/​doi.org/​10.4230/​LIPIcs.STACS.2021.6

[12] Y. Aharonov, L. Davidovich, and N. Zagury. ``Quantum random walks''. Phys. Rev. A 48, 1687 (1993).
https:/​/​doi.org/​10.1103/​PhysRevA.48.1687

[13] D. A. Meyer. ``From quantum cellular automata to quantum lattice gases''. J. Stat. Phys. 85, 551–574 (1996).
https:/​/​doi.org/​10.1007/​BF02199356

[14] E. Farhi and S. Gutmann. ``Quantum computation and decision trees''. Phys. Rev. A 58, 915 (1998).
https:/​/​doi.org/​10.1103/​PhysRevA.58.915

[15] A. Montanaro. ``Quantum speedup of Monte Carlo methods''. Proc. R. Soc. A 471, 20150301 (2015).
https:/​/​doi.org/​10.1098/​rspa.2015.0301

[16] S. Marsh and J. B. Wang. ``Combinatorial optimization via highly efficient quantum walks''. Phys. Rev. Res. 2, 023302 (2020).
https:/​/​doi.org/​10.1103/​PhysRevResearch.2.023302

[17] N. Slate, E. Matwiejew, S. Marsh, and J. B. Wang. ``Quantum walk-based portfolio optimisation''. Quantum 5, 513 (2021).
https:/​/​doi.org/​10.22331/​q-2021-07-28-513

[18] P. A. M. Casares, Roberto Campos, and M. A. Martin-Delgado. ``Qfold: Quantum walks and deep learning to solve protein folding''. Quantum Sci. Technol. 7, 025013 (2022).
https:/​/​doi.org/​10.1088/​2058-9565/​ac4f2f

[19] A. A. Melnikov, L. E. Fedichkin, and A. Alodjants. ``Predicting quantum advantage by quantum walk with convolutional neural networks''. New J. Phys. 21, 125002 (2019).
https:/​/​doi.org/​10.1088/​1367-2630/​ab5c5e

[20] S. Aaronson and A. Ambainis. ``Quantum search of spatial regions (extended abstract)''. In F. Titsworth, editor, 44th Annual Ieee Symposium on Foundations of Computer Science, Proceedings. Pages 200–209. Los Alamitos (2003). IEEE Computer Soc.
https:/​/​doi.org/​10.1109/​SFCS.2003.1238194

[21] A. M. Childs and J. Goldstone. ``Spatial search by quantum walk''. Phys. Rev. A 70, 022314 (2004).
https:/​/​doi.org/​10.1103/​PhysRevA.70.022314

[22] D. O. Oriekhov, G. Jin, and E. Greplova. ``Dynamical localization in 2D topological quantum random walks'' (2025). arXiv:2406.18768.
arXiv:2406.18768

[23] N. Shenvi, J. Kempe, and K. B. Whaley. ``Quantum random-walk search algorithm''. Phys. Rev. A 67, 052307 (2003).
https:/​/​doi.org/​10.1103/​PhysRevA.67.052307

[24] V. Potoček, A. Gabris, T. Kiss, and I. Jex. ``Optimized quantum random-walk search algorithms on the hypercube''. Phys. Rev. A 79, 012325 (2009).
https:/​/​doi.org/​10.1103/​PhysRevA.79.012325

[25] A. Ambainis, A. Gilyen, S. Jeffery, and M. Kokainis. ``Quadratic Speedup for Finding Marked Vertices by Quantum Walks''. In Proceedings of the 52nd Annual Acm Sigact Symposium on Theory of Computing (stoc '20). Pages 412–424. Assoc Computing Machinery (2020).
https:/​/​doi.org/​10.1145/​3357713.3384252

[26] S. Apers, S. Chakraborty, L. Novo, and J. Roland. ``Quadratic Speedup for Spatial Search by Continuous-Time Quantum Walk''. Phys. Rev. Lett. 129, 160502 (2022).
https:/​/​doi.org/​10.1103/​PhysRevLett.129.160502

[27] J. D. Whitfield, C. A. Rodríguez-Rosario, and A. Aspuru-Guzik. ``Quantum stochastic walks: A generalization of classical random walks and quantum walks''. Phys. Rev. A 81, 022323 (2010).
https:/​/​doi.org/​10.1103/​PhysRevA.81.022323

[28] G. Bressanini, C. Benedetti, and M. G. A. Paris. ``Decoherence and classicalization of continuous-time quantum walks on graphs''. Quantum Inf. Process. 21, 317 (2022).
https:/​/​doi.org/​10.1007/​s11128-022-03647-x

[29] S. Wald and L. Bottcher. ``From classical to quantum walks with stochastic resetting on networks''. Phys. Rev. E 103, 012122 (2021).
https:/​/​doi.org/​10.1103/​PhysRevE.103.012122

[30] M. Bruderer and M. B. Plenio. ``Decoherence-enhanced performance of quantum walks applied to graph isomorphism testing''. Phys. Rev. A 94, 062317 (2016).
https:/​/​doi.org/​10.1103/​PhysRevA.94.062317

[31] N. Dalla Pozza and F. Caruso. ``Quantum state discrimination on reconfigurable noise-robust quantum networks''. Phys. Rev. Res. 2, 043011 (2020).
https:/​/​doi.org/​10.1103/​PhysRevResearch.2.043011

[32] L.-J. Wang, J.-Y. Lin, and S. Wu. ``Implementation of quantum stochastic walks for function approximation, two-dimensional data classification, and sequence classification''. Phys. Rev. Res. 4, 023058 (2022).
https:/​/​doi.org/​10.1103/​PhysRevResearch.4.023058

[33] F. Caruso, A. Crespi, A. G. Ciriolo, F. Sciarrino, and R. Osellame. ``Fast escape of a quantum walker from an integrated photonic maze''. Nature Commun. 7, 11682 (2016).
https:/​/​doi.org/​10.1038/​ncomms11682

[34] N. Dalla Pozza, L. Buffoni, S. Martina, and F. Caruso. ``Quantum reinforcement learning: the maze problem''. Quantum Mach. Intell. 4, 11 (2022).
https:/​/​doi.org/​10.1007/​s42484-022-00068-y

[35] N. Dudhe, P. K. Sahoo, and C. Benjamin. ``Testing quantum speedups in exciton transport through a photosynthetic complex using quantum stochastic walks''. Phys. Chem. Chem. Phys. 24, 2601 (2022).
https:/​/​doi.org/​10.1039/​d1cp02727a

[36] U. Nzongani, A. Simonetto, and G. Di Molfetta. ``Nonunitary enhanced transfer efficiency in quantum walk search on complex networks''. Phys. Rev. A 112, 052451 (2025).
https:/​/​doi.org/​10.1103/​jhbs-27mm

[37] S. Garnerone. ``Thermodynamic formalism for dissipative quantum walks''. Phys. Rev. A 86, 032342 (2012).
https:/​/​doi.org/​10.1103/​PhysRevA.86.032342

[38] C. Benjamin and N. Dudhe. ``Resolving degeneracies in Google search via quantum stochastic walks''. J. Stat. Mech.-Theory Exp. 2024, 013402 (2024).
https:/​/​doi.org/​10.1088/​1742-5468/​ad1384

[39] S. Longhi. ``Dynamical Phase Transitions in Open Quantum Walks''. Adv. Quantum Technol. 8, e00539 (2025).
https:/​/​doi.org/​10.1002/​qute.202500539

[40] G. Pólya. ``Uber eine aufgabe betreffend die irrfahrt im strassennetz''. Math. Ann. 84, 149–160 (1921).
https:/​/​doi.org/​10.1007/​BF01458701

[41] M. Štefaňák, I. Jex, and T. Kiss. ``Recurrence and Pólya number of quantum walks''. Phys. Rev. Lett. 100, 020501 (2008).
https:/​/​doi.org/​10.1103/​PhysRevLett.100.020501

[42] Z. Darázs and T. Kiss. ``Pólya number of the continuous-time quantum walks''. Phys. Rev. A 81, 062319 (2010).
https:/​/​doi.org/​10.1103/​PhysRevA.81.062319

[43] F. A. Grünbaum, L. Velázquez, A. H. Werner, and R. F. Werner. ``Recurrence for discrete time unitary evolutions''. Commun. Math. Phys. 320, 543 (2013).
https:/​/​doi.org/​10.1007/​s00220-012-1645-2

[44] T. Nitsche, S. Barkhofen, R. Kruse, L. Sansoni, M. Štefaňák, A. Gábris, V. Potoček, T. Kiss, I. Jex, and Ch. Silberhorn. ``Probing measurement-induced effects in quantum walks via recurrence''. Sci. Adv. 4, eaar6444 (2018).
https:/​/​doi.org/​10.1126/​sciadv.aar6444

[45] Xiao-Xiao Chen, Ya-Jing Wang, An-Ning Zhang, Zhe Meng, Qing-Yuan Wu, Xin-Bing Song, and Xue-Shun Shi. ``Unmonitored and monitored recurrence in single-photon quantum walks''. Phys. Rev. A 110, 012219 (2024).
https:/​/​doi.org/​10.1103/​PhysRevA.110.012219

[46] J. Kempe. ``Discrete Quantum Walks Hit Exponentially Faster''. Probab. Theory Relat. Fields 133, 215 (2005).
https:/​/​doi.org/​10.1007/​s00440-004-0423-2

[47] H. Krovi and T. A. Brun. ``Hitting time for quantum walks on the hypercube''. Phys. Rev. A 73, 032341 (2006).
https:/​/​doi.org/​10.1103/​PhysRevA.73.032341

[48] H. Krovi and T. A. Brun. ``Quantum walks with infinite hitting times''. Phys. Rev. A 74, 042334 (2006).
https:/​/​doi.org/​10.1103/​PhysRevA.74.042334

[49] S. Dhar, S. Dasgupta, and A. Dhar. ``Quantum time of arrival distribution in a simple lattice model''. J. Phys. A Math. Theor. 48, 115304 (2015).
https:/​/​doi.org/​10.1088/​1751-8113/​48/​11/​115304

[50] S. Dhar, S. Dasgupta, A. Dhar, and D. Sen. ``Detection of a quantum particle on a lattice under repeated projective measurements''. Phys. Rev. A 91, 062115 (2015).
https:/​/​doi.org/​10.1103/​PhysRevA.91.062115

[51] F. Thiel, E. Barkai, and D. A. Kessler. ``First detected arrival of a quantum walker on an infinite line''. Phys. Rev. Lett. 120, 040502 (2018).
https:/​/​doi.org/​10.1103/​PhysRevLett.120.040502

[52] R. Yin, K. Ziegler, F. Thiel, and E. Barkai. ``Large fluctuations of the first detected quantum return time''. Phys. Rev. Res. 1, 033086 (2019).
https:/​/​doi.org/​10.1103/​PhysRevResearch.1.033086

[53] R. Yin and E. Barkai. ``Restart expedites quantum walk hitting times''. Phys. Rev. Lett. 130, 050802 (2023).
https:/​/​doi.org/​10.1103/​PhysRevLett.130.050802

[54] Q. Wang, S. Ren, R. Yin, K. Ziegler, E. Barkai, and S. Tornow. ``First Hitting Times on a Quantum Computer: Tracking vs. Local Monitoring, Topological Effects, and Dark States''. Entropy 26, 869 (2024).
https:/​/​doi.org/​10.3390/​e26100869

[55] J. Bourgain, F. A. Grünbaum, L. Velázquez, and J. Wilkening. ``Quantum Recurrence of a Subspace and Operator-Valued Schur Functions''. Commun. Math. Phys. 329, 1031 (2014).
https:/​/​doi.org/​10.1007/​s00220-014-1929-9

[56] F. A. Grünbaum and L. Velázquez. ``A generalization of schur functions: Applications to nevanlinna functions, orthogonal polynomials, random walks and unitary and open quantum walks''. Advances Math. 326, 352–464 (2018).
https:/​/​doi.org/​10.1016/​j.aim.2017.12.014

[57] B. Tregenna, W. Flanagan, Maile R., and V. Kendon. ``Controlling discrete quantum walks: coins and initial states''. New J. Phys. 5, 83 (2003).
https:/​/​doi.org/​10.1088/​1367-2630/​5/​1/​383

[58] K. G. Sandeep, Thomas K., and Lajos D. ``Unitary equivalence of quantum walks''. Phys. Lett. A 379, 100 (2015).
https:/​/​doi.org/​10.1016/​j.physleta.2014.11.001

[59] A. Ambainis, E. Bach, A. Nayak, A. Vishwanath, and J. Watrous. ``One-dimensional quantum walks''. In Proceedings of the Thirty-third Annual ACM Symposium on Theory of Computing. Pages 37–49. STOC '01New York, NY, USA (2001). ACM.
https:/​/​doi.org/​10.1145/​380752.380757

[60] N. Konno. ``Quantum Random Walks in One Dimension''. Quantum Inform. Process. 1, 345–354 (2002).
https:/​/​doi.org/​10.1023/​A:1023413713008

[61] G. Grimmett, S. Janson, and P. F. Scudo. ``Weak limits for quantum random walks''. Phys. Rev. E 69, 026119 (2004).
https:/​/​doi.org/​10.1103/​PhysRevE.69.026119

[62] M. Sabri, E. Segawa, and M. Štefaňák. ``Conditional limit measure of a one-dimensional quantum walk with an absorbing sink''. Phys. Rev. A 98, 012136 (2018).
https:/​/​doi.org/​10.1103/​PhysRevA.98.012136

[63] P. L. Krapivsky and S. Redner. ``Kinetics of a diffusive capture process: lamb besieged by a pride of lions''. J. Phys. A: Math. Gen. 29, 5347 (1996).
https:/​/​doi.org/​10.1088/​0305-4470/​29/​17/​011

[64] S. Redner and P. L. Krapivsky. ``Capture of the lamb: Diffusing predators seeking a diffusing prey''. Am. J. Phys. 67, 1277–1283 (1999).
https:/​/​doi.org/​10.1119/​1.19115

[65] M. Štefaňák. ``Monitored recurrence of a one-parameter family of three-state quantum walks''. Phys. Scr. 98, 064001 (2023).
https:/​/​doi.org/​10.1088/​1402-4896/​accf43

[66] A. D. Córcoles, M. Takita, K. Inoue, S. Lekuch, Z. K. Minev, J. M. Chow, and J. M. Gambetta. ``Exploiting Dynamic Quantum Circuits in a Quantum Algorithm with Superconducting Qubits''. Phys. Rev. Lett. 127, 100501 (2021).
https:/​/​doi.org/​10.1103/​PhysRevLett.127.100501

[67] F. Acasiete, F. P. Agostini, J. Khatibi Moqadam, and R. Portugal. ``Implementation of quantum walks on IBM quantum computers''. Quantum Inf Process 19, 426 (2020).
https:/​/​doi.org/​10.1007/​s11128-020-02938-5

[68] S. Singh, C. H. Alderete, R. Balu, Ch. Monroe, N. M. Linke, and C. M. Chandrashekar. ``Quantum circuits for the realization of equivalent forms of one-dimensional discrete-time quantum walks on near-term quantum hardware''. Phys. Rev. A 104, 062401 (2021).
https:/​/​doi.org/​10.1103/​PhysRevA.104.062401

[69] L. Razzoli, G. Cenedese, M. Bondani, and G. Benenti. ``Efficient Implementation of Discrete-Time Quantum Walks on Quantum Computers''. Entropy 26, 313 (2024).
https:/​/​doi.org/​10.3390/​e26040313

[70] R. S. Sarkar and B. Adhikari. ``Quantum circuit model for discrete-time three-state quantum walks on Cayley graphs''. Phys. Rev. A 110, 012617 (2024).
https:/​/​doi.org/​10.1103/​PhysRevA.110.012617

[71] T. Kitagawa, M. A. Broome, A. Fedrizzi, M. S. Rudner, E. Berg, I. Kassal, A. Aspuru-Guzik, E. Demler, and A. G. White. ``Observation of topologically protected bound states in photonic quantum walks''. Nature Commun. 3, 882 (2012).
https:/​/​doi.org/​10.1038/​ncomms1872

[72] J. K. Asbóth. ``Symmetries, topological phases, and bound states in the one-dimensional quantum walk''. Phys. Rev. B 86, 195414 (2012).
https:/​/​doi.org/​10.1103/​PhysRevB.86.195414

[73] C. Cedzich, F. A. Grünbaum, C. Stahl, L. Velázquez, A. H. Werner, and R. F. Werner. ``Bulk-edge correspondence of one-dimensional quantum walks''. J. Phys. A: Math. Theor. 49, 21LT01 (2016).
https:/​/​doi.org/​10.1088/​1751-8113/​49/​21/​21LT01

[74] J. K. Asbóth, L. Oroszlány, and A. Pályi. ``A Short Course on Topological Insulators''. Volume 919 of Lecture Notes in Physics. Springer International Publishing. Cham (2016).
https:/​/​doi.org/​10.1007/​978-3-319-25607-8

[75] S. Barkhofen, T. Nitsche, F. Elster, L. Lorz, A. Gabris, I. Jex, and Ch. Silberhorn. ``Measuring topological invariants in disordered discrete-time quantum walks''. Phys. Rev. A 96, 033846 (2017).
https:/​/​doi.org/​10.1103/​PhysRevA.96.033846

[76] url: https:/​/​gitlab.fjfi.cvut.cz/​potocvac/​dtqsw-recurrence.
https:/​/​gitlab.fjfi.cvut.cz/​potocvac/​dtqsw-recurrence

[77] C. S. Patlak. ``Random walk with persistence and external bias''. Bull. Math. Biophys. 15, 311 (1953).
https:/​/​doi.org/​10.1007/​BF02476407

[78] G. H Weiss. ``Some applications of persistent random walks and the telegrapher's equation''. Physica A: Stat. Mech. Appl. 311, 381 (2002).
https:/​/​doi.org/​10.1016/​S0378-4371(02)00805-1

[79] P. Cénac, A. Le Ny, B. de Loynes, and Y. Offret. ``Persistent Random Walks. I. Recurrence Versus Transience''. J. Theor. Probab. 31, 232 (2018).
https:/​/​doi.org/​10.1007/​s10959-016-0714-4

[80] N. Konno. ``Limit Theorems and Absorption Problems for One-Dimensional Correlated Random Walks''. Stochastic Models 25, 28 (2009).
https:/​/​doi.org/​10.1080/​15326340802640941

[81] C. Kiumi, N. Konno, and S. Tamura. ``Return probability of quantum and correlated random walks''. Entropy 24, 584 (2022).
https:/​/​doi.org/​10.3390/​e24050584

Cited by

[1] Quancheng Liu, Sabine Tornow, David A. Kessler, and Eli Barkai, "Fractionally quantized recurrence detection times in monitored quantum many-body systems", Proceedings of the National Academy of Sciences 123 22, e2529694123 (2026).

[2] Saori Yoshino, Honoka Shiratori, Tomoki Yamagami, Ryoichi Horisaki, and Etsuo Segawa, "Normal Variance Mixture with Arcsine Law of an Interpolating Walk Between Persistent Random Walk and Quantum Walk", Entropy 27 7, 670 (2025).

[3] Ammara Ammara, Václav Potoček, Martin Štefaňák, and Francesco V. Pepe, "Quantum Walk on a Line with Absorbing Boundaries", arXiv:2508.13318, (2025).

The above citations are from Crossref's cited-by service (last updated successfully 2026-07-17 02:04:55) and SAO/NASA ADS (last updated successfully 2026-07-17 02:04:56). The list may be incomplete as not all publishers provide suitable and complete citation data.