Can PCE solve the factorisation problem via optimisation?

Technical Summary: Can PCE Solve the Factorisation Problem via Optimisation?

Problem Statement
Integer factorisation, particularly of semiprime numbers ($N = p \cdot q$), is a foundational problem in computational number theory and the security basis for RSA cryptography. While Shor's algorithm offers a polynomial-time quantum solution, current Noisy Intermediate-Scale Quantum (NISQ) hardware lacks the qubit count and coherence required for practical implementation. Alternative approaches, such as Variational Quantum Algorithms (VQAs) that convert factorisation into binary optimisation problems, face scalability issues, typically requiring a number of qubits that scales linearly with the number of binary variables. This linear scaling renders them unfeasible for large-scale instances on current hardware. The paper investigates whether Pauli Correlation Encoding (PCE), a framework capable of encoding $m$ binary variables using a polynomial number of qubits ($n \ll m$), can be adapted to solve the factorisation problem via optimisation with limited resources.

Methodology
The study reformulates the factorisation problem as a binary optimisation task and applies PCE to reduce qubit requirements. The methodology involves:

1. Encoding Strategies: Two distinct approaches were developed to map the factorisation constraints into a cost function:
   • Basic Approach: Directly encodes the binary representations of the unknown factors $p$ and $q$. The cost function minimises the squared Hamming distance between the target integer $N$ and the candidate product $x_p \cdot x_q$, with penalties to avoid trivial solutions (e.g., $N \cdot 1$).
   • Difference of Two Squares (DoTS) Approach: Reformulates the problem as finding integers $a$ and $b$ such that $a^2 \equiv b^2 \pmod N$ (with $a \not\equiv \pm b$). The factors are recovered via $\gcd(a-b, N)$ and $\gcd(a+b, N)$. The cost function combines a term enforcing the modular congruence with a term verifying the resulting factorisation.
2. Quantum Circuit: A hardware-efficient "brickwork" ansatz was employed, consisting of alternating layers of single-qubit rotations ($R_X, R_Y, R_Z$) and entangling gates ($R_{XX}, R_{YY}, R_{ZZ}$). The PCE compression order $k$ determines the circuit depth and the number of qubits required ($n \approx m/k$).
3. Optimisation: The parameterised quantum circuits were simulated classically using Qiskit Aer. The optimisation was performed using three gradient-free algorithms: Differential Evolution (DE), Particle Swarm Optimisation (PSO), and Quantum Delta Particle Swarm Optimisation (QDPSO). The sign function was used to approximate binary variables, avoiding the hyperbolic tangent relaxation to prevent infinite real-valued solutions.

Key Contributions and Results

• Resource Reduction: The study demonstrates that PCE can drastically reduce the number of qubits required for factorisation. For typical RSA key lengths, the required qubits remain within an "affordable" range for current or near-term hardware, and for compression orders $k > 2$, the problem can be solved entirely on classical computers via quantum circuit emulation.
• Performance Comparison:
  • DoTS vs. Basic: The DoTS approach consistently outperformed the Basic approach. The DoTS cost function, which captures the arithmetic structure of the difference-of-squares relation, yielded higher success rates and a more favourable optimisation landscape.
  • Optimiser Sensitivity: Differential Evolution (DE) proved to be the most robust optimiser, achieving successful factorisations across various bit-lengths. Swarm-based methods (PSO, QDPSO) exhibited significantly lower success rates, suggesting the optimisation landscape is challenging for these specific algorithms.
  • Scalability Limits: The method successfully factored semiprimes up to 36 bits using the DoTS approach with $k=4$ and DE. Success rates declined for integers larger than 25–36 bits, indicating intrinsic limitations in the current cost function formulations for larger instances.
• Search Efficiency: Analysis of the number of objective function evaluations showed that the algorithm does not rely on brute-force exploration. The number of evaluations remained several orders of magnitude below the size of the combinatorial search space ($2^n$), indicating a guided search process.

Significance and Claims
The paper positions this work as a preliminary, exploratory contribution rather than a definitive solution or a claim of computational advantage over existing algorithms.

• Feasibility: The primary finding is that PCE-based algorithms are a plausible framework for studying factorisation as an optimisation problem with limited quantum resources. It offers an alternative perspective to established methods like VQF and QAOA by decoupling the number of variables from the number of qubits.
• Limitations: The authors explicitly state that the current formulations do not scale successfully to cryptographically relevant integer sizes (e.g., 2048-bit RSA). The success of the method is heavily dependent on the design of the classical cost function and the choice of optimiser.
• Future Directions: The study suggests that future research should focus on:
  • Designing more informative cost functions that better capture the arithmetic structure of factorisation (potentially incorporating carry variables).
  • Exploring balanced factor assumptions (common in RSA) to reduce variable counts.
  • Investigating warm-start strategies and alternative ansatz architectures.
  • Evaluating performance under realistic noise models.

In conclusion, while the method does not currently threaten RSA security, it establishes a viable, resource-efficient framework for investigating factorisation via quantum-inspired optimisation, warranting further research into cost function design and algorithmic refinements.