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.
A quantum computer is a heterogeneous
device [
The possibility of creating logical (digital)
probabilistic devices that can work according to
the same formulas as real quantum coprocessors
and can implement quantum algorithms is shown
in previous works [
Quantum computers possible field use is large
numbers factorization [
In previous works, the implementation of
digital Hadamard elements and digital quantum
Fourier transform on FPGAs was shown [
Simulation of individual quantum gates is
used to simulate quantum algorithms. To
simulate the reversibility of a qubit, models of
reversible logic architecture [
The aim of the work is to show the possibility of performing quantum algorithms (using the example of factoring the number 15 by Shor's 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).
Qubit quantum state
can be represented
(Figure 2) as a simple displacement of end point
of unit radius [
j as a result of quantum state
measurement is equal to p j 2j . In this
N 1
case, the sum of all probabilities P i2 1 .
j0
In unit circle (Figure 2) which is used in [
A digital quantum gate that is used to change the state of a digital qubit can be represented as a logic circuit Figure 1.
The digital quantum gate includes an ALU, a comparator, and a pipelined register.
ALU transforms the code of the previous state DataIn of the qubit under the influence of the Instruction with the possible use of the measured state QI of the neighboring qubit (or states of qubits). The new DataO status code is compared in a comparator with the random variable Asin_f to obtain the measured state of the qubit QO ' . The output of the gate is the qubit state code DataOut and the measured state QO of the qubit, which are taken from the output of the pipeline register.
DataIn QI Instruction Asin_f
ALU
DateO B Comparator A
QO '
RG
DateOut QO
In a heterogeneous digital quantum coprocessor, a random variable at the input of each digital quantum gate is generated by a separate pseudo-random code generator (PRNG) and a Read-Only-Memory (ROM) based functional converter. The converter changes the random variable A according to the formula A sin_ f D arcsin
A (Figure 3).
QI DataIn Instruction
Random
Number A QO1 DQCell QI1
QIj QI1 QO1 DQCell
StateOut
Digital qubit circuit for a homogeneous coprocessor Figure 5 has only one difference in comparison with the circuit in Figure 4: all random variables Asin_f for each digital quantum gate are generated using one pseudorandom code generator and one functional converter.
A schematic diagram of a digital quantum coprocessor is shown in Figure 6. In heterogeneous coprocessor, the number of pseudo-random code generators and functional transformers coincides with the number of digital quantum gates. Both oscillators and transformers are located near the digital quantum gates (Figure 3) inside the digital qubits of the Qline circuit in Figure 6.
In Shor's algorithm [
If n log2 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
least 2n qubits, because Shor’s algorithm
requires x to take values between 0 and at least
N2 and the modular exponentiation function can
be written [
Figure 7 of Shor's algorithm implementation illustrates quantum superiority very well. If we take only the upper part (Figure 8) of Figure 7 diagram, then the quantum Fourier transform will determine the frequency of the white noise that the Hadamard elements create. After the initial reset, each Hadamard element transfers the qubit to the neutral position, when the angle θ = π/4 and the state of each qubit with the same probability p0 =p1 = 0,5 can be measured both as 0 and as 1. And the measured state of the upper register in Figure 8 can take any value from 0 to 22n-1. The state spectrum of the upper register will include all 22n states. H H
X
QFT t n e m e rs u a e M
Let's conduct a thought experiment - imagine 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 new state code, the possible codes will be in the range from 0 to 22n-1. Now imagine that t runs to 0. Then at each moment of time the state of the upper register will contain all codes in the range from 0 to 22n-1.
If, on the other hand, modular exponentiation is performed over the outputs of the upper register (CU in Figure 7), then at each "moment" only states that give the same result of modular exponentiation at the output of the CU be in the spectrum of upper register states. That is, at each "moment" of time, the spectrum of states will be different. For example, for the function y = 2xmod15 spectrum is presented in Figure 9.
At some "moment" at the output of CU there will be a result y = 1, then in the spectrum of upper register states there will be 0, 4, 8, 12, … codes (Figure 10). The distance between the same codes, that is, the period of y = 2xmod15 function will be equal to r = 4. This period will be determined using the quantum Fourier transform (as the reciprocal of the repetition rate F of the extracted codes r = 1/F). At another "moment", the CU output will have the result y = 4, then in the spectrum of upper register states there will be 2, 6, 10, 14, ... codes (Figure 11).
y=2xmod15
But the period of y = 2xmod15 function will still be r = 4. And it will again be determined using the quantum Fourier transform. Whatever the result at the CU output, in the corresponding spectrum of states there will be only codes that allow determining the period of the function y = 2xmod15 in one measurement and this period will be r = 4. Determining the period of a function in one measurement illustrates quantum superiority. This does not take into account the time to create a quantum circuit Figure 7.
The period of the y = axmodM function can be
determined not only by quantum, but also by
logical (digital) methods in several clock cycles.
For example, in [
Also, one of the limitations of Shor's
algorithm is the requirement for the parity of the
period r. It was shown in [
Once again, we recall that all the "moments" in a quantum computer are one and the same moment in time (Figure 10, Figure 11).
Attaching (Figure 7) an additional circuit to the upper register changes the state spectrum at any given "moment" in time. This is similar to a high-pass filter in analog technology connecting a capacitor removes high frequencies from the spectrum, removes interference.
Convenient examples are used to illustrate the quantum superiority in determining the period of y = axmodM function. In the example considered earlier, when M = 15 = 3 * 5, period r is power of 2: r = 4 = 22 and both factors are Fourier primes, they can be represented as 22m 1 : 3 220 1, 5 221 1 . With such factors, formula (1) will have the form (2): (2) ax mod M ( a20 mod M )x0 ( a21 mod M )x1 ( a22n1 mod M )x2n1 =
Formula (2) makes it possible to find the period using a digital quantum coprocessor.
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 register state of the circuit Figure 7. Thus, Figure 10 corresponds to the upper register in Figure 7 measured xx...x00 state, and Figure 11 corresponds to its xx...x10 state.
The implementation of Shor's algorithm in a digital quantum coprocessor is shown in Figure 12.
The lower register in Figure 12 is a classic digital logic circuit, signals at its outputs formation (for the considered example of finding the period of y = axmodM function with a = 2, M = 15) is shown by Table 1 and Table 2. Measuring the states of the developed digital quantum qubits does not change the code of this state, which is indicated by the letter D on the meter symbol in the circuit Figure 12.
The calculated values of y = axmodM function transform the state X into a state X C correlated with the function values. For the considered example, this transformation is described in Table 3.
D D
D Quantum part Classical part t n e m rseeau M 0 tirseeg r 0 R e p p U 0
Further, Figure 13 - Figure 20 show the results of the quantum part of Shor's algorithm (determining the period of the function y = axmodM (a = 2, M = 15) in the digital quantum coprocessor Figure 7 with 8 digital qubits in the upper register, the width of each qubit is 8 bits. The research was carried out on two types of coprocessors - homogeneous and heterogeneous. For statistic, each study was repeated 4096 times with the same input data. In this case, the frequency of occurrence of each result (the probability of the result) was recorded.
Since the upper register with 2n = 8 qubits was used, the number of different measured codes at the output of the Fourier quantum transform is N = 22n = 256.
In Figure 13 - Figure 20, these 256 codes are plotted along the horizontal axis, from 0 to 255. The figures show the codes that, as a result of the study, were found most often (high probability states – State_HP). The vertical axis shows the probability (Probability) of the occurrence of the indicated codes, the value of the probability (Value) is indicated in percent.
First of all figures show the results of white noise states generator Figure 8 study, the state of the qubits at the output of the upper register is
X xxxxxxxx . Figure 13 and Figure 14 show how such white noise is perceived by quantum Fourier transformer in homogeneous (Figure 13) and heterogeneous (Figure 14) digital quantum coprocessors. Measurement of such quantum state can give any code in the range 0255 with equal probability. A heterogeneous coprocessor perceives white noise more correctly. 1 Controlled Unit CU 21 CU4 , a 2, a2 4 a x1=0 (multiplication by 1) ( x1x0 )( x1 x0 )( x1x0 )( x1 x0 )
After the quantum Fourier transform, determining the number of repetitions of the measured codes gives the following results: both homogeneous and heterogeneous quantum coprocessors correctly determine that there are no repetitions of codes when carrying out a large number of measurements (the number of repetitions is F = 0). A homogeneous coprocessor generates such result with probability of 84.195% (Figure 15), and heterogeneous - with probability 32.805 % (Figure 16).
After confirming correct operation of both digital quantum elements of Hadamard and quantum Fourier transformer, which is also built from digital qubits, studies of Shor's algorithm implementation (Figure 7) were continued. Figure 17 and Figure 18 show how the quantum Fourier transform perceives correlated with y = axmodM function upper register state X C in homogeneous (Figure 17) and heterogeneous (Figure 18) digital quantum coprocessors.
And in this case, the heterogeneous coprocessor perceives correlated states more correctly.
y = 2xmod15 function has period T = 4. The discrete Fourier transform should most often form the result F = N/T = 256/4 = 64. Despite the difference in the perception of correlated upper register states, both homogeneous and heterogeneous quantum coprocessors correctly determine the repetition rate of codes when carrying out a large number of measurements, they correctly determine the number of repetitions F = 64. A homogeneous coprocessor generates such a result with probability 21.439 % (Figure 19), and heterogeneous - with probability 15.341 % (Figure 20).
In this example, adding a lower register and
an upper register state converter (Figure 12) adds
practically nothing to the hardware costs of a
discrete Fourier transform implementation
(Figure 8). These costs were determined in
previous works [
The article shows the possibility of determining the period of the y = axmodM function in a digital quantum coprocessor. Determination of the period is necessary for the execution of Shor's factorization algorithm.
The possibility of implementing Shor's factorization algorithm using two types of implemented on FPGA digital quantum coprocessors - homogeneous and heterogeneous - is shown. For the research, the factorization of the number 15 was chosen (a = 2, M = 15). Determining the period of the y = axmodM function is a task of a quantum coprocessor.
The studies were carried out on coprocessors with 8 digital qubits, the state of each qubit was encoded using 8 bits.
A homogeneous digital quantum coprocessor has the best performance: the probability of obtaining a correct result is 21.439%, and that of a heterogeneous one is 15.341%.
The coprocessor is focused on implementation in FPGA. The presented results were obtained after simulating VHDLdescriptions of coprocessors.
The digital quantum coprocessor outputs each subsequent result at the system frequency of the FPGA. In the simulation, this frequency was 1 GHz (period was 1 ns).