Table 1.
Shor and Regev algorithms metrics comparison. The content is based on paper [9].
| Algorithm | Multiplication algorithm | Width | Gate complexity |
|---|---|---|---|
| Shor [3] | Harvey, Hoeven [18] | O(n log n) | O(n2 log n) |
| Shor | Schoolbook | O(n) | O(n3) |
| Shor | Gidney [19], KMY [20] | O(n) | Oϵ(n2+ϵ) |
| Optimized Shor [12,14,15,21,22] | Schoolbook | (1.5 + o(1))n | |
| Regev [7] | Schoolbook | O(n3/2) | |
| Regev [7] | Harvey, Hoeven [18] | O(n3/2) | O(n3/2 log n) |
| Optimized Regev [9] | Harvey, Hoeven [18] | O(n log n) | O(n3/2 log n) |
| Optimized Regev [9] | Gidney [19], KMY [20] | (10.32 + o(1))n | |
| Optimized Regev [9] | Schoolbook [23] | (10.32 + o(1))n | O(n5/2 log n) |
| Our implementation | Schoolbook | O(n) | O(n5/2 log n) |
Table 2.
The biggest factorized number N depending on d and qd parameters.
| d | qd | N |
|---|---|---|
| ceil | ceil | 57 |
| ceil | floor | 57 |
| floor | ceil | 119 |
| floor | floor | 143 |
Figure 1.
General quantum circuit for N = 57, d ceil and qd ceil (ceil_ceil) parameters.
Figure 2.
Decomposed quantum circuit for N = 57, d ceil and qd ceil (ceil_ceil) parameters.
Figure 3.
Output vector measurements for N = 51 and ceil_ceil parameters.
Figure 4.
Output vector measurements for N = 51 and ceil_floor parameters.
Table 3.
Comparison of exact values of T and their approximations using function for selected values of N.
| N | 15 | 21 | 35 | 51 | 57 |
| value of n | 4 | 5 | 6 | 6 | 6 |
| value of d | 2 | 3 | 3 | 3 | 3 |
| exact value of T | 3 | 2 | 3 | 3 | 3 |
| approximate value of T | 2.718 | 2.301 | 2.718 | 2.718 | 2.718 |
Figure 5.
Runtime comparison for ceil_ceil and ceil_floor parameters.
Figure 6.
Quantum part runtime comparison for floor_ceil and floor_floor parameters.
Table 4.
Average runtime up to N = 57.
| Algorithm | Average runtime |
|---|---|
| Regev (ceil_ceil) | 2 h 21 min 11.24 s |
| Regev (ceil_floor) | 2 h 47 min 53.43 s |
| Regev (floor_ceil) | 3 min 18.27 s |
| Regev (floor_floor) | 5 min 2.21 s |
| Shor | 14 min 3 s |
Figure 7.
Classical part runtime comparison for all parameters configurations.
Figure 8.
Effectiveness comparison for ceil_ceil for all types of test.
Figure 9.
Effectiveness comparison for ceil_floor for all types of test.
Figure 10.
Effectiveness comparison for floor_ceil for all types of test.
Figure 11.
Effectiveness comparison for floor_floor for all types of test.
Table 5.
Average effectiveness of Regev’s algorithm variants for three test types and Shor’s algorithm.
| Algorithm | Type 1 | Type 2 | Type 3 |
|---|---|---|---|
| Regev (ceil_ceil) | 49.00 | 44.94 | 48.34 |
| Regev (ceil_floor) | 52.08 | 47.81 | 55.06 |
| Regev (floor_ceil) | 47.95 | 44.20 | 51.46 |
| Regev (floor_floor) | 48.05 | 43.74 | 51.29 |
| Shor | 77.10 | 77.10 | 77.10 |
Figure 12.
Effectiveness comparison for t = 5.
Figure 13.
Effectiveness comparison for t = 8.
Figure 14.
Effectiveness comparison for t = 14.
Figure 15.
Effectiveness comparison for t = 2.
Table 6.
Effectiveness for different values of parameter t.
| Factorized number N | 21 | 33 | 35 | 39 | 51 | 55 | 57 |
| t for which obtained the highest effectiveness | 14 | 8 | 14 | 5 | 8 | 11 | 2 |
| Effectiveness of finding square root of unity modulo-N [%] | 94 | 86 | 74 | 100 | 100 | 62 | 82 |
| Effectiveness of finding non-trivial square root of unity modulo-N [%] | 74 | 56 | 48 | 100 | 98 | 32 | 70 |
| N | Factorized semiprime integer, product of primes p and q. |
| n | Number of bits in the binary representation of number N. |
| p | Prime number, factor of number N. |
| q | Prime number, factor of number N. |
| (a1, …, ad) | The first d squared numbers that are coprime with N; for convenience, the squares of primes are used. |
| (b1, …, bd) | The first d numbers that are coprime with N; for convenience, the prime numbers are used. |
| d | Number of dimensions in Regev’s algorithm, also defines the number of quantum input registers. Its value is either equal to (ceil version) or equal to (floor version). |
| qd | The boundary of the exponents in Regev’s algorithm, also defines a width of each of the quantum input registers. Its value is either equal to (ceil version) or equal to (floor version). |
| ceil_ceil | d and qd parameters combination when d and qd are both in ceil version. |
| ceil_floor | d and qd parameters combination when d is in ceil version and qd is in floor version. |
| floor_ceil | d and qd parameters combination when d is in floor version and qd is in ceil version. |
| floor_floor | d and qd parameters combination when d and qd are both in floor version. |
| ℒ | A lattice containing vectors that allow computing the square root of unity modulo-N. |
| ℒ0 | A lattice containing vectors that allow computing the trivial square root of unity modulo-N. |
| ℒ′ | A lattice used to retrieve the period vector from the vectors obtained in the quantum part. |
| ℒ* | Dual lattice of the lattice ℒ. |
| B | A matrix whose columns form a basis of the lattice ℒ′. |
| t | Parameter used to transform vectors returned by quantum circuit into vectors that approximates dual lattice vectors in ℒ*. |