Classical solvers solve random Ising models on heavy-hex graphs efficiently, with Gurobi showing linear or weakly quadratic scaling up to 100k variables and simulated annealing showing exponential time-to-solution without cubic terms.
A note on QUBO instances defined on Chimera graphs
1 Pith paper cite this work. Polarity classification is still indexing.
1
Pith paper citing it
abstract
McGeoch and Wang (2013) recently obtained optimal or near-optimal solutions to some quadratic unconstrained boolean optimization (QUBO) problem instances using a 439 qubit D-Wave Two quantum computing system in much less time than with the IBM ILOG CPLEX mixed-integer quadratic programming (MIQP) solver. The problems studied by McGeoch and Wang are defined on subgraphs -- with up to 439 nodes -- of Chimera graphs. We observe that after a standard reformulation of the QUBO problem as a mixed-integer linear program (MILP), the specific instances used by McGeoch and Wang can be solved to optimality with the CPLEX MILP solver in much less time than the time reported in McGeoch and Wang for the CPLEX MIQP solver. However, the solution time is still more than the time taken by the D-Wave computer in the McGeoch-Wang tests.
fields
math.OC 1years
2024 1verdicts
UNVERDICTED 1representative citing papers
citing papers explorer
-
Classical Combinatorial Optimization Scaling for Random Ising Models on 2D Heavy-Hex Graphs
Classical solvers solve random Ising models on heavy-hex graphs efficiently, with Gurobi showing linear or weakly quadratic scaling up to 100k variables and simulated annealing showing exponential time-to-solution without cubic terms.