Efficient partition of integer optimization problems with one-hot encoding
arXiv:1906.07385 · doi:10.1038/s41598-019-49539-6
Abstract
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.
14 pages, 6 figures, 3 tables
References in corpus (24)
- Ising formulations of many NP problems
- Quantum Annealing in the Transverse Ising Model
- Theory of Quantum Annealing of an Ising Spin Glass
- Defining and detecting quantum speedup
- Mathematical Foundation of Quantum Annealing
- Quantum Boltzmann Machine
- Observation of topological phenomena in a programmable lattice of 1,800 qubits
- Architectural considerations in the design of a superconducting quantum annealing processor
- What is the Computational Value of Finite Range Tunneling?
- Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design
- Quantum annealing of the Traveling Salesman Problem
- Solving the Optimal Trading Trajectory Problem Using a Quantum Annealer
- Quantum-Assisted Learning of Hardware-Embedded Probabilistic Graphical Models
- Optimization by Quantum Annealing: Lessons from hard 3-SAT cases
- Improving solutions by embedding larger subproblems in a D-Wave quantum annealer
- Seeking Quantum Speedup Through Spin Glasses: The Good, the Bad, and the Ugly
- Efficiency of quantum versus classical annealing in non-convex learning problems
- Optimization by Quantum Annealing: Lessons from Simple Cases
- Item Listing Optimization for E-commerce Websites based on Diversity
- Building an iterative heuristic solver for a quantum annealer
- Direct comparison of quantum and simulated annealing on a fully-connected Ising ferromagnet
- Quantum annealing speedup over simulated annealing on random Ising chains
- The Chiral Potts Spin Glass in d=2 and 3 Dimensions
- Belief-Propagation Guided Monte-Carlo Sampling