Source-linked AI summary
Variational Quantum Factoring
Eric R. Anschuetz, Jonathan P. Olson, Alán Aspuru-Guzik, Yudong Cao
TL;DR
Current NISQ devices have limited qubit counts and circuit depth, placing Shor’s algorithm beyond practical reach. VQF preprocesses factoring equations to reduce the Hamiltonian’s qubit requirements, then trains a QAOA ansatz to seek an approximate ground state. After O(n) circuit layers, success probability plateaus for m = 35, 56153, and 291311, while depth scaling is poorer for m = 77, 1207, and 33667.
Problem
Current NISQ devices have limited qubit counts and circuit depth, placing Shor’s algorithm beyond practical reach.
Source: §I · p. 2Method
VQF preprocesses factoring equations to reduce the Hamiltonian’s qubit requirements, then trains a QAOA ansatz to seek an approximate ground state.
Source: §I · p. 3, §III · p. 7Results
After O(n) circuit layers, success probability plateaus for m = 35, 56153, and 291311, while depth scaling is poorer for m = 77, 1207, and 33667.
Source: A. Depth Scaling · p. 11Takeaways & Limitations
Hybrid classical/quantum methods such as VQF may be more amenable to factoring on a quantum computer in the next decade.
Source: §V · p. 12Circuit-depth scaling does not fare as well for m = 77, 1207, and 33667.
Source: A. Depth Scaling · p. 11
Abstract
from arXiv · showhide
Integer factorization has been one of the cornerstone applications of the field of quantum computing since the discovery of an efficient algorithm for factoring by Peter Shor. Unfortunately, factoring via Shor's algorithm is well beyond the capabilities of today's noisy intermediate-scale quantum (NISQ) devices. In this work, we revisit the problem of factoring, developing an alternative to Shor's algorithm, which employs established techniques to map the factoring problem to the ground state of an Ising Hamiltonian. The proposed variational quantum factoring (VQF) algorithm starts by simplifying equations over Boolean variables in a preprocessing step to reduce the number of qubits needed for the Hamiltonian. Then, it seeks an approximate ground state of the resulting Ising Hamiltonian by training variational circuits using the quantum approximate optimization algorithm (QAOA). We benchmark the VQF algorithm on various instances of factoring and present numerical results on its performance.
I. INTRODUCTION
Shor’s algorithm offers a quantum approach to factoring, but present NISQ devices have limited qubit counts and circuit depth. VQF instead combines classical preprocessing with QAOA to seek low-energy states of an Ising formulation of factoring.
I. INTRODUCTION
- Prior Shor implementations reduce qubit requirements through circuit improvements, including an adaptive iterative phase-estimation approach with an n+1-qubit cost.The introduction also describes quantum annealing and simulated adiabatic evolution as experimental directions for Ising-based factoring.Source: §I · pp. 2–3
- Present NISQ devices have about 10^2–10^3 noisy qubits and limited reliable circuit depth, placing Shor’s algorithm and fault-tolerance-dependent alternatives beyond current practical reach.The paper describes fault-tolerant quantum computers as a distant prerequisite for these approaches.Source: §I · p. 2
- The Ising approach encodes multiplication constraints on factor and carry bits, assigning penalties to bit strings that violate an equation.Earlier work also identified specific factoring instances whose equations can be simplified substantially.Source: §I · pp. 2–3
- VQF maps factoring to an Ising Hamiltonian, preprocesses equations to reduce required qubits, and trains a QAOA ansatz using local and global optimization.The paper explores six factoring instances and the scheme’s effectiveness and robustness.Source: §I · p. 3
A. Factoring as binary optimization
The section formulates factoring as binary multiplication constraints and uses their satisfaction to identify factor assignments through an Ising energy minimization.
A. Factoring as binary optimization
- Binary multiplication of the unknown factors must satisfy O(n_m) equations involving the bits of the factors and carry bits.The number of equations is n_c = n_p + n_q − 1.Source: A. Factoring as binary optimization · p. 4
- Factoring is represented by assigning binary values to the factor and carry variables so that each multiplication clause is satisfied.The clauses are associated with the equations over Z.Source: A. Factoring as binary optimization · p. 4
- The Hamiltonian’s ground state satisfies the generated constraints, while assignments that violate an equation receive an energy penalty.When the input has more than two prime factors, the ground-state manifold is degenerate over factor pairs; the scheme can be repeated or extended to seek further factors.Source: A. Factoring as binary optimization · p. 4
- The discussion assumes the input is a biprime, while noting that primality can be detected separately.For an input with more than two prime factors, the method can produce a manifold of factor pairs.Source: A. Factoring as binary optimization · p. 4
B. Simplifying the clauses
Classical preprocessing simplifies the binary clauses before Hamiltonian construction, with the observed effect of reducing the number of qubits needed for most instances.
B. Simplifying the clauses
- The preprocessing applies classical simplification rules to clauses and can solve subsets of binary variables directly.The procedure also truncates a carry-bit sum when that bit cannot be one without making the equation unsatisfiable.Source: B. Simplifying the clauses · p. 5
- The preprocessing bounds the magnitude of the factoring equation’s final term by excluding carry-bit terms that cannot occur in any satisfying assignment.The exclusion follows because the subtrahend would otherwise exceed the minuend for every assignment of the other variables.Source: B. Simplifying the clauses · p. 5
- For most tested instances, preprocessing greatly reduces the number of qubits required to solve the problem.The text points to Figure 1 for the empirical reduction.Source: B. Simplifying the clauses · p. 5
C. Constructing the Ising Hamiltonian
After preprocessing, the factoring constraints define an Ising Hamiltonian whose ground state corresponds to a satisfying assignment. Its qubit requirement scales empirically as O(n_m), rather than O(n_m log(n_m)) without simplification.
C. Constructing the Ising Hamiltonian
- The simplified clauses are converted into a classical energy function whose minimization represents solving the factoring constraints.The resulting clauses are quantized to form a factoring Hamiltonian.Source: C. Constructing the Ising Hamiltonian · pp. 5–6
- O(n_m) qubit scaling is observed with preprocessing, versus O(n_m log(n_m)) asymptotically without simplification.Figure 1 empirically compares the qubit requirements after applying the algorithm with those without simplification.Source: Figure 1 · p. 6, C. Constructing the Ising Hamiltonian · p. 6
- The encoded factoring instance has a 4-local Ising Hamiltonian.A quadratic representation is also possible by introducing variables and additional constraints, but the paper says this is unnecessary for its gate-model method.Source: C. Constructing the Ising Hamiltonian · pp. 6–7
- The gate-model approach can use known methods for time evolution under k-local Hamiltonians, avoiding the need to impose restricted pairwise couplings.The quadratic conversion is described as necessary for quantum annealing devices with restricted pairwise coupling.Source: C. Constructing the Ising Hamiltonian · p. 7
III. VARIATIONAL QUANTUM FACTORING ALGORITHM
VQF casts factoring as minimizing an Ising cost Hamiltonian and uses QAOA to seek an approximate ground state. The section also describes parameter training and its numerical scaling.
III. VARIATIONAL QUANTUM FACTORING ALGORITHM
- The algorithm uses QAOA to prepare an approximate ground state of the cost Hamiltonian, with angles β and γ across s layers.For fixed s, a classical optimizer minimizes the cost function M(β, γ).Source: §III · p. 7
- VQF approximately solves factoring by minimizing the Ising Hamiltonian in Equation (7), constructed from simplified Boolean clauses.The cost Hamiltonian Hc is set equal to H, and satisfying the simplified clauses corresponds to finding simultaneous zeros.Source: §III · p. 7
- For finite depth, the optimized state can generically have exponentially small overlap with the true ground state, though numerical evidence suggests s ∈ O(n) often gives large overlap.The fidelity tends to 1 as s approaches infinity.Source: §III · p. 7
- Parameters are initialized by layer-by-layer grid search over each (γ_i, β_i) pair, then refined with BFGS.The authors motivate grid resolution using a gradient bound and report that coarser grids seemed sufficient numerically.Source: §III · p. 8
- The worst-case total VQF cost for depth s is O(s^2 n^4 c_n^8), but the authors describe this bound as numerically loose and give no guarantee of a global optimum.The number of BFGS evaluations until convergence appeared independent of problem size and linear in circuit depth.Source: §III · pp. 8–9
- BFGS convergence was approximately independent of problem size and scaled approximately linearly with the number of parameters.The reported error bars are one standard deviation over three problem instances.Source: §III · pp. 9–10
A. Depth Scaling
Noisy simulations found that success probability plateaued at a large fraction for three instances after O(n) circuit layers, while three other instances did not scale as well with depth.
A. Depth Scaling
- In noisy biprime-factoring simulations, success probability for m = 35, 56153, and 291311 plateaued after O(n) circuit layers.The plotted measure was the probability of finding the correct factors, shown as a function of circuit-layer count.Source: A. Depth Scaling · pp. 10–11
- Factoring is efficient to check, so samples from the optimized VQF ansatz can be tested until the correct factors are found.The reported squared overlap measures overlap with assignments of all p_i and q_i, not necessarily all carry bits z_ij.Source: A. Depth Scaling · p. 11
- Depth scaling was poorer for m = 77, 1207, and 33667, including instances requiring no more qubits than some better-scaling cases.The authors note that these instances lack p ↔ q symmetry and contain carry bits, but say further insight is needed to explain the discrepancy.Source: A. Depth Scaling · p. 11
B. Noise Scaling
The section tests how Pauli-channel noise affects VQF, finding weak dependence on the noise rate below a threshold. The simulations include sampling noise and examine two factoring instances.
B. Noise Scaling
- The simulations apply a Pauli channel after each unitary and after preparing |+>⊗n.The single-qubit error rate is ε; cost-function estimates use ν = 10000 samples.Source: B. Noise Scaling · p. 11
- Noise effects are examined across two VQF instances as a function of error rate.The instances’ dependence on noise rate is plotted in Figure 4.Source: B. Noise Scaling · p. 11
- Below a certain error threshold, VQF is weakly dependent on the noise rate.The study examines two VQF instances and includes sampling noise when estimating the cost function.Source: B. Noise Scaling · p. 11
V. DISCUSSION
The discussion presents VQF as a hybrid factoring approach that may suit near-term devices and could be competitive with Shor’s algorithm in an error-corrected setting. Its scalability and resource requirements remain open questions.
V. DISCUSSION
- The discussion frames factoring as relevant to public-key cryptography and notes that Shor implementations for cryptographically relevant integers would require thousands of error-corrected qubits.The text says this exceeds what near-term noisy intermediate-scale devices can provide.Source: §V · pp. 11–12
- Below a certain error threshold, success probability is approximately independent of the noise rate.The error bars represent one standard deviation over three runs.Source: §V · p. 12
- VQF uses classical preprocessing and post-processing, which may make it more amenable to factoring on quantum computers in the next decade.The authors state that whether it scales asymptotically under realistic optimization constraints and quantum-device noise remains to be seen.Source: §V · p. 12
- In an error-corrected setting, VQF trades off coherent-gate count against repetitions and could be competitive with Shor’s algorithm.The authors say further work is needed to compare the resources required by the two approaches.Source: §V · p. 12
- Preliminary numerics suggest that carry-bit presence negatively affects VQF, with little dependence on the number of carry bits at fixed problem size.The discussion identifies explaining difficult factoring instances and comparing resource requirements as open work.Source: §V · p. 13
- The authors say more numerical and analytical studies are needed to understand VQF’s potential scalability under realistic NISQ conditions.They also look forward to experimental implementations on current NISQ devices.Source: §V · pp. 12–13