Implementation of Shor's Algorithm in a Digital Quantum Coprocessor Valeriy Hlukhov 1 1 Lviv Polytechnic National University, 12 Bandera str., Lviv, 29013, Ukraine Abstract The advantages of digital quantum coprocessors include a larger quantum volume, normal operating conditions, the presence of memory, the presence of a tested and reliable element base on which they can be implemented, and the availability of technology for using this element base. The element base refers to field programmable gate arrays (FPGAs). The paper presents the principles of building digital quantum gates, digital qubits and both homogeneous and heterogeneous digital quantum coprocessors. The capabilities of real quantum computers are usually illustrated by performing factorization of the number 15 using Shor's algorithm. This paper describes the implementation of quantum Shor's algorithm for factorizing the number 15 in a digital quantum coprocessor, which is implemented in FPGA. The difference between a real quantum coprocessor and a digital one is shown. A technique for determining the characteristics of a digital quantum coprocessor is described. Its probabilistic characteristics are also given. Keywords Digital qubit, digital quantum coprocessor, heterogeneous coprocessor, homogeneous coprocessor, Shor's algorithm, FPGA shown. The hardware base for digital quantum 1. Introduction1 coprocessors is FPGA. Unlike real quantum coprocessors, digital ones operate at normal temperatures (like classical computers) and have A quantum computer is a heterogeneous a larger quantum volume. This makes the device [1] that consists of a classical control development of such coprocessors actual and computer and its quantum accelerator [2] - a important. quantum coprocessor. Real quantum Quantum computers possible field use is large coprocessors are analog and probabilistic numbers factorization [5], [6]. This operation is devices. They consist of qubits, quantum gates used to hack information security systems that provide a change in their states. A classical use public key algorithms, such as RSA [7]. computer controls the operation of a quantum Shor's algorithm [8] is used for this. The main coprocessor, checks the correctness of the results elements of the quantum coprocessor that of its work, and in case of an incorrect result, it implements Shor's algorithm are Hadamard restarts the coprocessor to work. elements, quantum Fourier transform, modular The possibility of creating logical (digital) exponentiation [9], and qubit state meters. In real probabilistic devices that can work according to quantum coprocessors, these elements (except the same formulas as real quantum coprocessors for meters) consist of qubits; changes in their and can implement quantum algorithms is shown states are provided by quantum gates. in previous works [3], [4]. The possibility of In previous works, the implementation of creating digital quantum gates, digital qubits and, digital Hadamard elements and digital quantum based on them, digital quantum coprocessors is Fourier transform on FPGAs was shown [3], [4]. In one FPGA, it is possible to create a quantum ISIT 2021: II International Scientific and Practical Conference Fourier transform from thousands of digital «Intellectual Systems and Information Technologies», September qubits. The internal state of a digital qubit can be 13–19, 2021, Odesa, Ukraine EMAIL: Glukhov@polynet.lviv.ua (A. 1) represented by binary code θ in the range from ORCID: 0000-0002-0542-7447 (A. 1) 0.00...0 to 1.00...0. Also, options for encoding ©️ 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). the states of digital qubits with binary codes of CEUR Workshop Proceedings (CEUR-WS.org) various lengths - from 3 to 32 bits were state QI of the neighboring qubit (or states of considered [3], [4]. Simulation of individual quantum gates is qubits). The new DataO status code is compared used to simulate quantum algorithms. To in a comparator with the random variable Asin_f simulate the reversibility of a qubit, models of to obtain the measured state of the qubit QO ' . reversible logic architecture [10] and gates [11] The output of the gate is the qubit state code have been developed. In this work, more DataOut and the measured state QO of the complex logic circuits are simulated to ensure reversibility of quantum circuits. qubit, which are taken from the output of the pipeline register. 2. Purpose of work DataIn DateO DateOut QI QO ' QO ALU B RG The aim of the work is to show the possibility Instruction Comparator of performing quantum algorithms (using the Asin_f A example of factoring the number 15 by Shor's Figure 1: A digital quantum gate QGate [1] factorization algorithm) in a digital quantum coprocessor implemented on the FPGA. For this, the possibility of implementing modular exponentiation on the FPGA and the possibility of the effect of the results of this operation on the states of digital qubits is shown, which allows us to determine the period of y = axmodM function (determining the period of a function is the main task of a quantum coprocessor in the implementation of Shor's algorithm). Figure 2: Bloch sphere for qubit complex 3. Qubit amplitudes (left) and a unit circle for real ones (right) Qubit quantum state  can be represented In a heterogeneous digital quantum (Figure 2) as a simple displacement of end point coprocessor, a random variable at the input of of unit radius [12]. The probability pj of each digital quantum gate is generated by a obtaining state j as a result of quantum state separate pseudo-random code generator (PRNG) and a Read-Only-Memory (ROM) based  measurement is equal to p j  2j . In this functional converter. The converter changes the N 1 random variable A according to the formula case, the sum of all probabilities P    1 . j 0 2 i A sin_ f  D  arcsin A (Figure 3). In unit circle (Figure 2) which is used in [4] p0  cos2  and p1  sin 2  respectively. QGate QI QO QI QO DataIn DataOut DataIn DataOut 4. Digital gates, qubits and quantum Instruction Instruction coprocessors 2n+1 Random Number ROM Asin_f A D Asin_f PRNG D  arcsin A A digital quantum gate that is used to change the state of a digital qubit can be represented as a Figure 3: A digital quantum cell DQCell for logic circuit Figure 1. heterogonous digital quantum coprocessor [3] The digital quantum gate includes an ALU, a comparator, and a pipelined register. Digital qubit circuit for a heterogeneous ALU transforms the code of the previous state coprocessor Figure 4 will represent a series DataIn of the qubit under the influence of the connection of several digital quantum cells Instruction with the possible use of the measured Figure 3. QO1 QOj 5. Shor’s algorithm QO1 DQCell QO1 DQCell StateOut DataIn Data1 Dataj-1 In Shor's algorithm [8], the problem of DataIn DataOut DataIn DataOut QI 1 QI 1 factorizing the number M is reduced to the problem of determining the period r of the QI 1 QIj Instructions Instruction1 Instructionj function y = axmodM, which is calculated by the Figure 4: A digital quantum qubit as line (QLine) controlled units CU (Figure 7), where a is an arbitrary integer. This is precisely the problem of DQCells for heterogonous digital quantum that a quantum computer solves. It is shown that coprocessor the greatest common divisor GCD(ar/2+1, M) can be a divisor of the number M. The subsequent Digital qubit circuit for a homogeneous finding of the greatest common divisor is coprocessor Figure 5 has only one difference in performed by a classical computer. comparison with the circuit in Figure 4: all random variables Asin_f for each digital quantum gate are generated using one pseudo- 0 H random code generator and one functional Upper Register converter. Measurement 0 H QFT A schematic diagram of a digital quantum coprocessor is shown in Figure 6. In 0 H heterogeneous coprocessor, the number of Lower Register 0 pseudo-random code generators and functional 0 CU 20 a CU 21 a CU 2 2 n 1 a 1 transformers coincides with the number of digital quantum gates. Both oscillators and transformers Figure 7: Shor’s algorithm implementation in are located near the digital quantum gates real quantum computer (Figure 3) inside the digital qubits of the Qline circuit in Figure 6. If n  log 2 N  is the required number of bits to represent the number N to be factored than the upper quantum register in Figure 7 requires at QO1 QOj least 2n qubits, because Shor’s algorithm QO1 QGate QO1 QGate requires x to take values between 0 and at least DataIn DataIn DataOut Data1 Dataj-1 DataIn DataOut DataOut N2 and the modular exponentiation function can QI 1 QI 1 be written [9] as 2 n1 QI 1 Instruction1 QIj Instructionj a x mod M  ( a 2 mod M )x ( a 2 mod M )x    ( a 2 mod M )x 0 0 1 1 (1) 2 n1 Asin_f Figure 7 of Shor's algorithm implementation illustrates quantum superiority very well. If we Figure 5: A digital quantum qubit as line (QLine) take only the upper part (Figure 8) of Figure 7 of DQGates for homogenous digital quantum diagram, then the quantum Fourier transform coprocessor will determine the frequency of the white noise that the Hadamard elements create. After the initial reset, each Hadamard element transfers the QO0.1 ,QO0.2 ,...,QO0. j QBi0 DataIn QLine0 QO0 Switch Matrix qubit to the neutral position, when the angle Asin_f DataOut DataOut1 QI0.1 ,QI0.2 ,...,QI0. j θ = π/4 and the state of each qubit with the same Asin_f QI0 probability p0 =p1 = 0,5 can be measured both as ... QO0. j ,QO1. j ,..., QOm1. j QBo 0 and as 1. And the measured state of the upper QOm1.1 ,QOm1.2 ,...,QOm1. j QBim-1 QLinem-1 QOm-1 DataIn DataOutm register in Figure 8 can take any value from 0 to Asin_f Asin_f DataOut QI m1.1 ,QI m1.2 ,...,QI m1. j QIm-1 22n-1. The state spectrum of the upper register will include all 22n states. 2n+1 ROM Asin_f A D PRNG D  arcsin A Figure 6: A generalized functional diagram of a digital quantum coprocessor 0 H Upper Register X y=(2x)mod15=1 Measurement 0 H QFT 0 H 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 x Figure 8: White noise X generated by a Figure 10: X codes for which y = 2xmod15 =1 quantum circuit Let's conduct a thought experiment - imagine y=(2x)mod15=4 that in some way with a period t we find out the state of the upper register without changing states of its qubits. Each time we will receive a 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 x new state code, the possible codes will be in the Figure 11: X codes for which y = 2xmod15 =4 range from 0 to 22n-1. Now imagine that t runs to 0. Then at each moment of time the state of the But the period of y = 2xmod15 function will upper register will contain all codes in the range still be r = 4. And it will again be determined from 0 to 22n-1. using the quantum Fourier transform. Whatever If, on the other hand, modular exponentiation the result at the CU output, in the corresponding is performed over the outputs of the upper spectrum of states there will be only codes that register (CU in Figure 7), then at each "moment" allow determining the period of the function only states that give the same result of modular y = 2xmod15 in one measurement and this period exponentiation at the output of the CU be in the will be r = 4. Determining the period of a spectrum of upper register states. That is, at each function in one measurement illustrates quantum "moment" of time, the spectrum of states will be superiority. This does not take into account the different. For example, for the function time to create a quantum circuit Figure 7. y = 2xmod15 spectrum is presented in Figure 9. The period of the y = axmodM function can be At some "moment" at the output of CU there determined not only by quantum, but also by will be a result y = 1, then in the spectrum of logical (digital) methods in several clock cycles. upper register states there will be 0, 4, 8, 12, … For example, in [5], [6] it is proposed to codes (Figure 10). The distance between the approach the solution of the problem from the same codes, that is, the period of y = 2xmod15 other side: fix r = 2, and determine the random function will be equal to r = 4. This period will variable a from the given r = 2. With this be determined using the quantum Fourier approach, a quantum computer is no longer transform (as the reciprocal of the repetition rate needed. But Shor's algorithm is convenient for F of the extracted codes r = 1/F). At another demonstrating quantum superiority using "moment", the CU output will have the result y = separate examples - for determining the result in 4, then in the spectrum of upper register states one measurement. there will be 2, 6, 10, 14, ... codes (Figure 11). Also, one of the limitations of Shor's algorithm is the requirement for the parity of the period r. It was shown in [5], [6] that this y 9 y=2xmod15 condition is optional. The period r can be odd if 8 a is a square. 7 Once again, we recall that all the "moments" 6 in a quantum computer are one and the same 5 moment in time (Figure 10, Figure 11). 4 Attaching (Figure 7) an additional circuit to 3 the upper register changes the state spectrum at 2 any given "moment" in time. This is similar to a 1 high-pass filter in analog technology - 0 connecting a capacitor removes high frequencies 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 x from the spectrum, removes interference. Figure 9: Modular exponentiation Convenient examples are used to illustrate the quantum superiority in determining the period of y = axmodM function. In the example considered Table 1 earlier, when M = 15 = 3 * 5, period r is power Controlled Unit CU 20  CU 2 , a  2, a 2  2 0 of 2: r = 4 = 22 and both factors are Fourier a primes, they can be represented as 2 2  1 : m Control x0=0 x0=1 signal (multiplication (multiplication 3  2 2  1 , 5  2 2  1 . With such factors, 0 1 by 1) by 2) formula (1) will have the form (2): Input 0001 0001 mod M )x2 n1 = 2 n1 a x mod M  ( a 2 mod M )x0 ( a 2 mod M )x1    ( a 2 0 1 Output 0001 0010 = 2 mod 15  ( 2 mod 15 ) ( 2 mod 15 )    ( 2 mod 15 ) = x 20 x0 21 x1 22 n 1 x2 n 1 (2) binary = ( 2 mod 15 )x ( 4 mod 15 )x ( 1 mod 15 )x    ( 1 mod 15 )x = 0 1 1 2 n 1 Output 000x0 00 x0 0 = ( 2 mod 15 ) ( 4 mod 15 )  2 4 x0 x1 x0 x1 logical Formula (2) makes it possible to find the Output, period using a digital quantum coprocessor. 00 x0 x0 formula The height of the bars in Figure 10, Figure 11 illustrates the probability of receiving the code x as a result of mentally measuring the upper 6. Discussions register state of the circuit Figure 7. Thus, Figure 10 corresponds to the upper register in Further, Figure 13 - Figure 20 show the Figure 7 measured xx...x00 state, and results of the quantum part of Shor's algorithm (determining the period of the function Figure 11 corresponds to its xx...x10 state. y = axmodM (a = 2, M = 15) in the digital The implementation of Shor's algorithm in a quantum coprocessor Figure 7 with 8 digital digital quantum coprocessor is shown in qubits in the upper register, the width of each Figure 12. qubit is 8 bits. The research was carried out on The lower register in Figure 12 is a classic two types of coprocessors - homogeneous and digital logic circuit, signals at its outputs heterogeneous. For statistic, each study was formation (for the considered example of finding repeated 4096 times with the same input data. In the period of y = axmodM function with a = 2, this case, the frequency of occurrence of each M = 15) is shown by Table 1 and Table 2. result (the probability of the result) was recorded. Measuring the states of the developed digital Since the upper register with 2n = 8 qubits quantum qubits does not change the code of this was used, the number of different measured state, which is indicated by the letter D on the codes at the output of the Fourier quantum meter symbol in the circuit Figure 12. transform is N = 22n = 256. The calculated values of y = axmodM function In Figure 13 - Figure 20, these 256 codes are transform the state X into a state X C plotted along the horizontal axis, from 0 to 255. The figures show the codes that, as a result of the correlated with the function values. For the study, were found most often (high probability considered example, this transformation is states – State_HP). The vertical axis shows the described in Table 3. probability (Probability) of the occurrence of the indicated codes, the value of the probability D (Value) is indicated in percent. 0 H First of all figures show the results of white Upper Register X XI XC noise states generator Figure 8 study, the state of Measurement Quantum D 0 H State Transformer QFT the qubits at the output of the upper register is 0 H D X  xxxxxxxx . Figure 13 and Figure 14 D D D Quantum part show how such white noise is perceived by x0 x1 x2 n 1 Classical part quantum Fourier transformer in homogeneous (Figure 13) and heterogeneous (Figure 14) digital Lower Register 0 0 CU 20 CU 21 CU 22 n1 a a a y = axmodM quantum coprocessors. Measurement of such 1 quantum state can give any code in the range 0- Figure 12: Shor’s algorithm implementation in 255 with equal probability. A heterogeneous digital quantum coprocessor coprocessor perceives white noise more correctly. Table 2 number of measurements (the number of repetitions is F = 0). A homogeneous Controlled Unit CU 21  CU 4 , a  2, a 4 21 a coprocessor generates such result with Control x1=0 x1=1 probability of 84.195% (Figure 15), and signal (multiplication (multiplication heterogeneous - with probability 32.805 % by 1) by 4) (Figure 16). Input After confirming correct operation of both 00 x0 x0 00 x0 x0 digital quantum elements of Hadamard and Output 00( x1 x0 )( x1 x0 ) ( x1 x0 )( x1 x0 )00 quantum Fourier transformer, which is also built logical from digital qubits, studies of Shor's algorithm Output, implementation (Figure 7) were continued. formula ( x1 x0 )( x1 x0 )( x1 x0 )( x1 x0 ) Figure 17 and Figure 18 show how the quantum Fourier transform perceives correlated with Table 3 y = axmodM function upper register state X C Controlled Unit CU 21  CU 4 , a  2, a 2  4 1 in homogeneous (Figure 17) and heterogeneous a (Figure 18) digital quantum coprocessors. X  xxxxxxxx . y = axmodM XC And in this case, the heterogeneous (measured x1x0) coprocessor perceives correlated states more 00 1 xx...x00 correctly. y = 2xmod15 function has period T = 4. The 01 2 xx...x01 discrete Fourier transform should most often 10 4 form the result F = N/T = 256/4 = 64. Despite the xx...x10 difference in the perception of correlated upper 11 8 xx...x11 register states, both homogeneous and heterogeneous quantum coprocessors correctly determine the repetition rate of codes when After the quantum Fourier transform, carrying out a large number of measurements, determining the number of repetitions of the they correctly determine the number of measured codes gives the following results: both repetitions F = 64. A homogeneous coprocessor homogeneous and heterogeneous quantum generates such a result with probability 21.439 % coprocessors correctly determine that there are (Figure 19), and heterogeneous - with probability no repetitions of codes when carrying out a large 15.341 % (Figure 20). Figure 13: Number of perceived white noise states at QFT input, homogeneous quantum coprocessor Figure 14: Number of perceived white noise states at QFT input, heterogeneous quantum coprocessor Figure 15: Number of repetitions of white noise states, homogeneous quantum coprocessor Figure 16: Number of repetitions of white noise states, heterogeneous quantum coprocessor Figure 17: Upper register states that are perceived at the input of QFT and correlated with the function y = axmodM, homogeneous quantum coprocessor Figure 18: Upper register states that are perceived at the input of QFT and correlated with the function y = axmodM, heterogeneous quantum coprocessor Figure 19: The number of states repetitions when determining the period of a function, homogeneous quantum coprocessor Figure 20: The number of states repetitions when determining the period of a function, heterogeneous quantum coprocessor The results of Shor's algorithm execution are Fourier transform with the number of digital summarized in the Table 4. qubits up to 1024. 7. Implementation 8. Conclusions In this example, adding a lower register and The article shows the possibility of an upper register state converter (Figure 12) adds determining the period of the y = axmodM practically nothing to the hardware costs of a function in a digital quantum coprocessor. discrete Fourier transform implementation Determination of the period is necessary for the (Figure 8). These costs were determined in execution of Shor's factorization algorithm. previous works [3], [4]. It was shown that on one FPGA it is possible to implement the discrete Table 4 Technology and Engineering Systems Probability of correct results, % Journal (ASTESJ), 2020, 5(6), 1643-1650, Qubits number 8 DOI: 10.25046/aj0506195. [5] J. A. Smolin, G. Smith, A. Vargo, Qubits width, bit 8 Pretending to factor large numbers on a Homogenous coprocessor 21.439 quantum computer, arXiv: 1301.7007v 1 Heterogeneous coprocessor 15.341 [quant-ph] (2013). http://arxiv.org/abs/1301.7007. The possibility of implementing Shor's [6] J. A. Smolin, G. Smith, A. Vargo, factorization algorithm using two types of Oversimplifying quantum factoring. Nature implemented on FPGA digital quantum 499, 163-165 (11 July 2013). coprocessors - homogeneous and heterogeneous [7] Y. Wang, H. Zhang and H. Wang, - is shown. For the research, the factorization of "Quantum polynomial-time fixed-point the number 15 was chosen (a = 2, M = 15). attack for RSA," in China Communications, Determining the period of the y = axmodM vol. 15, no. 2, pp. 25-32, Feb. 2018, doi: function is a task of a quantum coprocessor. 10.1109/CC.2018.8300269. The studies were carried out on coprocessors [8] P. Shor, “Polynomial-Time Algorithms for with 8 digital qubits, the state of each qubit was Prime Factorization and Discrete encoded using 8 bits. Logarithms on a Quantum Computer,” in A homogeneous digital quantum coprocessor 35th Annual Symposium on Foundations of has the best performance: the probability of Computer Science, 124–134, 1994, obtaining a correct result is 21.439%, and that of available at: a heterogeneous one is 15.341%. https://www.jstor.org/stable/2653075?seq=1 The coprocessor is focused on , accessed 25 Nov. 2020. implementation in FPGA. The presented results [9] A. Pavlidis, D. Gizopoulos. Fast Quantum were obtained after simulating VHDL- Modular Exponentiation Architecture for descriptions of coprocessors. Shor's Factorization Algorithm. July 2014. The digital quantum coprocessor outputs each Quantum Information & subsequent result at the system frequency of the Computation 14(7&8):0649-0682. FPGA. In the simulation, this frequency was 1 [10] B. Dey, K. Khalil, A. Kumar and M. GHz (period was 1 ns). Bayoumi, "A Reversible-Logic based Architecture for Artificial Neural Network," 2020 IEEE 63rd International Midwest 9. References Symposium on Circuits and Systems (MWSCAS), 2020, pp. 505-508, doi: [1] X. Fu et al., “A heterogeneous quantum 10.1109/MWSCAS48704.2020.9184662. computer architecture,” in 2016 ACM [11] Quantum-computing.ibm.com. Shor’s International Conference on Computing algorithm. Reversible classical circuits, Frontiers (CF'16), 323–330, 2016, 2020. URL: https://quantum- doi: http://dx.doi.org/10.1145/2903150.2906 computing.ibm.com/composer/docs/iqx/gui 827. de/shors-algorithm. [2] L. Riesebos et al., "Quantum Accelerated [12] E. Grumbling, M. Horowitz (eds.). Computer Architectures," 2019 IEEE “Quantum computing: progress and International Symposium on Circuits and prospects”. The National Academies of Systems (ISCAS), 2019, pp. 1-4, doi: Sciences, Engineering, and Medicine. 10.1109/ISCAS.2019.8702488. Washington, DC: National Academies [3] V. Hlukhov. “FPGA-Based Digital Press. 2019. Quantum Computer Verification”. The 11th IEEE International Conference on Dependable Systems, Services and Technologies, DESSERT’2020. 14-18 May, 2020, Kyiv, Ukraine. In press. [4] V. Hlukhov, “FPGA-Based Homogeneous and Heterogeneous Digital Quantum Coprocessors”, Advances in Science,