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

October, 2022


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(pN) 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.

Resource Type: