Comment to Spatial Search by Quantum Walk is Optimal for Almost all Graphs

Abstract

This comment is to correct the proof of optimality of quantum spatial search for Erdős-Rényi graphs presented in `Spatial Search by Quantum Walk is Optimal for Almost all Graphs' (https://doi.org/10.1103/PhysRevLett.116.100501). The authors claim that if $p\ge \frac{{\log }^{3/2}(n)}{n}$, then the CTQW-based search is optimal for almost all graphs. Below we point the issues found in the main paper, and propose corrections, which in fact improve the result to $p=\omega (\log (n)/n)$ in case of transition rate $\gamma =1/{\lambda }_1$. In the case of the proof for simplified transition rate $1/(np)$ we pointed a possible issue with applying perturbation theory.

The comments applies for the paper found in https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.116.100501

Cited by in corpus (1)

• Application of graph theory in quantum computer science