Gast ::
| Hauptseite > Workflowsammlungen > In Bearbeitung > Improving cardinality constraints for the annealer |
| Hauptseite > Workflowsammlungen > In Bearbeitung > Improving cardinality constraints for the annealer |
| Poster (Other) | FZJ-2026-05093 |
2026
Abstract: <ul> <li> Annealers are analog quantum computers that can solve only one type of problem: the Ising problem. However, there exists a one-to-one mapping between the Ising formulation and the Quadratic Unconstrained Binary Optimization (QUBO) problem. Since many optimization problems of practical interest can be expressed as QUBOs, annealers become promising candidates for solving them. </li> <li> A central challenge in mapping a problem to QUBO form is the encoding of constraints, because constraints cannot be directly incorporated into the QUBO or into the annealer. A careful choice of encoding is therefore crucial for the performance of the annealer. </li> <li> One of the most common constraints is the cardinality constraint, which enforces that exactly $k$ out of $n$ binary variables take the value $1$, with the remaining variables set to $0$. The standard encoding introduces a penalty term by squaring the difference between the sum of the binary variables and $k$, multiplied by a penalty factor, and adding this term to the objective function. Expanding this square yields coefficients for single variables and for pairs of variables, which fits naturally into the QUBO structure. However, this encoding induces all-to-all connectivity: every problem variable becomes coupled to every other variable. The physical connectivity of current annealer hardware is far more limited, making this standard encoding poorly suited for such architectures. </li> <li> Vyskocil and Djidjev propose an alternative encoding that uses only nearest neighbour connections and is optimized for the specific hardware topology of the annealer. In the special case $k=1$, information propagates along a line. As the number of variables grows, the performance of this constraint degrades because information must travel increasingly long distances. </li> <li> This is where our binary-search-based idea comes into play: it yields an encoding in which information can propagate in logarithmically many steps between any two points. In the general "$k$"-case, their method requires $O(kn)$ variables to represent the constraint. Our adder-based construction significantly reduces this overhead for large $k$, and in combination with the binary-search structure, information still flows efficiently. The total number of auxiliary variables required—those used for the binary search plus those used for the adders—is between $n$ for $k=1$ and $5 * n$ for $k=n/2$. For all cardinality constraints with $k>n/2$, the constraint can be reformulated by summing over the negated variables. </li></ul>
|
The record appears in these collections: |
PDF
Volltext