Source-linked AI summary
Efficient partition of integer optimization problems with one-hot encoding
Shuntaro Okada, Masayuki Ohzeki, Shinichiro Taguchi
TL;DR
The paper addresses how to efficiently solve large integer optimization problems on a limited-size quantum annealer when one-hot encoding creates a search space dominated by infeasible solutions. It proposes two partitioning methods that extract subproblems with feasible alternatives, and reports improved solution efficiency, with binary partitioning generally performing best except for the ferromagnetic Potts model.
Problem
One-hot encoding expands integer optimization into a binary search space dominated by infeasible solutions, while quantum-annealer hardware requires large problems to be partitioned into small subproblems.
Method
The paper proposes multivalued and binary partitioning methods that select binary variables associated with tentatively selected components and include feasible alternatives.
Results
The binary partition shows the best performance among three methods except for the ferromagnetic Potts model, while the proposed methods efficiently obtain better solutions across assessed Potts models.
Takeaways & Limitations
Binary partitioning can embed more binary variables and avoid adjusting λ, whereas its restriction to two components per integer variable can reduce performance on ferromagnetic Potts models.
Takeaways & Limitations
Binary partitioning considers only two components for each integer variable, leading to poor performance for the ferromagnetic Potts model.
Abstract
from arXiv · showhide
Quantum annealing is a heuristic algorithm for solving combinatorial optimization problems, and D-Wave Systems Inc. has developed hardware for implementing this algorithm. The current version of the D-Wave quantum annealer can solve unconstrained binary optimization problems with a limited number of binary variables, although cost functions of many practical problems are defined by a large number of integer variables. To solve these problems with the quantum annealer, the integer variables are generally binarized with one-hot encoding, and the binarized problem is partitioned into small subproblems. However, the entire search space of the binarized problem is considerably extended compared to that of the original integer problem and is dominated by unfeasible solutions. Therefore, to efficiently solve large optimization problems with one-hot encoding, partitioning methods that extract subproblems with as many feasible solutions as possible are required.
Introduction
Quantum annealing applies quantum fluctuations to combinatorial optimization, but D-Wave hardware handles limited-size binary problems, requiring large integer-variable problems to be encoded and partitioned. One-hot encoding greatly expands the binary search space with mostly infeasible configurations, motivating partitions that retain many feasible solutions.
- Quantum annealing: Quantum annealing searches combinatorial-optimization ground states through quantum tunneling, and D-Wave hardware implements this approach with superconducting flux qubits.The paper contrasts quantum fluctuations in QA with thermal fluctuations in simulated annealing.
- Hardware constraints: D-Wave hardware has limited qubits and connectivity, so large optimization problems must be iteratively partitioned into solvable subproblems.The subproblem results are used to improve the current solution.
- One-hot encoding: Practical integer-variable cost functions are converted to QUBO or Ising form using one-hot encoding before quantum-annealing optimization.Each integer variable is represented through binary variables associated with its possible components.
- Penalty formulation: A penalty parameter λ enforces one-hot feasibility, but excessively large values amplify noise and control-error effects, making λ selection necessary.The penalty term is introduced in the unconstrained formulation to extract configurations satisfying the constraint.
- One-hot constraint: Only Q^N of 2^(NQ) binary configurations satisfy the one-hot constraint, leaving the binarized search space dominated by infeasible solutions.Each of N integer variables has Q possible components, while each contributes Q binary variables.
- Partitioning motivation: The paper proposes partitioning methods that extract subproblems containing more feasible solutions, including a method that avoids adjusting λ.The proposed methods target problems with a single one-hot constraint.
Results
The study proposes multivalued and binary partitions that retain feasible alternatives while optimizing large one-hot-encoded problems through iterative subproblem embedding. Their performance is evaluated on four Potts-model variants, with outcomes depending on the partitioning method and model.
- Proposed methods: Two proposed methods, multivalued and binary partitioning, extract subproblems involving tentatively selected components and feasible alternatives.Both methods are summarized as alternatives to random partitioning for large optimization problems under the one-hot constraint.
- Proposed methods: The multivalued partition selects two or more components for each integer variable, but its subproblem still contains infeasible solutions and retains the penalty term.Additional components are randomly selected and explored for each variable.
- Proposed methods: The binary partition selects exactly one alternative component per integer variable and represents staying or transitioning with a new binary variable.Its subproblem cost function is defined over these stay-or-transition variables.
- Proposed methods: The binary partition omits penalty-term interactions, enabling more embedded binary variables and considerably increasing the feasible solutions in the subproblem.Its limitation is that only two components are considered per integer variable, which leads to poor performance for the ferromagnetic Potts model.
- Evaluation: Performance is evaluated on ferromagnetic, anti-ferromagnetic, Potts glass, and Potts gauge glass models with 10 × 10 × 10 integer variables.The Potts gauge glass includes interactions between different components when Δij ≠ 0.
- Evaluation: The optimization iterates subproblem embedding, quantum-annealer optimization, replacement by the best of 1,000 returned solutions, and greedy digital optimization.Solution energies are compared across random, multivalued, and binary partitions over repeated subproblem optimizations.
Discussion
The discussion explains why partition performance differs across Potts models: infeasible low-energy states can help some updates, while binary partitions may rarely capture domain-wall-eliminating subproblems. Frustration and the availability of improving binary subproblems instead favor binary or multivalued partitions in different models.
- Infeasible intermediate states: Lower-energy infeasible states can let random or multivalued partitions reach better feasible solutions through constraint-violating intermediate states.For a one-dimensional ferromagnetic model, flipping a binary variable changes energy by −2J + λ, so J < λ < 2J permits such an intermediate update.
- Results overview: The figure compares average, maximum, and minimum energies over 16 trials for ferromagnetic, anti-ferromagnetic, Potts glass, and Potts gauge glass models.
- Frustrated models: The multivalued partition outperforms the random partition on Potts glass and Potts gauge glass models because many ground-state interactions are frustrated.
- Ferromagnetic model: Binary partitions perform worst for the ferromagnetic Potts model because they rarely extract subproblems capable of eliminating domain walls.For the illustrated ten-variable state, the probability of selecting the needed component for five variables is (1/3)^5 = 1/243.
- Binary-partition advantage: Binary partitions perform best except in the ferromagnetic model when several binary subproblems can improve the current solution and are therefore more likely to be extracted.The anti-ferromagnetic example has two improving binary subproblems associated with a frustrated interaction.
Conclusion
The paper proposes two partitioning methods for large one-hot-constrained optimization problems on a D-Wave quantum annealer and evaluates them across four Potts models.
- Performance: The binary partition performs best among the three methods except for the ferromagnetic Potts model.
- Trade-offs: Binary partitioning embeds more binary variables and avoids adjusting λ, but considers only two components for each integer variable.
- Scope: The binary partition’s limitation is mitigated for anti-ferromagnetic problems and frustrated optimization problems with many improving binary subproblems.
- Scope: The study did not identify problems for which the multivalued partition was most suitable, although it outperformed random partitioning for frustrated problems.
Methods
The methods construct partitioned subproblems and use embedding criteria to exploit D-Wave hardware while increasing the feasible search space under the one-hot constraint. Binary partitions use fewer components per integer variable, whereas multivalued partitions retain more components but include infeasible solutions.
- Multivalued Partition: The multivalued embedding procedure prioritizes adjacent binary variables and tentatively selected components, then excludes integer variables represented by only one embedded component.Criterion 1 favors adjacency, while Criterion 2 prioritizes the tentatively selected component after the initial embedding choices.
- Multivalued Partition: The embedding assessment reports 65.8% of integer variables with all four components embedded and an average of 225 embedded binary variables for the multivalued partition.The assessment uses the Potts gauge glass model on D-Wave 2000Q_2 with defects and averages 1,000 trials.
- Binary Partition: The binary partition randomly selects one additional component for each integer variable, producing a two-component subproblem whose solutions all satisfy the one-hot constraint.Its QUBO uses yi = 0 for staying with the tentative component and yi = 1 for transitioning to the other component, without a penalty term.
- Binary Partition: The binary subproblem has lower interaction density than the multivalued subproblem because it omits the penalty term that creates partially fully connected interactions.
- Binary Partition: The binary partition embeds an average of 408 binary variables versus 225 for the multivalued partition, and its embedded subproblem contains only feasible solutions.Consequently, the number of feasible solutions in the embedded subproblem is considerably increased for binary partitioning.
Author contributions statement
The author contributions assign concept development and experiments to S. O., evaluation planning and manuscript review to M. O., and project direction to S. T.
- Contributions: S. O. conceived and developed the concept and carried out all experiments.
- Contributions: M. O. proposed the validity-evaluation plan, discussed the results, and reviewed the manuscript.
- Contributions: S. T. directed the project.