Developing a mobilephone app to demonstrate Shor's prime factorization

[Abstract] I have written several articles about Shor's prime factorization, one of the pinnacles of quantum algorithms. The mobilephone app I developed this time is an all-in-one app that includes both classical processing and quantum algorithms. However, I did not create the quantum algorithm part myself, but used the quantum circuit simulator Quirk. Quirk does not provide an API, so the necessary parameters for linking the classical and quantum parts are passed manually. The significance of this app is that it allows you to complete the execution of the entire Shor's algorithm on a single screen (although it is limited to small integers). In practice, this method of manually passing the necessary parameters (not a fully automated process) while checking the results of the quantum circuit simulation is useful for deepening your understanding. I would like to demonstrate this in detail below.

🔴Details of Shor's Factoring Algorithm

The theory and calculation details of Shor's algorithm are written in this article. Also, the most important part, finding order, is an application of quantum phase estimation, and this is also explained in detail in this article. Therefore, this article only describes the overview and usage of the app developed this time.

🔴All-in-one app for Shor's algorithm

First, the overall image of the developed app is shown in Fig.1. This screen shows an example of decomposing 221, given as the product of two prime numbers 13 and 17, into the original two prime numbers. It consists of a classical calculation part and a quantum calculation part.

This app was created with MIT App Inventor. The classical part verifies the order (period) candidates obtained from the quantum part, and if they are valid, prime factorization is performed immediately. If they are not, a parameter (called A here) is changed appropriately and the process is retried. Meanwhile, the quantum part calls the quantum circuit simulator Quirk to obtain order candidates. The Quirk screen is crowded, but you can use your finger to zoom in on the parts you need.

🔴How to use the app

Please see Fig.2 below. Give two prime numbers p and q, and press the blue button "setup R" to obtain the desired integer R. Next, turn on the switch with red characters "Quirk Q Sim". Then, manually give this integer R as an input to the displayed Quirk simulator. Give another (randomly selected) integer A to Quirk in the same way. This Quirk quantum circuit is designed to find candidates for the order (i.e., period) of f(x) = A^x mod R. This simulation consists of a total of 14 qubits. (8 qubits for problem setting, 6 qubits for solution)

Next, as shown in Fig. 3, the results of the Quirk simulation (measurement results) show that out of 256 (=2⁸) bases, only four appeared with a probability of 25% each. If you enlarge the screen, you can see that one of the bases, |010000⟩, is a candidate for giving the order. Set this as the binary bit string "010000" in the window at the top of the screen.

Next, press the round "Shor" button as shown in Fig. 4. This binary bit string is then converted into a decimal, and then converted into a rational number (fraction s/r) using the continued fraction approximation method. The denominator r becomes a candidate for the order. In this example (N=221, A=18), s=1 and r=4. The validity of the order can be confirmed, and as mentioned earlier, we get GCD(A^r/2+1, R)=13 and GCD(A^r/2-1, R)=17, completing the prime factorization!

Although it is not a fully automated process, it is impressive that the entire Shor prime factorization can be demonstrated on a single screen in this app!

🔴Shor's Algorithm is Probabilistic

So far we have seen the whole picture of Shor's algorithm. It is a probabilistic algorithm. In fact, another result executed under the above conditions did not give a valid order, and the prime factorization ultimately failed. Such an example is shown in Fig. 5.

However, when executed using a fully quantum computer, the correct answer can be obtained with a sufficiently small number of attempts! The details are described in Nielsen & Chuang [1].

[Additional Notes]

MIT App Inventor was once again very useful. It was great to be able to call the external quantum circuit simulator Quirk easily using the WebViewer. On the other hand, if all the processing related to "f(x) = A^x mod R" was created in App Inventor, the number of blocks would increase, making it difficult to manage. Furthermore, it was necessary to use the Modular Exponentiation Method to prevent the calculation from overflowing. Therefore, this time, most of these were created in JavaScript and called from App Inventor. This kind of integration with JavaScript is also useful.

In creating this app, I referred to the chapter II-5 of Nielsen & Chuang [1], the chapter 7 of Wong [2] and the chapter 9 of Burd[3]. I would like to express my gratitude.

Reference

[1] Michael A. Nielsen and Isaac L. Chuang: Quantum Computation and Quantum Information - 10th Anniversary Edition, Cambridge University Press, 2010 (First published 2000).

[2] Thomas G. Wong: Introduction to Classical and Quantum Computing, Rooted Grove, 2022.

[3] Barry Burd: Quantum Computing Algorithms -Discover how a little math goes a long way, Packt Publishing, 2023.

https://users.drew.edu/bburd/quantum/