Recursive Generation of Multi-Qubits Control Gate to Facilitate the Grover's Quantum Algorithm in Large Scale Database Search
Wen-Li Wang, Shahid Hussain, Nathaniel V. Rondinelli, Mei-Huei Tang, Saif Ur Rehman Khan · 2024
Context: Grover's algorithm is a powerful tool in the realm of quantum computing because it offers exponential speedup over classical linear searching for unstructured / unsorted search problems. However, it is challenging to construct efficient and scalable circuits for a multi-input control gate in the algorithm, particularly with a huge number of qubit inputs. Problem: Traditional circuit construction methods often require manual composition for the multi-input gate from basic quantum gates, which can be time consuming and error prone, thus hindering practical implementation. Moreover, the number of simple gates in the composition grows exponentially with the addition of each qubit. Method: This research provides an approach to recursively generate the oracle using Toffoli gates as the fundamental units to enhance scalability and reusability while maintaining effectiveness. The methodology leverages IBM Qiskit and Quantum Lab to simulate quantum computation to prove the practicality and feasibility. Result: The findings from the experiments between recursively and non-recursively generated circuits suggest that our recursive approach can offer comparable accuracy and computational complexity compared to the non-recursive approach. However, it tends to require a larger number of basic quantum gates due to a lack of circuit optimization. Conclusion: The results showcase the applicability of utilizing recursion as a speedy and economical alternative to generate circuits when implementing the Grover's algorithm. It not only presents potential scalability benefits, but also creates an avenue for further research on test verification and performance improvement to the computing community when running in actual quantum hardware.