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.
18 pages, 5 figures
References in corpus (8)
- Array Programming with NumPy
- Spatial search by quantum walk
- Decoherence in quantum walks - a review
- Faster quantum walk algorithm for the two dimensional spatial search
- Stochastic Representation of a Class of Non-Markovian Completely Positive Evolutions
- On the adiabatic condition and the quantum hitting time of Markov chains
- Sampling, rates, and reaction currents through reverse stochastic quantization on quantum computers
- Coins Make Quantum Walks Faster