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 cla...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(√N) 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 over0.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.展开更多
基金supported by the National Key Research and Development Program(Grant No.2017YFA0305200)the Key Research and Development Program of Guangdong Province of China(Grant Nos.2018B030329001,and 2018B030325001)+1 种基金the National Natural Science Foundation of China(Grant No.61974168)support from the National Young 1000 Talents Plan。
文摘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(√N) 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 over0.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.
