A Unified Framework of Quantum Walk Search

Understand

The main results on quantum walk search are scattered over different, incomparable frameworks, most notably the hitting time framework, originally by Szegedy, the electric network framework by Belovs, and the MNRS framework by Magniez, Nayak, Roland and Santha.

• As a result, a number of pieces are currently missing.
• For instance, the electric network framework allows quantum walks to start from an arbitrary initial state, but it only detects marked elements.
• In recent work by Ambainis et al., this problem was resolved for the more restricted hitting time framework, in which quantum walks must start from the stationary distribution.