QAOA with fewer qubits: a coupling framework to solve larger-scale Max-Cut problem

Maximum cut (Max-Cut) problem is one of the most important combinatorial optimization problems because of its various applications in real life, and recently Quantum Approximate Optimization Algorithm (QAOA) has been widely employed to solve it. However, as the size of the problem increases, the number of qubits required will become larger. With the aim of saving qubits, we propose a coupling framework for designing QAOA circuits to solve larger-scale Max-Cut problem. This framework relies on a classical algorithm that approximately solves a certain variant of Max-Cut, and we derive an approximation guarantee theoretically, assuming the approximation ratio of the classical algorithm and QAOA. Furthermore we design a heuristic approach that fits in our framework and perform sufficient numerical experiments, where we solve Max-Cut on various $24$-vertex Erd\H{o}s-R\'enyi graphs. Our framework only consumes $18$ qubits and achieves $0.9950$ approximation ratio on average, which outperforms the previous methods showing $0.9778$ (quantum algorithm using the same number of qubits) and $0.9643$ (classical algorithm). The experimental results indicate our well-designed quantum-classical coupling framework gives satisfactory approximation ratio while reduces the qubit cost, which sheds light on more potential computing power of NISQ devices