Matched-multiphase Grover algorithm for a small number of marked states
F. Masafumi Toyama, S. Kasai, W. van Dijk, Yukihisa Nogami · Physical Review A · 2009
Recently, we proposed a multiphase-matching method for the Grover algorithm with a matching rule for multiple phases ${\ensuremath{\alpha}}_{j}$ and ${\ensuremath{\beta}}_{j}$, $j=1,\dots{},k$, where $k$ is the number of Grover operations. The phases are matched such that ${\ensuremath{\alpha}}_{j}=\ensuremath{-}{\ensuremath{\beta}}_{k\ensuremath{-}j+1}$ globally over a sequence of $k$ Grover operations. The success probability ${P}_{6}(\ensuremath{\lambda})$ for $k=6$ was found to be almost constant and unity over a wide range of $\ensuremath{\lambda}$, i.e., $0.107\phantom{\rule{0.2em}{0ex}}77\ensuremath{\leqslant}\ensuremath{\lambda}\ensuremath{\leqslant}1$, where $\ensuremath{\lambda}$ is the fraction of marked items in a database state. For $\ensuremath{\lambda}<0.107\phantom{\rule{0.2em}{0ex}}77$, however, ${P}_{6}(\ensuremath{\lambda})$ decreases rapidly to zero as $\ensuremath{\lambda}$ decreases and the efficiency of the method deteriorates. In this Brief Report we show that the difficulty with small values of $\ensuremath{\lambda}$ mentioned above can be alleviated by increasing the number of operations $k$. With $k=20$, for example, we find a value of ${P}_{20}(\ensuremath{\lambda})$ that is almost constant and unity in the region of small $\ensuremath{\lambda}$ where the matching with six Grover operations is not effective. The matching with $k=6$ and the one with $k=20$ complement each other so that the entire range of $0\ensuremath{\lesssim}\ensuremath{\lambda}<1$ can be well covered.