Can PCE solve the factorisation problem via optimisation?

This paper investigates the feasibility of applying Pauli Correlation Encoding (PCE) to the integer factorisation problem. Integer factorisation, particularly of semiprime numbers, is the backbone of RSA cryptography and remains computationally intractable for classical systems. While quantum algorithms like Shor’s offer a theoretical solution, they are not yet feasible on current Noisy Intermediate-Scale Quantum (NISQ) hardware. The authors explore whether the compression capabilities of PCE can reduce the qubit requirements for variational quantum factorisation, providing a new perspective on how to map these problems onto quantum hardware.

The researchers reformulate the factorisation of a composite integer N into a binary optimisation problem. By representing the factors as binary variables and translating the multiplication constraint N = p * q into a set of algebraic clauses, they construct a cost function whose global minimum corresponds to the correct factors. They then apply the PCE framework, which uses Pauli operator strings to encode a large number of binary variables into a significantly smaller number of qubits. The study tests two specific encoding strategies—the Basic approach and the DoTS approach—using a hardware-efficient brickwork ansatz to evaluate performance and scalability.

The study provides a conceptual framework for using PCE in computational number theory. The authors observe that while PCE allows for a reduction in the number of qubits, the optimisation landscape remains complex due to the combinatorial nature of the factorisation problem. The results serve as an exploratory contribution, highlighting the practical constraints of implementing such methods on near-term quantum hardware. The authors emphasize that this work is not a replacement for established methods but rather an alternative approach for future research into quantum-inspired optimisation.