On Hitting Times For General Quantum Markov Processes

Republished By Plato

Followers: 0

Lorenzo Laneve^1,2, Francesco Tacchino², and Ivano Tavernelli²

¹Faculty of Informatics — Università della Svizzera Italiana, 6900 Lugano, Switzerland
²IBM 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.

On Hitting Times for General Quantum Markov Processes PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Featured image: Flow-chart of the process for the generalized hitting time: unlike in the classical case, we check for the hit only every $T$ steps, where $T$ is sampled each time independently from a fixed probability distribution.

► BibTeX data

@article{Laneve2023hittingtimesgeneral, doi = {10.22331/q-2023-07-12-1056}, url = {https://doi.org/10.22331/q-2023-07-12-1056}, title = {On {H}itting {T}imes for {G}eneral {Q}uantum {M}arkov {P}rocesses}, author = {Laneve, Lorenzo and Tacchino, Francesco and Tavernelli, Ivano}, journal = {{Quantum}}, issn = {2521-327X}, publisher = {{Verein zur F{“{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}}, volume = {7}, pages = {1056}, month = jul, year = {2023}<br /> }

► 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

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.

SEO Powered Content & PR Distribution. Get Amplified Today.
PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
PlatoESG. Automotive / EVs, Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
BlockOffsets. Modernizing Environmental Offset Ownership. Access Here.
Source: https://quantum-journal.org/papers/q-2023-07-12-1056/

Time Stamp: July 12, 2023

Time Stamp: Apr 3, 2024

Quantifying fermionic interactions from the violation of Wick’s theorem

Source Cluster:

Quantum Journal

Source Node: 1722910

Time Stamp: Oct 13, 2022

On relating one-way classical and quantum communication complexities

Source Cluster:

Quantum Journal

Source Node: 1841006

Time Stamp: May 22, 2023

Republished By Plato

Coherent feedback in optomechanical systems in the sideband-unresolved regime

Actis: A Strictly Local Union–Find Decoder

LIMDD: A Decision Diagram for Simulation of Quantum Computing Including Stabilizer States

Distance-based resource quantification for sets of quantum measurements

Subradiant edge states in an atom chain with waveguide-mediated hopping

Near-deterministic hybrid generation of arbitrary photonic graph states using a single quantum emitter and linear optics

Tight Cramér-Rao type bounds for multiparameter quantum metrology through conic programming

A full circuit-based quantum algorithm for excited-states in quantum chemistry

A quantum logic gate for free electrons

From Non-Markovian Dissipation to Spatiotemporal Control of Quantum Nanodevices

Quantifying fermionic interactions from the violation of Wick’s theorem

About Us

Vertical Search & Ai

Platform

Stay Connected

Account