Pauli Correlation Encoding for Budget-Contraint Optimization

Abstract: Quantum optimization has gained increasing attention as advances in quantum hardware enable the exploration of problem instances approaching real-world scale. Among existing approaches, variational quantum algorithms and quantum annealing dominate current research; however, both typically rely on one-hot encodings that severely limit scalability. Pauli Correlation Encoding (PCE) was recently introduced as an alternative paradigm that reduces qubit requirements by embedding problem variables into Pauli correlations. Despite its promise, PCE has not yet been studied in the context of constrained optimization. In this work, we extend the PCE framework to constrained combinatorial optimization problems and evaluate its performance across multiple problem sizes. Our results show that the standard PCE formulation struggles to reliably enforce constraints, which motivates the introduction of the Iterative-$α$ PCE. This iterative strategy significantly improves solution quality, achieving consistent constraint satisfaction while yielding better cut sizes across a wide range of instances. These findings highlight both the limitations of current PCE formulations for constrained problems and the effectiveness of iterative strategies for advancing quantum optimization in the NISQ era.