A multilevel approach for solving large-scale QUBO problems with noisy hybrid quantum approximate optimization

Quantum approximate optimization is one of the promising candidates for useful quantum computation, particularly in the context of finding approximate solutions to Quadratic Unconstrained Binary Optimization (QUBO) problems. However, the existing QPUs are relatively small, and canonical mappings of QUBO via the Ising model require one qubit per variable, rendering direct large-scale optimization infeasible. In classical optimization, a general strategy for addressing many large-scale problems is via multilevel/multigrid methods, where the large target problem is iteratively coarsened, and the global solution is constructed from multiple small-scale optimization runs. In this work, we experimentally test how existing QPUs perform as a sub-solver within such a multilevel strategy.