Can PCE solve the factorisation problem via optimisation?
Fernando Alonso, Colomán Samprón, Jacobo Veiga, Andrés Gómez
quant-ph, cs.CR
Submitted: 2026-07-26
Comments: 30 pages, including 55 references. 13 figures
Code: https://github.com/sotostzam/particle-swarm-optimization
License: http://creativecommons.org/licenses/by/4.0/
The gist: The ongoing progress in quantum technologies has fueled a sustained exploration of their potential applications across various domains, particularly in computational problems that are considered
Terminology
Abstract
The ongoing progress in quantum technologies has fueled a sustained exploration of their potential applications across various domains, particularly in computational problems that are considered intractable for classical systems. Among these problems, integer factorisation remains of special interest due to its relevance to widely used cryptographic schemes such as RSA. Among the different possibilities, one approach to factorisation is to convert the problem into a binary optimisation problem. However, current proposals usually need a large number of qubits that make them unfeasible within the current hardware. In this work, we investigate a possible adaptation of the Pauli Correlation Encoding (PCE) algorithm to the factorisation problem. Due to its compression capability, it can drastically reduce the number of needed qubits. The proposed approach explores how the structure and dynamics of the PCE framework may be employed to encode and analyze candidate factor relations within a quantum computational setting. Rather than presenting a replacement for established quantum factorisation methods, this study aims to provide a preliminary examination of the feasibility and limitations of the proposed adaptation. We discuss the algorithmic design, its conceptual relationship with existing quantum approaches, and the practical constraints associated with implementation on current or near-term quantum hardware. Initial observations suggest that the method may offer an alternative perspective for studying factorisation within the broader context of quantum computation, although no claim is made regarding computational advantage. These results are intended primarily as an exploratory contribution to ongoing research in quantum algorithms and computational number theory.
Sources
- How to factor 2048 bit RSA integers with less than a million noisy qubits
- Integer Factorization: Another perspective
- Revisiting Fermat's Factorization for the RSA Modulus
- Practical Challenges in Executing Shor's Algorithm on Existing Quantum Platforms
- Assessing the Benefits and Risks of Quantum Computers
- The State of Factoring on Quantum Computers
- Fundamental limitations on optimization in variational quantum algorithms
- Variational quantum algorithms on cat qubits
- Large-scale portfolio optimization using Pauli Correlation Encoding
- Progressive Binarization - Pauli Correlation Encoding: a Continuation Method for Constrained Optimization
- Benchmark of Pauli Correlation Encoding for different optimisation problems
- Quantum factorization of 56153 with only 4 qubits
- Variational Quantum Factoring
- Variational Quantum Eigensolver Approach to Prime Factorization on IBM's Noisy Intermediate Scale Quantum Computer
- On quantum factoring using noisy intermediate scale quantum computers
- Factoring integers with sublinear resources on a superconducting quantum processor
- Optimization Strategies for Variational Quantum Algorithms in Noisy Landscapes
Related papers
- Reconquering Bell sampling on qudits: stabilizer learning and testing, quantum pseudorandomness bounds, and more
- Encrypted clones can leak: Classification of informative subsets in Quantum Encrypted Cloning
- Polynomial-time classical and quantum simulation of quantum impurity models
- Theory of quantum-enhanced interferometry with general Markovian light sources
- A convergent hierarchy of spectral gap certificates for qubit Hamiltonians
- Universal Bound and Phase Transition in Many-Body Fermionic Non-Gaussianity