Benchmarking Ansatze for Pauli Correlation Encoding in the Maximum Independent Set Problem
Abstract
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.
Related
- Certified Non-Degenerate Maximum-Likelihood Benchmarking of Quantum LDPC Decoders
- Benchmarking Quantum Feature Encoding Strategies for Binary Classification with QSVM
- Scalable quantum-enhanced greedy algorithm for the maximum independent set problems on random regular graphs
- Benchmarking Single-Photon Sources for Measurement-Device-Independent Quantum Key Distribution
- Maximum-Entropy Extension of Quantum Correlation Functions from Short Real-Time Dynamics
BibTeX
@misc{reeves2026benchmarking,
title = {{Benchmarking Ansatze for Pauli Correlation Encoding in the Maximum Independent Set Problem}},
author = {Cian C. Reeves and Aaron C. Kemp and Richard Padbury and Eva Lia Tarquini and Christoph Kloeffel and Vedangi Pathak and Hamed Mohammadbagherpoor and Vincent Beltrani},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03949},
eprint = {2610.03949},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03949},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Benchmarking Ansatze for Pauli Correlation Encoding in the Maximum Independent Set Problem
AU - Cian C. Reeves
AU - Aaron C. Kemp
AU - Richard Padbury
AU - Eva Lia Tarquini
AU - Christoph Kloeffel
AU - Vedangi Pathak
AU - Hamed Mohammadbagherpoor
AU - Vincent Beltrani
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.03949
UR - https://arxiv.org/abs/2610.03949
AB - 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.
ER -