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:2606.25117

Feasibility-driven QAOA with penalty scheduling

Francesco Ferrari, Matteo Vandelli, Daniele Dragoni

quant-phSubmitted Jun 23, 2026• Announced Jun 25, 2026• 0 citations
arXivHTMLPDF

Abstract

Most available quantum algorithms address constrained optimization problems by treating constraints as soft penalty terms within a QUBO formulation. This approach requires careful adjustment of the penalty coefficients, which scales poorly with the number of constraints and lacks a proper strategy to balance feasibility and solution quality. In this work, we introduce two extensions of standard linear-ramp QAOA (lr-QAOA) tailored to problems with multiple heterogeneous constraints. We first construct $Λ$-lr-QAOA, in which each penalty term is assigned its own linear-ramp schedule, promoting penalty weights from external hyperparameters to internal variational parameters of QAOA, similarly to the objective and mixer parameters. By optimizing all schedules jointly in a single run, this approach eliminates nested penalty tuning and scales more efficiently to multiple constraints. The optimization is guided by a feasibility-driven loss function that pushes the quantum state towards high-quality feasible solutions. As a further refinement, we introduce piecewise-ramp QAOA, in which the linear ramps are replaced by two-segment piecewise schedules, enhancing the expressiveness of the Ansatz at the cost of a small parameter overhead independent of the circuit depth. We benchmark both methods on Earth-observation satellite mission planning tasks formulated as budget-constrained Maximum Weight Independent Set problems. Numerical results show that piecewise-ramp QAOA consistently outperforms lr-QAOA and $Λ$-lr-QAOA across circuit depths and system sizes. Furthermore, both $Λ$-lr-QAOA and piecewise-ramp QAOA exhibit a high feasibility rate, which is crucial in industrial applications. Our analysis highlights an intrinsic feasibility-optimality trade-off, which we address by introducing a filtered variant of the loss providing a single hyperparameter to tune this balance.

Comments
13 pages, 8 figures

Related papers

Shallow and Robust QAOA: Improving Feasibility and Hardware Performance via Linear-Chain and Ramp Schedules

Talha Azfar, Ruimin Ke

Abstract The Quantum Approximate Optimization Algorithm (QAOA) is known to struggle on near-term hardware due to constraint handling, parameter search overhead, and tight depth limits. We address this with a hardware-aware co-design: a linear-ramp parameter schedule paired with a Linear-Chain (LC) ansatz that restricts $ZZ$ interactions to nearest neighbors, lowering swaps and depth. We benchmark Linear-Ramp LC-QAOA against standard QAOA, Two-Step QAOA, and Grover-Mixer QAOA on small VRP instances across ideal simulation, Aer simulation, and IBM Eagle/Heron runs, measuring feasibility, solution quality, and hardware efficiency. Linear-ramp improves convergence and feasibility; LC reduces two-qubit gates and boosts noise robustness. Grover-Mixer and Two-Step can aid constraints in theory but are hampered in practice by deeper circuits. On hardware, overall feasibility remains $<1$\%, yet LC-QAOA with $XpXm$ dynamical decoupling more than doubles feasibility and recovers the optimum in several trials. We also show efficient scaling, including a larger case with ramp-initialized LC-QAOA plus CVaR. The results underscore hardware-aligned ansätze and structured schedules as a promising path.

•Jan 5, 2026•0 citations

Toward a linear-ramp QAOA protocol: evidence of a scaling advantage in solving some combinatorial optimization problems

J. A. Montañez-Barrera, Kristel F. L. Michielsen

Abstract The quantum approximate optimization algorithm (QAOA) is a promising algorithm for solving combinatorial optimization problems (COPs), with performance governed by variational parameters $${\{{\gamma }_{i},{\beta }_{i}\}}_{i = 0}^{p-1}$$ { γ i , β i } i = 0 p − 1 . While most prior work has focused on classically optimizing these parameters, we demonstrate that fixed linear ramp schedules, linear ramp QAOA (LR-QAOA), can efficiently approximate optimal solutions across diverse COPs. Simulations with up to N q = 42 qubits and p = 400 layers suggest that the success probability scales as $$P({x}^{* })\approx {2}^{-\eta (p){N}_{q}+C}$$ P ( x * ) ≈ 2 − η ( p ) N q + C , where η ( p ) decreases with increasing p . For example, in Weighted Maxcut instances, η (10) = 0.22 improves to η (100) = 0.05. Comparisons with classical algorithms, including simulated annealing, Tabu Search, and branch-and-bound, show a scaling advantage for LR-QAOA. We show results of LR-QAOA on multiple QPUs (IonQ, Quantinuum, IBM) with up to N q = 109 qubits, p = 100, and circuits requiring 21,200 CNOT gates. Finally, we present a noise model based on two-qubit gate counts that accurately reproduces the experimental behavior of LR-QAOA.

arXiv:2405.09169•npj Quantum Information•Aug 4, 2025•34 citations

Extrapolation method to optimize linear-ramp quantum approximate optimization algorithm parameters: Evaluation of runtime scaling

Vanessa Dehn, Martin Zaefferer, Gerhard Hellstern +3 more

The quantum approximate optimization algorithm (QAOA) has been suggested as a promising candidate for the solution of combinatorial optimization problems. Yet, whether—or under what conditions—it may offer an advantage compared with classical algorithms remains to be proven. Using the standard variational form of QAOA requires a high number of circuit parameters that have to be optimized at a sufficiently large depth, which constitutes a bottleneck for achieving a potential scaling advantage. The linear-ramp QAOA has been proposed to address this issue, as it relies on only two parameters that have to be optimized. Based on this, we develop a method to estimate suitable values for those parameters through extrapolation, starting from smaller problem sizes (number of qubits) toward larger problem sizes. We apply this method to several use cases, such as portfolio optimization, feature selection, clustering, and weighted maxcut. From results obtained on a noiseless quantum emulator, we evaluate the quantum runtime scaling for finding the optimal solution and compare it with that of classical methods. In the case of portfolio optimization, we demonstrate superior scaling compared with the classical runtime for the problem sizes of up to 28 qubits that we consider in this work.

arXiv:2504.08577•Physical Review A•Jan 15, 2026•2 citations

Constraint-Aware Quantum Optimization via Hamming Weight Operators

Yajie Hao, Qiming Ding, Xiao Yuan +1 more

Constrained combinatorial optimization with strict linear constraints underpins applications in drug discovery, power grids, logistics, and finance, yet remains computationally demanding for classical algorithms, especially at large scales. The Quantum Approximate Optimization Algorithm (QAOA) offers a promising quantum framework, but conventional penalty-based formulations distort optimization landscapes and demand deep circuits, undermining scalability on near-term hardware. In this work, we introduce Hamming Weight Operators, a new class of constraint-aware operators that confine quantum evolution strictly within the feasible subspace. Building on this idea, we develop Adaptive Hamming Weight Operator QAOA, which dynamically selects the most effective operators to construct shallow, problem-tailored circuits. We validate our approach on benchmark tasks from both finance and high-energy physics, specifically portfolio optimization and two-jet clustering with energy balance. Across these problems, our method inherently satisfies all constraints by construction, converges faster, and achieves higher Approximation Ratios than penalty-based QAOA, while requiring roughly half as many gates. By embedding constraint-aware operators into an adaptive variational framework, our approach establishes a scalable and hardware-efficient pathway for solving practical constrained optimization problems on near-term quantum devices.

quant-pharXiv:2601.01516•Science China Physics Mechanics and Astronomy•Jan 6, 2026•2 citations

A Non-Variational Quantum Approach to the Job Shop Scheduling Problem

Miguel Angel Lopez-Ruiz, Emily L. Tucker, Arnold, Emma M. +3 more

Quantum heuristics offer a potential advantage for combinatorial optimization but are constrained by near-term hardware limitations. We introduce Iterative-QAOA, a variant of QAOA designed to mitigate these constraints. The algorithm combines a non-variational, shallow-depth circuit approach using fixed-parameter schedules with an iterative warm-starting process. We benchmark the algorithm on Just-in-Time Job Shop Scheduling Problem (JIT-JSSP) instances on IonQ Forte Generation QPUs, representing some of the largest such problems ever executed on quantum hardware. We compare the performance of the algorithm against both the Variational Quantum Imaginary Time Evolution (VarQITE) algorithm and the non-variational Linear Ramp (LR) QAOA algorithm. We find that Iterative-QAOA robustly converges to find optimal solutions as well as high-quality, near-optimal solutions for all problem instances evaluated. We evaluate the algorithm on larger problem instances up to 97 qubits using tensor network simulations. The scaling behavior of the algorithm indicates potential for solving industrial-scale problems on fault-tolerant quantum computers.

arXiv:2510.26859•Oct 30, 2025•0 citations

An Empirical Evaluation of Quantum-Inspired QUBO Methods for Heterogeneous HPC Workflow Mapping and Scheduling

Aasish Kumar Sharma, Christian Boehme, Julian Martin Kunkel

Heterogeneous HPC workflow scheduling under multiple hard constraints poses a challenging combinatorial optimization problem. Classical exact solvers provide optimal solutions but often face scalability limitations, motivating interest in quantum-inspired Quadratic Unconstrained Binary Optimization (QUBO) formulations as alternative optimization paradigms. This work presents a systematic and reproducible empirical evaluation of QUBO-based scheduling methods against established classical baselines, including MILP, CP-SAT, GA, and HEFT. We evaluate three QUBO variants, single-run simulated annealing, multi-attempt annealing, and a layered QAOA-inspired schedule, together with hybrid enhancement strategies on both ground-truth validation workflows (3–4 tasks) and synthetic scaling instances (5–20 tasks). All solvers are assessed through a unified evaluation pipeline that explicitly tracks feasibility, makespan, and resource utilization under progressive constraint activation and controlled penalty sweeps. Results show that all approaches recover the expected optimal makespan on validation instances, confirming formulation correctness. However, feasibility degradation emerges for specific QUBO variants as constraint interactions intensify, particularly when communication costs are introduced. Penalty sensitivity analysis reveals a sharp feasibility threshold for QUBO-SA, where insufficient penalties consistently fail and moderate-to-strong penalties restore feasibility. Scaling experiments delineate the regimes in which classical solvers and heuristics remain robust across all tested sizes, while QUBO-SA loses feasibility beyond 15 tasks and the QAOA-inspired variant beyond 10 tasks. Overall, the study provides a clear empirical characterization of the reliability boundaries of quantum-inspired QUBO formulations for heterogeneous HPC scheduling and identifies the regimes where classical approaches remain preferable under current formulations and solver capabilities.

ISC High Performance (ISC)•Jun 1, 2026•0 citations
Most available quantum algorithms address constrained optimization problems by treating constraints as soft penalty terms within a QUBO formulation. This approach requires careful adjustment of the penalty coefficients, which scales poorly with the number of constraints and lacks a proper strategy to balance feasibility and solution quality. In this work, we introduce two extensions of standard linear-ramp QAOA (lr-QAOA) tailored to problems with multiple heterogeneous constraints. We first construct ΛΛΛ-lr-QAOA, in which each penalty term is assigned its own linear-ramp schedule, promoting penalty weights from external hyperparameters to internal variational parameters of QAOA, similarly to the objective and mixer parameters. By optimizing all schedules jointly in a single run, this approach eliminates nested penalty tuning and scales more efficiently to multiple constraints. The optimization is guided by a feasibility-driven loss function that pushes the quantum state towards high-quality feasible solutions. As a further refinement, we introduce piecewise-ramp QAOA, in which the linear ramps are replaced by two-segment piecewise schedules, enhancing the expressiveness of the Ansatz at the cost of a small parameter overhead independent of the circuit depth. We benchmark both methods on Earth-observation satellite mission planning tasks formulated as budget-constrained Maximum Weight Independent Set problems. Numerical results show that piecewise-ramp QAOA consistently outperforms lr-QAOA and ΛΛΛ-lr-QAOA across circuit depths and system sizes. Furthermore, both ΛΛΛ-lr-QAOA and piecewise-ramp QAOA exhibit a high feasibility rate, which is crucial in industrial applications. Our analysis highlights an intrinsic feasibility-optimality trade-off, which we address by introducing a filtered variant of the loss providing a single hyperparameter to tune this balance.
Abstract The Quantum Approximate Optimization Algorithm (QAOA) is known to struggle on near-term hardware due to constraint handling, parameter search overhead, and tight depth limits. We address this with a hardware-aware co-design: a linear-ramp parameter schedule paired with a Linear-Chain (LC) ansatz that restricts ZZZZZZ interactions to nearest neighbors, lowering swaps and depth. We benchmark Linear-Ramp LC-QAOA against standard QAOA, Two-Step QAOA, and Grover-Mixer QAOA on small VRP instances across ideal simulation, Aer simulation, and IBM Eagle/Heron runs, measuring feasibility, solution quality, and hardware efficiency. Linear-ramp improves convergence and feasibility; LC reduces two-qubit gates and boosts noise robustness. Grover-Mixer and Two-Step can aid constraints in theory but are hampered in practice by deeper circuits. On hardware, overall feasibility remains <1<1<1\%, yet LC-QAOA with XpXmXpXmXpXm dynamical decoupling more than doubles feasibility and recovers the optimum in several trials. We also show efficient scaling, including a larger case with ramp-initialized LC-QAOA plus CVaR. The results underscore hardware-aligned ansätze and structured schedules as a promising path.
Abstract The quantum approximate optimization algorithm (QAOA) is a promising algorithm for solving combinatorial optimization problems (COPs), with performance governed by variational parameters {γi,βi}i=0p−1{\{{\gamma }_{i},{\beta }_{i}\}}_{i = 0}^{p-1}{γi​,βi​}i=0p−1​ { γ i , β i } i = 0 p − 1 . While most prior work has focused on classically optimizing these parameters, we demonstrate that fixed linear ramp schedules, linear ramp QAOA (LR-QAOA), can efficiently approximate optimal solutions across diverse COPs. Simulations with up to N q = 42 qubits and p = 400 layers suggest that the success probability scales as P(x∗)≈2−η(p)Nq+CP({x}^{* })\approx {2}^{-\eta (p){N}_{q}+C}P(x∗)≈2−η(p)Nq​+C P ( x * ) ≈ 2 − η ( p ) N q + C , where η ( p ) decreases with increasing p . For example, in Weighted Maxcut instances, η (10) = 0.22 improves to η (100) = 0.05. Comparisons with classical algorithms, including simulated annealing, Tabu Search, and branch-and-bound, show a scaling advantage for LR-QAOA. We show results of LR-QAOA on multiple QPUs (IonQ, Quantinuum, IBM) with up to N q = 109 qubits, p = 100, and circuits requiring 21,200 CNOT gates. Finally, we present a noise model based on two-qubit gate counts that accurately reproduces the experimental behavior of LR-QAOA.
The quantum approximate optimization algorithm (QAOA) has been suggested as a promising candidate for the solution of combinatorial optimization problems. Yet, whether—or under what conditions—it may offer an advantage compared with classical algorithms remains to be proven. Using the standard variational form of QAOA requires a high number of circuit parameters that have to be optimized at a sufficiently large depth, which constitutes a bottleneck for achieving a potential scaling advantage. The linear-ramp QAOA has been proposed to address this issue, as it relies on only two parameters that have to be optimized. Based on this, we develop a method to estimate suitable values for those parameters through extrapolation, starting from smaller problem sizes (number of qubits) toward larger problem sizes. We apply this method to several use cases, such as portfolio optimization, feature selection, clustering, and weighted maxcut. From results obtained on a noiseless quantum emulator, we evaluate the quantum runtime scaling for finding the optimal solution and compare it with that of classical methods. In the case of portfolio optimization, we demonstrate superior scaling compared with the classical runtime for the problem sizes of up to 28 qubits that we consider in this work.
Constrained combinatorial optimization with strict linear constraints underpins applications in drug discovery, power grids, logistics, and finance, yet remains computationally demanding for classical algorithms, especially at large scales. The Quantum Approximate Optimization Algorithm (QAOA) offers a promising quantum framework, but conventional penalty-based formulations distort optimization landscapes and demand deep circuits, undermining scalability on near-term hardware. In this work, we introduce Hamming Weight Operators, a new class of constraint-aware operators that confine quantum evolution strictly within the feasible subspace. Building on this idea, we develop Adaptive Hamming Weight Operator QAOA, which dynamically selects the most effective operators to construct shallow, problem-tailored circuits. We validate our approach on benchmark tasks from both finance and high-energy physics, specifically portfolio optimization and two-jet clustering with energy balance. Across these problems, our method inherently satisfies all constraints by construction, converges faster, and achieves higher Approximation Ratios than penalty-based QAOA, while requiring roughly half as many gates. By embedding constraint-aware operators into an adaptive variational framework, our approach establishes a scalable and hardware-efficient pathway for solving practical constrained optimization problems on near-term quantum devices.
Quantum heuristics offer a potential advantage for combinatorial optimization but are constrained by near-term hardware limitations. We introduce Iterative-QAOA, a variant of QAOA designed to mitigate these constraints. The algorithm combines a non-variational, shallow-depth circuit approach using fixed-parameter schedules with an iterative warm-starting process. We benchmark the algorithm on Just-in-Time Job Shop Scheduling Problem (JIT-JSSP) instances on IonQ Forte Generation QPUs, representing some of the largest such problems ever executed on quantum hardware. We compare the performance of the algorithm against both the Variational Quantum Imaginary Time Evolution (VarQITE) algorithm and the non-variational Linear Ramp (LR) QAOA algorithm. We find that Iterative-QAOA robustly converges to find optimal solutions as well as high-quality, near-optimal solutions for all problem instances evaluated. We evaluate the algorithm on larger problem instances up to 97 qubits using tensor network simulations. The scaling behavior of the algorithm indicates potential for solving industrial-scale problems on fault-tolerant quantum computers.
Heterogeneous HPC workflow scheduling under multiple hard constraints poses a challenging combinatorial optimization problem. Classical exact solvers provide optimal solutions but often face scalability limitations, motivating interest in quantum-inspired Quadratic Unconstrained Binary Optimization (QUBO) formulations as alternative optimization paradigms. This work presents a systematic and reproducible empirical evaluation of QUBO-based scheduling methods against established classical baselines, including MILP, CP-SAT, GA, and HEFT. We evaluate three QUBO variants, single-run simulated annealing, multi-attempt annealing, and a layered QAOA-inspired schedule, together with hybrid enhancement strategies on both ground-truth validation workflows (3–4 tasks) and synthetic scaling instances (5–20 tasks). All solvers are assessed through a unified evaluation pipeline that explicitly tracks feasibility, makespan, and resource utilization under progressive constraint activation and controlled penalty sweeps. Results show that all approaches recover the expected optimal makespan on validation instances, confirming formulation correctness. However, feasibility degradation emerges for specific QUBO variants as constraint interactions intensify, particularly when communication costs are introduced. Penalty sensitivity analysis reveals a sharp feasibility threshold for QUBO-SA, where insufficient penalties consistently fail and moderate-to-strong penalties restore feasibility. Scaling experiments delineate the regimes in which classical solvers and heuristics remain robust across all tested sizes, while QUBO-SA loses feasibility beyond 15 tasks and the QAOA-inspired variant beyond 10 tasks. Overall, the study provides a clear empirical characterization of the reliability boundaries of quantum-inspired QUBO formulations for heterogeneous HPC scheduling and identifies the regimes where classical approaches remain preferable under current formulations and solver capabilities.