On Hitting Times for General Quantum Markov Processes

Understand

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\"oning'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.