Discrete optimization: A quantum revolution?

We develop several quantum procedures and investigate their potential to solve discrete optimization problems. First, we introduce a binary search procedure and illustrate how it can be used to effectively solve the binary knapsack problem. Next, we introduce two other procedures: a hybrid branch-and-bound procedure that allows to exploit the structure of the problem and a random-ascent procedure that can be used to solve problems that have no clear structure and/or are difficult to solve using traditional methods. We explain how to assess the performance of these procedures and perform an elaborate computational experiment. Our results show that we can match the worst-case performance of the best classical algorithms when solving the binary knapsack problem. After improving and generalizing our procedures, we show that they can be used to solve any discrete optimization problem. To illustrate, we show how to solve the quadratic binary knapsack problem. For this problem, our procedures outperform the best classical algorithms. In addition, we demonstrate that our procedures can be used as heuristics to find (near-) optimal solutions in limited time Not only does our work provide the tools required to explore a myriad of future research directions, it also shows that quantum computing has the potential to revolutionize the field of discrete optimization.