论文标题
评论量子步行对空间搜索的评论对于几乎所有图表都是最佳的
Comment to Spatial Search by Quantum Walk is Optimal for Almost all Graphs
论文作者
论文摘要
此评论是为了纠正“量子搜索中显示的erdős-rényi图的量子空间搜索的最佳证明”（量子步行搜索几乎所有图形都是最佳的”（https://doi.org/10.1103/physrevlett.116.100501）。作者声称，如果$ p \ geq \ frac {\ log^{3/2}（n）} {n} $，则基于CTQW的搜索对于几乎所有图形都是最佳的。在下面，我们指出了主要论文中发现的问题，并提出了校正，实际上，在过渡速率$γ= 1/λ_1$的情况下，将结果提高到$ p =ω（\ log（n）/n）$。在简化过渡速率$ 1/（np）$的证明的情况下，我们指出了应用扰动理论的可能问题。
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\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=ω(\log(n)/n)$ in case of transition rate $γ= 1/λ_1$. In the case of the proof for simplified transition rate $1/(np)$ we pointed a possible issue with applying perturbation theory.
