A note on QUBO instances defined on Chimera graphs
read the original 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 1 Pith paper
-
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 wit...
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.