quantum-computing

Recurrence in discrete-time quantum stochastic walks

Martin Stefanak, Vaclav Potocek, Iskender Yalcinkaya, Aurel Gabris, and Igor Jex

26 min read

0 likes

⚡ Quantum Brief

Researchers discovered that adding classical randomness to quantum walks can paradoxically reduce recurrence probability, defying intuition that noise would make systems behave more classically. This counterintuitive effect persists even as step numbers approach infinity. The study analyzed discrete-time quantum stochastic walks on a line, revealing conditions where quantum-classical interplay suppresses return probability more effectively than pure quantum or classical walks alone. Numerical evaluations confirmed this isn't transient but a robust asymptotic feature. The findings challenge the assumption that classical noise always increases recurrence, showing quantum interference and randomness can create more efficient escape mechanisms than either pure quantum or classical dynamics. Potential applications include designing superior quantum search algorithms and understanding quantum information resilience in noisy environments, where controlled stochasticity could enhance performance. This work builds on prior quantum walk research but introduces a novel regime where hybrid quantum-classical systems outperform both pure quantum and classical approaches in specific tasks.

AI Audio Summary

0:00 / 0:00

Click to play

Quantum News · Media Library

Understand this faster with AI

Ask ChatGPT

Research with Perplexity

Explain with Claude

Discuss on Grok

AbstractInterplay 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.Featured image: Recurrence probability as a function of stochasticity for different parameters of the quantum coin.Popular summaryIn 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@article{Stefanak2026recurrencein, doi = {10.22331/q-2026-01-22-1982}, url = {https://doi.org/10.22331/q-2026-01-22-1982}, title = {Recurrence in discrete-time quantum stochastic walks}, author = {Stefanak, Martin and Potocek, Vaclav and Yalcinkaya, Iskender and Gabris, Aurel and Jex, Igor}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {1982}, month = jan, year = {2026} }► 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/e24050584Cited byCould not fetch Crossref cited-by data during last attempt 2026-01-22 10:47:47: Could not fetch cited-by data for 10.22331/q-2026-01-22-1982 from Crossref. This is normal if the DOI was registered recently. Could not fetch ADS cited-by data during last attempt 2026-01-22 10:47:56: No response from ADS or unable to decode the received json data when getting the list of citing works.This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions. AbstractInterplay 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.Featured image: Recurrence probability as a function of stochasticity for different parameters of the quantum coin.Popular summaryIn 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@article{Stefanak2026recurrencein, doi = {10.22331/q-2026-01-22-1982}, url = {https://doi.org/10.22331/q-2026-01-22-1982}, title = {Recurrence in discrete-time quantum stochastic walks}, author = {Stefanak, Martin and Potocek, Vaclav and Yalcinkaya, Iskender and Gabris, Aurel and Jex, Igor}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {10}, pages = {1982}, month = jan, year = {2026} }► 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.

Read Original

Source Information

Source: Quantum Journal

Website: https://quantum-journal.org/feed/

Discussion

0 professional contributions

Be the first to add a constructive contribution.

Recurrence in discrete-time quantum stochastic walks

Tags

Source Information