Variational quantum optimization with multibasis encodings

Despite extensive research efforts, few quantum algorithms for classical optimization demonstrate a realizable
quantum advantage. The utility of many quantum algorithms is limited by high requisite circuit depth and non-
convex optimization landscapes. We tackle these challenges by introducing a variational quantum algorithm that
benefits from two innovations: multibasis graph encodings using single-qubit expectation values and nonlinear
activation functions. Our technique results in increased observed optimization performance and a factor-of-two
reduction in requisite qubits. While the classical simulation of many qubits with traditional quantum formalism
is impossible due to its exponential scaling, we mitigate this limitation with exact circuit representations using
factorized tensor rings. In particular, the shallow circuits permitted by our technique, combined with efficient
factorized tensor-based simulation, enable us to successfully optimize the MaxCut of the 512-vertex DIMACS
library graphs on a single GPU. By improving the performance of quantum optimization algorithms while
requiring fewer quantum resources and utilizing shallower, more error-resistant circuits, we offer tangible
progress for variational quantum optimization.