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.
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.
The continuous progress of quantum technologies has spurred the exploration of their potential applications across diverse fields, particularly in combinatorial optimisation. In this work, we study a quantum-classical optimisation framework based on Pauli Correlation Encoding, an encoding scheme that can represent m binary variables using a polynomial number of qubits. To evaluate the performance of the method, we use three classical optimisation problems against the instances of the QOPTLib benchmark. The study includes an analysis of the impact of the compression order of the encoding scheme, the problem structure, and hyperparameter selection on solution quality, as well as the role of post-processing in improving performance. Additionally, we study the effect of shot-based execution and hardware noise, showing how these factors influence both the accuracy of expected value estimation and the overall dynamics of the optimisation process. The results indicate that the proposed PCE-based framework achieves competitive performance against the benchmark and, in several cases, obtains equivalent or even superior solutions, highlighting its potential as an efficient encoding strategy for quantum optimisation in the NISQ and near fault-tolerant era.
Pauli Correlation Encoding (PCE) reduces the qubit requirements of quantum optimization by embedding the problem variables into the expectation values of Pauli observables, so that the number of qubits can be much smaller than the number of variables. PCE has not yet been studied for constrained optimization. We extend it to constrained combinatorial problems, using the budget-constrained MinCut as a case study, and show that the standard formulation fails to reliably enforce the constraint: feasibility hinges on the binarization of the encoded variables, which depends sensitively on hyperparameters that are hard to tune and do not transfer across instances. To address this, we introduce Progressive-Binarization PCE (PB-PCE), an adaptive continuation scheme that progressively increases the binarization parameter while re-optimizing the circuit from the previous solution, driving the variables towards the binary domain. PB-PCE attains near-complete constraint satisfaction (88--100\%) and smaller cut sizes than standard PCE, with a number of stages (10--20) essentially independent of problem size, solving instances of up to 300 variables with only 9-qubit circuits.
Pauli Correlation Encoding (PCE) is a heuristic framework for binary optimisation that encodes classical variables into many-body Pauli observables. While PCE requires fewer qubits than other approaches, it relies on estimating a large number of Pauli expectation values whose signs determine the variables' values, which can incur substantial measurement overhead. Here, we introduce efficiently simulable PCE, a class of dequantised PCE realisations where all expectation values needed can be computed efficiently classically. We instantiate this idea using free-fermionic evolutions, realised by matchgate circuits, and Instantaneous Quantum Polynomial (IQP) circuits. On MaxCut, Maximum Independent Set, Multi-Dimensional Knapsack, and Max3SAT benchmarks, these methods produce high-quality solutions across problem sizes ranging from tens to thousands of variables. Our results show that PCE is naturally understood as a correlation-based optimisation framework with both quantum and classically simulable realisations. This yields a dequantised baseline for evaluating future quantum PCE implementations.
Compressed quantum encodings aim to overcome hardware limitations towards tackling challenging problems at scale, with many classical variables mapped onto noncommuting observables of fewer qubits. Classically, relaxations such as the semidefinite program formulation of MaxCut trade solution quality for computational efficiency. By contrast, quantum relaxations based on compression can amplify the worst-case complexity of the problem being solved. We study quantum random access optimization (QRAO), a special case of the Pauli correlation encoding (PCE) framework that assigns up to three binary variables to the Pauli X, Y, and Z observables of each qubit, with the packing choices determining the compressed Hamiltonian to be optimized. We identify explicit QRAO optimal energy promise problems complete for NP, StoqMA, and QMA, with inverse-polynomial promise gaps for the latter two. Our problem reductions preserve inverse-polynomial promise gaps without requiring gadgets or ancillas. For any prescribed packing, we show that weighted MaxCut instances compress, up to a known shift and rescaling, to arbitrary nonnegative-weight pairwise Pauli couplings allowed by the packing. For QRAO, using one aligned axis gives an NP-complete energy problem. Using two or three positive aligned Pauli axes generally gives QMA-complete problems, with bipartite restrictions in BQP ∩ StoqMA.
We show that this computational hardness survives compilation and is practically relevant. Notably, this result applies directly to the current QRAO compiler implementation in Qiskit Optimization 0.7.0, confirming our hardness results are not artifacts of artificial or contrived packing rules. Altogether our results identify worst-case complexity barriers arising from quantum compression, while making no broad claims about typical cases or the performance and trainability of algorithm pipelines that use it.
The increasing complexity of 5G and emerging 6G wireless networks has intensified the need for scalable optimization techniques capable of addressing computationally challenging combinatorial problems. While quantum optimization offers a promising alternative, current near-term quantum hardware remains limited by qubit availability, noise, and scalability constraints. Pauli Correlation Encoding (PCE) has emerged as a qubit-efficient optimization framework that addresses these challenges through polynomial variable compression. However, the impact of compression on representability and solution recovery remains poorly understood. In this work, we investigate the hypothesis that increasing compression ratios introduce representability constraints arising from algebraic closure relationships among encoded Pauli observables. Using Maximum Independent Set benchmark problems, we evaluate multiple PCE ansatz designs and compression ratios. We find that ansatz selection is critical to both solution quality and feasibility, with two ansatz families consistently outperforming alternatives and achieving approximation ratios approaching 0.9. Furthermore, increasing circuit repetitions provides limited benefit and can degrade performance. Most notably, reducing compression by increasing the number of available qubits significantly improves raw solution quality, while post-processed performance remains comparatively stable. These findings suggest that representability effects play an important role in compressed PCE encodings and provide new insight into the relationship among compression, ansatz design, decoding, and solution quality in scalable quantum optimization.
Abstract Quantum computing is gaining popularity across a wide range of scientific disciplines due to its potential to solve long-standing computational problems that are considered intractable with classical computers. One promising area where quantum computing has potential is in the speed-up of NP -hard optimisation problems that are common in industrial areas such as logistics and finance. Newcomers to the field of quantum computing who are interested in using this technology to solve optimisation problems do not have an easily accessible source of information on the current capabilities of quantum computers and algorithms. This paper aims to provide a comprehensive overview of the theory of quantum optimisation techniques and their practical application, focusing on their near-term potential for noisy intermediate scale quantum devices. The paper starts by drawing parallels between classical and quantum optimisation problems, highlighting their conceptual similarities and differences. Two main paradigms for quantum hardware are then discussed: analogue and gate-based quantum computers. While analog devices such as quantum annealers are effective for some optimisation problems, they have limitations and cannot be used for universal quantum computation. In contrast, gate-based quantum computers offer the potential for universal quantum computation, but they face challenges with hardware limitations and accurate gate implementation. The paper provides a detailed mathematical discussion with references to key works in the field, as well as a more practical discussion with relevant examples. The most popular techniques for quantum optimisation on gate-based quantum computers, the quantum approximate optimisation algorithm and the quantum alternating operator ansatz framework, are discussed in detail. However, it is still unclear whether these techniques will yield quantum advantage, even with advancements in hardware and noise reduction. The paper concludes with a discussion of the challenges facing quantum optimisation techniques and the need for further research and development to identify new, effective methods for achieving quantum advantage.