Abstract
This comment is to correct the proof of optimality of quantum spatial search for Erd\H{o}s-R\'enyi 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≥ 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=ω(log(n)/n) in case of transition rate γ = 1/λ₁. In the case of the proof for simplified transition rate 1/(np) we pointed a possible issue with applying perturbation theory.