Keywords

1 Introduction

Quantum Computing (QC) is a revolutionary technology that exploits the rules of Quantum Mechanics to speedily solve specific problems and process information in ways that are not possible with classic Conventional Computing (CC). In CC, computer scientists are interested in solving optimization and decision problems within polynomial and/or non-polynomial time limit. This is very challenging for NP-complete problems for the problem size can grow exponentially. In contrast to CC for having one state to be on or off at a time, QC can deal with multiple states at the same time, contributing to its high-speed computation performance. Hence, computer science and software engineering communities have endeavored to leverage the discriminative power of QC to find solutions for difficult optimization and decision problems by possibly maintaining a polynomial time even after a significant growth in problem size. One of such problems is to factor numbers into primes and determine the answer in a reasonable time, especially when the number of digits grows exponentially [1]. Factoring integers is a complex problem that has been widely studied in number theory and cryptography. However, the conventional computers have struggled to factor large integers within a polynomial time until the introduction of Shor’s algorithm [2]. The algorithm is a QC approach developed by American mathematician Peter Shor in 1994 to solve this hard problem. Shor’s algorithm is also recognized as a strong tool in the cryptographic and code-cracking domain to crack cryptographic algorithms that are frequently used for online communication and trade. This is because many encryption algorithms, including the RSA, are developed based on the challenge of factoring huge integers. The Shor’s method can factor large integers significantly faster and more quickly than traditional algorithms, thus defeating the RSA encryption and many other encryption schemes [3].

QC intrigues the community to perform complex tasks by exploiting the principles of quantum mechanics that can account for multiple states simultaneously to gain great performance. Such ability is deemed impossible or impractical to CC with only one state at a time. Today, computer scientists are interested in solving complex problems as quickly as possible using QC even with an exponential growth in the problem size. In [4], Devitt et al. have investigated the practical implementation of Shor’s algorithm. In this study, an empirical study is conducted to investigate the impact, ability, and limitation of QC in terms of solving complex problems in polynomial time. A comparative analysis is performed between QC and CC in terms of solving complex problems in polynomial time. Moreover, the experiment explores the effects and benefits of QC in solving less complicated polynomial problems.

2 Related Works

This section gives a summary of the related work, implications, and limitations. In [5], Ugwuishiwu et. al. Investigated the mechanisms of quantum cryptography and compared quantum and classical encryption schemes. In their study, the authors gave a brief overview of quantum computation and explained Shor’s algorithm. Moreover, they demonstrated the power of QC in terms of how encryption could be accomplished by utilizing the properties of quantum particles and provided examples of the complexities of Shor’s algorithm [5].

Quantum computers and Shor’s algorithm can pose a threat to today’s cryptographic systems. With the prevalence of data breaches, researchers are increasingly interested in finding ways to safeguard data security using quantum cryptography [4].

In addition to the benefits of QC, Aaronson [6] also identified certain limitations. The investigation showed that quantum computers could be extremely efficient at some specific tasks, where the computation abilities outperformed current computers moderately for most problems. This realization indicates a potential to lead to the discovery of new fundamental physical principles. The concept of a “magic computer” capable of quickly solving NP- complete problems, could change the world, as it could be used to find patterns in large datasets such as stock market data or brain activity recordings [6]. Nevertheless, the author also claimed that quantum computers are not an all-purpose device. They are best suited for specific types of computations, such as those that involve large amounts of data and require high-speed processing. These are known as quantum advantage tasks, e.g., quantum simulation and quantum cryptography [5, 6].

In [7], Nene and Upadhyay scrutinized a well-known and widely used encryption-based RSA algorithm and investigated the difficulty of factoring large integers within polynomial time. The authors described the capability of Shor’s quantum algorithm in terms of breaking RSA encryption in a reasonable time. The authors further presented a systematic approach to factoring integers using Shor’s quantum algorithm on a classical computer through simulation. The results were verified theoretically and concluded a need for further empirical investigations [8,9,10].

Thomas et al. [12] tried to leverage and scale Shor’s algorithm in their study on Ion- trap quantum computers (a particular kind of quantum computer). The authors applied the algorithm with the use and manipulation of seven qubits and four “cache qubits”. They factored the number 15 through extended arithmetic operations and modular multipliers. With a degree of confidence of more than 99%, the algorithm was able to provide the proper factors. This is a crucial milestone towards the creation of a scalable quantum computer and the actual use of quantum algorithms [13, 14].

3 Proposed Method

This study empirically assesses the efficacy of QC in solving complex problems and reason the tradeoff between execution time and problem size. The layout of the proposed method is shown in Fig. 1, and the constituent components are described as follows.

Fig. 1.
figure 1

Workflow of the proposed method

Full size image

3.1 Input

This component represents the input for a chosen algorithm. Take the Shor’s algorithm for example. The input is an integer value, whose prime factor is expected to be found.

3.2 QC-Circuit

The QC-Circuit in the proposed method is functional in two steps as follows.

3.2.1 Quantum Circuit Design

The layout of the QC-circuit design is shown in Fig. 2. The exponent register is first placed into an equal superposition of states using Hadamard gates. This is a vital step in making sure the adopted quantum algorithm can fully benefit from quantum physics’ features. The final qubit in the target register is then subjected to the application of a phase kickback gate. This gate is used to help make sure the algorithm can run smoothly and produce the most accurate result possible.

Fig. 2.
figure 2

Quantum Circuit design for input value of 15 in Shor’s Algorithm

Full size image

Afterwards, a modular exponential gate is used to perform the series of controlled unitary units required for phase estimation. This gate, which is an essential part of the process, enables us to precisely determine the phase of the quantum state that is dealt with. Once finished, the next step will apply the inverse quantum Fourier transform to the exponent register. This phase is crucial because it enables us to get pertinent data about the qubits’ current state from the register and ensures that the final output is as precise as feasible.

To obtain the outcome, the exponent register will be measured and the data from the register’s qubits in this last phase of the procedure can be retrieved. The output of the algorithm is the result of this measurement, and it may be utilized to carry out different computing operations.

3.2.2 Quantum Circuit Design

For simulation of the proposed QC-design, the capabilities of Google’s Cirq was leveraged. Using Google’s Cirq, the Quantum Virtual Machine enables us to operate and test quantum circuits on simulated hardware that replicates the limitations and noise behavior of real quantum devices. Before placing our quantum algorithms to use on the actual quantum hardware, the simulator of the virtual machine provides an economical way to test and debug the algorithms.

3.3 Comparison and Evaluation

Google’s open-source quantum computing framework, Cirq, provides an accessible platform for researchers and developers to experiment with Shor’s algorithm and test it with different integer inputs. With the help of Cirq, we utilized the already implemented Shor’s algorithm to run on a quantum simulator by Google, to test the performance of the algorithm in factoring integers with different numbers of digits.

For comparison, the general number field sieve (GNFS) algorithm [15] in number theory was also applied to integers with different numbers of digits because this traditional computing approach can factor integers within a much more reasonable amount of time than the brute-force method documented on Cirq with demo code. However, it’s still not as efficient as the quantum algorithm. Our evaluation is based on the size of the input integer and the time required to locate the prime factors. These two are considered as the major criteria for assessing the QC performance in solving the integer factoring problems in polynomial time. The size of the input integer will be determined by the number of digits, which represents how lengthy the number is [9]. The time it takes to locate the prime factors will be measured in seconds and used to reflect the computational efficiency of the algorithm.

The success of comparing the performance of QC with that of the traditional computing approach through the input size and time as two key metrics will enable us to study the influence of further issues on QC performance and identify other potential barriers to its wider adoption involving more problems. The statistics can then provide straightforward and objective results to assess QC’s performance.

4 Experimental Procedure

The following steps present our experimental procedure of the proposed study to run the Shor’s algorithm.

Step-1: Initializing an input and output qubit register in the quantum computer is the first step, with n and n0 qubits, respectively, assigned to the state |ψ0⟩ = |0…0⟩n|0…0⟩n0.

Step-2: The next step is to prepare a superposition by applying q Hadamard gates, where q = 2n.

Step-3: The output register of state |ψ2⟩ is measured. The result of that measurement is then discarded and put into the input register of state |ψ3⟩.

Step-4: The result y of the input register of state |ψ4⟩ is measured. This value helps determine the continued fraction representation of y/q. Finally, each convergent result is tested in order and reduced to their lowest terms.

5 Result and Discussion

The result of the proposed method is displayed in Table 1 and Fig. 3. In the table, it shows the measured values of QC and CC in terms of keeping a tradeoff between problem size and polynomial time. Figure 3 on the other hand gives a visual representation of the same results for easy comparison between QC and CC using a bar chart.

The classical computer can take an exponential amount of time to calculate the factors as the number of digits in the integers becomes larger. In contrast, the quantum computer spends about the same amount of time to factor the integers, regardless of the number of digits. The time gap between the quantum and conventional computers becomes more and more significant as the problem size increases. For example, according to the results of Table 1 for the case of 231273, the quantum computer takes less than one second, but the conventional computer takes more than five seconds.

Table 1. Time analysis for factoring using Quantum and Classical computing approaches
Full size table

Finding 1:

figure a

The results of Fig. 3 conclude our first finding that quantum computer can be exponentially quicker than the classical computer in solving the proposed algorithm (i.e., Shor’s algorithm), especially when the problem size increases. However, the advantage of QC over CC diminishes when the problem size is rather small, adhered to [11].

Fig. 3.
figure 3

Comparative analysis of QC and CC for Shor’s algorithm

Full size image

Finding 2:

figure b

It is crucial to remember that the performance of a quantum computer is dependent on a variety of parameters, including the number of qubits. Factoring big numbers is simply one of the many polynomial problems that quantum computers can perform faster than classical computers. One of the significances is that quantum computers can take a rather constant time, as shown in Fig. 3, to find solutions for the increasing problem sizes. This on the other hand indicates our second finding that QC can process a large input size of data remarkably faster than CC as well. Nonetheless, the two findings do not imply that quantum computers are superior to classical computers in all activities.

6 Implications to Research Community

The aim of the proposed study is to empirically investigate the implications of QC to solve complex problems in terms of polynomial time and its advantage over CC. Through the experimental results of the proposed study, we have realized the following consequences for the research community.

  • Quantum computing has the ability to dramatically accelerate the process of factoring big numbers in polynomial time.

  • Cryptography and code cracking could be possibly done in polynomial time.

  • Rapid resolution for polynomial problems can also have significant effects in other disciplines, including machine learning, optimization, and simulation.

  • Researchers might employ quantum computers to more accurately and efficiently model physical systems and tackle challenging optimization issues.

  • To secure sensitive information, the improvement to many existing security methods could rely on QC.

  • The speed with which complex or hard problems may be solved also suggests that other issues, like as the Traveling Salesman Problem or other kinds of search tasks, which are not known to be time-consuming on classical computers, can be solved using quantum computers.

In short, the speed of quantum computers in rapid problem-solving has the potential to revolutionize numerous industries and offer new opportunities for research and technological development.

7 Conclusion

The experimental results have indicated the efficacy of Quantum Computing (QC) over Classical Computing (CC) to solve complex problems such as optimization and decision problems in terms of polynomial time. This proposed study was conducted to investigate the QC claim regarding its speed of solving complex problems and efficacy over CC. The well-known and widely used Shor’s algorithm was exploited, and the capabilities of Google Cirq were leveraged to design and simulate the QC circuit for the algorithm. This empirical study successfully measures the performance of QC and CC and performs a comparative analysis. The conclusions of this work are; 1) With a small problem size, the performance of QC shows no superiority to CC for Shor’s algorithm, 2) QC starts to outperform CC when the problem size or input size grows large, 3) Cryptography and code cracking application could rely on QC for its ability to solve complex problems more quickly, and 4) Research community can rely on QC to solve NP-complete problems in a much greater performance, such as Knapsack, Hamiltonian path and Travelling salesman problems.