On Hitting Times for General Quantum Markov Processes

Lorenzo Laneve1,2, Francesco Tacchino2, and Ivano Tavernelli2

1Faculty of Informatics — Università della Svizzera Italiana, 6900 Lugano, Switzerland
2IBM Quantum, IBM Research — Zurich, Säumerstrasse 4, 8803 Rüschlikon, Switzerland

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

Abstract

Random walks (or Markov chains) are models extensively used in theoretical computer science. Several tools, including analysis of quantities such as hitting and mixing times, are helpful for devising randomized algorithms. A notable example is Schöning's algorithm for the satisfiability (SAT) problem. In this work, we use the density-matrix formalism to define a $\textit{quantum Markov chain}$ model which directly generalizes classical walks, and we show that a common tools such as hitting times can be computed with a similar formula as the one found in the classical theory, which we then apply to known quantum settings such as Grover's algorithm.

► BibTeX data

► References

[1] T. Schöning. ``A probabilistic algorithm for k-sat and constraint satisfaction problems''. In 40th Annual Symposium on Foundations of Computer Science (Cat. No.99CB37039). Pages 410–414. (1999).
https:/​/​doi.org/​10.1109/​SFFCS.1999.814612

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

[3] Hari Krovi, Maris Ozols, and Jérémie Roland. ``Adiabatic condition and the quantum hitting time of markov chains''. Phys. Rev. A 82, 022333 (2010).
https:/​/​doi.org/​10.1103/​PhysRevA.82.022333

[4] Frédéric Magniez, Ashwin Nayak, Jérémie Roland, and Miklos Santha. ``Search via quantum walk''. SIAM Journal on Computing 40, 142–164 (2011).
https:/​/​doi.org/​10.1137/​090745854

[5] Shantanav Chakraborty, Leonardo Novo, and Jérémie Roland. ``Finding a marked node on any graph via continuous-time quantum walks''. Phys. Rev. A 102, 022227 (2020).
https:/​/​doi.org/​10.1103/​PhysRevA.102.022227

[6] J Kempe. ``Quantum random walks: An introductory overview''. Contemporary Physics 44, 307–327 (2003).
https:/​/​doi.org/​10.1080/​00107151031000110776

[7] Julia Kempe. ``Discrete Quantum Walks Hit Exponentially Faster''. Probability Theory and Related Fields 133, 215–235 (2005).
https:/​/​doi.org/​10.1007/​s00440-004-0423-2

[8] A. Ambainis. ``Quantum walk algorithm for element distinctness''. In 45th Annual IEEE Symposium on Foundations of Computer Science. Pages 22–31. (2004).
https:/​/​doi.org/​10.1109/​FOCS.2004.54

[9] Andrew M. Childs and Jason M. Eisenberg. ``Quantum algorithms for subset finding''. Quantum Information and Computation 5, 593–604 (2005).
https:/​/​doi.org/​10.26421/​qic5.7

[10] Neil Shenvi, Julia Kempe, and K. Birgitta Whaley. ``Quantum random-walk search algorithm''. Physical Review A 67, 052307 (2003).
https:/​/​doi.org/​10.1103/​physreva.67.052307

[11] David Layden, Guglielmo Mazzola, Ryan V. Mishmash, Mario Motta, Pawel Wocjan, Jin-Sung Kim, and Sarah Sheldon. ``Quantum-enhanced markov chain monte carlo'' (2022). arXiv:2203.12497.
arXiv:2203.12497

[12] Guglielmo Mazzola. ``Sampling, rates, and reaction currents through reverse stochastic quantization on quantum computers''. Phys. Rev. A 104, 022431 (2021).
https:/​/​doi.org/​10.1103/​PhysRevA.104.022431

[13] Dorit Aharonov, Andris Ambainis, Julia Kempe, and Umesh Vazirani. ``Quantum walks on graphs''. Conference Proceedings of the Annual ACM Symposium on Theory of Computing (2001).
https:/​/​doi.org/​10.1145/​380752.380758

[14] M. Szegedy. ``Quantum speed-up of markov chain based algorithms''. In 45th Annual IEEE Symposium on Foundations of Computer Science. Pages 32–41. (2004).
https:/​/​doi.org/​10.1109/​FOCS.2004.53

[15] Avatar Tulsi. ``Faster quantum-walk algorithm for the two-dimensional spatial search''. Phys. Rev. A 78, 012310 (2008).
https:/​/​doi.org/​10.1103/​PhysRevA.78.012310

[16] Andris Ambainis, András Gilyén, Stacey Jeffery, and Martins Kokainis. ``Quadratic speedup for finding marked vertices by quantum walks''. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing. Page 412–424. STOC 2020New York, NY, USA (2020). Association for Computing Machinery.
https:/​/​doi.org/​10.1145/​3357713.3384252

[17] Viv Kendon. ``Decoherence in quantum walks – a review''. Mathematical Structures in Computer Science 17, 1169–1220 (2007).
https:/​/​doi.org/​10.1017/​s0960129507006354

[18] Viv Kendon and Ben Tregenna. ``Decoherence can be useful in quantum walks''. Physical Review A 67, 042315 (2003).
https:/​/​doi.org/​10.1103/​physreva.67.042315

[19] Michael A. Nielsen and Isaac L. Chuang. ``Quantum computation and quantum information: 10th anniversary edition''. Cambridge University Press. (2010).
https:/​/​doi.org/​10.1017/​CBO9780511976667

[20] Adrián A. Budini. ``Stochastic representation of a class of non-markovian completely positive evolutions''. Phys. Rev. A 69, 042107 (2004).
https:/​/​doi.org/​10.1103/​PhysRevA.69.042107

[21] Stan Gudder. ``Quantum markov chains''. Journal of Mathematical Physics 49, 072105 (2008).
https:/​/​doi.org/​10.1063/​1.2953952

[22] James D. Whitfield, César A. Rodríguez-Rosario, and Alán Aspuru-Guzik. ``Quantum stochastic walks: A generalization of classical random walks and quantum walks''. Physical Review A 81, 022323 (2010).
https:/​/​doi.org/​10.1103/​physreva.81.022323

[23] Karuna Kadian, Sunita Garhwal, and Ajay Kumar. ``Quantum walk and its application domains: A systematic review''. Computer Science Review 41, 100419 (2021).
https:/​/​doi.org/​10.1016/​j.cosrev.2021.100419

[24] Salvador Elías Venegas-Andraca. ``Quantum walks: a comprehensive review''. Quantum Information Processing 11, 1015–1106 (2012).
https:/​/​doi.org/​10.1007/​s11128-012-0432-5

[25] Frédéric Magniez, Ashwin Nayak, Peter C. Richter, and Miklos Santha. ``On the Hitting Times of Quantum Versus Random Walks''. Algorithmica 63, 91–116 (2012).
https:/​/​doi.org/​10.1007/​s00453-011-9521-6

[26] Yosi Atia and Shantanav Chakraborty. ``Improved upper bounds for the hitting times of quantum walks''. Physical Review A 104, 032215 (2021).
https:/​/​doi.org/​10.1103/​physreva.104.032215

[27] Andris Ambainis, Julia Kempe, and Alexander Rivosh. ``Coins make quantum walks faster''. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms. Page 1099–1108. SODA '05USA (2005). Society for Industrial and Applied Mathematics.
https:/​/​doi.org/​10.48550/​arXiv.quant-ph/​0402107
arXiv:quant-ph/0402107

[28] A. Didi and E. Barkai. ``Measurement-induced quantum walks''. Phys. Rev. E 105, 054108 (2022).
https:/​/​doi.org/​10.1103/​PhysRevE.105.054108

[29] H. Friedman, D. A. Kessler, and E. Barkai. ``Quantum walks: The first detected passage time problem''. Phys. Rev. E 95, 032141 (2017).
https:/​/​doi.org/​10.1103/​PhysRevE.95.032141

[30] Sabine Tornow and Klaus Ziegler. ``Measurement induced quantum walks on an ibm quantum computer'' (2022). arXiv:2210.09941.
arXiv:2210.09941

[31] J. R. Norris. ``Markov chains''. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press. (1997).
https:/​/​doi.org/​10.1017/​CBO9780511810633

[32] Lov K. Grover. ``A fast quantum mechanical algorithm for database search''. In Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing. Page 212–219. STOC '96New York, NY, USA (1996). Association for Computing Machinery.
https:/​/​doi.org/​10.1145/​237814.237866

[33] Lov K. Grover. ``Quantum mechanics helps in searching for a needle in a haystack''. Physical Review Letters 79, 325–328 (1997).
https:/​/​doi.org/​10.1103/​physrevlett.79.325

[34] Wolfram Research, Inc. ``Mathematica, Version 13.1''. Champaign, IL, 2022.

[35] Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchant, Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. ``Array programming with NumPy''. Nature 585, 357–362 (2020).
https:/​/​doi.org/​10.1038/​s41586-020-2649-2

[36] A. D. Córcoles, Maika Takita, Ken Inoue, Scott Lekuch, Zlatko K. Minev, Jerry M. Chow, and Jay 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

[37] Andrew Cross, Ali Javadi-Abhari, Thomas Alexander, Niel De Beaudrap, Lev S. Bishop, Steven Heidel, Colm A. Ryan, Prasahnt Sivarajah, John Smolin, Jay M. Gambetta, and Blake R. Johnson. ``OpenQASM 3: A broader and deeper quantum assembly language''. ACM Transactions on Quantum Computing 3, 1–50 (2022).
https:/​/​doi.org/​10.1145/​3505636

[38] Qiskit Community. ``Qiskit: An open-source framework for quantum computing'' (2017).

[39] David A Levin and Yuval Peres. ``Markov chains and mixing times''. Volume 107. American Mathematical Soc. (2017).
https:/​/​doi.org/​10.1090/​mbk/​107

[40] Jun He and Xin Yao. ``A study of drift analysis for estimating computation time of evolutionary algorithms''. Natural Computing 3, 21–35 (2004).
https:/​/​doi.org/​10.1023/​B:NACO.0000023417.31393.c7

[41] Benjamin Doerr, Daniel Johannsen, and Carola Winzen. ``Multiplicative drift analysis''. Algorithmica 64, 673–697 (2012).
https:/​/​doi.org/​10.1007/​s00453-012-9622-x

Cited by

On Crossref's cited-by service no data on citing works was found (last attempt 2024-06-22 03:39:50). On SAO/NASA ADS no data on citing works was found (last attempt 2024-06-22 03:39:50).