Comparison of Performances for Quantum and Conventional Algorithms: Shor’s algorithm and Boson Sampling
DOI:
https://doi.org/10.54097/hset.v38i.5873Keywords:
quantum computing; quantum algorithm; Shor’s algorithm; Boson sample.Abstract
Quantum computing has been extensive popularity discussed recently. The foundation of quantum study is the investigation of how quantum computing shows its superiority compared with conventional algorithms. On this basis, this paper focuses on the comparison of the performances of quantum and conventional algorithms about the same relevant area. Two classic problems, factorization of large integer and boson sampling, are chosen to show the specific difference of related quantum and conventional algorithms towards the same problem. This paper specifically compares the performance of Shor's algorithm and other advanced traditional integer factorization algorithms for prime factorization problems and compares the processing capabilities of traditional algorithms and Gaussian Boson sampling for sampling problems. According to the analysis, for the same research problem, quantum algorithms show strong advantages over traditional algorithms in many performances, e.g., time efficiency, algorithm adaptability. It leads to a deeper understanding of quantum superiority and a further explanation of the significance of the development of quantum computing.
Downloads
References
De Oliveira A N, Walborn S P, Monken C H. Implementing the Deutsch algorithm with polarization and transverse spatial modes. Journal of Optics B: Quantum and Semiclassical Optics, 2005, 7(9): 288.
Qiu D, Zheng S. Revisiting Deutsch-Jozsa Algorithm. Information and Computation, 2020, 275: 104605.
Amellal H, Meslouhi A, El Allati A. Effectiveness of quantum algorithms on classical computing complexities. Proceedings of the 3rd International Conference on Smart City Applications. 2018: 1-3.
Lipton R J, Regan K W. Quantum Algorithms via Linear Algebra: A Primer. MIT Press, 2014.
Harrow A W, Hassidim A, Lloyd S. Quantum algorithm for linear systems of equations. Physical review letters, 2009, 103(15): 150502.
Duan B, Yuan J, Yu C H, et al. A survey on HHL algorithm: From theory to application in quantum machine learning. Physics Letters A, 2020, 384(24): 126595.
Fedorov D A, Peng B, Govind N, et al. VQE method: A short survey and recent developments. Materials Theory, 2022, 6(1): 1-21.
Streif M, Leib M. Comparison of QAOA with quantum and simulated annealing. arXiv preprint arXiv:1901.01903, 2019.
Childs A M. Universal computation by quantum walk. Physical review letters, 2009, 102(18): 180501.
Koundinya A K. Performance Analysis of Parallel Pollard's Rho Algorithm. arXiv preprint arXiv:1305.4365, 2013.
Sarnaik S, Bhakkad R, Desai C. Comparative study on Integer Factorization algorithm-Pollard's RHO and Pollard's P-1. 2015 2nd International Conference on Computing for Sustainable Global Development (INDIACom). IEEE, 2015: 677-679.
Chinniah P, Muthusamy N, Ramalingam A. A special purpose integer factorization algorithm. Proceedings of the Second International Conference on Computational Science, Engineering and Information Technology. 2012: 175-181.
Hamdi S M, Zuhori S T, Mahmud F, et al. A Compare between Shor's quantum factoring algorithm and General Number Field Sieve. 2014 International Conference on Electrical Engineering and Information & Communication Technology. IEEE, 2014: 1-6.
Van Meter R, Itoh K M, Ladd T D. Architecture-dependent execution time of Shor's algorithm. Controllable Quantum States: Mesoscopic Superconductivity and Spintronics (MS+ S2006). 2008: 183-188.
Quantum computing. IBM Retrieved from: https://quantum-computing.ibm.com/composer/docs/iqx/guide/shors-algorithm
Gard B T, Motes K R, Olson J P, et al. An introduction to boson-sampling. From atomic to mesoscale: The role of quantum coherence in systems of various complexities. 2015: 167-192.
Brod D J, Galvão E F, Crespi A, et al. Photonic implementation of boson sampling: a review. Advanced Photonics, 2019, 1(3): 034001.
Martino L, Elvira V. Metropolis sampling. arXiv preprint arXiv:1704.04629, 2017.
Clifford P, Clifford R. Faster classical boson sampling. arXiv preprint arXiv:2005.04214, 2020.
Ying L, Ze-Yao H, Chao-Jian L, et al. Review on quantum advantages of sampling problems. ACTA PHYSICA SINICA, 2021, 70(21).
Deshpande A, Mehta A, Vincent T, et al. Quantum computational advantage via high-dimensional Gaussian boson sampling. Science advances, 2022, 8(1): eabi7894.
Hamilton C S, Kruse R, Sansoni L, et al. Gaussian boson sampling. Physical review letters, 2017, 119(17): 170501.
Preskill J. Quantum computing 40 years later. arXiv preprint arXiv:2106.10522, 2021.Fangfang. Research on power load forecasting based on Improved BP neural network. Harbin Institute of Technology, 2011.
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
