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

International Joint Conference on Computer Science and Software Engineering

Improving Knapsack QUBO Embeddings on D-Wave Systems via a Chained Partial-Sum Formulation

Woratham Khangtragool, Sanpawat Kantabutra

Published Jun 24, 2026• 0 citations
Publisher

Abstract

Exact QUBO formulations of knapsack preserve correctness at the ground state, but they induce dense interactions that are costly to minor-embed on sparse quantum annealing hardware. We propose a knapsack-specific chained partial-sum formulation that replaces one dense budget constraint by a sequence of smaller constraints with intermediate variables. This preserves exactness while reducing interactions and density. We give a sufficient penalty condition for correctness, propose a greedy grouping heuristic with adaptive register sizing, and benchmark embeddability on working graphs of D-Wave Pegasus and Zephyr systems. Compared with the standard dense slack formulation, the proposed formulation supports larger instances, uses fewer physical qubits, and produces shorter chains under D-Wave’s heuristic embedding algorithm. These improvements are consistent across the tested hardware topologies and indicate that the chained partial-sum formulation is a practical exact alternative for embedding knapsack QUBOs on current quantum annealing systems.

DOI
10.1109/jcsse68839.2026.11597000

Related papers

Sparse QUBO Formulation for Efficient Embedding via Network-Based Decomposition of Equality and Inequality Constraints

Kohei Suda, Soshun Naito, Yoshihiko Hasegawa

Quantum annealing is a promising approach for solving combinatorial optimization problems. However, its performance is often limited by the overhead of additional qubits required for embedding logical QUBO models onto quantum annealers. This overhead becomes severe when logical QUBO models have dense connectivity. Such dense structures frequently arise when formulating equality and inequality constraints. To address this issue, we propose a method to construct a significantly sparser logical QUBO model for these constraints. By adding auxiliary variables based on specific network structures, our approach decomposes the original constraint into smaller, more manageable constraints. We demonstrate that this method reduces the number of edges (quadratic terms) from $O(N^2)$ to $O(N)$ for the one-hot constraint and to $O(N\log N)$ in the worst case for general equality constraints, where $N$ is the number of variables. Experimental results on D-Wave's hardware show that our formulation leads to substantial reductions in the number of qubits required for embedding, shorter average chain lengths, lower chain break rates, and higher feasible solution rates compared to conventional methods. This work provides a practical tool for efficiently solving constrained optimization problems on current and future quantum annealers.

quant-pharXiv:2601.18108•Jan 27, 2026•1 citation

Resource-efficient QUBO formulations for the Knapsack and Bin Packing problem

Pim van den Heuvel

Quantum computing approaches, such as Quantum Annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA), have emerged as promising candidates for solving combinatorial optimization problems. Since these approaches typically work with Quadratic Unconstrained Binary Optimization (QUBO) problems, constraints, when present, are commonly encoded as penalty terms. Conventional approaches to incorporate inequality constraints into QUBO formulations additionally require the introduction of slack variables, increasing the required number of qubits. The Knapsack and Bin Packing problems are optimization problems with such inequality constraints. We show that the number of slack variables required to formulate the Knapsack problem as a QUBO problem can be reduced using certain properties specific to this problem. Moreover, we present two separate strategies for the Knapsack and Bin Packing problems that avoid using the costly slack variables altogether. Instead, both strategies solve several QUBO problems, with varying penalty constants, such that at least one of them is a good representation of the given optimization problem. Numerical simulations of QAOA, as well as experiments on a D-Wave quantum annealer, show that these slack-less approaches can improve performance compared to the conventional slack variable method (in terms of success probability), even when the latter is allowed to vary penalty constants too.

•Jan 1, 2025•0 citations

Resource-efficient formulations of the Knapsack problem for quantum computing

Pim van den Heuvel, Vrinda Mehta, Dennis Willsch +2 more

Quantum computing has emerged as a new tool for solving combinatorial optimization problems. Quantum optimization approaches usually operate on the subclass of Quadratic Unconstrained Binary Optimization (QUBO) problems. Many optimization problems can be reformulated in this form, though there are often multiple ways to do so. The choice of formulation can considerably affect the performance of QUBO solvers in practice. In this work, we study QUBO formulations of the Knapsack problem, a canonical example of a problem with inequality constraints. In the standard formulation these constraints are converted into penalty terms, which requires additional slack variables. Here, we investigate three more resource-efficient approaches for formulating the Knapsack as a QUBO. The first two modify the standard formulation, either by deriving a smaller penalty constant or by reducing the number of slack variables. The third approach is a wholly different method, which avoids the use of slack variables entirely. All three approaches increase the probability of finding the optimal solution, both in simulations of the linear ramp Quantum Approximate Optimization Algorithm (LR-QAOA) and on a D-Wave quantum annealer. The slackless method performs best, increasing success probabilities by several orders of magnitude even for relatively small problem sizes.

arXiv:2611.06797•Nov 4, 2026•0 citations

A Penalty-Free Pipeline for Direct Quantum-Annealer Portfolio Optimization

Luis Lozano

Cardinality-constrained portfolio selection is routinely cast as a quadratic unconstrained binary optimization (QUBO) and submitted to a quantum processing unit (QPU) for direct annealing. We show that this standard penalty encoding is the binding constraint for direct-QPU execution on current D-Wave Pegasus and Zephyr hardware. Expanding the exact cardinality penalty contributes a dense rank-one term that makes the logical interaction graph complete regardless of the covariance, producing chain-break fractions from 83% at small universes up to 92% at the full forty-nine-industry Fama--French universe, and zero feasible raw samples at every tested scale. Topology-aware sparsification reduces chain breaks to near zero, but any sparsifier that removes off-diagonal entries also dilutes the cardinality constraint; an ablation reveals that this sparsify-and-project pipeline is dominated by the classical projector, not the QPU. We propose removing the penalty entirely: sample an objective-only QUBO built from expected returns and the risk-scaled covariance on hardware, and enforce cardinality classically through a deterministic feasibility projector. Across 4,468 saved embedding records on live Pegasus and Zephyr hardware, spanning equities up to forty-nine assets and football-betting instances up to forty-eight, this penalty-free pipeline reduces mean chain-break fractions from 71%--92% down to at most 0.04%, and post-processed regret is at most 0.03% relative to greedy classical references at every tested scale. We do not claim quantum advantage; the penalty encoding, not the sparse hardware topology, is the limiting factor for direct-QPU portfolio optimization at currently accessible scales.

quant-pharXiv:2605.17628•May 19, 2026•1 citation

QUBO Formulations and Quantum Optimization for the Multi-Dimensional Knapsack Problem With Conflict, Forcing, and Precedence Constraints

Evren Güney, Joachim C.F. Ehrenthal

Constrained knapsack variants are well-suited for QUBO-based quantum optimization, but adding logical relations can inflate the binary model and complicate penalty selection. This work examines the multi-dimensional knapsack problems augmented with conflict, forcing, and precedence (CFP) constraints using Quadratic Unconstrained Binary Optimization (QUBO) models across classical and quantum platforms. The additional logical constraints are incorporated through quadratic penalty terms that modify existing QUBO coefficients without introducing additional binary variables beyond the slack variables used for the capacity constraints. Computational studies are conducted to assess how each of the three constraint types affects solution behavior, including solution quality, computation time, and sensitivity to penalty parameter magnitudes. The approach is demonstrated on representative small-scale instances using QAOA on IBM Quantum gate-based device and quantum annealing on a D-Wave Advantage processor, with results compared with Gurobi as classical solver. The experiments show that the proposed QUBO formulations achieve optimal or near-optimal solutions for small instances, while showing the sensitivity of current quantum hardware to penalty selection, and scaling. Overall, CFP penalties are variable-neutral relative to the slack-based capacity representation, while the capacity terms dominate logical-qubit count and coupling density. Future work may target more compact or hardware-aware capacity modeling.

IEEE Access•Jan 1, 2026•2 citations

Exploring Topologies in Quantum Annealing: A Hardware-Aware Perspective

Mario Bifulco, Luca Roversi

Quantum Annealing (QA) offers a promising framework for solving NP-hard optimization problems, but its effectiveness is constrained by the topology of the underlying quantum hardware. Solving an optimization problem $P$ via QA involves a hardware-aware circuit compilation which requires representing $P$ as a graph $G_P$ and embedding it into the hardware connectivity graph $G_Q$ that defines how qubits connect to each other in a QA-based quantum processing unit (QPU). Minor Embedding (ME) is a possible operational form of this hardware-aware compilation. ME heuristically builds a map that associates each node of $G_P$ -- the logical variables of $P$ -- to a chain of adjacent nodes in $G_Q$ by means of one of its minors, so that the arcs of $G_P$ are preserved as physical connections among qubits in $G_Q$. The static topology of hardwired qubits can clearly lead to inefficient compilations because $G_Q$ cannot be a clique, currently. We propose a methodology and a set of criteria to evaluate how the hardware topology $G_Q$ can negatively affect the embedded problem, thus making the quantum optimization more sensible to noise. We evaluate the result of ME across two QPU topologies: Zephyr graphs (used in current D-Wave systems) and Havel-Hakimi graphs, which allow controlled variation of the average node degree. This enables us to study how the ratio `number of nodes/number of incident arcs per node' affects ME success rates to map $G_P$ into a minor of $G_Q$. Our findings, obtained through ME executed on classical, i.e. non-quantum, architectures, suggest that Havel-Hakimi-based topologies, on average, require shorter qubit chains in the minor of $G_P$, exhibiting smoother scaling of the largest embeddable $G_P$ as the QPU size increases. These characteristics indicate their potential as alternative designs for QA-based QPUs.

quant-pharXiv:2511.03327•Nov 6, 2025•1 citation
Exact QUBO formulations of knapsack preserve correctness at the ground state, but they induce dense interactions that are costly to minor-embed on sparse quantum annealing hardware. We propose a knapsack-specific chained partial-sum formulation that replaces one dense budget constraint by a sequence of smaller constraints with intermediate variables. This preserves exactness while reducing interactions and density. We give a sufficient penalty condition for correctness, propose a greedy grouping heuristic with adaptive register sizing, and benchmark embeddability on working graphs of D-Wave Pegasus and Zephyr systems. Compared with the standard dense slack formulation, the proposed formulation supports larger instances, uses fewer physical qubits, and produces shorter chains under D-Wave’s heuristic embedding algorithm. These improvements are consistent across the tested hardware topologies and indicate that the chained partial-sum formulation is a practical exact alternative for embedding knapsack QUBOs on current quantum annealing systems.
Quantum annealing is a promising approach for solving combinatorial optimization problems. However, its performance is often limited by the overhead of additional qubits required for embedding logical QUBO models onto quantum annealers. This overhead becomes severe when logical QUBO models have dense connectivity. Such dense structures frequently arise when formulating equality and inequality constraints. To address this issue, we propose a method to construct a significantly sparser logical QUBO model for these constraints. By adding auxiliary variables based on specific network structures, our approach decomposes the original constraint into smaller, more manageable constraints. We demonstrate that this method reduces the number of edges (quadratic terms) from O(N2)O(N^2)O(N2) to O(N)O(N)O(N) for the one-hot constraint and to O(Nlog⁡N)O(N\log N)O(NlogN) in the worst case for general equality constraints, where NNN is the number of variables. Experimental results on D-Wave's hardware show that our formulation leads to substantial reductions in the number of qubits required for embedding, shorter average chain lengths, lower chain break rates, and higher feasible solution rates compared to conventional methods. This work provides a practical tool for efficiently solving constrained optimization problems on current and future quantum annealers.
Quantum computing approaches, such as Quantum Annealing (QA) and the Quantum Approximate Optimization Algorithm (QAOA), have emerged as promising candidates for solving combinatorial optimization problems. Since these approaches typically work with Quadratic Unconstrained Binary Optimization (QUBO) problems, constraints, when present, are commonly encoded as penalty terms. Conventional approaches to incorporate inequality constraints into QUBO formulations additionally require the introduction of slack variables, increasing the required number of qubits. The Knapsack and Bin Packing problems are optimization problems with such inequality constraints. We show that the number of slack variables required to formulate the Knapsack problem as a QUBO problem can be reduced using certain properties specific to this problem. Moreover, we present two separate strategies for the Knapsack and Bin Packing problems that avoid using the costly slack variables altogether. Instead, both strategies solve several QUBO problems, with varying penalty constants, such that at least one of them is a good representation of the given optimization problem. Numerical simulations of QAOA, as well as experiments on a D-Wave quantum annealer, show that these slack-less approaches can improve performance compared to the conventional slack variable method (in terms of success probability), even when the latter is allowed to vary penalty constants too.
Quantum computing has emerged as a new tool for solving combinatorial optimization problems. Quantum optimization approaches usually operate on the subclass of Quadratic Unconstrained Binary Optimization (QUBO) problems. Many optimization problems can be reformulated in this form, though there are often multiple ways to do so. The choice of formulation can considerably affect the performance of QUBO solvers in practice. In this work, we study QUBO formulations of the Knapsack problem, a canonical example of a problem with inequality constraints. In the standard formulation these constraints are converted into penalty terms, which requires additional slack variables. Here, we investigate three more resource-efficient approaches for formulating the Knapsack as a QUBO. The first two modify the standard formulation, either by deriving a smaller penalty constant or by reducing the number of slack variables. The third approach is a wholly different method, which avoids the use of slack variables entirely. All three approaches increase the probability of finding the optimal solution, both in simulations of the linear ramp Quantum Approximate Optimization Algorithm (LR-QAOA) and on a D-Wave quantum annealer. The slackless method performs best, increasing success probabilities by several orders of magnitude even for relatively small problem sizes.
Cardinality-constrained portfolio selection is routinely cast as a quadratic unconstrained binary optimization (QUBO) and submitted to a quantum processing unit (QPU) for direct annealing. We show that this standard penalty encoding is the binding constraint for direct-QPU execution on current D-Wave Pegasus and Zephyr hardware. Expanding the exact cardinality penalty contributes a dense rank-one term that makes the logical interaction graph complete regardless of the covariance, producing chain-break fractions from 83% at small universes up to 92% at the full forty-nine-industry Fama--French universe, and zero feasible raw samples at every tested scale. Topology-aware sparsification reduces chain breaks to near zero, but any sparsifier that removes off-diagonal entries also dilutes the cardinality constraint; an ablation reveals that this sparsify-and-project pipeline is dominated by the classical projector, not the QPU. We propose removing the penalty entirely: sample an objective-only QUBO built from expected returns and the risk-scaled covariance on hardware, and enforce cardinality classically through a deterministic feasibility projector. Across 4,468 saved embedding records on live Pegasus and Zephyr hardware, spanning equities up to forty-nine assets and football-betting instances up to forty-eight, this penalty-free pipeline reduces mean chain-break fractions from 71%--92% down to at most 0.04%, and post-processed regret is at most 0.03% relative to greedy classical references at every tested scale. We do not claim quantum advantage; the penalty encoding, not the sparse hardware topology, is the limiting factor for direct-QPU portfolio optimization at currently accessible scales.
Constrained knapsack variants are well-suited for QUBO-based quantum optimization, but adding logical relations can inflate the binary model and complicate penalty selection. This work examines the multi-dimensional knapsack problems augmented with conflict, forcing, and precedence (CFP) constraints using Quadratic Unconstrained Binary Optimization (QUBO) models across classical and quantum platforms. The additional logical constraints are incorporated through quadratic penalty terms that modify existing QUBO coefficients without introducing additional binary variables beyond the slack variables used for the capacity constraints. Computational studies are conducted to assess how each of the three constraint types affects solution behavior, including solution quality, computation time, and sensitivity to penalty parameter magnitudes. The approach is demonstrated on representative small-scale instances using QAOA on IBM Quantum gate-based device and quantum annealing on a D-Wave Advantage processor, with results compared with Gurobi as classical solver. The experiments show that the proposed QUBO formulations achieve optimal or near-optimal solutions for small instances, while showing the sensitivity of current quantum hardware to penalty selection, and scaling. Overall, CFP penalties are variable-neutral relative to the slack-based capacity representation, while the capacity terms dominate logical-qubit count and coupling density. Future work may target more compact or hardware-aware capacity modeling.
Quantum Annealing (QA) offers a promising framework for solving NP-hard optimization problems, but its effectiveness is constrained by the topology of the underlying quantum hardware. Solving an optimization problem PPP via QA involves a hardware-aware circuit compilation which requires representing PPP as a graph GPG_PGP​ and embedding it into the hardware connectivity graph GQG_QGQ​ that defines how qubits connect to each other in a QA-based quantum processing unit (QPU). Minor Embedding (ME) is a possible operational form of this hardware-aware compilation. ME heuristically builds a map that associates each node of GPG_PGP​ -- the logical variables of PPP -- to a chain of adjacent nodes in GQG_QGQ​ by means of one of its minors, so that the arcs of GPG_PGP​ are preserved as physical connections among qubits in GQG_QGQ​. The static topology of hardwired qubits can clearly lead to inefficient compilations because GQG_QGQ​ cannot be a clique, currently. We propose a methodology and a set of criteria to evaluate how the hardware topology GQG_QGQ​ can negatively affect the embedded problem, thus making the quantum optimization more sensible to noise. We evaluate the result of ME across two QPU topologies: Zephyr graphs (used in current D-Wave systems) and Havel-Hakimi graphs, which allow controlled variation of the average node degree. This enables us to study how the ratio `number of nodes/number of incident arcs per node' affects ME success rates to map GPG_PGP​ into a minor of GQG_QGQ​. Our findings, obtained through ME executed on classical, i.e. non-quantum, architectures, suggest that Havel-Hakimi-based topologies, on average, require shorter qubit chains in the minor of GPG_PGP​, exhibiting smoother scaling of the largest embeddable GPG_PGP​ as the QPU size increases. These characteristics indicate their potential as alternative designs for QA-based QPUs.