On Hitting Times for General Quantum Markov Processes
arXiv:2210.10188 · doi:10.22331/q-2023-07-12-1056
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 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.
arXiv comment18 pages, 5 figures
References in corpus (22)
- Array Programming with NumPy
- Quantum Mechanics helps in searching for a needle in a haystack
- Quantum random walks - an introductory overview
- A Quantum Random Walk Search Algorithm
- Quantum walks: a comprehensive review
- Spatial search by quantum walk
- Search via Quantum Walk
- OpenQASM 3: A broader and deeper quantum assembly language
- Decoherence in quantum walks - a review
- Decoherence can be useful in quantum walks
- Multiplicative Drift Analysis
- Faster quantum walk algorithm for the two dimensional spatial search
- Quantum stochastic walks: A generalization of classical random walks and quantum walks
- Stochastic Representation of a Class of Non-Markovian Completely Positive Evolutions
- Quantum walks: the first detected passage time problem
- On the adiabatic condition and the quantum hitting time of Markov chains
- Finding a marked node on any graph by continuous-time quantum walk
- Sampling, rates, and reaction currents through reverse stochastic quantization on quantum computers
- Measurement induced quantum walks
- Improved Upper Bounds for the Hitting Times of Quantum Walks
- Quantum algorithms for subset finding
- Coins Make Quantum Walks Faster