A novel noisy intermediate-scale quantum computing algorithm for solving an n-vertex MaxCut problem with log(n) qubits.

As an error-corrected quantum computer is still far away the quantum computing community has dedicated much attention to developing algorithms for currently available Noisy Intermediate-Scale Quantum computers (NISQ). Thus far, within NISQ, optimization problems are one of the most commonly studied and are almost exclusively tackled with the Quantum Approximate Optimization Algorithm (QAOA). This algorithm is best known for computing graph partitions with a maximal separation of edges (MaxCut), but can easily calculate other problems related to graphs. Here, I present a novel quantum optimization algorithm which uses exponentially less qubits as compared to the QAOA while requiring a significantly reduced number of quantum operations to solve the MaxCut problem. Such an improved performance allowed me to partition graphs with 32 nodes on publicly available 5 qubit gate-based quantum computers without any preprocessing such as division of the graph into smaller subgraphs. This results represent a 40% increase in graph size as compared to state-of-art experiments on gate-based quantum computers such as Google Sycamore. The obtained lower bound is 54.9% on the solution for actual hardware benchmarks and 77.6% on ideal simulators of quantum computers. Furthermore, large-scale optimization problems represented by graphs of a 128 nodes are tackled with simulators of quantum computers, again without any pre-division into smaller subproblems and a lower solution bound of 67.9% is achieved.