Enhancing subproblem decomposition for large-scale optimization using quantum correlations

The scale of problems that quantum optimization solvers can tackle is constrained by the number of qubits and error rates in the hardware. To mitigate this, we present a quantum algorithm that decomposes large optimization problems into smaller subproblems. The algorithm introduces effective correlations between the subproblems, which can then be solved individually while accounting for the global structure of the original problem. We investigate the performance of the proposed algorithm via extensive simulations and test its experimental implementation on a superconducting device.