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

LMLPG-TQA Lagrangian-Multiplier and LP-Guided Trotterized Quantum Annealing for Constrained Combinatorial Optimization

Dominika Pillerová

Published Nov 1, 2026• 0 citations
Publisher

Abstract

I present a hybrid quantum-classical framework for constrained combinatorialoptimization based on fixed-schedule Trotterized Quantum Annealing (TQA). Theproposed approach combines Lagrangian-inspired penalty encoding, linearprogramming (LP)-guided problem decomposition, and static interaction pruning toimprove the sampling of high-quality feasible solutions while limiting quantum circuitcomplexity. Unlike conventional variational approaches that rely on iterative classical optimization ofcircuit parameters, my method employs a predetermined annealing schedule and penaltycoefficients determined during classical preprocessing. The constrained objective isencoded using a linear weight term and a quadratic penalty on deviations from theassigned capacity. LP relaxation guides the allocation of the global capacity betweenindependent problem groups, while static pruning reduces the number of pairwiseinteractions in the problem Hamiltonian. The resulting Trotterized evolution isimplemented without iterative optimization of quantum circuit angles. The framework is investigated on a 24-item knapsack problem, decomposed into twoindependent 12-variable subproblems and executed on quantum hardware. It builds onmy earlier experiments with ungrouped TQA on knapsack instances of 10 to 15 items, inwhich I used a sampling budget of 10 × 2^N shots. Because the fixed, coarse Trotterizedschedule spreads the probability over many configurations, the best solutions have smallindividual probabilities: with smaller budgets their position in the frequency ranking wasdominated by sampling noise and they could remain far down the list, whereas at 10 ×2^N shots they moved towards the front. In several runs on 15 items the optimalsolution was found within the top 1 % of the most frequently sampled configurations.These observations are empirical, drawn from a large number of runs rather than acontrolled scaling study. They suggest that the method may offer an effective way ofaccessing near-optimal solutions without relying on repeated variational parameteroptimization, although it requires a higher sampling budget in the experimentsconsidered. For the 24-item problem, a classical reconstruction procedure combinesindependently sampled group configurations to recover globally feasible solutions,including the exact optimum, even when the complete optimal bitstring is not observedin a single quantum measurement. These results motivate further investigation of fixed-schedule, penalty-based TQA as ahardware-oriented alternative to variational quantum optimization for constrained problems.In particular, the observed sampling behavior, feasibility-quality trade-off, andresource requirements provide a basis for systematic comparisons with CVaR-based andoptimizer-driven approaches.

DOI
10.5281/zenodo.23860343

Related papers

Variational determination of penalty parameters in quantum annealing

Ji-Qian Qin, Yu Yunlong, Xiang‐Bin Wang

Abstract Quantum annealing (QA) offers a promising approach for solving constrained combinatorial optimization on near-term quantum devices. It encodes solutions into the ground states of the Ising problem Hamiltonians through penalty terms and penalty parameters to enforce constraints. We propose a variational determination framework to address the issue of penalty parameter selection through three progressively generalized methods: the Frozen method variationally adjusts parameters in a tunable Hamiltonian to prepare evolved states minimizing the energy of a target Hamiltonian with Frozen parameters; the Time-Transfer method applies optimized parameters to longer annealing times; and the Full-Transfer method extends this approach across both system sizes and annealing durations. The effectiveness of these methods stems from energy minimization steering the evolution toward the low-energy subspace. Evaluated on vertex cover problems over 40 randomly generated 12-vertex 3-regular graphs, the Frozen method improves the average single-run success probability from 0.27 ± 0.02 to 0.62 ± 0.03 at t a = 10 , and reduces the average number of runs required for 99.9% success probability by 3.8 times at t a = 2 (including optimization overhead). Crucially, both Time-Transfer method and Full-Transfer method achieve single-run fidelity improvements comparable to the Frozen method, while reducing the number of runs required for 99.9% success probability at t a = 2.5 by 6.63 times and 6.4 times, respectively. The speedup of the Time-Transfer method excludes initial optimization at t a = 2 , whereas Full-Transfer method provides end-to-end acceleration. Our variational framework establishes that optimization-informed short-time QA can match the performance of extended schedules, offering a practical approach for current quantum devices.

Quantum Science and Technology•Dec 23, 2025•1 citation

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

Postprocessing Variationally Scheduled Quantum Algorithm for Constrained Combinatorial Optimization Problems

Tatsuhiko Shirai, Nozomu Togawa

We propose a post-processing variationally scheduled quantum algorithm (pVSQA) for solving constrained combinatorial optimization problems (COPs). COPs are typically transformed into ground-state search problems of the Ising model on a quantum annealer or gate-based quantum device. Variational methods are used to find an optimal schedule function that leads to high-quality solutions in a short amount of time. Post-processing techniques convert the output solutions of the quantum devices to satisfy the constraints of the COPs. pVSQA combines the variational methods and the post-processing technique. We obtain a sufficient condition for constrained COPs to apply pVSQA based on a greedy post-processing algorithm. We apply the proposed method to two constrained NP-hard COPs: the graph partitioning problem and the quadratic knapsack problem. pVSQA on a simulator shows that a small number of variational parameters is sufficient to achieve a (near-)optimal performance within a predetermined operation time. Then building upon the simulator results, we implement pVSQA on a quantum annealer and a gate-based quantum device. The experimental results demonstrate the effectiveness of our proposed method.

arXiv:2309.08120•IEEE Transactions on Quantum Engineering•Jan 1, 2024•8 citations

On good encodings for quantum annealer and digital optimization solvers

Alberto Ceselli, Marco Premoli

Several optimization solvers inspired by quantum annealing have been recently developed, either running on actual quantum hardware or simulating it on traditional digital computers. Industry and academics look at their potential in solving hard combinatorial optimization problems. Formally, they provide heuristic solutions for Ising models, which are equivalent to quadratic unconstrained binary optimization (QUBO). Constraints on solutions feasibility need to be properly encoded. We experiment on different ways of performing such an encoding. As benchmark we consider the cardinality constrained quadratic knapsack problem (CQKP), a minimal extension of QUBO with one inequality and one equality constraint. We consider different strategies of constraints penalization and variables encoding. We compare three QUBO solvers: quantum annealing on quantum hardware (D-Wave Advantage), probabilistic algorithms on digital hardware and mathematical programming solvers. We analyze their QUBO resolution quality and time, and the persistence values extracted in the quantum annealing sampling process. Our results show that a linear penalization of CQKP inequality improves current best practice. Furthermore, using such a linear penalization, persistence values produced by quantum hardware in a generic way allow to match a specific CQKP metric from literature. They are therefore suitable for general purpose variable fixing in core algorithms for combinatorial optimization.

Scientific Reports•Apr 6, 2023•10 citations

A Quantum Approach for Stochastic Constrained Binary Optimization

Sarthak Gupta, Vassilis Kekatos

Analytical and practical evidence indicates the advantage of quantum computing solutions over classical alternatives. Quantum-based heuristics relying on the variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA) have been shown numerically to generate high-quality solutions to hard combinatorial problems, yet incorporating constraints to such problems has been elusive. To this end, this work puts forth a quantum heuristic to cope with stochastic binary quadratically constrained quadratic programs (QCQP). Identifying the strength of quantum circuits to efficiently generate samples from probability distributions that are otherwise hard to sample from, the variational quantum circuit is trained to generate binaryvalued vectors to approximately solve the aforesaid stochastic program. The method builds upon dual decomposition and entails solving a sequence of judiciously modified standard VQE tasks. Tests on several synthetic problem instances using a quantum simulator corroborate the near-optimality and feasibility of the method, and its potential to generate feasible solutions for the deterministic QCQP too.

arXiv:2301.01443•IEEE International Conference on Acoustics Speech and Signal Processing•May 5, 2023•4 citations

Optimization of Penalty Weights in Quantum Annealing for Dynamic Spectrum Allocation

Yuhi Kurebayashi, Yui Yamashita, Yoshito Tobe

Quantum annealing offers a powerful means to solve combinatorial optimization problems formulated as Quadratic Unconstrained Binary Optimization (QUBO). In constrained problems, appropriate penalty weights are critical: too small yields infeasibility, too large harms solution quality. This paper proposes a rigorous method to determine lower bounds for penalty weights, ensuring constraint satisfaction without degrading optimization. Applied to the Dynamic Spectrum Allocation (DSA) problem with priority-aware extensions, the method leverages iterative quantum annealing to reduce tuning overhead. Experiments show improved efficiency and feasibility over conventional approaches.

Asia-Pacific Conference on Communications (APCC)•Nov 26, 2025•0 citations
I present a hybrid quantum-classical framework for constrained combinatorialoptimization based on fixed-schedule Trotterized Quantum Annealing (TQA). Theproposed approach combines Lagrangian-inspired penalty encoding, linearprogramming (LP)-guided problem decomposition, and static interaction pruning toimprove the sampling of high-quality feasible solutions while limiting quantum circuitcomplexity. Unlike conventional variational approaches that rely on iterative classical optimization ofcircuit parameters, my method employs a predetermined annealing schedule and penaltycoefficients determined during classical preprocessing. The constrained objective isencoded using a linear weight term and a quadratic penalty on deviations from theassigned capacity. LP relaxation guides the allocation of the global capacity betweenindependent problem groups, while static pruning reduces the number of pairwiseinteractions in the problem Hamiltonian. The resulting Trotterized evolution isimplemented without iterative optimization of quantum circuit angles. The framework is investigated on a 24-item knapsack problem, decomposed into twoindependent 12-variable subproblems and executed on quantum hardware. It builds onmy earlier experiments with ungrouped TQA on knapsack instances of 10 to 15 items, inwhich I used a sampling budget of 10 × 2^N shots. Because the fixed, coarse Trotterizedschedule spreads the probability over many configurations, the best solutions have smallindividual probabilities: with smaller budgets their position in the frequency ranking wasdominated by sampling noise and they could remain far down the list, whereas at 10 ×2^N shots they moved towards the front. In several runs on 15 items the optimalsolution was found within the top 1 % of the most frequently sampled configurations.These observations are empirical, drawn from a large number of runs rather than acontrolled scaling study. They suggest that the method may offer an effective way ofaccessing near-optimal solutions without relying on repeated variational parameteroptimization, although it requires a higher sampling budget in the experimentsconsidered. For the 24-item problem, a classical reconstruction procedure combinesindependently sampled group configurations to recover globally feasible solutions,including the exact optimum, even when the complete optimal bitstring is not observedin a single quantum measurement. These results motivate further investigation of fixed-schedule, penalty-based TQA as ahardware-oriented alternative to variational quantum optimization for constrained problems.In particular, the observed sampling behavior, feasibility-quality trade-off, andresource requirements provide a basis for systematic comparisons with CVaR-based andoptimizer-driven approaches.
Abstract Quantum annealing (QA) offers a promising approach for solving constrained combinatorial optimization on near-term quantum devices. It encodes solutions into the ground states of the Ising problem Hamiltonians through penalty terms and penalty parameters to enforce constraints. We propose a variational determination framework to address the issue of penalty parameter selection through three progressively generalized methods: the Frozen method variationally adjusts parameters in a tunable Hamiltonian to prepare evolved states minimizing the energy of a target Hamiltonian with Frozen parameters; the Time-Transfer method applies optimized parameters to longer annealing times; and the Full-Transfer method extends this approach across both system sizes and annealing durations. The effectiveness of these methods stems from energy minimization steering the evolution toward the low-energy subspace. Evaluated on vertex cover problems over 40 randomly generated 12-vertex 3-regular graphs, the Frozen method improves the average single-run success probability from 0.27 ± 0.02 to 0.62 ± 0.03 at t a = 10 , and reduces the average number of runs required for 99.9% success probability by 3.8 times at t a = 2 (including optimization overhead). Crucially, both Time-Transfer method and Full-Transfer method achieve single-run fidelity improvements comparable to the Frozen method, while reducing the number of runs required for 99.9% success probability at t a = 2.5 by 6.63 times and 6.4 times, respectively. The speedup of the Time-Transfer method excludes initial optimization at t a = 2 , whereas Full-Transfer method provides end-to-end acceleration. Our variational framework establishes that optimization-informed short-time QA can match the performance of extended schedules, offering a practical approach for current quantum devices.
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.
We propose a post-processing variationally scheduled quantum algorithm (pVSQA) for solving constrained combinatorial optimization problems (COPs). COPs are typically transformed into ground-state search problems of the Ising model on a quantum annealer or gate-based quantum device. Variational methods are used to find an optimal schedule function that leads to high-quality solutions in a short amount of time. Post-processing techniques convert the output solutions of the quantum devices to satisfy the constraints of the COPs. pVSQA combines the variational methods and the post-processing technique. We obtain a sufficient condition for constrained COPs to apply pVSQA based on a greedy post-processing algorithm. We apply the proposed method to two constrained NP-hard COPs: the graph partitioning problem and the quadratic knapsack problem. pVSQA on a simulator shows that a small number of variational parameters is sufficient to achieve a (near-)optimal performance within a predetermined operation time. Then building upon the simulator results, we implement pVSQA on a quantum annealer and a gate-based quantum device. The experimental results demonstrate the effectiveness of our proposed method.
Several optimization solvers inspired by quantum annealing have been recently developed, either running on actual quantum hardware or simulating it on traditional digital computers. Industry and academics look at their potential in solving hard combinatorial optimization problems. Formally, they provide heuristic solutions for Ising models, which are equivalent to quadratic unconstrained binary optimization (QUBO). Constraints on solutions feasibility need to be properly encoded. We experiment on different ways of performing such an encoding. As benchmark we consider the cardinality constrained quadratic knapsack problem (CQKP), a minimal extension of QUBO with one inequality and one equality constraint. We consider different strategies of constraints penalization and variables encoding. We compare three QUBO solvers: quantum annealing on quantum hardware (D-Wave Advantage), probabilistic algorithms on digital hardware and mathematical programming solvers. We analyze their QUBO resolution quality and time, and the persistence values extracted in the quantum annealing sampling process. Our results show that a linear penalization of CQKP inequality improves current best practice. Furthermore, using such a linear penalization, persistence values produced by quantum hardware in a generic way allow to match a specific CQKP metric from literature. They are therefore suitable for general purpose variable fixing in core algorithms for combinatorial optimization.
Analytical and practical evidence indicates the advantage of quantum computing solutions over classical alternatives. Quantum-based heuristics relying on the variational quantum eigensolver (VQE) and the quantum approximate optimization algorithm (QAOA) have been shown numerically to generate high-quality solutions to hard combinatorial problems, yet incorporating constraints to such problems has been elusive. To this end, this work puts forth a quantum heuristic to cope with stochastic binary quadratically constrained quadratic programs (QCQP). Identifying the strength of quantum circuits to efficiently generate samples from probability distributions that are otherwise hard to sample from, the variational quantum circuit is trained to generate binaryvalued vectors to approximately solve the aforesaid stochastic program. The method builds upon dual decomposition and entails solving a sequence of judiciously modified standard VQE tasks. Tests on several synthetic problem instances using a quantum simulator corroborate the near-optimality and feasibility of the method, and its potential to generate feasible solutions for the deterministic QCQP too.
Quantum annealing offers a powerful means to solve combinatorial optimization problems formulated as Quadratic Unconstrained Binary Optimization (QUBO). In constrained problems, appropriate penalty weights are critical: too small yields infeasibility, too large harms solution quality. This paper proposes a rigorous method to determine lower bounds for penalty weights, ensuring constraint satisfaction without degrading optimization. Applied to the Dynamic Spectrum Allocation (DSA) problem with priority-aware extensions, the method leverages iterative quantum annealing to reduce tuning overhead. Experiments show improved efficiency and feasibility over conventional approaches.