Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Highlights in Science Engineering and Technology

Comparison of Performances for Quantum and Conventional Algorithms: Shor’s algorithm and Boson Sampling

Shuang-cheng Jia

Published Mar 16, 2023• 3 citations
Publisher

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.

DOI
10.54097/hset.v38i.5873

Related papers

Analysis and Implementation of Quantum Computing Algorithms

Caroline Fedele, Asai Asaithambi

In this research, we investigate the relationships between classical and quantum computing, and the superior time complexity and memory allocation proposed theoretically for quantum algorithms. This is accomplished by building quantum circuits to represent algorithms and test in a quantum computer simulation. Classical circuit components have been continually reducing in size to the point where they are now being impacted by quantum properties, resulting in the need to investigate quantum computing. The inherent parallelism of quantum computing also allows us to solve problems for which classical computers are inept. The class of intractable problems in computing where the solution can only be found through exhaustive search is where we observe quantum computing supremacy. It is important to explore and advance our knowledge of quantum computing so we are prepared for when it becomes a reality, and so that in the future our understanding of encryption is deepened and new quantum-proof methods can be developed. Although Google and IBM have developed physical quantum computers, there is still a large deficit in knowledge of how they may be utilized. There is also a gap between proposed superior quantum solutions and problems demonstrably solved using quantum algorithms. Among the problems classically considered intractable is one extremely relevant to cybersecurity, known as Shor’s algorithm, that being an efficient algorithm for integer factorization, breaks down our well-established methods of cryptography. The aim of this research is to show the differences and advantages of quantum computing, and to specifically demonstrate how we can use Shor’s algorithm in a quantum system.

•Jan 1, 2020•0 citations

Quantum Shor's Algorithm vs. Classical General Number Field Sieve (GNFS) Approach for Large Integer Factorization

S. S. Kavitha, Narasimha Kaulgud, B. Sharmila +3 more

Quantum integer factorization is a groundbreaking field that explores the use of quantum algorithms, notably Shor's algorithm, to efficiently factorize large integers into their prime components. Its potential implications on modern encryption techniques, such as the Rivest-Shamir-Adleman (RSA) algorithm, are of considerable interest. This paper's central aim is to contrast the computational time and implementation of the Integer Factorization Problem (IFP) between classical and quantum computers. The inner workings of Quantum Shor's algorithm are broken down step by step, and the estimated processing time is contrasted with the classical General Number Field Sieve (GNFS) approach. Given the exponential speedup provided by quantum computing, this comparison helps assess Shor's algorithm's possible advantage over GNFS in factoring large numbers. Direct comparisons with GNFS are currently difficult due to Shor's algorithm's reliance on large-scale quantum computer development for practical execution speeds. This paper focuses on solving integer factorization up to$2^{n}$bits.

International Conference on Next Generation Communication & Information Processing (INCIP)•Jan 23, 2025•1 citation

Quantum Computing Algorithms for Integer Factorization: A Comparative Analysis

Nadia Ahmed

The field of quantum computing has witnessed remarkable advancements in recent years, particularly in its potential applications to solve computationally hard problems such as integer factorization. a comparative analysis of quantum computing algorithms for integer factorization, focusing on their theoretical foundations, computational complexity, and practical implications. We review prominent algorithms such as Shor's algorithm, which leverages quantum parallelism and period finding to efficiently factor large composite integers, and compare them with classical factorization algorithms like the General Number Field Sieve (GNFS). Through a comprehensive examination of algorithmic strategies, runtime complexities, and quantum circuit implementations, we assess the relative strengths and limitations of quantum computing approaches for integer factorization. Furthermore, we discuss potential challenges and future research directions in harnessing the power of quantum computing to address cryptographic security and algorithmic complexity in the era of post-quantum cryptography.

Modern Dynamics: Mathematical Progressions.•May 25, 2024•8 citations

Implementation And Analysis of Regev’s Quantum Factorization Algorithm

Przemysław Pawlitko, Natalia Moćko, Marcin Niemiec +1 more

Abstract Quantum computing represents a significant advancement in computational capabilities. Of particular concern is its impact on asymmetric cryptography through, notably, Shor’s algorithm and the more recently developed Regev’s algorithm for factoring composite numbers. We present our implementation of the latter with the aim of exposing experimental phenomena. Our analysis encompasses both quantum simulation results and classical component examples, with particular emphasis on comparative cases between Regev’s and Shor’s algorithms. Our experimental results reveal that Regev’s algorithm outperforms Shor’s algorithm for certain composite numbers in practice. However, we observed significant performance variations across different input values. Despite Regev’s algorithm’s theoretical asymptotic advantage in effectiveness, our implementation exhibited longer execution times than Shor’s algorithm for small-integer factorization in both quantum and classical components. These findings offer insights into the practical challenges and performance characteristics of implementing Regev’s algorithm in realistic quantum computing scenarios.

arXiv:2502.09772•Quantum Information and Computation•Mar 1, 2026•0 citations

A Comparative Analysis of Shor’s Algorithm and Factorization Methods

Alaa Khudhair Abbas, Saba Hussein Rashid, Saba Alaa Abdulwahhab +1 more

Large integer factorization has long been a significant problem in computer science and mathematics. With the advent of Shor's algorithm, a polynomial-time factoring technique created for quantum computers, an effective solution to this problem became possible. Using quantum mechanics concepts. Qantum computing appears to be a novel approach to solving these complex problems. Classical computers are currently using the General Number Field Sieve (GNFS), Trial Division, the Elliptic Curve Method (EC),Fermat's Factorization, and the Quadratic Sieve(QS) are some of the best classical factoring techniques. However, this study examines these conventional approaches to determine their implications for cryptographic security, analyzing their weaknesses, usefulness, strengths, and difficulties. This paper alsodiscusses how Shor's algorithm affects cybersecurity because of its exponential speed advantage over traditional techniques. This paper also uses Shor’s algorithm get Q*P in using quantum facilities to break the algorithm like RSA algorithm

Journal of Al-Nahrain University-Science•Jun 15, 2026•0 citations

A Compare between Shor's quantum factoring algorithm and General Number Field Sieve

Shah Muhammad Hamdi, Syed Tauhid Zuhori, Firoz Mahmud +1 more

Factoring large integers has been one of the most difficult problems in the history of mathematics and computer science. There was no efficient solution of this problem until Shor's algorithm emerged. Shor's algorithm is a polynomial time factoring algorithm which works on a quantum computer. Quantum computing is a new paradigm of computing that uses quantum mechanical phenomena in solving problems. The computers we are using right now are called classical computer. The most efficient classical factoring algorithm is General Number Field Sieve (GNFS). GNFS also cannot factor integers in polynomial time. In this paper, we compared these two algorithms in factoring integer in a standalone system.

International Conference on Electrical Engineering and Information Communication Technology•Apr 1, 2014•14 citations
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.
In this research, we investigate the relationships between classical and quantum computing, and the superior time complexity and memory allocation proposed theoretically for quantum algorithms. This is accomplished by building quantum circuits to represent algorithms and test in a quantum computer simulation. Classical circuit components have been continually reducing in size to the point where they are now being impacted by quantum properties, resulting in the need to investigate quantum computing. The inherent parallelism of quantum computing also allows us to solve problems for which classical computers are inept. The class of intractable problems in computing where the solution can only be found through exhaustive search is where we observe quantum computing supremacy. It is important to explore and advance our knowledge of quantum computing so we are prepared for when it becomes a reality, and so that in the future our understanding of encryption is deepened and new quantum-proof methods can be developed. Although Google and IBM have developed physical quantum computers, there is still a large deficit in knowledge of how they may be utilized. There is also a gap between proposed superior quantum solutions and problems demonstrably solved using quantum algorithms. Among the problems classically considered intractable is one extremely relevant to cybersecurity, known as Shor’s algorithm, that being an efficient algorithm for integer factorization, breaks down our well-established methods of cryptography. The aim of this research is to show the differences and advantages of quantum computing, and to specifically demonstrate how we can use Shor’s algorithm in a quantum system.
Quantum integer factorization is a groundbreaking field that explores the use of quantum algorithms, notably Shor's algorithm, to efficiently factorize large integers into their prime components. Its potential implications on modern encryption techniques, such as the Rivest-Shamir-Adleman (RSA) algorithm, are of considerable interest. This paper's central aim is to contrast the computational time and implementation of the Integer Factorization Problem (IFP) between classical and quantum computers. The inner workings of Quantum Shor's algorithm are broken down step by step, and the estimated processing time is contrasted with the classical General Number Field Sieve (GNFS) approach. Given the exponential speedup provided by quantum computing, this comparison helps assess Shor's algorithm's possible advantage over GNFS in factoring large numbers. Direct comparisons with GNFS are currently difficult due to Shor's algorithm's reliance on large-scale quantum computer development for practical execution speeds. This paper focuses on solving integer factorization up to2n2^{n}2nbits.
The field of quantum computing has witnessed remarkable advancements in recent years, particularly in its potential applications to solve computationally hard problems such as integer factorization. a comparative analysis of quantum computing algorithms for integer factorization, focusing on their theoretical foundations, computational complexity, and practical implications. We review prominent algorithms such as Shor's algorithm, which leverages quantum parallelism and period finding to efficiently factor large composite integers, and compare them with classical factorization algorithms like the General Number Field Sieve (GNFS). Through a comprehensive examination of algorithmic strategies, runtime complexities, and quantum circuit implementations, we assess the relative strengths and limitations of quantum computing approaches for integer factorization. Furthermore, we discuss potential challenges and future research directions in harnessing the power of quantum computing to address cryptographic security and algorithmic complexity in the era of post-quantum cryptography.
Abstract Quantum computing represents a significant advancement in computational capabilities. Of particular concern is its impact on asymmetric cryptography through, notably, Shor’s algorithm and the more recently developed Regev’s algorithm for factoring composite numbers. We present our implementation of the latter with the aim of exposing experimental phenomena. Our analysis encompasses both quantum simulation results and classical component examples, with particular emphasis on comparative cases between Regev’s and Shor’s algorithms. Our experimental results reveal that Regev’s algorithm outperforms Shor’s algorithm for certain composite numbers in practice. However, we observed significant performance variations across different input values. Despite Regev’s algorithm’s theoretical asymptotic advantage in effectiveness, our implementation exhibited longer execution times than Shor’s algorithm for small-integer factorization in both quantum and classical components. These findings offer insights into the practical challenges and performance characteristics of implementing Regev’s algorithm in realistic quantum computing scenarios.
Large integer factorization has long been a significant problem in computer science and mathematics. With the advent of Shor's algorithm, a polynomial-time factoring technique created for quantum computers, an effective solution to this problem became possible. Using quantum mechanics concepts. Qantum computing appears to be a novel approach to solving these complex problems. Classical computers are currently using the General Number Field Sieve (GNFS), Trial Division, the Elliptic Curve Method (EC),Fermat's Factorization, and the Quadratic Sieve(QS) are some of the best classical factoring techniques. However, this study examines these conventional approaches to determine their implications for cryptographic security, analyzing their weaknesses, usefulness, strengths, and difficulties. This paper alsodiscusses how Shor's algorithm affects cybersecurity because of its exponential speed advantage over traditional techniques. This paper also uses Shor’s algorithm get Q*P in using quantum facilities to break the algorithm like RSA algorithm
Factoring large integers has been one of the most difficult problems in the history of mathematics and computer science. There was no efficient solution of this problem until Shor's algorithm emerged. Shor's algorithm is a polynomial time factoring algorithm which works on a quantum computer. Quantum computing is a new paradigm of computing that uses quantum mechanical phenomena in solving problems. The computers we are using right now are called classical computer. The most efficient classical factoring algorithm is General Number Field Sieve (GNFS). GNFS also cannot factor integers in polynomial time. In this paper, we compared these two algorithms in factoring integer in a standalone system.