Solving QUBOs with a Quantum-Amenable branch and bound method

Optimization problems are ubiquitous in the financial industry, such as finding the best portfolio given a preferred return and risk characteristic or determining the optimal withdrawal strategy from a retirement account. However, these problems can be incredibly complex and time-consuming to solve. That's why AWS and FCAT proposed a new optimization solver. By leveraging high-performance computing techniques and exploring the potential of quantum computing, researchers are paving the way for new breakthroughs in finance and other fields.

The Challenge

For many problems, the optimization process involves searching through a large space of potential solutions, which can take a long time even on the most powerful computers. However, with the availability of more advanced hardware such as more powerful CPUs, GPUs, and potentially quantum computers in the future, it's essential to prepare for these new technologies by examining what problems are best suited for them and how we can modify our algorithms accordingly.

The Impact

A faster solver could significantly benefit financial firms by enabling the creation of more accurate portfolios for customers and fund managers, allowing for greater customization to meet individual needs, and facilitating real-time or near real-time decision making.

The Outcomes

The optimization solver uses a particular form of branch-and-bound method to solve QUBO (quadratic unconstrained binary optimization) problems. This is a wide class of optimization problems and may include some problems in portfolio optimization. The researchers added many techniques from high-performance computing and operations research to drastically boost the solver performance. For example, they implemented the tree traversal logic such that it benefits from the high number of cores available in today's CPUs. Moreover, the bounding technique used in the solver can be implemented in early fault-tolerant quantum devices, making it more likely to benefit from a future quantum speedup than other commercial solvers.

The Deep Dive

The researchers describe and experimentally validate an exact classical branch and bound solver with techniques such as variable reordering, a primal heuristic based on simulated annealing, and a truncated computation of the recursive bound. These techniques are designed to optimize the solver's performance for a variety of hardware architecture, making it a promising tool for solving complex optimization problems in finance and other industries. For further details on this project, read the full paper here.