Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.27362

Quantum-Classical Hybrid Methods for Optimization: Lessons from Classical Decomposition

David E. Bernal Neira

math.OCcs.ETquant-phSubmitted Oct 19, 2026• Announced Oct 21, 2026• 0 citations
arXivHTMLPDF

Abstract

Quantum and physics-inspired solvers provide specialized sampling interfaces for Ising and quadratic unconstrained binary optimization models, but constrained optimization requires broader coordination and certification. This survey uses classical decomposition to analyze how such solvers can be integrated into hybrid quantum-classical algorithms. We distinguish formal decomposition, reformulation and reduction, and computational orchestration. For each interface, we ask what the transformation preserves, which assumptions make the outer method converge, and which certificates the implemented inner routine supplies. The central questions are whether that information meets the classical algorithm's requirements and whether hybridization improves solution quality or total cost enough to justify its coordination overhead. Benders decomposition, column generation, graph reduction, and copositive methods illustrate this distinction by separating heuristic proposals from classical certification. We also distinguish component effects within a fixed wrapper, reduction--solver interactions, and comparisons between complete quantum-enabled and classical systems. The analyzed studies provide conditional component benefits and favorable co-design evidence, but do not establish transferable end-to-end superiority over strong classical comparators. The resulting framework identifies opportunities for constraint programming and operations research in structure-preserving design, safeguarded hybrid algorithms, and controlled benchmarking.

AI Summary

This survey asks how quantum and physics-inspired optimization samplers can be integrated into classical decomposition algorithms without confusing candidate solutions with the certificates required for convergence or optimality. It separates formal decomposition, reformulation and reduction, and computational orchestration, then examines interfaces including Benders masters, column-generation pricing, mixed-binary ADMM, graph reductions, and copositive separation. The central analysis identifies what each transformation preserves, what the outer algorithm assumes, and what the implemented quantum routine actually returns. A sampled Benders master objective is not a certified lower bound; unsuccessful heuristic pricing does not certify that no improving column exists. In copositive separation, a classically verified negative witness supplies a valid cut, whereas failure to sample one does not certify membership. Exact continuous-oracle guarantees are distinguished from finite-grid encodings and heuristic solves. Performance evidence is organized into fixed-wrapper component effects, reduction–solver interactions, and independently optimized system comparisons. The purposive corpus covers 30 studies, with 25 main-table entries, plus 23 software implementations. Reported findings are mixed: in qReduMIS, a classical simulated-annealing variant matches or exceeds the quantum arm on all 39 tested instances, although budgets are not time-matched. Other studies show conditional component benefits or favorable co-design evidence, but the corpus does not establish robust, transferable end-to-end superiority over strong classical comparators. The survey is neither exhaustive nor an experimental reproduction. Its conclusions retain each study’s restrictions, including unmatched resources, incomplete timing, simulation or projected execution costs, limited uncertainty estimates, and opaque proprietary hybrid components.

Little sign of AI-generated textAI use disclosed
OpenAI ChatGPT and Codex assisted with literature and software discovery, drafting, structural revision, technical and citation checks, copyediting, and preparation of LaTeX/TikZ source and diagrams.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
34 pages main paper, 91 pages including supplementary material, 7 figures, invited paper after CPAIOR 2024 workshop on quantum computing

Related papers

A Copositive Framework for Analysis of Hybrid Ising-Classical Algorithms

Robin Brown, David E. Bernal, Davide Venturelli +1 more

Abstract. Recent years have seen significant advances in quantum/quantum-inspired technologies capable of approximately searching for the ground state of Ising spin Hamiltonians. The promise of leveraging such technologies to accelerate the solution of difficult optimization problems has spurred an increased interest in exploring methods to integrate Ising problems as part of their solution process, with existing approaches ranging from direct transcription to hybrid quantum-classical approaches rooted in existing optimization algorithms. While it is widely acknowledged that quantum computers should augment classical computers, rather than replace them entirely, comparatively little attention has been directed toward deriving analytical characterizations of their interactions. In this paper, we present a formal analysis of hybrid algorithms in the context of solving mixed-binary quadratic programs (MBQP) via Ising solvers. By leveraging an existing completely positive reformulation of MBQPs, as well as a new strong-duality result, we show the exactness of the dual problem over the cone of copositive matrices, thus allowing the resulting reformulation to inherit the straightforward analysis of convex optimization. We propose to solve this reformulation with a hybrid quantum-classical cutting-plane algorithm. Using existing complexity results for convex cutting-plane algorithms, we deduce that the classical portion of this hybrid framework is guaranteed to be polynomial time. This suggests that when applied to NP-hard problems, the complexity of the solution is shifted onto the subroutine handled by the Ising solver.

arXiv:2207.13630•SIAM Journal on Optimization•Apr 15, 2024•16 citations

Theoretical Foundations of Hybrid Quantum-Classical Optimization, unified Framework for Combinatorial Problems

Jeffrey Quinn Cordova, Punith Khandelwal

This paper presents a comprehensive theoretical framework that unifies various hybrid quantumclassical optimization approaches for combinatorial problems. Building upon recent advances in Quantum Approximate Optimization Algorithm (QAOA) and quantum-enhanced heuristics, we establish a mathematical foundation that connects amplitude amplification, counterdiabatic annealing, and classical relaxation techniques. We derive general convergence criteria and performance bounds for hybrid algorithms, demonstrating how quantum subroutines can be systematically integrated with classical optimization methods. The framework encompasses both unconstrained and constraint-preserving formulations, providing theoretical guarantees for problem classes including graph optimization, scheduling, and resource allocation. We analyze the trade-offs between quantum circuit depth, classical preprocessing overhead, and solution quality, establishing conditions under which exponential or polynomial speedups can be achieved. Our theoretical analysis reveals fundamental limitations and opportunities in hybrid algorithm design, offering guidelines for selecting appropriate quantum-classical decompositions based on problem structure. This work contributes to the growing understanding of quantum advantage in optimization and provides a roadmap for developing provably efficient hybrid algorithms across diverse application domains.

•Oct 31, 2025•0 citations

QC-C&CG: Quantum-Classical Algorithm for Two-stage Adaptive Robust Optimization

Duong The Do, Jiaming Cheng, Duong Tung Nguyen

Quantum optimization provides a promising approach for solving large-scale combinatorial problems through quadratic unconstrained binary optimization (QUBO) formulations. However, integrating QUBO-based solvers into structured optimization frameworks while preserving solution guarantees remains a fundamental challenge. This paper develops a hybrid quantum-classical column-and-constraint generation (QCCG) framework for solving two-stage adaptive robust optimization problems with binary first-stage decisions and linear recourse under polyhedral uncertainty. The proposed approach reformulates the restricted master problem as a QUBO and solves it approximately using a quantum optimizer, while retaining a classical adversarial subproblem to compute worst-case recourse and certify solution quality. We construct a constraint-preserving QUBO encoding for inequality-constrained master problems using slack variables and penalty terms, enabling general mixed-integer structures to be mapped to quantum-compatible representations. To address inexactness arising from discretization, penalty modeling, and quantum optimization, we introduce a bound-adjustment mechanism that yields valid lower and upper bounds and provides a certified stopping criterion. We show that the proposed framework generalizes classical column-and-constraint generation and retains its convergence properties when the master problem is solved exactly. Numerical experiments on two-stage robust location-transportation problems demonstrate that the proposed hybrid approach achieves solution quality comparable to classical methods while reducing the computational burden associated with solving mixed-integer master problems, highlighting the potential of hybrid quantum-classical optimization for scalable decision-making under uncertainty.

arXiv:2609.13216•Aug 28, 2026•0 citations

Leveraging Classical and Quantum Computing for Process Systems Engineering Applications: Decomposition Algorithm with Ising Solvers for Efficient Discrete Landscape Exploration

Yirang Park, David E. Bernal Neira

Conceptual process design is a crucial aspect of chemical engineering that involves process synthesis. Mixed-integer nonlinear programming is a powerful framework for modeling such design problems by combining discrete and continuous variables; however, the combinatorial complexity of discrete choices, coupled with nonlinearities, presents challenging monolithic problems. Using decomposition, discrete subproblems can potentially benefit from Ising solvers, while simulators and nonlinear solvers offer powerful tools for handling nonlinearities. This work aims to: evaluate use of Ising-based solvers for discrete optimization and holistic process optimization through two case studies: an ionic liquid selection and its process design, and a more complex problem of drug manufacturing process optimization. The discrete subproblem is formulated as an integer program or quadratic unconstrained binary optimization and solved using a commercial classical or Ising solvers such as simulated annealing (SA), quantum annealing (QA), and entropy computing (EC) respectively. The commercial classical solver had the shortest runtime, whereas EC took the longest, followed by QA and SA, in reaching feasible and optimal solutions. The heuristics identified all or most feasible solutions in a single run, demonstrating advantages in solution diversity and efficient and broad exploration of the solution space over the classical solver, while the classical solver provides an optimality guarantee and rapid convergence speed. In process design, where insights of alternative designs and cost comparisons are more valuable than an optimal solution, heuristics offer a better-suited decision-making strategy. The comparative analysis highlights the strengths of each method and underscores the potential of this heterogeneous computing approach that leverages different methods to address practical optimization problems.

arXiv:2603.19520•Mar 19, 2026•0 citations

Performance enhancing of hybrid quantum-classical Benders approach for MILP optimization

Sergio López-Baños, Elisabeth Lobe, Ontje Lünsdorf +1 more

Mixed-integer linear programming problems are extensively used in industry for a wide range of optimization tasks. However, as they get larger, they present computational challenges for classical solvers within practical time limits. Quantum annealers can, in principle, accelerate the solution of problems formulated as quadratic unconstrained binary optimization instances, but their limited scale currently prevents achieving practical speedups. Quantum-classical algorithms have been proposed to take advantage of both paradigms and to allow current quantum computers to be used in larger problems. In this work, a hardware-agnostic Benders' decomposition algorithm and a series of enhancements with the goal of taking the most advantage of quantum computing are presented. The decomposition consists of a master problem with integer variables, which is reformulated as a quadratic unconstrained binary optimization problem and solved with a quantum annealer, and a linear subproblem solved by a classical computer. The enhancements consist, among others, of different embedding processes that substantially reduce the pre-processing time of the embedding computation without compromising solution quality, a conservative handling of cut constraints, and a stopping criterion that accounts for the limited size of current quantum computers and their heuristic nature. The proposed algorithm is benchmarked against classical approaches using a D-Wave quantum annealer for a scalable family of transmission network expansion planning problems.

quant-pharXiv:2601.14024•Jan 21, 2026•2 citations

Flexible integration of classical and quantum techniques in the evolutionary path to quantum utility

Prashanti Priya Angara

This dissertation addresses fundamental challenges in solving constrained combinatorial optimization problems using hybrid quantum-classical computing approaches. Quantum computing shows promise for tackling computationally intractable problems, current approaches face significant limitations. The path forward in computing involves combining quantum and classical computing approaches. Quantum processing units (QPUs) will play a key role in accelerating algorithms in optimization, simulation, and machine learning applications beyond what classical computers can achieve on their own, similar to how graphical processing units (GPUs) have become integral to general-purpose computing. The current generation of quantum devices is limited by noise and circuit depth constraints, making it challenging to gain practical utility. Hybrid quantum-classical approaches, which combine quantum computing resources with classical computing resources, are essential for addressing these limitations on near-term devices. In the area of combinatorial optimization, current practical state-of-the-art hybrid approaches are variational in nature, relying on parameterized quantum circuits to encode solutions and classical optimization techniques to find optimal parameters. While the ultimate goal of solving computationally intractable problems is to find 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 hybrid quantum-classical approach for tackling these challenging problems that are encoded using quadratic and higher-order unconstrained binary optimization problems (QUBO and HUBO). QAOA alternates between two operators: a problem-specific cost Hamiltonian that encodes the optimization objective, and a mixer Hamiltonian that explores the solution space. The algorithm's parameters are iteratively optimized using classical methods to maximize the probability of sampling high-quality solutions. However, these methods often struggle with solution feasibility, especially for problems where the solutions must satisfy specific constraints. Penalty-based encodings require careful parameter tuning and risk producing infeasible solutions, while feasibility-preserving methods demand deeper quantum circuits that are challenging to implement on near-term quantum devices. In this dissertation, we present novel strategies that reduce or omit dependency on penalty parameters while maintaining solution quality, effectively capturing both optimal and near-optimal solutions, and balancing the trade-offs between circuit depth and solution feasibility. 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. QAOA 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 effectiveness of the SCOOP framework on selected NP-hard problems, some of which can be encoded quadratically (such as Minimum Vertex Cover and Maximum Independent Set), and some that can be encoded using higher-order terms (such as Minimum Dominating Set, Minimum Maximal Matching, and Minimum Set Cover). We also apply our framework to constrained combinatorial optimization problems that can be solved in polynomial time, such as Minimum Edge Cover and Maximum Matching. Experimental results on full statevector simulators and tensor network simulators show that SCOOP significantly improves the probability of finding high-quality feasible solutions across various problem classes, on problems that can be encoded quadratically as well as problems that can be encoded using higher-order terms. We also demonstrate the effectiveness of SCOOP on real quantum hardware, specifically IBM Quantum Heron R2 processors with 156 qubits, showing that SCOOP can be applied to practical problems with current quantum hardware limitations. This work makes significant contributions toward achieving quantum utility by enabling systematic investigation of constrained optimization problems on quantum devices. While current quantum computing research primarily focuses on unconstrained problems like MaxCut, real-world applications typically involve constraints. SCOOP provides a scalable framework for encoding constrained problems, extending quantum computing's practical utility beyond simple unconstrained cases. By eliminating dependency on penalty parameters and providing natural problem formulations, SCOOP makes it feasible to explore quantum solutions for constrained problems where classical exact methods become intractable. This capability is crucial for identifying promising avenues for demonstrating quantum utility across diverse constrained optimization problems, advancing the practical applicability of quantum computing approaches.

•Jan 1, 2025•0 citations
Quantum and physics-inspired solvers provide specialized sampling interfaces for Ising and quadratic unconstrained binary optimization models, but constrained optimization requires broader coordination and certification. This survey uses classical decomposition to analyze how such solvers can be integrated into hybrid quantum-classical algorithms. We distinguish formal decomposition, reformulation and reduction, and computational orchestration. For each interface, we ask what the transformation preserves, which assumptions make the outer method converge, and which certificates the implemented inner routine supplies. The central questions are whether that information meets the classical algorithm's requirements and whether hybridization improves solution quality or total cost enough to justify its coordination overhead. Benders decomposition, column generation, graph reduction, and copositive methods illustrate this distinction by separating heuristic proposals from classical certification. We also distinguish component effects within a fixed wrapper, reduction--solver interactions, and comparisons between complete quantum-enabled and classical systems. The analyzed studies provide conditional component benefits and favorable co-design evidence, but do not establish transferable end-to-end superiority over strong classical comparators. The resulting framework identifies opportunities for constraint programming and operations research in structure-preserving design, safeguarded hybrid algorithms, and controlled benchmarking.
This survey asks how quantum and physics-inspired optimization samplers can be integrated into classical decomposition algorithms without confusing candidate solutions with the certificates required for convergence or optimality. It separates formal decomposition, reformulation and reduction, and computational orchestration, then examines interfaces including Benders masters, column-generation pricing, mixed-binary ADMM, graph reductions, and copositive separation.
The central analysis identifies what each transformation preserves, what the outer algorithm assumes, and what the implemented quantum routine actually returns. A sampled Benders master objective is not a certified lower bound; unsuccessful heuristic pricing does not certify that no improving column exists. In copositive separation, a classically verified negative witness supplies a valid cut, whereas failure to sample one does not certify membership. Exact continuous-oracle guarantees are distinguished from finite-grid encodings and heuristic solves.
Performance evidence is organized into fixed-wrapper component effects, reduction–solver interactions, and independently optimized system comparisons. The purposive corpus covers 30 studies, with 25 main-table entries, plus 23 software implementations. Reported findings are mixed: in qReduMIS, a classical simulated-annealing variant matches or exceeds the quantum arm on all 39 tested instances, although budgets are not time-matched. Other studies show conditional component benefits or favorable co-design evidence, but the corpus does not establish robust, transferable end-to-end superiority over strong classical comparators.
The survey is neither exhaustive nor an experimental reproduction. Its conclusions retain each study’s restrictions, including unmatched resources, incomplete timing, simulation or projected execution costs, limited uncertainty estimates, and opaque proprietary hybrid components.
Abstract. Recent years have seen significant advances in quantum/quantum-inspired technologies capable of approximately searching for the ground state of Ising spin Hamiltonians. The promise of leveraging such technologies to accelerate the solution of difficult optimization problems has spurred an increased interest in exploring methods to integrate Ising problems as part of their solution process, with existing approaches ranging from direct transcription to hybrid quantum-classical approaches rooted in existing optimization algorithms. While it is widely acknowledged that quantum computers should augment classical computers, rather than replace them entirely, comparatively little attention has been directed toward deriving analytical characterizations of their interactions. In this paper, we present a formal analysis of hybrid algorithms in the context of solving mixed-binary quadratic programs (MBQP) via Ising solvers. By leveraging an existing completely positive reformulation of MBQPs, as well as a new strong-duality result, we show the exactness of the dual problem over the cone of copositive matrices, thus allowing the resulting reformulation to inherit the straightforward analysis of convex optimization. We propose to solve this reformulation with a hybrid quantum-classical cutting-plane algorithm. Using existing complexity results for convex cutting-plane algorithms, we deduce that the classical portion of this hybrid framework is guaranteed to be polynomial time. This suggests that when applied to NP-hard problems, the complexity of the solution is shifted onto the subroutine handled by the Ising solver.
This paper presents a comprehensive theoretical framework that unifies various hybrid quantumclassical optimization approaches for combinatorial problems. Building upon recent advances in Quantum Approximate Optimization Algorithm (QAOA) and quantum-enhanced heuristics, we establish a mathematical foundation that connects amplitude amplification, counterdiabatic annealing, and classical relaxation techniques. We derive general convergence criteria and performance bounds for hybrid algorithms, demonstrating how quantum subroutines can be systematically integrated with classical optimization methods. The framework encompasses both unconstrained and constraint-preserving formulations, providing theoretical guarantees for problem classes including graph optimization, scheduling, and resource allocation. We analyze the trade-offs between quantum circuit depth, classical preprocessing overhead, and solution quality, establishing conditions under which exponential or polynomial speedups can be achieved. Our theoretical analysis reveals fundamental limitations and opportunities in hybrid algorithm design, offering guidelines for selecting appropriate quantum-classical decompositions based on problem structure. This work contributes to the growing understanding of quantum advantage in optimization and provides a roadmap for developing provably efficient hybrid algorithms across diverse application domains.
Quantum optimization provides a promising approach for solving large-scale combinatorial problems through quadratic unconstrained binary optimization (QUBO) formulations. However, integrating QUBO-based solvers into structured optimization frameworks while preserving solution guarantees remains a fundamental challenge. This paper develops a hybrid quantum-classical column-and-constraint generation (QCCG) framework for solving two-stage adaptive robust optimization problems with binary first-stage decisions and linear recourse under polyhedral uncertainty. The proposed approach reformulates the restricted master problem as a QUBO and solves it approximately using a quantum optimizer, while retaining a classical adversarial subproblem to compute worst-case recourse and certify solution quality. We construct a constraint-preserving QUBO encoding for inequality-constrained master problems using slack variables and penalty terms, enabling general mixed-integer structures to be mapped to quantum-compatible representations. To address inexactness arising from discretization, penalty modeling, and quantum optimization, we introduce a bound-adjustment mechanism that yields valid lower and upper bounds and provides a certified stopping criterion. We show that the proposed framework generalizes classical column-and-constraint generation and retains its convergence properties when the master problem is solved exactly. Numerical experiments on two-stage robust location-transportation problems demonstrate that the proposed hybrid approach achieves solution quality comparable to classical methods while reducing the computational burden associated with solving mixed-integer master problems, highlighting the potential of hybrid quantum-classical optimization for scalable decision-making under uncertainty.
Conceptual process design is a crucial aspect of chemical engineering that involves process synthesis. Mixed-integer nonlinear programming is a powerful framework for modeling such design problems by combining discrete and continuous variables; however, the combinatorial complexity of discrete choices, coupled with nonlinearities, presents challenging monolithic problems. Using decomposition, discrete subproblems can potentially benefit from Ising solvers, while simulators and nonlinear solvers offer powerful tools for handling nonlinearities. This work aims to: evaluate use of Ising-based solvers for discrete optimization and holistic process optimization through two case studies: an ionic liquid selection and its process design, and a more complex problem of drug manufacturing process optimization. The discrete subproblem is formulated as an integer program or quadratic unconstrained binary optimization and solved using a commercial classical or Ising solvers such as simulated annealing (SA), quantum annealing (QA), and entropy computing (EC) respectively. The commercial classical solver had the shortest runtime, whereas EC took the longest, followed by QA and SA, in reaching feasible and optimal solutions. The heuristics identified all or most feasible solutions in a single run, demonstrating advantages in solution diversity and efficient and broad exploration of the solution space over the classical solver, while the classical solver provides an optimality guarantee and rapid convergence speed. In process design, where insights of alternative designs and cost comparisons are more valuable than an optimal solution, heuristics offer a better-suited decision-making strategy. The comparative analysis highlights the strengths of each method and underscores the potential of this heterogeneous computing approach that leverages different methods to address practical optimization problems.
Mixed-integer linear programming problems are extensively used in industry for a wide range of optimization tasks. However, as they get larger, they present computational challenges for classical solvers within practical time limits. Quantum annealers can, in principle, accelerate the solution of problems formulated as quadratic unconstrained binary optimization instances, but their limited scale currently prevents achieving practical speedups. Quantum-classical algorithms have been proposed to take advantage of both paradigms and to allow current quantum computers to be used in larger problems. In this work, a hardware-agnostic Benders' decomposition algorithm and a series of enhancements with the goal of taking the most advantage of quantum computing are presented. The decomposition consists of a master problem with integer variables, which is reformulated as a quadratic unconstrained binary optimization problem and solved with a quantum annealer, and a linear subproblem solved by a classical computer. The enhancements consist, among others, of different embedding processes that substantially reduce the pre-processing time of the embedding computation without compromising solution quality, a conservative handling of cut constraints, and a stopping criterion that accounts for the limited size of current quantum computers and their heuristic nature. The proposed algorithm is benchmarked against classical approaches using a D-Wave quantum annealer for a scalable family of transmission network expansion planning problems.
This dissertation addresses fundamental challenges in solving constrained combinatorial optimization problems using hybrid quantum-classical computing approaches. Quantum computing shows promise for tackling computationally intractable problems, current approaches face significant limitations. The path forward in computing involves combining quantum and classical computing approaches. Quantum processing units (QPUs) will play a key role in accelerating algorithms in optimization, simulation, and machine learning applications beyond what classical computers can achieve on their own, similar to how graphical processing units (GPUs) have become integral to general-purpose computing. The current generation of quantum devices is limited by noise and circuit depth constraints, making it challenging to gain practical utility. Hybrid quantum-classical approaches, which combine quantum computing resources with classical computing resources, are essential for addressing these limitations on near-term devices. In the area of combinatorial optimization, current practical state-of-the-art hybrid approaches are variational in nature, relying on parameterized quantum circuits to encode solutions and classical optimization techniques to find optimal parameters. While the ultimate goal of solving computationally intractable problems is to find 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 hybrid quantum-classical approach for tackling these challenging problems that are encoded using quadratic and higher-order unconstrained binary optimization problems (QUBO and HUBO). QAOA alternates between two operators: a problem-specific cost Hamiltonian that encodes the optimization objective, and a mixer Hamiltonian that explores the solution space. The algorithm's parameters are iteratively optimized using classical methods to maximize the probability of sampling high-quality solutions. However, these methods often struggle with solution feasibility, especially for problems where the solutions must satisfy specific constraints. Penalty-based encodings require careful parameter tuning and risk producing infeasible solutions, while feasibility-preserving methods demand deeper quantum circuits that are challenging to implement on near-term quantum devices. In this dissertation, we present novel strategies that reduce or omit dependency on penalty parameters while maintaining solution quality, effectively capturing both optimal and near-optimal solutions, and balancing the trade-offs between circuit depth and solution feasibility. 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. QAOA 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 effectiveness of the SCOOP framework on selected NP-hard problems, some of which can be encoded quadratically (such as Minimum Vertex Cover and Maximum Independent Set), and some that can be encoded using higher-order terms (such as Minimum Dominating Set, Minimum Maximal Matching, and Minimum Set Cover). We also apply our framework to constrained combinatorial optimization problems that can be solved in polynomial time, such as Minimum Edge Cover and Maximum Matching. Experimental results on full statevector simulators and tensor network simulators show that SCOOP significantly improves the probability of finding high-quality feasible solutions across various problem classes, on problems that can be encoded quadratically as well as problems that can be encoded using higher-order terms. We also demonstrate the effectiveness of SCOOP on real quantum hardware, specifically IBM Quantum Heron R2 processors with 156 qubits, showing that SCOOP can be applied to practical problems with current quantum hardware limitations. This work makes significant contributions toward achieving quantum utility by enabling systematic investigation of constrained optimization problems on quantum devices. While current quantum computing research primarily focuses on unconstrained problems like MaxCut, real-world applications typically involve constraints. SCOOP provides a scalable framework for encoding constrained problems, extending quantum computing's practical utility beyond simple unconstrained cases. By eliminating dependency on penalty parameters and providing natural problem formulations, SCOOP makes it feasible to explore quantum solutions for constrained problems where classical exact methods become intractable. This capability is crucial for identifying promising avenues for demonstrating quantum utility across diverse constrained optimization problems, advancing the practical applicability of quantum computing approaches.