Depth-First Grover Search Algorithm on Hybrid Quantum-Classical Computer

October, 2022

Abstract

We demonstrated the detailed construction of the hybrid quantum-classical computer. Based on this architecture, the useful concept of amplitude interception is illustrated. It is then embedded into a combination of Depth-First Search and Grover's algorithm to generate a novel approach, the Depth-First Grover Search(DFGS), to handle multi-solution searching problems on unstructured databases with an unknown number of solutions. Our new algorithm attains an average complexity of O(mN−−√) which performs as efficient as a normal Grover Search, and a O(p–√N) complexity with a manually determined constant p for the case with all elements are solutions, where a normal Grover Search will degenerate to O(NN−−√). The DFGS algorithm is more robust and stable in comparison.