Iterative approaches to quantum optimization via problem reductions

Existing approaches to tackling combinatorial optimization problems on quantum computers typically operate by constructing a quantum algorithm from which global candidate solutions are directly sampled. However, this often leads to onerous requirements on the quantum device if one expects to find optimal or high-quality approximate solutions with this approach. An alternative paradigm is to instead use the quantum computer in an iterative fashion to obtain partial information about the given problem instance at each step (such as expectation values of local operators or other instance properties), which is then used to classically simplify the instance, and after enough iterations a global solution is obtained. In this direction we propose and study a general hybrid quantum-classical framework for quantum optimization via iterative problem reductions. Our framework encapsulates and extends a number of related existing quantum approaches such as RQAOA as well as various classical greedy algorithms. In particular, we propose how to extend these approaches to the important setting of problems with hard feasibility constraints, through either feasibility-preserving or penalty-based approaches. We further show how our framework naturally extends to a variant of branch-and-bound tree search, which as a heuristic can be run for some number of iterations and the best solution found returned, or the tree exhaustively searched (up to branch pruning) when a complete (exact) solver is required. Our results help pave the way towards novel deployment of quantum computers for optimization and new paths to potential advantage in the hybrid quantum-classical setting.