The Art of Avoiding Constraints: A Penalty-free Approach to Constrained Combinatorial Optimization with QAOA

Prashanti Priya Angara, Ulrike Stege, Hausi Müller, Danylo Lykov, Yuri Alexeev · 2025

Read The Art of Avoiding Constraints: A Penalty-free Approach to Constrained Combinatorial Optimization with QAOA by Prashanti Priya Angara, Ulrike Stege, Hausi Müller, Danylo Lykov, Yuri Alexeev (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-10077.txt.

Description

Prashanti Priya Angara and co-authors tackle constrained problems with a quantum method called QAOA in 2025. Such problems allow only answers that meet set limits, but the quantum method is built for problems with no limits at all.

The usual fix adds penalty terms, yet picking the right penalty values is hard. The authors instead reshape the constrained problem into an unconstrained profit problem whose good answers line up with good answers to the first. They test the idea on three classic hard problems: vertex cover, independent set, and clique. Runs on two quantum software platforms show the approach can find optimal or near-optimal answers.

Catalog record

CREATORPrashanti Priya Angara, Ulrike Stege, Hausi Müller, Danylo Lykov, Yuri Alexeev
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE78 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-10077

Browse the full library · About the Tower of Babel