In this talk I will be discussing the MNRS quantum random walk technique introduced by Magniez et al.[1] and discussing an example of its application on the longest common substring problem. The applications on string problems was introduced and discussed by Akmal and Jin.[2] They show that the longest common substring problem can be solved by a quantum algorithm in time \(\tilde O(n^{2/3})\) (where \(\tilde O\) indicates that polylog terms are suppressed) by combining the quantum random walk with string synchronizing sets and generalized difference covers.
[1]: Frederic Magniez, Ashwin Nayak, Peter C. Richter, and Miklos Santha. "On the hitting times of quantum versus random walks". SODA 2009, pp. 86–95. Algorithmica 63: 91–116, 2012. arXiv:0808.0084
[2]: Shyan Akmal and Ce Jin. "Near-optimal quantum algorithms for string problems". SODA 2022, pp. 2791–2832. arXiv:2110.09696.