Performance of parity QAOA for the signed max-cut problem
Open Access
- 24 February 2026
- journal article
- Published by IOP Publishing in New Journal of Physics
- Vol. 28 (3)
Abstract
The practical implementation of quantum optimization algorithms on noisy intermediate-scale quantum devices requires accounting for their limited connectivity. As such, the Parity architecture was introduced to overcome this limitation by encoding binary optimization problems onto planar quantum chips. We investigate the performance of the Quantum Approximate Optimization Algorithm on the Parity architecture (Parity QAOA) for solving instances of the signed Max-Cut problem on complete and regular graphs. By comparing the algorithms at fixed circuit depth, we demonstrate that Parity QAOA outperforms conventional QAOA implementations based on SWAP networks. Our analysis utilizes Clifford circuits to estimate lower performance bounds for Parity QAOA for problem sizes that would be otherwise inaccessible on classical computers. For single layer circuits we additionally benchmark the recursive variant of the two algorithms, showing that their performance is equal.Keywords
All Related Versions
Funding Information
- Horizon Europe (101113690 (PASQuanS2.1))
- Bundesministerium für Wirtschaft und Klimaschutz (QuaST)
- Austrian Science Fund (10.55776/F71)
- Austrian Science Fund (10.55776/Y1067)
- QuantERA (101017733)
- NextGenerationEU (FO999896208)
This publication has 39 references indexed in Scilit:
- Toward a linear-ramp QAOA protocol: evidence of a scaling advantage in solving some combinatorial optimization problemsnpj Quantum Information, 2025
- A review on Quantum Approximate Optimization Algorithm and its variantsPhysics Reports, 2024
- Space-efficient binary optimization for variational quantum computingnpj Quantum Information, 2022
- Efficient Encoding of the Weighted MAX $k$-CUT on a Quantum Computer Using QAOASN Computer Science, 2021
- Quantum approximate optimization of non-planar graph problems on a planar superconducting processorNature Physics, 2021
- Quantum algorithms: an overviewnpj Quantum Information, 2016
- Maximum balanced subgraph problem parameterized above lower boundTheoretical Computer Science, 2013
- Algorithmic and complexity results for decompositions of biological networks into monotone subsystemsBioSystems, 2007
- Direct search algorithms for optimization calculationsActa Numerica, 1998
- Some simplified NP-complete graph problemsTheoretical Computer Science, 1976