Figure 1.
Figure 2.
Figure 3.
Figure 4.
Figure 5.
Figure 6.
Figure 7.
Figure 8.
Figure 9.
Figure 10.
Figure 11.
Figure 12.
Figure 13.
Figure 14.
Figure 15.
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 |
j_qic-2026-0012_tab_007
| 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. |
j_qic-2026-0012_tab_008
| 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. |
j_qic-2026-0012_tab_009
| ℒ | 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 ℒ*. |
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 |
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) |
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 |
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 |
Comparison of exact values of T and their approximations using function exp(n2d)\exp \left( {{n \over {2d}}} \right) 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 |