We introduce a sparse Walsh-Pauli correlation encoding for MaxCut, in which graph variables are represented by diagonal Pauli-string expectation values computed classically as normalized XOR autocorrelations of Walsh coefficients. The complete Walsh basis can reproduce the diagonal correlators of arbitrary quantum states, while a structured sparse support reduces the number of trainable coefficients to $m+1$ for $m$ graph variables. We evaluate the method on $1{,}400$ held-out random graphs with up to $7{,}000$ vertices, obtaining empirical approximation ratios near $0.98$ relative to MQLib heuristic references. On Gset instances G14, G23, G60, and G64, the sparse model achieves mean refined approximation ratios of $0.9828$, $0.9926$, $0.9781$, and $0.9369$, respectively, with $80.4\%$-$89.3\%$ fewer parameters than the complete Walsh representation. The trained coefficients are transferred without retraining to quantum circuits. Statevector simulations of the four Gset instances achieve fidelities above $0.99994$ and preserve all correlator signs. Separately, a seven-qubit experiment on a $15$-vertex graph executed on IBM quantum hardware achieves a correlator-sign agreement of $0.927\pm0.049$ relative to the corresponding noiseless circuit. These results demonstrate the potential of sparse Walsh-PCE for large-instance quantum-inspired MaxCut optimization while validating the transfer of classically trained parameters to quantum hardware.
We introduce a sparse Walsh-Pauli correlation encoding for MaxCut, in which graph variables are represented by diagonal Pauli-string expectation values computed classically as normalized XOR autocorrelations of Walsh coefficients. The complete Walsh basis can reproduce the diagonal correlators of arbitrary quantum states, while a structured sparse support reduces the number of trainable coefficients to m+1 for m graph variables. We evaluate the method on 1,400 held-out random graphs with up to 7,000 vertices, obtaining empirical approximation ratios near 0.98 relative to MQLib heuristic references. On Gset instances G14, G23, G60, and G64, the sparse model achieves mean refined approximation ratios of 0.9828, 0.9926, 0.9781, and 0.9369, respectively, with 80.4%-89.3% fewer parameters than the complete Walsh representation. The trained coefficients are transferred without retraining to quantum circuits. Statevector simulations of the four Gset instances achieve fidelities above 0.99994 and preserve all correlator signs. Separately, a seven-qubit experiment on a 15-vertex graph executed on IBM quantum hardware achieves a correlator-sign agreement of 0.927±0.049 relative to the corresponding noiseless circuit. These results demonstrate the potential of sparse Walsh-PCE for large-instance quantum-inspired MaxCut optimization while validating the transfer of classically trained parameters to quantum hardware.
Quantum approaches for combinatorial optimization problems have attracted considerable attention in recent years. Among these approaches, Pauli Correlation Encoding (PCE) has emerged as a promising framework for quantum devices with limited qubit resources because it embeds optimization variables in expectation values of Pauli strings. However, the mechanisms underlying its performance and the reasons for its saturation remain unclear. In this work, we investigate these questions through a systematic analysis of expressivity and trainability. First, we compare PCE with classical surrogate models based on tensor networks whose structures progressively approach the topology of the PCE circuit. The results show that PCE attains comparable solution quality with substantially fewer trainable parameters, indicating strong parameter efficiency. Second, to determine whether the performance saturation of conventional PCE is caused by insufficient expressivity or by optimization difficulty, we perform a diagnostic expressivity test in which the circuit is trained toward reference configurations for Max-Cut. The results show that even shallow PCE circuits can represent strong solutions, indicating that the main bottleneck is not the representational power of the ansatz, but the trainability under the relaxed objective function. Motivated by this finding, we propose a multistage continuation framework that gradually transforms a smooth relaxed objective into a sharper objective that more closely approximates the target discrete problem. Numerical experiments on G-set instances with 800 vertices show that the proposed method consistently outperforms conventional PCE and is competitive with representative graph neural network (GNN) methods. These results clarify the main factors behind PCE performance and provide a practical strategy for improving PCE on quantum devices with limited qubit resources.
Pauli correlation encoding (PCE) encodes m binary variables in the signs of k-body Pauli correlators of n=O(m1/k) qubits, and trains a parameterized circuit on a relaxed loss of sharpness α. The strongest published schedules sharpen this loss aggressively and are benchmarked with exact expectation values, whereas a quantum computer estimates correlators from a finite number of shots. We show that the sharpness is a hidden shot budget. Since the expected sign of a correlator estimated from S shots, erf(cS/2), agrees with tanh(0.851Sc) to within 0.019, the edge term of the relaxed loss at α=0.851S approximately equals, up to a constant, minus twice the cut expected from decoding S shots. This explains why schedules tuned with exact expectation values lose their advantage at realistic budgets, and yields a shot-aware schedule whose final sharpness is set by the shot budget. On five G-set graphs with 800 variables on 13 qubits, this schedule outperforms every published schedule at its target budget in all 150 paired comparisons of the decoded circuit output, owing to the sharpness at 1.6×104 shots and mostly to switching off the regularization at 103; after a classical bit-swap search, it remains the best on average at 1.6×104 shots. Device noise damps the correlators by a factor s, which amounts to a smaller shot budget s2S. On the IBM Heron processor ibm_fez, an all-to-all ansatz of the type used for the best published G-set results compiles to 835 CZ gates and decodes to a random cut, while our 96-CZ hardware-native circuit, trained in simulation and sharpened to α≃0.65sS, retains up to 0.919 of the best-known cut. For new circuits, a damping and an offset calibrated on other circuits of the same graph predicted the decoded cuts at 103 shots to within 0.002.
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.
Pauli Correlation Encoding (PCE) compresses m binary variables onto n=O(m1/k) qubits by mapping them to commuting Pauli correlators, but its continuous expectation values must be decoded into feasible binary solutions, a challenge for dense-constraint problems. We apply PCE to mRNA secondary-structure prediction, formulated as a densely constrained QUBO, and train with a QUBO-space sigmoid loss thatpreserves the QUBO penalty structure. For decoding, we introduce the Problem-Aware Guided Decoder (PAGD), which scores candidate variable commitments by combining marginal QUBO energy reduction with a trained expectation-value prior and constraint-aware feasibility pruning. On six benchmark mRNA sequences (30-60 nt, 50-240 variables, 7-14 qubits), PAGD with 100 restarts achieves 75-100 percent near-optimal recovery, defined as P(gap<1%), for sequences up to 152 variables, compared with 0-30 percent for a sign-rounding plus local-search baseline. On the 240-variable instance, trained PAGD reaches 50 percent P(gap<1%) at 200 restarts, outperforming untrained-circuit and random-expectation-value controls. Hardware-scale tests extend the pipeline to three 102-105 nt instances (694-745 variables, 172,000-193,000 pair constraints, 23 qubits) on IBM Heron processors. The circuits transpile SWAP-free into 480 native two-qubit gates at depth 256, and PAGD decoded gaps on QPU runs match or beat simulator means for all three instances, including exact CPLEX-optimum recovery for one sequence. These results show that PCE-trained priors can survive deployment to noisy superconducting hardware at biologically relevant scale.
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 Parity Architecture was originally introduced in the context of quantum optimization algorithms to overcome hardware connectivity constraints. Here, we show that its benefits extend beyond this role by identifying specific parity transformations that enhance the success probability of the Quantum Approximate Optimization Algorithm (QAOA) for optimization problems defined on hardware-native and sparse graphs. Numerical simulations suggest that this enhancement originates from the higher-order operators introduced by the Parity representation, which accelerate the propagation of correlations across the physical device. We investigate this mechanism for the Signed Max-Cut problem on 3-regular graph instances and demonstrate its practical relevance on IBM Heron quantum processors. QAOA parameters are first classically optimized on small training instances containing up to 14 vertices and subsequently transferred to larger instances executed on quantum hardware. We consider Signed Max-Cut instances of up to 40 vertices and find that, together with an error mitigation technique, the parity-based QAOA identifies the optimal solutions for all the considered 40-vertex instances, whereas the conventional QAOA fails under the same conditions.