  Quantum computers are devices, which allow more efficient solutions of
problems as compared to their classical counterparts. As the timeline to
developing a quantum-error corrected computer is unclear, 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 quite
often 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. These
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 predivision into smaller
subproblems and a lower solution bound of 67.9% is achieved. The study
presented here paves way to using powerful genetic optimizer in synergy with
quantum computers
