Comment to Spatial Search by Quantum Walk is Optimal for Almost all Graphs
This comment is to correct the proof of optimality of quantum spatial search for Erdos Renyi graphs presented in `Spatial Search by Quantum Walk is Optimal for Almost all Graphs' (this https URL) The authors claim that if $p\geq \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.