Applying Recursive Quantum Circuit Generation to Solve Database Search Problems Using Grover's Algorithm

Open Access
- Author:
- Rondinelli, Nate
- Area of Honors:
- Software Engineering (Behrend)
- Degree:
- Bachelor of Science
- Document Type:
- Thesis
- Thesis Supervisors:
- Wen-Li Wang, Thesis Supervisor
Wen-Li Wang, Thesis Honors Advisor
Shahid Hussain, Faculty Reader - Keywords:
- Quantum Computing
Grover's Algorithm
Recursion
Toffoli Gate
Qiskit - Abstract:
- 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 search problems. However, it is challenging to construct efficient and scalable circuits for Grover’s algorithm, particularly with increasing numbers of qubit inputs. Problem: Traditional circuit construction methods often require manual composition and result in lengthy and complex circuits. This hinders practical implementation, and the difficulty increases as the search space grows exponentially with additional qubits. Method: The proposed research provides the approach of recursively generating oracle circuits using Toffoli gates as the fundamental units to enhance scalability and reusability while maintaining effectiveness. The methodology leverages Qiskit and IBM Quantum Lab simulation for computation due to limited access to quantum hardware. Result: Through experiments and comparisons between recursively and non-recursively generated circuits, the findings suggest that the recursive approach offers comparable accuracy and computational complexity to the non-recursive approach. However, it tends to require a larger number of basic quantum gates. Conclusion: This research highlights the possibility of utilizing recursively generated circuits as an alternative when implementing Grover’s algorithm. It presents potential scalability benefits and creates an avenue for further research into the time complexity of using actual quantum hardware to validate these results.