Higher-order Parity Constraints for Quantum Approximate Optimization
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.
Related
- Binary Optimization with Complex Constraints via Quantum Approximate Multi-Objective Optimization
- Depth analysis of the Quantum Approximate Optimization Algorithm with a Grover mixer
- Optimal FALQON for Quantum Approximate Optimization via Layer-wise Parameter Tuning
- The Overlap Gap Property: Separating Quantum and Quantum-Inspired Approximate Optimization Algorithms
- Quantum Approximate Optimization via Noise-Directed Adaptive Warm-Starting
BibTeX
@misc{weidinger2026higherorder,
title = {{Higher-order Parity Constraints for Quantum Approximate Optimization}},
author = {Anita Weidinger and Glen Bigan Mbeng and Roeland ter Hoeven and Wolfgang Lechner},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26381},
eprint = {2610.26381},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26381},
}
RIS
TY - UNPB
TI - Higher-order Parity Constraints for Quantum Approximate Optimization
AU - Anita Weidinger
AU - Glen Bigan Mbeng
AU - Roeland ter Hoeven
AU - Wolfgang Lechner
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.26381
UR - https://arxiv.org/abs/2610.26381
AB - 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.
ER -