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: pangara@uvic.ca 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 graphs with up to ten qubits and eight layers of QAOA. To the best of our knowledge, experimental results for both MinDS and M 3 using quantum techniques remain unexplored in the literature. In the remainder of this paper, we discuss related work (Sec. II ) and define the necessary relationship between a constrained and an unconstrained COP, and introduce our SCOOP framework (Sec. III ). We derive SCOOP twins and their Hamiltonians in Sections IV – VI . Sections VII and VIII present an evaluation of the SCOOP framework using Xanadu PennyLane, and Section IX concludes the paper. II Related Work We introduce the problems of study, selected to illustrate our SCOOP framework, related work QAOA, as well as on encoding optimization problems for the use with QAOA. Problems of Study In the early 1970s, among the first sets of problems proved to be NP-hard are Minimum Dominating Set , Minimum Set Cover , and Minimum Maximal Matching [ 15 ] . We picked these problems for our case studies and give problem definitions in Secs. III – VI . Both MinDS and M 3 remain hard even when the input graphs are restricted to bipartite graphs of maximum degree 3 [ 16 , 17 ] . These problems have applications in various domains: Finding small dominating sets has applications in social networks [ 18 ] , wireless networks [ 19 , 20 ] and biological networks—for the identification of disease-genes and to extract biological motifs [ 21 ] . Minimum set covers find applications in networking, such as in the lifetime maximization of wireless sensor networks [ 22 ] and link-state routing approaches [ 23 ] . Minimum maximal matchings are valuable in resource allocation [ 24 ] . Quantum Approximate Approximation Algorithm QAOA, introduced by Farhi et al. in 2014 [ 2 ] , is a hybrid quantum-classical heuristic algorithm designed to solve combinatorial optimization problems. The standard vanilla QAOA framework includes: (1) an initial equal superposition state, |\psi_{0}\rangle=\ket{+}^{\otimes n} , (2) an ansatz comprising alternating parameterized cost unitaries ( U(\boldsymbol{\gamma})=e^{-i\boldsymbol{\gamma}\hat{H}_{C}} ) and mixing unitaries ( U(\boldsymbol{\beta})=e^{-i\boldsymbol{\beta}\hat{H}_{M}} ) applied over p layers, and (3) a classical optimizer that minimizes the expected value of the cost Hamiltonian. The algorithm’s performance depends on the choice of ansatz, parameters (\boldsymbol{\gamma},\boldsymbol{\beta}) , and classical optimizer, with common methods including L-BFGS, COBYLA, Adam, and Gradient Descent. Numerous variants of QAOA targetting constrained optimization have emerged over the years, notably by Hadfield et al. [ 14 ] , Saleem et al. [ 25 , 26 ] , Egger et al. [ 27 ] . In existing studies, QAOA performance has primarily been evaluated on Erdős-Rényi random graphs with varying edge probabilities [ 28 , 25 ] and bounded-degree graphs, particularly random 3-regular graphs [ 29 , 30 ] . Herrman et al. [ 31 ] investigated MaxCut performance using QAOA with up to three layers across various small graphs (up to eight nodes). Unconstrained Binary Optimization Problems While QA strictly requires a QUBO formulation, QAOA generally can handle both QUBO and HUBO problems. Initially, lower-order terms and, consequently, QUBOs might be preferred. However, converting a HUBO into a QUBO through quadratization necessitates introducing auxillary variables and additional penalties [ 11 ] . In contrast, Campbell et al. [ 32 ] investigate the advantages of incorporating higher-order terms (HOTs) into the problem formulation. Their research underscores the potential of utilizing the inherent capabilities of gate-model quantum computers to manage HOTs, suggesting an expanded application domain for QAOA and paving the way for near-term quantum superiority on NP-hard problems. Pelofske et al. [ 33 ] conducted an experimental comparison between QAOA and QA on different hardware platforms. Their study focused on cubic ZZZ interactions, which are natively constructible for QAOA, while QA necessitates order reduction to quadratic interactions using auxiliary variables. Mandal et al. [ 34 ] study quadratization and propose a method of degree reduction that works directly in the Ising space. They note that a sparse problem in the Ising space—i.e., its cost Hamiltonian, defined by a sum of local terms that each involves a small, bounded number of variables and each variable appears in only a small number of terms— is not necessarily sparse in Boolean space and vice versa. A simple example illustrates this: Consider polynomial 2^{n}\prod_{i=1}^{n}b_{i} . Applying the transformation from binary to Ising variables ( b_{i}\leftarrow(1-Z_{i})/2 ) results in the Hamiltonian \sum_{I\subseteq\{1,\dots,n\}}(-1)^{|I|}\prod_{i\in I}Z_{i} , which grows exponentially [ 34 ] . In the context of the traveling salesperson problem (TSP), Glos et al. [ 35 ] propose a trade-off between the number of qubits and the circuit depth to demonstrate an efficient binary encoding for TSP. We note that the feasibility of the encoding of HUBOs or HOTs into a cost Hamiltonians is instance dependent; understanding the structural properties of the problem is crucial for assessing whether or not higher-order terms must be used as further discussed in Secs. VII and VIII . III The SCOOP framework In this section, we formalize a blueprint that guides us in deriving an unconstrained COP, P_{U} , from a constrained one, P_{C} . P_{U} possesses the necessary properties to obtain optimal and near-optimal solutions using the vanilla QAOA approach for P_{U} , followed by efficient post-processing. In general terms, a combinatorial optimization problem P takes as input, an instance x from its input domain \cal I (e.g., a graph from the set of all simple undirected graphs). For a given x\in I , a solution is s\in\text{Sol}(x) , where \text{Sol}(x) denotes the general set of possible solutions for x (e.g., if the instance is a graph G=(V,E) and every solution is a subset of vertices, then \text{Sol}(G)={\cal P}(V) , the powerset of V ). The objective function of P for an instance x\in I can be described as \texttt{obj}^{x}:\text{Sol}(x)\longrightarrow\mathbb{Q} (e.g., if the measure of the solution is size, and a solution to a graph problem is a vertex subset, say V^{\prime}\subseteq V , then \texttt{obj}^{x}(s)=\texttt{obj}^{G}(V^{\prime})=|V^{\prime}| ). A typical format for describing a COP P : For x\in I and s\in\text{Sol}(x) , \displaystyle\text{Optimize:}\quad|\texttt{obj}^{x}(s)| Note that in the case of an unconstrained COP, any s\in\text{Sol}(x) is a feasible solution. When talking about a COP that is unconstrained, we may call it P_{U} . If instead the COP considered is a constrained COP, then the set of feasible solutions is a subset of \text{Sol}(x) , denoted \text{Sol}_{C}(x) where \text{Sol}_{C}(x)\subset\text{Sol}(x) . A typical format for describing a constrained COP P_{C} is: for x\in I and s\in\text{Sol}(x) , \displaystyle\text{Optimize:}\quad|\texttt{obj}^{x}(s)| \displaystyle\text{Subject to:}\quad s\in\text{Sol}_{C}(x) Before describing the process of how to derive an unconstrained COP P_{U} from a given constrained COP P_{C} , we define a relationship between the problems that is sufficient to obtain optimal and near-optimal solutions using the vanilla QAOA approach for P_{U} , followed by efficient post-processing. We say that a constrained COP P_{C} with input domain I_{C} , feasible solutions \text{Sol}_{C} , and objective function \texttt{obj}_{C} , and an unconstrained COP P_{U} with input domain I_{U} , solutions \text{Sol}_{U}=\text{Sol} , and objective function \texttt{obj}_{U} , are s olution-enhanceable, c onstrained-unconstrained, o bjective-function-compatible o ptimization p roblem twins or SCOOP twins if the following conditions hold: 1. Identical Input Domains : The problems share the same input domain I , i.e., I=I_{C}=I_{U} . 2. Solution Containment : for every instance x\in I , \text{Sol}_{C}(x)\subseteq\text{Sol}_{U}(x) . That is, each feasible solution for P_{C} is a solution for P_{U} . 3. Objective Function Compatibility : For any x\in I there exists a polynomial-time computable function f_{x}:\mathbb{Q}\to\mathbb{Q} such that for all s\in\text{Sol}_{C}(x) : \texttt{obj}^{x}_{C}(s)=f_{x}(\texttt{obj}^{x}_{U}(s)) and \texttt{obj}^{x}_{U}(s)=f_{x}^{-1}(\texttt{obj}^{x}_{C}(s)). 4. Solution Enhance-ability : For each x\in I , and each s\in\text{Sol}_{U}(x) , s\in\text{Sol}_{C}(x) or there exists s^{\prime}\in\text{Sol}_{C}(x) , where s^{\prime} is computable in polynomial time from s . Furthermore, \texttt{obj}^{x}_{U}(s^{\prime}) is at least as good as \texttt{obj}^{x}_{U}(s) and \texttt{obj}^{x}_{C}(s^{\prime}) is at least as good as f_{x}(\texttt{obj}^{x}_{U}(s)) . We next describe a process that may allow, given a constrained problem P_{C} , to derive an unconstrained problem P_{U} such that P_{C} and P_{U} are SCOOP twins. Let P_{C} be a constrained combinatorial optimization problem where for x\in I , a feasible solution s\in\text{Sol}_{C}(x) has cost \texttt{obj}^{x}_{C}(s) . Step 1 Identify the constraints of P_{C} . Step 2 Consider any infeasible solution s^{\prime} for P_{C} . Identify a way to quantify the extent to which the solution satisfies the constraint, deriving \texttt{obj}^{x}_{U}(.) by relating it to \texttt{obj}^{x}_{C}(s^{\prime}) . Step 3 Develop P_{U} using cost function \texttt{obj}^{x}_{U}(.) . Step 4 Prove objective function compatibility. Step 5 Prove solution enhance-ability. Note that the existence of the SCOOP twin P_{U} for a given P_{C} yields NP-hardness for P_{U} as long as P_{C} is NP-hard. We illustrate our framework considering the NP-hard problem Minimum Maximal Matching (M 3 ) [ 15 ] , which is defined as follows. For a simple graph undirected graph G=(V,E) and a subset \textit{M}\subseteq E of edges, \displaystyle\text{Minimize:}\quad|M| \displaystyle\text{Subject to:}\quad\text{(1)~}M\text{~is a matching: for every pair of edges} \displaystyle\quad\quad\quad\quad\quad\quad ab,cd\in M,ab\not=cd,\quad a,b,c\text{~and~}d\text{~are} pairwise distinct \displaystyle\text{~\!~\!}\quad\quad~\quad~\quad\text{~(2)~}\text{matching~}M\text{~is a maximal: there is no edge} \displaystyle\quad\quad\quad\quad\quad\quad e\in E\text{~with~}M\cup\{e\}\text{~is a matching} Here, \texttt{obj}^{G}_{M^{3}}(M)=|M| . Solutions to the problem are subsets of edges (i.e., \text{Sol}(G)=|E| ) that must satisfy constraints (1) and (2), describing \text{Sol}_{C}(G)\subset\text{Sol}(G) . To quantify how much a subset E^{\prime} of edges satisfies the constraints, when E^{\prime} is not feasible, that is E^{\prime} does not satisfy one or both of the constraints, we say that an edge e\in E is covered by E^{\prime} if there is an edge e^{\prime}\in E^{\prime} such that e and e^{\prime} share a common endpoint. In other words every, edges covered by E^{\prime} are all edges in E^{\prime} plus all edges in E\setminus E^{\prime} that are "adjacent" to E^{\prime} . Now we can define \texttt{obj}^{G}_{\textit{PES}}(E^{\prime})=|\{e\in E\mid e\text{~is covered by~}E^{\prime}\}|-|E^{\prime}| . We are ready define the problem Maximum Profitable Edge Set (MaxPES) : for a graph G=(V,E) and \textit{E'}\subseteq E , \displaystyle\text{Maximize:}\quad\text{~profit~}\mathfrak{p}_{\text{PES}~}\text{where~}\mathfrak{p}_{\text{PES}~}=|\texttt{obj}^{G}_{\textit{PES}}(E^{\prime})| In Sec. V we prove that M 3 and MaxPES are indeed SCOOP twins. In the following section, we document that our framework applies to the two NP-hard problems Minimum Dominating Set and Minimum Set Cover (Secs. IV , VI ). IV Minimum Dominating Set A dominating set in an undirected graph G=(V,E) 1 1 1 In this section, we refer to simple undirected graphs without isolated vertices. with vertex set V and edge set E is a subset DS\in V such that every vertex in G is “dominated” by DS . A vertex is considered to dominate itself and all of its adjacent vertices. This ensures that all vertices in the graph are either part of the dominating set or directly connected to a vertex in it. A smallest possible dominating set is referred to as minimum dominating set . We define the problem Minimum Dominating Set ( MinDS ) for a graph G=(V,E) as follows. A subset of vertices \textit{DS}\subseteq V is a dominating set if every vertex v\in V is either in DS or adjacent to at least one vertex in DS . The objective is to find the smallest such set: \displaystyle\text{Minimize:}\quad|\textit{DS}| \displaystyle\text{Subject to:~}\text{~for all~}v\in V \displaystyle\quad\quad\ v\in\textit{DS~}\text{~or~}\text{~there exists~}u\in N(v)\ \mbox{such that}\ u\in\textit{DS} Using our SCOOP framework for MinDS , we derive the unconstrained problem Maximum Profit Domination or MaxPD . Theorem 1 below concludes the proof that MinDS and MaxPD are SCOOP twins. Step 1: Identify constraints The constraint that MinDS must satisfy to ensure feasibility is that the subset \textit{DS}\subseteq V is a dominating set. Step 2: Quantify feasibility of infeasible solution Consider the extent to which a subset of vertices dominates vertices and its closeness to being a dominating set (i.e., the more vertices are dominated, the better). Step 3: Develop objective function \texttt{obj}^{G}_{PD} For a subset \textit{PD}\subseteq V in G , \texttt{obj}^{G}_{PD}(PD)=|\{v\in V|v~\text{is dominated by}~PD\}|-|PD| . We also refer to the value produced by the objective function \texttt{obj}^{G}_{PD}(PD) as profit , \mathfrak{p}_{PD} . Before moving on to Step 4, we formulate the problem Maximum Profit Domination (MaxPD) [ 36 ] for a graph G=(V,E) and \textit{PD}\subseteq V : \displaystyle\text{Maximize:}\text{~profit~}\mathfrak{p}_{\text{PD}},\text{where~}{\mathfrak{p}}_{\text{PD}}=\texttt{obj}^{G}_{PD}(PD) Step 4: Objective function compatibility From Theorem 1 below, we can derive function f_{G}(.) . That is, f_{G}(\mathfrak{p})=|V|-k and f_{G}^{-1}(k)=|V|-\mathfrak{p} . Step 5: Solution enhance-ability Alg. 1 describes a polynomial-time post-processing procedure that converts a solution PD for MaxPD to a domintating set, i.e., a solution for MinDS while preserving solution quality. Theorem 1 . [ 36 ] For any graph G=(V,E) , G has a dominating set \textit{DS}\subseteq V of size k if and only if G has a subset \textit{PD}\subseteq V with profit {\mathfrak{p}}_{\text{PD}}=|V|-k . Proof. (Sketch) (\Rightarrow) Determining the profit {\mathfrak{p}}_{\text{PD}} of a dominating set \textit{DS}\subseteq V for G results in {\mathfrak{p}}_{\text{PD}}=\texttt{obj}^{G}_{PD}(DS) . Since DS is a dominating set {\mathfrak{p}}_{\text{PD}}=|E|-k . (\Leftarrow) Consider a subset PD\subseteq V with profit \mathfrak{p}_{\text{PD}}=|V|-k . If PD is a dominating set, then |\textit{PD}|=k and thus PD is a dominating set of size k . If instead PD is not a dominating set then we can obtain a dominating set of size at most |V|-{\mathfrak{p}}_{\text{PD}} by applying Algorithm 1 . Note that the algorithm at no step when expanding PD reduces the profit. ∎ Algorithm 1 Converting solutions: MaxPD to MinDS adapted from [ 36 ] 0: Graph G , Solution PD Let V_{\text{nd}} be the set of non-dominated vertices in G for each vertex v\in V_{\text{nd}} do if N(v)\not\subseteq\textit{PD} and v\notin\textit{PD} then Add v to PD end if end for Theorem 1 implies that, given an optimal solution to MaxPD PD for a graph G , we can obtain a minimum dominating set for G using Algorithm 1 . Having obtained the unconstrained SCOOP twin MaxPD for MinDS we are ready to describe the formulations of the cost Hamiltonians. Cost Hamiltonians for MinDS and MaxPD We describe cost Hamiltonians for both MinDS ( \hat{H}_{DS} ) and MaxPD ( \hat{H}_{PD} ) using higher-order unconstrained binary formulations. Let \vec{x}=(x_{1},x_{2},\dots,x_{|V|}) be a vector of binary variables, where x_{i}\in\{0,1\} for each i\in V , then, \displaystyle\hat{H}_{DS}(\vec{x}) \displaystyle=\hat{H}^{DS}_{N}(\vec{x})+\hat{H}^{DS}_{V}(\vec{x}) \displaystyle=A\sum_{i\in V}\Bigg[\Big((1-x_{i})\prod_{j\in N(i)}(1-x_{j})\Big)\Bigg]+B\sum_{v\in V}x_{v}, with, A>B , and \displaystyle\hat{H}_{PD}(\vec{x}) \displaystyle=\hat{H}^{PD}_{N}(\vec{x})-\hat{H}^{PD}_{V}(\vec{x}) \displaystyle=\sum_{i\in V}\Bigg[1-\Big((1-x_{i})\prod_{j\in N(i)}(1-x_{j})\Big)\Bigg]-\sum_{v\in V}x_{v}. We formulated the HUBO of the constrained COP MinDS following the guidelines of Glover et al. [ 11 ] . The goal of this HUBO is to minimize \hat{H}_{DS}(\vec{x}) . \hat{H}_{DS}(\vec{x}) imposes a penalty for vertices that are not dominated by a factor of A . Its minimum value is \hat{H}_{DS}(\vec{x})=B\sum_{v\in V}x_{v} . For the unconstrained COP MaxPD , the goal is to maximize the unconstrained objective \hat{H}_{PD}(\vec{x}) . The term \hat{H}^{PD}_{N}(\vec{x}) keeps track of all vertices that are dominated—the contribution of each vertex is 1 if dominated and 0 otherwise. We point out that Dinneen et al. [ 37 ] provide a different, quadratic, formulation for MinDS , which requires additional variables/qubits to balance penalties where more than one vertex is selected in the dominating set. V Minimum Maximal Matching Recall the problem Minimum Maximal Matching (M 3 ) introduced at the end of Sec. III , where we derive, as its SCOOP twin, the unconstrained problem Maximum Profitable Edge Set (MaxPES) . The profit formulation MaxPES of M 3 is derived by relaxing the two constraints of \textsc{M}^{3} : we neither require the set of edges to be a matching nor maximal. Using the SCOOP framework, this process can by summarized as follows. Step 1: Identify constraints The constraints that any solution M\subseteq E to M 3 must satisfy to ensure feasibility is that M is a matching that is maximal. Step 2: Quantify feasibility of infeasible solution Consider the extent to which a subset covers edges . An edge is covered by itself or is adjacent to an edge in the subset. Step 3: Develop objective function \texttt{obj}_{\text{PES}} For a subset \textit{PES}\subseteq E in G , \texttt{obj}^{G}_{\text{PES}}(\textit{PES})=|\{e\in E|~e~\text{is covered by}~\textit{PES}\}|-|\textit{PES}| . We refer to the value produced by the objective function \texttt{obj}^{G}_{\text{PES}}(\textit{PES}) as profit , \mathfrak{p}_{\text{PES}} . Step 4: Objective function compatibility From Theorem 2 we can derive function f_{G}(.) . Here, f_{G}(\mathfrak{p})=|E|-k and f_{G}^{-1}(k)=|E|-\mathfrak{p} . Step 5: Solution enhance-ability The proof of Theorem 2 shows a two-step process that converts any solution \textit{PES}\subseteq E for a given MaxPES -instance G=(V,E) to a maximal matching, and therefore to a solution for M 3 while preserving solution quality. Alg. 2 describes the first step of the polynomial-time post-processing procedure, i.e. converting PES to a maximal subset of edges—a subset \textit{PES}^{\prime} where the addition of any additional edge from E would reduce the profit–while preserving solution quality. Alg. 3 describes the second step that converts \textit{PES}^{\prime} to a maximal matching, again while preserving solution quality. We say that a subset that covers all edges is a maximal profitable edge set and a subset \textit{PES}\subseteq E that maximizes \texttt{obj}^{G}_{\text{PES}}(\textit{PES}) is a maximum profitable edge set . Determining minimum maximal matchings via maximum profitable edge sets The following theorem implies that we can derive, from any given subset of edges with profit \mathfrak{p} , a maximal matching MM with profit at least \mathfrak{p} . Theorem 2 . Let G=(V,E) be an undirected simple graph. G has a maximal matching \textit{MM}\subseteq E of size k if and only if G has a subset \textit{PES}\subseteq E with profit {\mathfrak{p}}_{\text{PES}}=|E|-k . Proof. (Sketch) (\Rightarrow) Consider a maximal matching \textit{MM}\subseteq E for G , |\textit{MM}|=k . MM has a profit of {\mathfrak{p}}_{\text{PES}}=|E_{\text{PES}}(G,\textit{MM})|-|\textit{MM}| , where E_{PES}(G,\textit{MM}) are the edges covered by MM . Since MM is a maximal matching, it covers all edges in G . Therefore, |E_{\text{PES}}(G,\textit{MM})|=|E| and {\mathfrak{p}}_{\text{PES}}=|E|-|k| . (\Leftarrow) Let subset \textit{PES}\subseteq E with {\mathfrak{p}}_{\text{PES}}=|E|-k . For the case where PES is a maximal matching, there is nothing to prove. If PES is not a maximal matching and E_{\text{PES}}(G,\textit{PES})=E , then |\textit{PES}|=k , and PES covers all edges, which means that PES is a maximal profitable edge set. If PES is neither a maximal matching nor a maximal profitable edge set, then PES does not cover all edges. One can obtain a maximal profitable edge set \textit{PES}^{\prime} of size at most |E|-{\mathfrak{p}}_{\text{PES}} and profit at least {\mathfrak{p}}_{\text{PES}} by covering the remaining edges in E\setminus E_{\text{PES}}(G,\textit{PES}) with post-processing Alg. 2 . Algorithm 2 Converting solutions: profitable edge sets to maximal profitable edge sets 0: Graph G , solution PES Let \textit{PES}^{\prime}=\textit{PES} Let E_{\text{unc}} be the set of uncovered edges in G for each edge (u,v)\in E_{\text{unc}} do if N_{e}(u,v)\not\subseteq\textit{PES} and (u,v)\notin\textit{PES} then Add (u,v) to \textit{PES}^{\prime} end if end for Finally, if the maximal profitable edges set \textit{PES}^{\prime} is not a matching, it can be converted in polynomial time into a maximal matching MM with |MM|\leq|PES^{\prime}| (Alg. 3 ). Algorithm 3 Converting a maximal profitable edge set into a maximal matching; adapted from [ 17 ] 0: Graph G , maximal profitable edge set \textit{PES}^{\prime} for each pair of adjacent edges (u,v),(v,w)\in\textit{PES}^{\prime} do if \textit{PES}^{\prime}\setminus(u,v) covers all edges then Remove (u,v) from \textit{PES}^{\prime} and break end if if \textit{PES}^{\prime}\setminus(v,w) covers all edges then Remove (v,w) from \textit{PES}^{\prime} and break else Let S be the set of edges incident to w Pick an edge (w,z)\in S , z\not=v , such that (w,z) is covered only by (v,w) \textit{PES}^{\prime}:=(\textit{PES}^{\prime}\setminus(v,w))\cup(w,z) end if end for ∎ Theorem 2 implies that, given a maximum profitable edge set PES for a graph G , we can obtain a minimum maximal matching for G using the procedure given in the proof. Generally, to convert any solution to instances for MaxPES to maximal matchings for the same instance without sacrificing the solution quality, we apply the 2-step procedure. We would like to point out a connection between the problems investigated in the section with to two other famous NP-hard problems. In 1980, Yannakakis and Garvil [ 17 ] pointed out the transformational equivalence between the problems M 3 and Minimum Edge Dominating Set (MinEDS) , the problem that for an undirected graph seeks a smallest subset of edges that covers every edge in the graph. When following the SCOOP framework one can see that the constrained problem M 3 and Minimum Edge Dominating Set share unconstrained SCOOP twin MaxPES . However, to convert solutions for MaxPES into solutions for MinEDS , Alg. 2 is sufficient. Another problem investigated in this paper is Minimum Independent Edge Dominating Set (MinIEDS) . An independent edge dominating set is a dominating set that is also a matching. While there is no difference between a minimum independent edge dominating set and a minimum maximal matching, not every edge dominating set is also a maximal matching. Similarly, not every maximal matching is also an edge dominating set. MaxPES , however, again serves a SCOOP twin for MinIEDS as any subset of edges of profit \mathfrak{p} can be converted into a matching of profit at least \mathfrak{p} . Cost Hamiltonians for MaxPES and M 3 We describe the cost Hamiltonians \hat{H}_{\text{M}^{3}} and \hat{H}_{\text{PES}} for M 3 and PES , respectively below. Let \vec{x}=(x_{1},x_{2},\dots,x_{|E|}) be a vector of binary variables, where x_{i}\in\{0,1\} for each i\in E . \displaystyle\hat{H}_{PES}(\vec{x}) \displaystyle=\hat{H}^{PES}_{N}(\vec{x})-\hat{H}^{PES}_{V}(\vec{x}) \displaystyle=\sum_{i\in E}\Bigg[1-\Big((1-x_{i})\prod_{j\in N_{e}(i)}(1-x_{j})\Big)\Bigg]-\sum_{i\in E}x_{i}. For MaxPES , the goal is to maximize the unconstrained objective \hat{H}_{PES}(\vec{x}) . The term \hat{H}^{PES}_{N}(\vec{x}) keeps track of all edges that are covered (the contribution of each edge that is covered is 1 and 0 otherwise). In 2014, Lucas [ 3 ] provided the QUBO formulation for M 3 . We include it here for comparison with the MaxPES formulation. Let \vec{x}=(x_{1},x_{2},\dots,x_{|E|}) be a vector of binary variables, where x_{e}\in\{0,1\} for each e\in E representing whether or not edge e is in the matching. The Hamiltonian \hat{H}_{M^{3}}(\vec{x},\vec{y}) is defined as follows: \hat{H}_{M^{3}}(\vec{x},\vec{y})=\hat{H}^{M^{3}}_{A}(\vec{x})+\hat{H}^{M^{3}}_{B}(\vec{y})+\hat{H}^{M^{3}}_{C}(\vec{x}), where: \hat{H}^{M^{3}}_{A}(\vec{x})=A\sum_{v\in V}\sum_{\{e_{1},e_{2}\}\subset\partial v}x_{e_{1}}x_{e_{2}} penalizes having two matched edges incident to the same vertex v , where \partial v is the set of edges incident to v . This term enforces the matching constraint. Auxiliary binary variables, \vec{y} , are defined such that y_{v}=\sum_{e\in\partial v}x_{e} (only valid for states with H_{A}=0 ) which indicates if a vertex v has a matched edge. Then, \hat{H}^{M^{3}}_{B}(\vec{y})=B\sum_{e=(u,v)\in E}(1-y_{u})(1-y_{v}) penalizes states where an edge (u,v) could be added to the matching (i.e., both y_{u}=0 and y_{v}=0 ) without violating the matching constraint, thus enforcing maximality. Finally, since \hat{H}^{M^{3}}_{C}(\vec{x})=C\sum_{e\in E}x_{e} counts the number of matched edges, the optimal value of the total Hamiltonian corresponds to a minimum maximal matching. Lucas highlights the absence of prior work on M 3 ; our current analysis confirms that it remains unaddressed in the literature from the perspective of QAOA or QA. VI Minimum Set Cover In the previous sections, we applied our SCOOP framework to two different graph problems. Now, we apply the SCOOP framework to a different type of constrained COP, Minimum Set Cover . Given a universe {U} consisting of n elements and a family \cal C consisting of m subsets of U whose union equals U , a set cover is a subfamily {\cal C^{\prime}}\subseteq\cal C where the union of elements in \cal C^{\prime} equals {U} . We begin by defining the problem and before applying our SCOOP framework to derive and solve the problem via its SCOOP twin. We define the optimization version of the problem Minimum Set Cover (MinSC) for a universe {U} , a family of subsets {\cal C}\subseteq{U} , and a subfamily {\cal C^{\prime}}\subseteq{\cal C} as follows: \displaystyle\text{Minimize:~}|{\cal C^{\prime}}| \displaystyle\text{Subject to:~}\bigcup\limits_{C_{i}\in{\cal C^{\prime}}}C_{i}={U} Step 1: Identify constraints The constraints that any solution {\cal C^{\prime}}\subseteq{\cal C} to MinSC must satisfy to ensure feasibility is that {\cal C^{\prime}} is a set cover for U , i.e., \bigcup\limits_{C_{i}\in{\cal C^{\prime}}}C_{i}={U} . Step 2: Quantify feasibility of infeasible solution Consider the extent to which a subfamily of {\cal C} covers the elements of U . Step 3: Develop objective function \texttt{obj}^{(U,{\cal C})}_{\text{PSC}} For a subfamily {\cal PSC}\subseteq{\cal C} , \texttt{obj}^{(U,{\cal C})}_{\text{PSC}}(\mathcal{PSC})=|\bigcup\limits_{C_{i}\in{\cal PSC}}C_{i}|-|\mathcal{PSC}| . We refer to the value produced by the objective function \mathfrak{p}_{\text{PSC}}=\texttt{obj}^{(U,{\cal C})}_{\text{PSC}}(\mathcal{PSC}) as profit . Step 4: Objective function compatibility From Theorem 3 we can derive function f_{U}(.) . Here, f_{U}(\mathfrak{p})=|U|-k and f_{U}^{-1}(k)=|U|-\mathfrak{p} . Before moving on to Step 5, we formulate the problem Maximum Profitable Set Coverage or MaxPSC for a universe U , a family of subsets \cal C and a subfamily \mathcal{PSC}\subseteq\cal U , \displaystyle\text{Maximize:}\text{~profit~}\mathfrak{p}_{\text{PSC}},\text{where~}{\mathfrak{p}}_{\text{PSC}}=\texttt{obj}^{(U,{\cal C})}_{\text{PSC}}(\mathcal{PSC}) Step 5: Solution enhance-ability The proof of Theorem 3 shows a process that converts any solution \mathcal{PSC}\subseteq\cal C for a given MaxPSC -instance (U,{\cal C}) into a set cover while preserving solution quality. Theorem 3 . For any universe U and family \cal C of subsets of U whose union equals U , U has a set cover of size k if and only if there is a subfamily \mathcal{PSC}\subseteq{\cal C} with profit \mathfrak{p}_{\text{PSC}}=|{U}|-k . Proof. (Sketch) Given: U , {\cal C} with \bigcup\limits_{C_{i}\in{\cal C}}C_{i}=U . (\Rightarrow) If there is a set cover {\cal C^{\prime}}\subseteq{\cal C} with |{\cal C^{\prime}}|=k , then \bigcup\limits_{C_{i}\in{\cal C^{\prime}}}C_{i}={U} . Thus, the profit of {\cal C^{\prime}} is \mathfrak{p}_{\text{PSC}}=|\bigcup\limits_{C_{i}\in{\cal C^{\prime}}}C_{i}|-k=|{U}|-k . (\Leftarrow) If there is a subfamily \mathcal{PSC}\subseteq\cal C with profit \mathfrak{p}_{\text{PSC}} , then |\bigcup\limits_{C_{i}\in{\mathcal{PSC}}}C_{i}|-|\mathcal{PSC}|\geq\mathfrak{p}_{\text{PSC}} . If \mathcal{PSC} is a set cover, then \bigcup\limits_{C_{i}\in\mathcal{PSC}}C_{i}={U} . Thus, |U|-|\mathcal{PSC}|\geq\mathfrak{p}_{\text{PSC}} , yielding |{U}|-\mathfrak{p}_{\text{PSC}}\geq|\mathcal{PSC}| . If \mathcal{PSC} is not a minimum set cover, then there exists x\in{U} such that for all C_{i}\subseteq\mathcal{PSC} , x\not\in C_{i} ; thus, \bigcup\limits_{C_{i}\in\mathcal{PSC}}C_{i}\neq{U} and |\bigcup\limits_{C_{i}\in C^{\prime}}C_{i}|<|{U}| . In this case we can obtain a set cover of size at most |U|-|\mathcal{PSC}| by applying Algorithm 4 . ∎ The proof of Theorem 3 , given a maximum profitable set coverage \mathcal{PSC} for a universe {U} and family \cal C of subsets of U such that \bigcup\limits_{C_{i}\in{\cal C}}C_{i}={U} , tells us that we can determine in polynomial time a minimum set cover for {U} using the procedure outlined in the proof above. Algorithm 4 Converting solutions: MaxPSC to MinSC 0: Universe U , family of subsets \mathcal{C} , Solution \mathcal{PSC} Let U_{\text{unc}} be the set of uncovered elements in U for each element x\in U_{\text{unc}} do for each subfamily C_{i}\in\mathcal{C}\setminus\mathcal{PSC} do if x\in{C_{i}} then Add C_{i} to PSC end if end for end for Cost Hamiltonians for MinSC and MaxPSC Fig. 1 : QAOA circuit for MaxPD , with p=1 for toy graph G=(V,E) , V=\{i,j,k\} and E=\{(i,j),(j,k)\} . The circuit shows the terms and interactions relevant to q_{i} . Yellow boxes indicate gates used for quadratic ( ZZ ) and cubic ( ZZZ ) terms. Lucas [ 3 ] defines a QUBO for MinSC using the following binary variables: • y_{i}=\left\{\begin{array}[]{ll}1&C_{i}\in{\cal C}^{\prime}\\ 0&C_{i}\not\in{\cal C}^{\prime}\end{array}\right. • x_{\alpha,m}=\left\{\begin{array}[]{ll}1&\textnormal{Number of }C_{i}\textnormal{'s}\in{\cal C}\textnormal{ with }\alpha\in C_{i}\textnormal{ is }m\geq 1\\ 0&\textnormal{otherwise}\end{array}\right. The QUBO for MinSC with penalties A and B are then defined on binary variables \vec{x} and \vec{y} as follows: \displaystyle\hat{H}_{SC}(\vec{x},\vec{y}) \displaystyle=\hat{H}^{SC}_{E}(\vec{x},\vec{y})+\hat{H}^{SC}_{S}(\vec{y}) where \hat{H}^{SC}_{E}(\vec{x},\vec{y})=A\sum_{\alpha=1}^{n}\left(1-\sum_{m=1}^{N}x_{\alpha,m}\right)^{2}+ A\sum_{\alpha=1}^{n}\left(\sum_{m=1}^{N}mx_{\alpha,m}-\sum_{i:\alpha\in C_{i}}y_{i}\right)^{2} and \hat{H}^{SC}_{S}(\vec{y})=B\sum_{i=1}^{N}{y_{i}} For MinSC , the QUBO formulation uses penalties to enforce the constraint that each element of the universe U is covered. The penalty also activates when the variable x_{\alpha,m} is counted more than once, which is necessary because we aim to count coverage only a single time (and penalize otherwise) even if the element appears in multiple subsets. In contrast, we formulate MaxPSC as a HUBO that naturally captures requirement that each element is counted only once even if it appears in multiple subsets. without the need for penalty terms. To describe MaxPSC as unconstrained binary optimization problem, we define the a HUBO. We begin with defining the binary variables y_{i} expressing whether or not subset C_{i} is selected into the cover, and x_{\alpha,i} that tells us whether or not element \alpha\in U\cap C_{i} : • y_{i}=\left\{\begin{array}[]{ll}1&C_{i}\in{\cal C}^{\prime}\\ 0&C_{i}\not\in{\cal C}^{\prime}\end{array}\right. • x_{\alpha,i}=\left\{\begin{array}[]{ll}1&\alpha\in U\text{ and }\alpha\in C_{i}\text{ for }C_{i}\in{\cal C}\\ 0&\text{otherwise}\end{array}\right. The total cost to maximize for MaxPSC is \displaystyle H_{PSC}(\vec{x},\vec{y}) \displaystyle=H^{PSC}_{E}(\vec{x},\vec{y})-H^{PSC}_{S}(\vec{y}) \displaystyle=\sum_{\alpha=1}^{|U|}\left(1-\prod_{i=1}^{|{\cal C}|}(1-x_{\alpha,i}y_{i})\right)-\sum_{i=1}^{|{\cal C}|}y_{i} where H^{PSC}_{S}(\vec{y}) corresponds to the size of {\cal C}^{\prime} , and H^{PSC}_{E}(\vec{x},\vec{y}) to the number of elements of U that are covered by the chosen subsets. VII Experimental Setup Fig. 2 : Probabilities for a sample graph (shown in inset of leftmost sub-figure) containing 5 vertices with p\in\{1,3,5\} layers. MinDS is run for three different penalty parameters and is shown in blue. For example, Dominating Set(3, 2) refers to penalties A=3,B=2 . Results of MaxPD are shown in orange and the post-processed results of MaxPD are shown in burgundy. We demonstrate the feasibility and effectiveness of our approach using the SCOOP twins for constrained COPs MinDS and M 3 . While implementation efforts on MinDS have been limited [ 38 , 37 ] , to the best of our knowledge, M 3 has not yet been implemented on gate-based quantum machines. This section details the experimental setup employed to evaluate the performance of QAOA using the SCOOP framework to compare with the standard penalty-based QAOA approach for solving Higher-Order Unconstrained Binary Optimization (HUBO) problems. Xanadu PennyLane All simulations and quantum circuit constructions were implemented using PennyLane, an open-source Python framework specialized for quantum differentiable programming. For this study, the simulations were performed using PennyLane’s built-in default qubit simulator with classical optimization performed using the RMSProp (Root Mean Squared Propagation) optimizer over 400 steps. Problem Instances To assess the scalability and effectiveness of our approach, we generated random 3-regular graphs with n=\{6,8,10\} nodes. These graph instances were chosen with a fixed-degree to limit the number of higher-order interactions. The structure of 3-regular graphs, when applied to the dominating set problem, results in higher-order terms in the HUBO with a maximum degree of four (quartic interactions). QAOA Setup We formulate all cost Hamiltonians as minimization problems, where variables in the subset evaluated are mapped to -1 and the variables not chosen are mapped to 1 . For each of the cost Hamiltonians, we transform binary variables to Ising ones by applying the transformation x_{i}\rightarrow\frac{1-Z_{i}}{2} . We use a basic Pauli-X mixer, \hat{H}_{M}=\sum_{i}X_{i} . Fig. 1 shows a sample QAOA circuit for the problem MaxPD with the terms and interactions shown for one of the nodes ( i with deg(i)=2 ). Assessing if this node is dominated in the set requires a Hamiltonian with 8 terms, involving interactions up to three nodes simultaneously. Evaluation metrics We performed QAOA simulations with the number of layers up to 8. To validate our proposed approach, we employ the following methodology: 1. A set of random 3-regular connected graphs of varying size are generated. 2. The given problem is solved using QAOA on the set of random graphs using our approach (SCOOP framework), as well as the penalty-term approach. 3. Results from our approach and results from the penalty-term QAOA are compared against classical exact solutions for varying graph sizes. Exact solutions to MinDS are obtained classically by formulating the problem as an integer linear program and solving it with the PuLP library in Python. Results are presented for the following evaluation metrics: 1. Probabilities (full-statevector results) for the penalty approach (with varying penalties), for the SCOOP framework (before and after post-processing). Fig. 2 illustrates this for the dominating set problem using a sample graph with five nodes. 2. We compare the penalty and SCOOP frameworks using summed probabilities of optimal and near-optimal solutions (we include the second and third best solutions), which represent the likelihood of obtaining high-quality solutions within the problem space in Fig. 3 . 3. Approximation ratios of the problems encoded using the SCOOP framework are calculated by dividing the expectation value obtained by QAOA divided by the optimal objective value calculated classically. For instance, r_{PD}=\frac{|\langle\psi(\boldsymbol{\gamma}^{*},\boldsymbol{\beta}^{*})|\hat{H}_{\text{PD}}|\psi(\boldsymbol{\gamma}^{*},\boldsymbol{\beta}^{*})\rangle|}{|\text{{MaxPD(G)}}|} (1) where (\boldsymbol{\gamma},\boldsymbol{\beta}) denote the parameters optimized by the classical optimizer for the problem MaxPD . The results, averaged over 10 randomly generated graphs, are presented in Fig. 4 . VIII Results and Discussion Fig. 3 : Probabilities of optimal & near-optimal solutions obtained over 8 layers for MinDS & MaxPD averaged over 10 3-regular graphs. The sub-figures in the first column show the summed probability of all the optimal solutions with n\in\{6,8,10\} . The sub-figures in the 2^{nd} column depict the summed probability of obtaining the optimal solution and the 2^{nd} best solution. The sub-figures in the 3^{rd} column indicates the summed probability of the optimal, 2^{nd} best and the 3^{rd} best solutions. Fig. 4 : Approximation ratios computed for MaxPD and MaxPES on PennyLane for n\in\{6,8,10\} averaged over 10 3-regular graphs. The profit of solutions to MinDS are guaranteed to be no worse than MaxPD (Alg. 1 ), and thus the approximation ratio is preserved for MinDS . Similarly, Algs. 2 and 3 imply that this approximation ratio also applies to M 3 . In our analysis, we examine the individual probabilities of obtaining feasible solutions for the constrained problem, comparing Hamiltonians for both SCOOP twins using the standard QAOA implementation. Fig. 2 shows a probability distribution for MaxPD and MinDS with p\in\{1,3,5\} layers for the five node graph shown in the inset of Fig. 2 , run on PennyLane’s standard analytical simulator ( default.qubit ). The classical optimizer used is the Root Mean Squared Propagation (RMSProp). The quantum-classical loop is run 400 times to obtain the results. The bar in the burgundy color in Fig. 2 shows the result of post-processing profit domination results to dominating set using Alg. 1 . As the number of layers increases, we can see a high probability (greater than 0.8) of obtaining the optimal result. Fig. 3 shows summed optimal and near-optimal probabilities for MaxPD and MinDS . For MinDS we present the results with penalties set to A=3,B=2 . The results are averaged over 10 3-regular graphs each of sizes n\in\{6,8,10\} . For a 3-regular graph, when all three neighbors of a node interact to contribute jointly to the cost, it results in terms involving four variables (the node plus its three neighbors), leading to a polynomial with a maximum degree of 4. Thus, in this case, the QAOA operates on a cost function of degree 4, rather than the more typical degree 2 in QUBOs. Fig. 4 shows the approximation ratio obtained for MaxPD and MaxPES for n\in\{6,8,10\} on 3-regular graphs. The derived approximation ratio applies not only to the SCOOP variants but also to the constrained versions of the problem. Specifically, Theorem 1 and Theorem 2 guarantee that the approximation ratio remains valid under the imposed constraints of MinDS and M 3 . From Figs. 3 and 4 , we observe that our method achieves an average probability of 10\%-40\% of sampling the best solution at p=1 for 3-regular graphs with up to 10 nodes. Our approach yields over 60\% probability of sampling near-optimal solutions at p=1 for n\in\{6,8,10\} —a probability that only increases with additional layers or broader solution sets. Due to the direct relationship with its constrained SCOOP twin MinDS , post-processing these solutions will only make the probability better (but not worse, see Theorem 1 ). In the past, for MinDS , comprehensive experiments have been done only on quantum annealing hardware by Dinneen et al. in 2017 [ 37 ] . M 3 , described in Lucas (2014) [ 3 ] , has not yet been tested on QA or gate-based hardware. IX Conclusions and Future Work We introduced our novel SCOOP framework (Sec. III ) that can serve as a blueprint to solve constrained COPs using vanilla QAOA. The SCOOP framework enables the discovery of optimal and -optimal solutions. Our framework 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 comes with the benefits that it scales for all inputs as it avoids penalizing solutions that do not satisfy the constraints, and supports the determination of near-optimal solutions. As use cases to apply the SCOOP framework (Secs. IV – VI ) we chose the NP-hard COPs MinDS , M 3 , and MinSC . For each, we determine its unconstrained SCOOP twin and describe its cost Hamiltonian as a HUBO. With MaxPES , and MaxPSC we not only introduced new unconstrained COPs but also showed them to be NP-hard. Our SCOOP framework not only applies to the problems reported in this paper, but also to other NP-hard constrained COPs such as the three transformational equivalent problems ( MinVC , MaxIS , and MaxCl ) featured in [ 8 ] . Table I gives a summary of problems that are identified to be SCOOP twins. For both MinDS and M 3 , we discuss our experimental results in terms of probabilities, summed probabilities of optimal and near-optimal solutions, and approximation ratios. These experiments were conducted using Xanadu’s PennyLane simulator on 3-regular graphs with up to ten qubits and eight layers of QAOA. Future Work As part of future work, we aim to extend our framework to a broader class of constrained optimization problems. We plan to investigate HUBO formulations within the context of QAOA by analyzing the complexity of their cost landscapes and comparing them to their quadratized counterparts. Furthermore, we intend to execute both QUBO and HUBO formulations of the unconstrained SCOOP twins on IBM’s quantum hardware. Argonne QTensor, a tensor-network simulator, enables efficient classical simulation of quantum circuits using tensor-network contractions. This is well studied for MaxCut with QAOA [ 30 ] . Design principles of QTensor allow for ease of extensibility of the framework with minimal changes to the underlying QTensor architecture. In Angara et al. [ 8 ] , QTensor is used to simulate QUBOs for the unconstrained twins of constrained optimization problems on sparse and 3-regular graphs with up to 70 nodes. In its current state, only QUBOs can be formulated for tensor network simulation. We plan to extend this framework to include formulations that allow higher-order terms and their expectation value calculation on QTensor.