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 nonconvex 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.

Automated summary

Despite previous research efforts, there have been limited quantum algorithms that demonstrate an achievable quantum advantage for classical optimization. This study proposes a variational quantum algorithm that overcomes the challenges of high circuit depth and nonconvex optimization landscapes through multibasis graph encodings and nonlinear activation functions. The results show improved optimization performance and reduced qubit requirements. Moreover, the study introduces exact circuit representations using factorized tensor rings to mitigate the exponential scaling limitation of classical simulation of many qubits. The shallow circuits and efficient simulation enable successful optimization of the MaxCut problem on 512-vertex DIMACS library graphs using a single GPU. The research offers tangible progress for variational quantum optimization by improving performance, requiring fewer resources, and utilizing shallower and more error-resistant circuits.