Enhancing Pauli Correlation Encoding for Quantum Optimization via Expressivity Analysis and Objective Function Refinement

Pauli Correlation Encoding (PCE) is a quantum approximate optimization algorithm that tackles large combinatorial problems by encoding many classical binary variables into few qubits via Pauli correlators. While the original PCE achieves Goemans–Williamson (GW)–level performance on large Max-Cut instances, a gap to best-known solutions remains.

In this work, we analyze the expressivity and trainability of the PCE ansatz and propose an improved strategy to enhance its performance beyond that of the GW algorithm, approaching the best-known classical solutions. First, we verify that the PCE ansatz is expressive enough to represent exact solutions and redesign it accordingly. We then attribute the residual performance gap to a mismatch between the relaxed training objective and the discrete Max-Cut cost function. To address this issue, we introduce a two-stage optimization: after an initial convergence using standard parameters, we restart the optimization with a refined objective better aligned with the discrete cost. This approach leads to a further decrease in the saturated training loss, improving the approximation ratio by an average of 1.0%. The resulting performance sets a new state of the art among quantum baselines with exceptional qubit efficiency. Our findings highlight that careful objective function design and optimization scheduling are crucial for enhancing the performance of PCE.