ICS 269, Spring 2022: Theory Seminar
Bren Hall 1423, 1:00 – 1:50

27 May 2022: Shion Fukuzawa

Quantum random walks and near-optimal quantum algorithms for string problems

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.