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 (which does not guarantee optimality) 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.
By: Sanjeeb Dash
Published in: RC25387 in 2013
Questions about this service can be mailed to reports@us.ibm.com .