SCOOP: A Quantum-Computing Framework for Constrained Combinatorial Optimization

Prashanti Priya Angara, Emily Martins, Ulrike Stege, Hausi Müller · 2025

Read SCOOP: A Quantum-Computing Framework for Constrained Combinatorial Optimization by Prashanti Priya Angara, Emily Martins, Ulrike Stege, Hausi Müller (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-2504-10897.txt.

Introduction

Prashanti Priya Angara and co-authors frame bound pick tasks for quantum-class solvers by way of free twins. The work dates to 2025. True pick tasks oft bear hard bounds that bare solvers can't hold. Near-best picks, fast, are the work aim in the field.

Their frame turns each bound task to a free twin task. The quantum solver works the twin, then a desk step trims picks back to the bound space. Three hard tasks ground the show, from guard sets to match and cover picks. Sim runs on a known stage proved the frame works and scales. Each task ties to a live use, from stock to webs.

Catalog record

CREATORPrashanti Priya Angara, Emily Martins, Ulrike Stege, Hausi Müller
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE51 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-10897

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

SCOOP: A Quantum-Computing Framework for Constrained Combinatorial Optimization Thanks: This research was supported in part by a National Sciences and Engineering Research Council (NSERC) of Canada Collaborative Research and Training Experience (CREATE) grant on Quantum Computing, NSERC Alliance Consortium Grant entitled Quantum Software Consortium – Exploring Distributed Quantum Solutions for Canada (QSC), and NSERC Alliance grant on Quantum Computing for Optimal Mobility. Corresponding author: [email protected] Prashanti Priya Angara, Emily Martins, Ulrike Stege, Hausi Müller Abstract While the ultimate goal of solving computationally intractable problems is to find a provably optimal solutions, practical constraints of real-world scenarios often necessitate focusing on efficiently obtaining high-quality, near-optimal solutions. The Quantum Approximate Optimization Algorithm (QAOA) is a state-of-the-art hybrid quantum-classical approach for tackling these challenging problems that are encoded using quadratic and higher-order unconstrained binary optimization problems (QUBO and HUBO). We present SCOOP, a novel QAOA-based framework for solving constrained optimization problems. SCOOP transforms a constrained problem into an unconstrained counterpart, forming SCOOP problem twins . The QAOA quantum algorithm operates on the unconstrained twin to identify potential optimal and near-optimal solutions. Effective classical post-processing reduces the solution set to the constrained problem space. Our SCOOP approach is solution-enhanced, objective-function-compatible, and scalable. We demonstrate the framework on three NP-hard problems, Minimum Dominating Set , Minimum Maximal Matching , and Minimum Set Cover appearing in practical application domains such as resource allocation, communication networks, and machine learning. We validate SCOOP’s feasibility and effectiveness on Xanadu PennyLane simulators. I Introduction When solving optimization problems, we often seek methods that not only determine optimal solutions but also identify near-optimal solutions. In applications where trade-offs between accuracy, efficiency, and practicality are paramount, identifying near-optimal solutions can hold significant value over solely seeking optimal solutions. We also seek methods that are scalable; one approach that hampers scalability is problem-specific tuning (e.g., penalty parameter tuning). Quantum computing offers promising avenues to tackle optimization problems, especially classically intractable combinatorial optimization problems (COPs). Both quantum annealing (QA) [ 1 ] and the quantum approximate optimization algorithm (QAOA) [ 2 ] are well-suited techniques. However, to apply these methods, the original COP must be transformed to be encoded on a quantum computer. The QAOA is a variational quantum algorithm specifically designed to solve unconstrained COPs on gate-based quantum hardware. The Ising model [ 1 , 3 ] is widely used in quantum combinatorial optimization because it provides a natural mathematical structure for encoding binary decision problems in a way that maps directly onto quantum hardware and algorithms like QA or QAOA. The field of quantum optimization relies heavily on Ising model formulations that use quadratic terms due to their direct compatibility with QA hardware. Gate-based hardware has no such restriction, as higher-order terms can be encoded natively using multi-qubit gates [ 4 ] . The higher order unconstrained binary optimization (HUBO) formulation offers a more expressive way to represent many optimization problems by directly incorporating multi-way ( K -local) interactions between variables [ 5 ] . Rapid advancements in gate-based quantum computers, particularly in qubit fidelity and connectivity, are paving the way for more effective handling of multi-qubit interactions [ 6 ] , and consequently the encoding of HUBO problems. TABLE I : SCOOP twins : NP-hard constrained COPs that allow the derivation of an unconstrained transformational equivalent COPs. Legend : MinVC : Minimum Vertex Cover, MaxIS : Maximum Independent Set, MaxCl : Maximum Clique Constrained Twin Unconstrained Twin Constraint Avoided Classical Post-processing MinDS [Sec. IV ] MaxPD (HUBO) Vertex domination Add vertices [Alg. 1 ] M 3 [Sec. V ] MaxPES (HUBO) Maximality, matching Add edges [Alg. 2 ], Ensure matching [Alg. 3 ] MinEDS [Sec. V ] MaxPES (HUBO) Edge domination Add edges [Alg. 2 ] MinIEDS [Sec. V ] MaxPES (HUBO) Edge domination, edge independence Add edges [Alg. 2 ], Ensure independence of edges [Alg. 3 ] MinSC [Sec. VI ] MaxPSC (HUBO) Set cover Add elements [Alg. 4 ] MinVC MaxPC (QUBO) Edge coverage Add vertices [ 7 , 8 ] MaxIS MaxPI (QUBO) Edge coverage Remove conflicted vertices [ 9 , 8 ] MaxCl MaxPCl (QUBO) Complete subgraph Remove conflicted vertices in complement graph [ 10 , 8 ] Constrained COPs involve constraints that limit the set of feasible solutions, thereby restricting the solution space. To model constrained COPs, penalties are typically introduced to discourage infeasible solutions [ 11 ] . While this approach guarantees to retain optimal solutions, it can encourage non-optimal infeasible solutions, since choosing optimal penalty values is challenging [ 12 , 13 ] . The field of quantum computing and optimization has seen significant advancements in recent years, with extensive studies on QUBOs and penalty methods to encode COPs. In 2014, Farhi introduced the QAOA technique [ 2 ] , which is specifically designed for solving unconstrained problems on gate-based quantum computers. Meanwhile, QA has historically been limited to problems with quadratic terms, requiring higher-order terms to be reduced through a process called quadratization. In 2019, Hadfield et al. [ 14 ] introduced an alternative method for constrained problems that restricts quantum evolution to the feasible subspace via carefully constructed quantum operators. A third alternative, distinct from both penalty-based methods and feasibility-preserving approaches, was recently proposed by Angara et al. [ 8 ] . This work investigates transformational equivalent unconstrained “profit” variants of three transformational equivalent COPs. These unconstrained variants are solved using Farhi’s original QAOA formulation (or vanilla QAOA), followed by classical post-processing. For these three problems, the authors demonstrate improved performance and practical scalability in terms of approximation ratios, as well as summed optimal and near-optimal probability metrics. In this paper, we introduce the novel SCOOP framework to solve constrained COPs using vanilla QAOA. Table I presents the NP-hard constrained problems alongside their unconstrained counterparts. It also details the type of transformations used to render all solution subsets feasible, and refers to the corresponding classical polynomial-time post-processing algorithm required to map solutions for the unconstrained problem into the feasible subspace of the original, constrained , COP. This framework provides a better encoding that enables the discovery of optimal and near-optimal solutions at scale. To achieve this, SCOOP guides the derivation of an unconstrained COP from the constrained COP. This process results in a penalty-free cost Hamiltonian that is well-suited for QAOA. Subsequently, the viable solutions obtained by QAOA are efficiently post-processed. Our approach offers the advantages that it scales for all inputs and supports the determination of near-optimal solutions. The main contributions of our paper are: (1) The SCOOP framework that guides the derivation of an unconstrained COP from a constrained COP. The SCOOP derivation leads to a penalty-free cost Hamiltonian that is palatable for QAOA. The viable solutions produced by QAOA are efficiently post-processed. (2) We formalize the conditions that the relationship between the constrained and unconstrained COPs must satisfy. (3) Following the SCOOP framework, we derive unconstrained COPs to solve the constrained problems listed in Table I . (4) For each unconstrained COP, we present the cost Hamiltonian that can serve as input to QAOA. (5) For both Minimum Dominating Set ( MinDS ) and Minimum Maximal Matching ( M 3 ), we discuss in detail the setup and results of our experiments performed on Xanadu’s Pennylane simulator for 3-regular

Read the complete text