Source-linked AI summary
Quantum Annealing for Prime Factorization
Shuxian Jiang, Keith A. Britt, Alexander J. McCaskey, Travis S. Humble, Sabre Kais
TL;DR
Integer factorization is computationally hard for known deterministic classical algorithms and underlies widely deployed encryption. The paper maps factoring to executable Ising Hamiltonians for quantum annealing, reducing resource requirements and demonstrating factorizations on available hardware.
Problem
Known deterministic classical algorithms for integer factorization require exponential time in log N, motivating its role as a hardness assumption for encryption.
Method
The approach directly transforms a factorization optimization problem into an Ising Hamiltonian, using ancillary variables to reduce higher-body terms and modifying multiplication to fit hardware constraints.
Results
The demonstrated methods use O(log^2(N)) qubits overall and include factoring N = 59989 with 59 variables and N = 143 with factors 13 and 11.
Takeaways & Limitations
The resource-efficient methods were experimentally verified on D-Wave 2000Q hardware as proof-of-concept demonstrations of quantum-annealing factorization.
Takeaways & Limitations
The asymptotic complexity of the approach remains unresolved because it depends on the minimum spectral gap, whose complexity has not been classified.
Abstract
from arXiv · showhide
We have developed a framework to convert an arbitrary integer factorization problem to an executable Ising model by first writing it as an optimization function and then transforming the k-bit coupling ($k\geq 3$) terms to quadratic terms using ancillary variables. The method is efficient and uses $\mathcal{O}(\text{log}^2(N))$ binary variables (qubits) for finding the factors of integer $N$. The method was tested using the D-Wave 2000Q for finding an embedding and determining the prime factors for a given composite number. As examples, we present quantum annealing results for factoring 15, 143, 59989, and 376289 using 4, 12, 59, and 94 logical qubits respectively. The method is general and could be used to factor larger numbers
1 Introduction
Integer factorization is computationally difficult for known deterministic classical methods, motivating quantum approaches. The paper develops a direct quantum-annealing procedure that maps factorization to an Ising Hamiltonian using O(log^2(N)) binary variables and demonstrates it on D-Wave hardware.
- Motivation: Known deterministic classical factoring algorithms require time exponential in log N, motivating quantum methods for factorization.Integer factorization underlies the hardness assumption of RSA and other encryption methods.
- Approach: The paper introduces quantum annealing as a variant of quantum adiabatic computation for solving integer factorization problems.The approach directly transforms the factorization problem into an executable Ising Hamiltonian.
- Approach: The direct formulation represents factors with binary variables, defines f(x) = (N−pq)^2, and minimizes this cost function.The factor bit lengths determine the binary representations of p and q.
- Approach: Higher-order terms are reduced to quadratic form by introducing auxiliary variables and adding penalty terms for constrained variable replacements.This produces an Ising function specified by local fields and pairwise couplings.
- Resource requirements: The resulting methods use O(log^2(N)) qubits, while the modified multiplication-table method also reduces coefficient ranges and higher-body terms for hardware implementation.The latter scheme uses roughly log^2(N)/4 binary variables and reduces the precision required by control hardware.
- Results: D-Wave experiments recovered the factors of 143 and used 59 variables for 59989, demonstrating the method on increasingly larger instances.For 143, the reported ground states correspond to p = 13, q = 11 or the reversed assignment; the 59989 construction uses auxiliary, factor, and carry variables.
2 Conclusions
The paper presents general quantum-annealing methods that encode integer factorization as Ising Hamiltonians using O(log^2(N)) qubits. Experiments on D-Wave 2000Q demonstrate the approach, while its asymptotic complexity remains unresolved.
- The authors present two general methods for factoring integers by converting factorization problems into Ising Hamiltonians.
- Both methods use O(log^2(N)) qubits in total.
- The methods were experimentally demonstrated on D-Wave 2000Q hardware as a proof of concept.
- The approach may support factoring larger numbers as quantum-annealing hardware gains qubits and parameter precision.
- The asymptotic complexity of the approach remains an outstanding question because it depends on the minimum spectral gap.
A.1 Factoring N = 15 = 5 × 3
For N = 15, the factorization objective is expanded into a polynomial in binary variables and then transformed into a quadratic Ising energy function.
- The factors are represented with binary variables as p = (x1x1)_2 and q = (x2x3x1)_2.
- The initial cost function is expanded into linear, quadratic, and cubic terms in x1, x2, and x3.
- Replacing the cubic product with an ancillary variable yields a quadratic polynomial in x1, x2, x3, and x4.
- The quadratic binary polynomial is converted into an Ising energy function over spin variables s1, s2, s3, and s4.
A.2 Factoring N = 143 = 13 × 11
For N = 143, the method constructs block equations, squares their residuals to form a cost function, reduces higher-order terms with ancillary variables, and maps the result to a 12-spin Ising Hamiltonian.
- The multiplication constraints are divided into blocks and expressed as two block equations for the factor and carry variables.
- The cost function is defined as the sum of squares of the equation residuals.
- Positive and negative higher-order terms are reduced to quadratic terms using ancillary-variable replacement rules.
- The resulting cost function introduces ancillary variables t1 through t4 for products of factor bits.
- A variable transformation maps the 12 binary variables to spin variables s1 through s12 and produces an Ising Hamiltonian with local fields and couplings.
A.3 Factoring N = 59989 = 251 × 239
For N = 59989 = 251 × 239, the construction uses a binary multiplication table whose carry lengths are determined block by block.
- Carry lengths are selected from the maximum carry generated by the variables in the block to the right.
- The rightmost nontrivial block has maximum carry 3, represented by the two-bit carry c2c1.
- The multiplication table is organized into blocks for 251 × 239 = 59989 in binary.
A.4 Factoring N = 376289 = 659 × 571
The section presents the binary multiplication table for 659 × 571 = 376289 and identifies the carry groups used in the construction. It also notes an overlap in column 214.
- The carry groups are organized as c14c13, c12c11c10, c9c8c7c6, c5c4c3, and c2c1.
- The multiplication-table construction has overlaps in column 214.
A.5 Range of Coefficients
The coefficient-range analysis bounds intermediate sums and carries using logarithmic scaling in N. It concludes that the final quadratic cost function has polynomially large coefficients, typically with O((log(N))^2) scaling in most cases.
- The factor lengths l1 and l2 are defined relative to log(N).
- For three-column blocks, the sum is bounded by 7l2+7 under all-one unknown bits and carries.
- The current-block sum and carry lengths are both O(log(log(N))).
- The combined coefficient range is bounded by log(N) for the stated three-block construction.
- The final quadratic cost function has polynomially large coefficients, usually scaling as O((log(N))^2).The analysis gives O((log(N))^3) in the majority-case bound before noting that most terms in different blocks are distinct.