Experimental demonstration of deterministic quantum search algorithms on a programmable silicon photonic chip

The Grover quantum search algorithm is a landmark quantum computing application, which has a speed advantage over classical algorithms for searching an unsorted database. For an unsorted database of N items, the classical algorithm needs to search O(N) times, while the Grover algorithm only needs O(vN) times. However, except for the special case of N = 4, the traditional Grover algorithm always has some probability of failure. To solve this problem, several schemes for deterministically performing quantum search have been proposed, but they all impose additional requirements on the query Oracle and cannot be implemented in many practical scenarios. Recently, Roy et al. [Phys. Rev. Res. 4, L022013 (2022)] proposed a new deterministic quantum search scheme with no additional requirements on the query Oracle, which has the potential to perfectly replace the traditional Grover algorithm. In this study, we experimentally implement on a programmable silicon quantum photonic chip four deterministic quantum search algorithms, including the Roy algorithm, all of which obtained an average search success rate of over 0.93, exceeding the theoretical maximum of 0.9074 that the traditional Grover algorithm can achieve. Our results demonstrate the feasibility and superiority of the deterministic quantum search algorithms and are expected to facilitate the wider application of these algorithms in future quantum information processing.

Automated summary

The Grover quantum search algorithm is a powerful tool for searching unsorted databases with a speed advantage over classical algorithms. However, it has a probability of failure in most cases. A new deterministic quantum search scheme proposed by Roy et al. shows potential to replace the traditional Grover algorithm without imposing additional requirements on the query Oracle.