arXiv:2610.26381
Higher-order Parity Constraints for Quantum Approximate Optimization
Anita Weidinger, Glen Bigan Mbeng, Roeland ter Hoeven, Wolfgang Lechner
Abstract
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.
AI Summary
The paper asks whether parity-encoded QAOA can improve optimization on sparse or hardware-native graphs, beyond avoiding connectivity mismatch. It studies signed Max-Cut using parity constraints acting on more than four qubits, trading greater circuit depth per layer for a smaller graph-based “covering depth,” used as a proxy for correlation propagation. Evidence comes from noiseless simulations and IBM Heron experiments. On a hardware-native 21-vertex heavy-hex graph, the encoding uses 22 physical qubits and two 12-body constraints. Covering depth falls from 10 to 2, while two-qubit depth per layer rises from 3 to 12; parity QAOA nevertheless achieves higher ground-state sampling probability on the tested instance. For random 3-regular graphs, parameters optimized on 12 signed instances of one 14-vertex graph are averaged and transferred to larger instances. With 4,096 shots per circuit, truncated constraint circuits, and decoding through seven spanning trees, parity QAOA finds an optimum for all 20 tested 40-vertex signed instances; direct QAOA finds none. The experiments use one graph topology per size, and the correlation-propagation explanation is suggestive rather than established. For larger instances, noise prevents improvement with a second full parity layer, motivating constraint truncation. The optimized first layer is an efficiently classically sampleable product state that already yields useful decoded solutions; quantum advantage is not established. Parameter concentration with size, transfer under truncation, and the generality of the modified training objective remain open.
Error found: The abstract omits that the larger hardware demonstrations use truncated parity circuits retaining approximately half the constraints. The experiments demonstrate a combined parity-based pipeline advantage but do not isolate higher-order constraints or accelerated correlation propagation as its cause. The modified training objective multiplies the selected outcome's decoded energy by 1.2, which rewards rather than penalizes that outcome when its energy is negative.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.