Article Sidebar
-
Complexity Theory, Quantum Algorithms, Quantum Computing
Abstract
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.
Full text article
References
Ajagekar, A., Humble, T., & You, F. (2020). Quantum computing based hybrid solution strategies for large-scale discrete-continuous optimization problems. Computers & Chemical Engineering, 132, 106630. https://doi.org/10.1016/j.compchemeng.2019.106630
Ajagekar, A., & You, F. (2019). Quantum computing for energy systems optimization: Challenges and opportunities. Energy, 179, 76–89. https://doi.org/10.1016/j.energy.2019.04.186
Bardin, J. C., Slichter, D. H., & Reilly, D. J. (2021). Microwaves in Quantum Computing. IEEE Journal of Microwaves, 1(1), 403–427. https://doi.org/10.1109/JMW.2020.3034071
Bonen, S., Alakusu, U., Duan, Y., Gong, M. J., Dadash, M. S., Lucci, L., Daughton, D. R., Adam, G. C., Iordanescu, S., Pasteanu, M., Giangu, I., Jia, H., Gutierrez, L. E., Chen, W. T., Messaoudi, N., Harame, D., Muller, A., Mansour, R. R., Asbeck, P., & Voinigescu, S. P. (2018). Cryogenic Characterization of 22nm FDSOI CMOS Technology for Quantum Computing ICs. IEEE Electron Device Letters, 1–1. https://doi.org/10.1109/LED.2018.2880303
Bravyi, S., Dial, O., Gambetta, J. M., Gil, D., & Nazario, Z. (2022). The future of quantum computing with superconducting qubits. Journal of Applied Physics, 132(16), 160902. https://doi.org/10.1063/5.0082975
Bruzewicz, C. D., Chiaverini, J., McConnell, R., & Sage, J. M. (2019). Trapped-ion quantum computing: Progress and challenges. Applied Physics Reviews, 6(2), 021314. https://doi.org/10.1063/1.5088164
Cacciapuoti, A. S., Caleffi, M., Tafuri, F., Cataliotti, F. S., Gherardini, S., & Bianchi, G. (2020). Quantum Internet: Networking Challenges in Distributed Quantum Computing. IEEE Network, 34(1), 137–143. https://doi.org/10.1109/MNET.001.1900092
Corcoles, A. D., Kandala, A., Javadi-Abhari, A., McClure, D. T., Cross, A. W., Temme, K., Nation, P. D., Steffen, M., & Gambetta, J. M. (2020). Challenges and Opportunities of Near-Term Quantum Computing Systems. Proceedings of the IEEE, 108(8), 1338–1352. https://doi.org/10.1109/JPROC.2019.2954005
Cuomo, D., Caleffi, M., & Cacciapuoti, A. S. (2020). Towards a distributed quantum computing ecosystem. IET Quantum Communication, 1(1), 3–8. https://doi.org/10.1049/iet-qtc.2020.0002
Egger, D. J., Gambella, C., Marecek, J., McFaddin, S., Mevissen, M., Raymond, R., Simonetto, A., Woerner, S., & Yndurain, E. (2020). Quantum Computing for Finance: State-of-the-Art and Future Prospects. IEEE Transactions on Quantum Engineering, 1, 1–24. https://doi.org/10.1109/TQE.2020.3030314
Fernandez-Carames, T. M., & Fraga-Lamas, P. (2020). Towards Post-Quantum Blockchain: A Review on Blockchain Cryptography Resistant to Quantum Computing Attacks. IEEE Access, 8, 21091–21116. https://doi.org/10.1109/ACCESS.2020.2968985
Gaitan, F. (2020). Finding flows of a Navier–Stokes fluid through quantum computing. Npj Quantum Information, 6(1), 61. https://doi.org/10.1038/s41534-020-00291-0
Ghosh, S., & Liew, T. C. H. (2020). Quantum computing with exciton-polariton condensates. Npj Quantum Information, 6(1), 16. https://doi.org/10.1038/s41534-020-0244-x
Gill, S. S., Kumar, A., Singh, H., Singh, M., Kaur, K., Usman, M., & Buyya, R. (2022). Quantum computing: A taxonomy, systematic review and future directions. Software: Practice and Experience, 52(1), 66–114. https://doi.org/10.1002/spe.3039
Grimsmo, A. L., Combes, J., & Baragiola, B. Q. (2020). Quantum Computing with Rotation-Symmetric Bosonic Codes. Physical Review X, 10(1), 011058. https://doi.org/10.1103/PhysRevX.10.011058
Henriet, L., Beguin, L., Signoles, A., Lahaye, T., Browaeys, A., Reymond, G.-O., & Jurczak, C. (2020). Quantum computing with neutral atoms. Quantum, 4, 327. https://doi.org/10.22331/q-2020-09-21-327
Hoo Teo, K., Zhang, Y., Chowdhury, N., Rakheja, S., Ma, R., Xie, Q., Yagyu, E., Yamanaka, K., Li, K., & Palacios, T. (2021). Emerging GaN technologies for power, RF, digital, and quantum computing applications: Recent advances and prospects. Journal of Applied Physics, 130(16), 160902. https://doi.org/10.1063/5.0061555
Hu, Z., Xia, R., & Kais, S. (2020). A quantum algorithm for evolving open quantum dynamics on quantum computing devices. Scientific Reports, 10(1), 3301. https://doi.org/10.1038/s41598-020-60321-x
Jurcevic, P., Javadi-Abhari, A., Bishop, L. S., Lauer, I., Bogorin, D. F., Brink, M., Capelluto, L., Günlük, O., Itoko, T., Kanazawa, N., Kandala, A., Keefe, G. A., Krsulich, K., Landers, W., Lewandowski, E. P., McClure, D. T., Nannicini, G., Narasgond, A., Nayfeh, H. M., … Gambetta, J. M. (2021). Demonstration of quantum volume 64 on a superconducting quantum computing system. Quantum Science and Technology, 6(2), 025020. https://doi.org/10.1088/2058-9565/abe519
Killoran, N., Izaac, J., Quesada, N., Bergholm, V., Amy, M., & Weedbrook, C. (2019). Strawberry Fields: A Software Platform for Photonic Quantum Computing. Quantum, 3, 129. https://doi.org/10.22331/q-2019-03-11-129
Kim, Y., Eddins, A., Anand, S., Wei, K. X., Van Den Berg, E., Rosenblatt, S., Nayfeh, H., Wu, Y., Zaletel, M., Temme, K., & Kandala, A. (2023). Evidence for the utility of quantum computing before fault tolerance. Nature, 618(7965), 500–505. https://doi.org/10.1038/s41586-023-06096-3
Klco, N., & Savage, M. J. (2019). Digitization of scalar fields for quantum computing. Physical Review A, 99(5), 052335. https://doi.org/10.1103/PhysRevA.99.052335
Larsen, M. V., Guo, X., Breum, C. R., Neergaard-Nielsen, J. S., & Andersen, U. L. (2021). Deterministic multi-mode gates on a scalable photonic quantum computing platform. Nature Physics, 17(9), 1018–1023. https://doi.org/10.1038/s41567-021-01296-y
Litinski, D. (2019). A Game of Surface Codes: Large-Scale Quantum Computing with Lattice Surgery. Quantum, 3, 128. https://doi.org/10.22331/q-2019-03-05-128
Low, P. J., White, B. M., Cox, A. A., Day, M. L., & Senko, C. (2020). Practical trapped-ion protocols for universal qudit-based quantum computing. Physical Review Research, 2(3), 033128. https://doi.org/10.1103/PhysRevResearch.2.033128
Nakajima, K., Fujii, K., Negoro, M., Mitarai, K., & Kitagawa, M. (2019). Boosting Computational Power through Spatial Multiplexing in Quantum Reservoir Computing. Physical Review Applied, 11(3), 034021. https://doi.org/10.1103/PhysRevApplied.11.034021
Ollitrault, P. J., Kandala, A., Chen, C.-F., Barkoutsos, P. Kl., Mezzacapo, A., Pistoia, M., Sheldon, S., Woerner, S., Gambetta, J. M., & Tavernelli, I. (2020). Quantum equation of motion for computing molecular excitation energies on a noisy quantum processor. Physical Review Research, 2(4), 043140. https://doi.org/10.1103/PhysRevResearch.2.043140
Pogorelov, I., Feldker, T., Marciniak, Ch. D., Postler, L., Jacob, G., Krieglsteiner, O., Podlesnic, V., Meth, M., Negnevitsky, V., Stadler, M., Höfer, B., Wächter, C., Lakhmanskiy, K., Blatt, R., Schindler, P., & Monz, T. (2021). Compact Ion-Trap Quantum Computing Demonstrator. PRX Quantum, 2(2), 020343. https://doi.org/10.1103/PRXQuantum.2.020343
Quantum Technology and Application Consortium – QUTAC, Bayerstadler, A., Becquin, G., Binder, J., Botter, T., Ehm, H., Ehmer, T., Erdmann, M., Gaus, N., Harbach, P., Hess, M., Klepsch, J., Leib, M., Luber, S., Luckow, A., Mansky, M., Mauerer, W., Neukart, F., Niedermeier, C., … Winter, F. (2021). Industry quantum computing applications. EPJ Quantum Technology, 8(1), 25. https://doi.org/10.1140/epjqt/s40507-021-00114-x
Romero, J., Babbush, R., McClean, J. R., Hempel, C., Love, P. J., & Aspuru-Guzik, A. (2018). Strategies for quantum computing molecular energies using the unitary coupled cluster ansatz. Quantum Science and Technology, 4(1), 014008. https://doi.org/10.1088/2058-9565/aad3e4
Suba??, Y., Somma, R. D., & Orsucci, D. (2019). Quantum Algorithms for Systems of Linear Equations Inspired by Adiabatic Quantum Computing. Physical Review Letters, 122(6), 060504. https://doi.org/10.1103/PhysRevLett.122.060504
Takeda, S., & Furusawa, A. (2019). Toward large-scale fault-tolerant universal photonic quantum computing. APL Photonics, 4(6), 060902. https://doi.org/10.1063/1.5100160
Vandersypen, L. M. K., & Eriksson, M. A. (2019). Quantum computing with semiconductor spins. Physics Today, 72(8), 38–45. https://doi.org/10.1063/PT.3.4270
Von Burg, V., Low, G. H., Häner, T., Steiger, D. S., Reiher, M., Roetteler, M., & Troyer, M. (2021). Quantum computing enhanced computational catalysis. Physical Review Research, 3(3), 033055. https://doi.org/10.1103/PhysRevResearch.3.033055
Wu, Y., Kolkowitz, S., Puri, S., & Thompson, J. D. (2022). Erasure conversion for fault-tolerant quantum computing in alkaline earth Rydberg atom arrays. Nature Communications, 13(1), 4657. https://doi.org/10.1038/s41467-022-32094-6
Authors
Copyright (c) 2025 Purwo Agus Sucipto, Loso Judijanto, Nasser Qudah
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
