Despite extensive research efforts, few quantum algorithms for classical optimization demonstrate an advantage that is realizable on near-term devices. The utility of many quantum algorithms is limited by high requisite circuit depth and nonconvex optimization landscapes. We tackle these challenges by introducing a new variational quantum algorithm that utilizes multi-basis graph encodings and nonlinear activation functions. Our technique results in increased optimization performance, a factor of two increase in effective quantum resources, and a quadratic reduction in measurement complexity. Further, we construct exact circuit representations using factorized tensor rings. This enables us to successfully optimize the MaxCut of the non-local 512-vertex DIMACS library graphs on a single A100 GPU using only shallow circuits. We further provide efficient distributed implementation via the Tensorly-Quantum library.