Optimal quantum search on truncated simplex lattices
Yunkai Wang, Shengjun Wu, Wei Wang · Physical Review A · 2020
First-order truncated simplex lattices have been used as interesting data structures to explore the properties of quantum search such as the effect of connectivity on search speed [D. A. Meyer and T. G. Wong, Phys. Rev. Lett. 114, 110503 (2015)]. In this paper, we further discuss quantum search algorithms for truncated simplex lattices. We first propose a multistage quantum algorithm for an $r\mathrm{th}$-order truncated simplex lattice with $N$ vertices based on the numerical calculation up to the fifth-order lattice, which requires an $(r+1)$-stage search process and consumes a run time $\mathrm{\ensuremath{\Theta}}({N}^{(2r+1)/(2r+2)})$ in general. Furthermore, with edge weights suitably adjusted (which increases the connectivity according to certain definitions), we merge the multistage search process into a single stage and achieve a fast quantum search algorithm with an optimal run time $\mathrm{\ensuremath{\Theta}}(\sqrt{N})$ for first-order truncated simplex lattices, which we conjecture is generally true for any-order lattice. Under small noise of the lattice structure, both our multistage and our single-stage search algorithms are quite robust.