  Due to the expected disparity in quantum vs. classical clock speeds, quantum
advantage for branch and bound algorithms is more likely achievable in settings
involving large search trees and low operator evaluation costs. Therefore, in
this paper, we describe and experimentally validate an exact classical branch
and bound solver for quadratic unconstrained binary optimization (QUBO)
problems that matches these criteria. Our solver leverages cheap-to-implement
bounds from the literature previously proposed for Ising models, including that
of Hartwig, Daske, and Kobe from 1984. We detail a variety of techniques from
high-performance computing and operations research used to boost solver
performance, including a global variable reordering heuristic, a primal
heuristic based on simulated annealing, and a truncated computation of the
recursive bound. We also outline a number of simple and inexpensive bound
extrapolation techniques. Finally, we conduct an extensive empirical analysis
of our solver, comparing its performance to state-of-the-art QUBO and MaxCut
solvers, and discuss the challenges of a speedup via quantum branch and bound
beyond those faced by any quadratic quantum speedup.
