Experimental Factoring Integers Using Fixed-Point-QAOA with a Trapped-Ion Quantum Processor

Introduction

1.

Shor’s algorithm [1,2] for factoring integers has become one of the examples of a practically relevant problem, which is hard for classical computers yet amenable for quantum processors. The implication of the integer factorization problem to the widely adopted cryptographic schemes, such as the RSA cryptosystem [3], is a clear motivation for studying its practical complexity within both the classical and quantum approaches [4,5]. Proof-of-concept experimental factoring of 15, 21, and 35 has been demonstrated on superconducting [6], trapped ion [7], and photonic [8-10] quantum computers. However, the implementation of Shor’s algorithm for breaking of actually employed cryptosystems requires resources, which seem to be far beyond the capabilities of existing and upcoming generations of quantum computing devices. For example, in order to factor a 2048-bit RSA integer (i.e., an integer N = pq where p, q are distinct primes), one would need 8 hours using 20 million noisy qubits [11]. Recently, this requirement has been updated to less than a week using less than a million noisy qubits [12].

While current quantum computers are not yet capable of running Shor’s algorithm in a regime that provides a quantum advantage, various approaches are being developed to implement factorization with fewer resources [13–15] or even with currently available noisy intermediate-scale quantum (NISQ) devices [16–18]. One of the proposed methods is the use of the variational quantum factorization (VQF), which has been applied to factorize 41-, 12-, and 13-bit integers on three, four, and five superconducting qubit systems, respectively [19]. The approach incorporates classical preprocessing that yields variable quantum resource requirements across different integers, with some cases achieving particularly significant qubit reductions. The recent paper [20] utilizes an IBM superconducting processor to factorize an 8-bit integer (253) using 9 qubits, without the need for classical preprocessing. This is achieved by applying the variational quantum eigensolver (VQE), which minimizes (N – pq)² to obtain the desired factorization. Additionally, [20] also presents a simulation of the factorization of up to 20-bit integers using up to 27 qubits.

Another approach, proposed in [21], combines Schnorr’s factorization method [22] with the quantum approximate optimization algorithm (QAOA) [23,24], which can be efficiently implemented on NISQ devices [25–28]. The seminal work [21] demonstrated the factorization of a 48-bit integer on 10 trapped ion qubits, describing the solution to a single subproblem using a quantum-classical hybrid quantum QAOA approach. However, as it has been shown [29,30] such an approach encounters a number of pitfalls coming from both classical and quantum domains. In particular, it has been observed [29] that demonstrating this subproblem solution does not equate to full factorization. Building on this, [31] investigated factorizing the same 43-bit integer using a digitized-counterdiabatic quantum algorithm. Their results demonstrated an improved success probability for one Hamiltonian identified in [21], though full factorization was not achieved.

In this study, we show that certain challenges associated with the QAOA-based factorization process can be addressed by switching to a fixed-point variant of QAOA (fpQAOA) [32]. While it became a routine to run QAOA with classical optimization of expectation values with respect to the parameters, such an approach suffers from the problem of global optimization and statistical fluctuations. To our knowledge, the alternative idea to exploit so-called universal angles (parameters) in the QAOA has been presented for the first time in [33]. We follow the latter approach so that in our fixed-point version of QAOA [32] we use fixed optimal parameters from the corresponding training set of tasks, normalize it (i.e., Hamiltonians), and then search for angles providing the maximum minimal increase in the probability of a correct answer, whereas the Max-Min problem is solved via evolution optimization. This allows us to solve reliably the closest vector problem (CVP), which lies in the basis of Schnorr’s algorithm, with the use of the quantum device. Within this approach, we demonstrate experimental factoring of the number 1591 = 37 × 43 using 6 qubits with a trapped ion quantum processor; see Table 1. We also present simulation results for 74425657 = 9521 × 7817 and 35183361263263 = 4194191 × 8388593 with 10 and 15 qubits, correspondingly. These results demonstrate an improvement in the required resources, compared to the simulation results presented in [20], which factored a 20-bit integer using 27 qubits. Although we expect that one of the difficulties in the realization of the QAOA-based factoring is resolved, this approach still requires further scalability studies.

Fixed-Point QAOA-Based Factoring

2.

Here we describe the main principles of the considered algorithm, Figure 1 shows the scheme of factoring, and the detailed description is presented in the Supplementary Materials. The crucial component of Schnorr’s factoring algorithm is the search for smooth relation pairs of integers, so-called sr-pairs. The definition of sr-pair is based on the factor base P_n: the set {p_i}_i=0,…,n of the first n primes together with – 1 (p₀ = – 1, p₁ = 2, p₂ = 3,…). A pair of integers (u, v) is called an sr-pair (for fixed P_n and an integer N) if u and u – vN have prime factors only from P_n. Note that the size of the factor base n is the most important hyperparameter of the algorithm (depending on the size of the factorized number N) and is also equal to the number of qubits of the quantum part.

Figure 1.

As soon as we have a sufficient number of such pairs, which is larger than the size of the factoring base (hyperparameter of the algorithm), we can form a system of linear equations that appears to be degenerate and always has a solution. This solution, by a classical Fermat’s method (see, e.g., [34]), provides a factorization with a high probability.

The problem of sr-pairs search can be reduced to the closest vector problem on a lattice: one needs to find the linear combination of vectors with integer coefficients closest to the target vector

Here f(i) is the random permutation of the first n natural numbers, c is the smoothness hyperparameter, and N is the integer to factorize. The closer the found solution to the desired vector, the greater the chance of obtaining an sr-pair.

Schnorr’s method relies on solving the CVP with the classic approximate Babai’s algorithm [35] with LLL-reduction (Lenstra–Lenstra–Lovász) [36]. As this algorithm gives only an approximate real-valued solution, in the original paper by Schnorr it was rounded to the closest integer value at the last step. The idea behind the recent proposal [21] is to choose the rounding side for each variable to find the closest integer-valued solution, which in turn directly reduces to a quadratic unconstrained binary optimization (QUBO) problem. The example of the rounding refinement is presented in Figure 2. Such class of problems is amenable to solving with QAOA

Figure 2.

QAOA is based on the trotterization of the adiabatic evolution of the following form:

The most common approach to QAOA is to classically optimize the expectation value E (β, γ) = 〈β, γ | Hp | β, γ〉 being estimated by the set of measurements (shots) on a quantum processor (see, e.g., Refs. [37–39]). In contrast, in the seminal QAOA paper [23] relies on searching optimal angles utilizing the efficient exact classical calculation of E (which was presented for Max-Cut problems on 3-regular graphs [23]) followed by sampling on a quantum processor. We have used an alternative approach based on the empirical hypothesis of close optimal angles for different instances of the same problem type [33,40,41].

To find fixed QAOA parameters, we use the training set consisting of 100 QUBO subproblems arised during factoring N = 48567227 on n = 10 qubits. As optimal QAOA problem angles γ scale together with QUBO coefficients, we normalize every QUBO coefficient matrix by its maximal value [32]. The ratio P_q / P_c of the probability P_q to measure the optimal (minimal) answer to its classical random sampling counterpart P_c was used as an optimization metric, and its minimum over the training set was maximized using random mutations optimization algorithm [42,43]. To minimize the quantum circuit depth, we use just a single layer of QAOA (p = 1), which significantly increases robustness of the quantum part of the algorithm. The quantum circuit for a single layer of QAOA used in the algorithm has the form presented in Figure 3, and Figure 4 demonstrates the scheme of the fpQAOA.

Figure 3.

Figure 4.

The resulting single-layer QAOA parameters used in the factorization are γ₁ := γ_* = 2.64 and β₁ := β_* = 0.33. The fixed-parameters approach allows avoiding the classical-quantum hybrid optimization procedure and fits well with the demands of Schnorr’s method: one does not need to obtain the exact or suboptimal solution of CVP, but sample solutions close to the target vector to increase the probability of forming a set of sr-pairs.

In the classical part of the algorithm, we directly follow Refs. [21] and [29]. We use the main factor base of the size B₁ = 6 (which is equal to the number of qubits), the relaxed factor base size for sr-pairs verification is B₂ = 11, the rounding parameter of lattice/target formation procedure is c = 1.5, and the parameter of LLL-reduction is δ = 0.75. For each lattice (which is formed by a random permutation of the diagonal), we conduct 5 measurements (shots) of each circuit. Due to a strongly stochastic nature of the algorithm the required number of circuits varies. The details of a single run of the factorization algorithm including the exact form of the circuit and corresponding parameters are provided in the Supplemental Material.

Experimental Setup

3.

Experimental demonstration of the algorithm was performed with a quantum processor based on a chain of ten ultracold ¹⁷¹ Yb⁺ ions in a linear Paul trap. Its characteristics are summarized in Table 2. Qubits are encoded in states |0〉 = ²S_1/2 (F = 0, m_F = 0) and |1〉 = ²D_3/2 (F = 2, m_F = 0), coupled by an optical E2 transition at wavelength λ = 435.5 nm. While the setup supports usage of all five Zeeman sublevels of the upper state for the information encoding (i.e., we have the qudit processor [44]); in this work we have used the processor in the qubit regime.

Before each experimental shot ions are Doppler cooled to the temperatures of approximately 1.5 mK, which is followed by the sideband-cooling of all radial motional modes close to the ground state and initialization to the |0〉 state by optical pumping [44]. On the next stage the target native gates sequence is being implemented. In our system single-qubit native gates are R_ϕ(θ) = exp(–iσ_ϕθ/2) and R_z(θ) = exp(iθ|1〉 〈 1|), where σ_ϕ = cosϕσ_x + sin ϕσ_y, and ϕ, θ — arbitrary angles. The first operation is performed by applying a laser pulse, resonant to the |0〉 → | 1〉 transition. In this case ϕ is determined by the relative phase of the laser field and the qubit, while θ is determined by the pulse duration. The R_z (θ) is a virtual gate [45] and is performed by shifting phases of all successive laser pulses applied to this ion. A native two-qubit operation for this system is a Mølmer-Sørensen gate [46-49] R_xx (2χ) ≡ XX(χ) = exp(–iχσ_x ⊗ σ_x). This gate is implemented by illuminating a target pair of ions with a bichromatic laser fields, coupling their electronic states with a collective motional degrees of freedom (in our case we use radial motional modes). These common motional modes serve as mediator, coupling both qubits. The laser fields are amplitude-modulated to decouple all electronic degrees of freedom from motional ones at the end of the gate and reduce sensitivity of the operation to the experimental parameters [50]. The processor supports XX (χ) gates with arbitrary χ and all-to-all connectivity. We also include R_zz (2χ) ≡ ZZ(χ) = exp(–iχσ_z ⊗ σ_z) gate in the list of supported operations, which is automatically hardware-efficiently transpiled as ZZ(χ) = (R_y (π/2) ⊗ R_y (π/2))XX(χ)(R_y (–π/2) ⊗ R_y (–π/2)) in the processor. At the end of each experimental shot the quantum register readout is performed using electron-shelving technique on the |²S_1/2) → |²P_1/2) transition at 369 nm [44, 51]. Ions fluorescence in this process is collected with a high numeric aperture lens and is sent via an array of multimode fibers to the multichannel photomultiplier tube.

Fidelities of the single-qubit and two-qubit operations are 99.946(6)% and 96.3(3)%, which are measured using randomized benchmarking [52], and parity oscillations observation [53], correspondingly. The qubits coherence time $T_2^{*}=30\left(2\right)$ ms was extracted from decay of Ramsey fringes contrast with increasing delay between π/2 pulses. To reduce cross-talk during single-qubit operations all Rϕ (θ) gates in the circuits are substituted with their composite analogues using SK1 scheme [54]. Particularly, two 2π rotations around specific axes are added after each singlequbit gate, which are known to suppress both cross-talks and rotation angle fluctuations.

More details on the experimental setup can be found in [44,55].

Experimental Results

4.

In the experiment, we use Schnorr’s approach assisted with the fixed-angles QAOA to factorize number 1591 = 37 × 43 using 6 qubits.

In a single sample run of the experiment (for details, see Supplemental Material), B₂ + 1 sr-pairs required to deterministically factorize the number were found in 43 steps (shots) using 9 different quantum circuits (each circuit repeated 5 times followed by the next circuit). However, in this particular sample run the first 39 shots appeared to be already sufficient to factorize the number. We have compared the average speed of collecting unique sr-pairs in three cases: (i) random sampling; (ii) experimentally obtained samples; (iii) samples obtained with noiseless emulator (see Figure 5(a)). The figure demonstrates the advantage of the quantum processor sampling results over the random sampling. However, the presence of the noise in the system decreases the efficiency of the method in comparison with a noiseless emulator. To illustrate the level of the noise in the quantum processor we also measured the output states probability distributions for several used circuits with better averaging and compared it with results expected in the absence of errors (for details, see Supplemental Material).

Figure 5.

In this experiment we chose to use 6 qubits as a trade-off between the problem size and quantum circuits fidelity. Numeric simulations show that the expected advantage over random sampling in QUBO-subproblems increases with the growth of qubits number and magnitude of a number to factorize (e.g., see Figure 5). At the same time as the number of two-qubit operations in each circuit is equal to n(n – 1)/2, where n is the number of qubits, the quantum sampling fidelity decreases with larger n. In our experiments n = 6 was the smallest number of qubits, where the advantage over random sampling was observed experimentally despite the better sampling fidelity at n < 6.

A number of shots per circuit was chosen using numerical simulations. It was set to be sufficient to find enough sr-pairs, keeping the total number of shots minimal.

Scalability Analysis

5.

The initial complexity estimates presented in Schnorr’s work [22] did not lead to practical results for factoring large numbers; however, the effectiveness of the method has still neither been proven nor strictly disproved. Based on Refs. [29,30,56,57] and own numerical experiments, the following difficulty can be noted: the probability that estimates obtaining an sr-pair by suboptimal solutions of CVP problem (obtained by classical or quantum methods) does not directly lead to the probability of obtaining a set of unique sr-pairs needed for the factorization. Further, we present a brief empirical analysis of scalability of the presented method. We use the number of measurement shots as a proxy for computational cost, as we adopt an exponential complexity model that ignores polynomial factors from quantum circuit depth (though this can be extended with circuit-level details). Figure 6 shows the logarithmic shot count versus the bit-length n_b of the factored integers.

Figure 6.

For fpQAOA-based factoring, we trained on 50 QUBO instances generated from random 24-bit integers using n = 10 (where n denotes the lattice size and the number of qubits). Since optimal parameter selection for n remains an open problem, we performed a grid search to determine the best n for each bit-length and algorithm variant; optimal values of n are presented in Table 3.

Numerical experiments on 25–40-bit integers reveal approximately exponential scaling within the tested range (Figure 6)—consistent with other NISQ-era quantum heuristics [58,59]. Results indicate that the shot count scales roughly as O(1.15^n_b) for p = 3 QAOA, even for such a low depth outperforming random sampling (m ≈ 1.19) and classical brute-force (m ≈ 1.414). While this suggests a quantum advantage for mid-scale factoring, we emphasize that this model is provisional—its validity at cryptographic scales (e.g., n_b > 100) remains untested (the true complexity could be strictly better or worse than this exponential estimate depending on the interaction between Schnorr’s lattice reduction and quantum optimization dynamics). We also want to note that for exponential scaling O(m^n_b), values like m ≈ 1.02 (enabling classical record 829-bit factoring in 10⁷ shots) may yield practical utility despite asymptotic limitations, as the base m dominates at intermediate scales.

The improvement of complexity of the presented method can possibly be achieved by hyperparameter optimization, increasing the depth p, dynamic p-scaling via Fourier encoding [38], and the enlargement of search spaces beyond single steps from classical approximations. We also emphasize that the quantum advantage should be verified against classical QUBO-solving methods more sophisticated than random sampling.

Conclusion and Outlook

6.

We have considered the Schnorr factoring scheme, where following the idea from [21], we adopt the QAOA method at the last step of Babai’s algorithm. However, for the first time we used a fixed-point feature of QAOA [32,33] for the factoring problem and were able to factor a specific integer. To the best of our knowledge, it is the first successful experimental factoring of a particular integer with fixed-point QAOA-assisted Schnorr approach, whereas previously it was only experimentally presented how to obtain some sr-pairs for this task using quantum computers.

To confirm both the overall scheme and the fixed-point approach, we experimentally factor 1591 = 37 × 43 using 6 qubits of the 10-qubit trapped-ion processor. Thus, this work provides the first complete implementation of quantum-enhanced Schnorr’s lattice-based factorization, filling a critical development gap among alternative quantum factoring methods. The fixed-angle QAOA approach enables scalable factoring of general integers, with simulations up to 45 bits on 15 qubits suggesting practical utility for near-term NISQ experiments and benchmarks.

For further research we leave the questions of the algorithm’s efficiency and thorough comparison with classical methods, as well as a more detailed investigation of the quantum processor noise influence.

Note added. After completion of this work, we became aware of [59], which also suggests using fixed-point QAOA in the same context. Authors have presented an alternative approach of fixed angles search and scaling, and conducted a thorough numerical analysis of QAOA-augmented refinement of CVP problem. In contrast, in our work we consider the complete factorization algorithm and its experimental trapped-ion implementation.

Supplemental Materials

In this supplemental section we provide the details of a single run of the factoring algorithm. Let’s consider the first random permutation (1, 3, 2, 5, 6, 4) used in the algorithm. The corresponding CVP is defined by the lattice

The approximate solution given by Babai’s algorithm based on LLL-reduction is

Fixed-Point-QAOA Circuits

To factor 1591 = 37 × 43 with fixed-point QAOA we implemented 9 quantum 6-qubit quantum circuits on a trapped-ion processor. Due to the fixed-point feature there is no need for classical-quantum hybrid optimization, therefore all necessary parameters for circuit construction can be obtained before execution on a quantum hardware. Exact architecture of executed quantum circuits with native for the processor single-qubit and two-qubit gates is presented in Figure 3. Parameters of the circuits, which correspond to angles in the gates R_z (θ_i) and ZZ(χ_ij), are given in Table 5. When χ_ij is equal to zero, ZZ (χ_ij) is not implemented. We note that to get sufficient statistics it was enough to perform 5 shots for each circuit. In total, 45 experimental shots were executed on a trapped-ion processor. To collect 12 sr-pairs 43 shots were enough.

Experimental QUBO Sampling Accuracy

In this section we present a comparison between experimentally obtained output states probabilities for circuits 1 and 6 from the Table 5 and ones calculated on a noiseless emulator (Figure 7).

Figure 7.

In Figure 8 we also show analogous output probability distributions for the circuits where we use only 5 qubits to factorize number 437. It can be seen that the sampling fidelity is generally higher than for a 6 qubit case due to smaller circuit depth. However, for such a small problem size no quantum advantage over random sampling was observed.

Figure 8.

Factoring Algorithm Details

Here we provide the description of the factoring algorithm adapted from [29]. The formal detailed description of Babai’s algorithm for CVP-approximation subroutine is presented in Algorithm 1. Overall factoring procedure is presented in Algorithm 2. Further, we consider the QUBO refinement of CVP-approximation. Generally, for any CVP defined by a lattice B = {b_ij} and a target vector t_j, we need to find integer coefficients a_i ∈ ℤ minimizing ${\displaystyle \sum _j{\left({\displaystyle \sum _i{a}_i}{b}_{ij}-t_j\right)}^2}$. Babai’s algorithm (however, it can be replaced by any other real approximation algorithm) provides a real-valued approximation c_i ∈ ℝ. Then the rounded values ⌈c_i⌋ are being taken as an approximate integer solution. Let us define variables that specify the rounding side:

Then the problem of choosing the side of each rounding has the form: