Quantum Computing and Complexity Theory - Purwo Agus Sucipto; Loso Judijanto; Nasser Qudah (Yayasan Adra Karima Hubbi, 2025)
The background of this research is driven by the rapid development of quantum computing which has the potential to change the paradigm in complexity theory and computational algorithms. The purpose of this study is to explore the advantages and limitations of quantum algorithms in solving problems with high complexity, as well as to understand their role in complexity theory. The research method used involves quantum computer simulations to analyze the performance of Shor and Grover's algorithms in solving cryptographic problems and large database searches, as well as comparing them with classical algorithms. The results show that quantum algorithms have significant advantages in solving certain problems, although there are technical obstacles in quantum hardware that affect overall performance. Quantum computing has great potential in the fields of cryptography and big data processing, but challenges such as quantum errors and decoherence still have to be overcome. The conclusion of this study confirms the importance of further research in improving quantum hardware and developing more efficient algorithms, as well as opening up new opportunities for the application of quantum computing in various industries.