Optimal and Deterministic Quantum Search on the Simplex of Complete Graphs
TL;DR
The first analytical proof of optimal quantum search on the simplex of complete graphs is given, proving that it occurs when the weight of the bridges equals $M$ and that the optimal runtime is achieved more broadly whenever the weight is at least $\sqrt{M}$.
Abstract
The simplex of complete graphs, also known as the first-order truncated simplex lattice, is a network of $M+1$ identical complete graphs, each with $M$ vertices, such that each clique contains an edge or bridge to every other clique. It contains $N = M(M+1)$ vertices, and previous asymptotic results using a continuous-time quantum walk to search this graph for a single marked vertex have either numerically demonstrated an optimal runtime of $O(\sqrt{N})$, or analytically proved a deterministic success probability of 1, but not both, even when the bridges are weighted. In this paper, we give the first analytical proof of optimal quantum search on this graph, proving that it occurs when the weight of the bridges equals $M$. In addition, we numerically show that the optimal runtime is achieved more broadly whenever the weight is at least $\sqrt{M}$. Furthermore, the algorithm is also deterministic when the weight scales between $\sqrt{M}$ and $M$, and this is the first example of quantum search on the simplex of complete graphs that is both asymptotically optimal and deterministic. In addition, for weights where the algorithm is nondeterministic, we give a way to find the marked vertex by inspecting neighboring vertices. Finally, while it is known that connectivity is not a reliable indicator of fast quantum search when comparing different graph families, we show that it is also unreliable within the graph family of weighted simplex of complete graphs.