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 n1
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 n1
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 ,..., QOm1. j QBo 0 and as 1. And the measured state of the upper
QOm1.1 ,QOm1.2 ,...,QOm1. 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 m1.1 ,QI m1.2 ,...,QI m1. 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 n1 =
2 n1
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 n1
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,