arXiv:2610.03949
Benchmarking Ansatze for Pauli Correlation Encoding in the Maximum Independent Set Problem
Cian C. Reeves, Aaron C. Kemp, Richard Padbury, Eva Lia Tarquini, Christoph Kloeffel, Vedangi Pathak, Hamed Mohammadbagherpoor, Vincent Beltrani
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.
AI Summary
The paper asks how circuit ansatz and variable compression affect solution quality and feasibility in Pauli Correlation Encoding (PCE) for maximum independent set (MIS). PCE assigns binary variables to signs of Pauli expectation values; the encoding uses same-axis, weight-two strings, supporting $3\binom{n}{2}$ variables on $n$ qubits. Four brickwork ansatze are compared using ideal matrix-product-state simulations, COBYLA optimization, one to three circuit repetitions, and five initializations per configuration. Tests cover nine geometric MIS instances with 134, 314, or 569 vertices, encoded on 10, 15, or 20 qubits. Solutions are assessed against CPLEX optima, including feasibility, primarily after classical one-bit-flip local search. Ansatze A and D give the strongest reported results: their best post-processed approximation ratios are typically $0.85$–$0.89$, reaching $1.00$ on one 134-vertex instance. D shows less run-to-run variation on larger instances. Additional repetitions generally offer limited improvement and sometimes degrade results. For three fixed 134-vertex instances, increasing qubits from 10 to 20 improves raw approximation ratios by $0.08$, $0.22$, and $0.19$, while post-processed performance changes little. The discussion links compression effects to algebraic dependencies among Pauli observables near extremal expectation values, but does not establish this mechanism: improved access to short-range correlators is another proposed explanation. Raw solutions remain poor enough to require post-processing. The study is restricted to ideal simulations, selected instances, and limited optimization settings; measurement overhead, noise, and quantum advantage are not evaluated.
Error found: The compression experiment simultaneously changes qubit count, the binarization parameter alpha and ansatz expressivity, so it cannot isolate representability as the cause of improved raw solutions. The reported compression trend is tested only on three 134-node graphs using ansatz D and five initializations per setting, leaving its generality unestablished. The discussion incorrectly asserts that retaining N_q−1 order-two Pauli strings necessarily creates dependence among encoded variables; same-axis strings forming a spanning tree admit all simultaneous eigenvalue assignments.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 11 pages, 6 figures