Abstract: Despite extensive research efforts, few quantum algorithms for classical optimization demonstrate 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 new variational quantum algorithm that benefits from two innovations: 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. 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 nonlocally connected 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.
Introduction
Variational Quantum Algorithms (VQAs), such as the Variational Quantum Eigensolver (VQE) and the Quantum Approximate Optimization Algorithm (QAOA), are leading candidates for achieving quantum advantage in solving NP-hard problems like MaxCut. However, these algorithms face significant hurdles: high qubit resource overhead, difficult optimization landscapes characterized by "barren plateaus," and the extreme difficulty of classical simulation at scale. This research introduces Multi-Basis Encoding (MBE) to address these limitations by rethinking the mapping of classical data onto quantum states.
Multi-Basis Encoding (MBE)
Traditionally, VQAs map each vertex of a graph to a single qubit, typically in the $z$-basis. This one-to-one mapping is resource-intensive. MBE innovates by mapping vertices to multiple Pauli bases (e.g., both $x$ and $z$) on the same physical qubit. This approach allows an $n$-vertex graph to be represented using only $n/2$ qubits, effectively doubling the efficiency of available quantum hardware.
Beyond resource efficiency, MBE introduces a "normalization constraint" ($\langle \sigma_i^z \rangle^2 + \langle \sigma_i^x \rangle^2 \leq 1$). This constraint acts as a regularizer, preventing the optimizer from greedily focusing on individual vertices and instead smoothing the overall training landscape. Furthermore, by relying on single-qubit measurements across different bases rather than complex edge correlations, MBE achieves a quadratic reduction in measurement complexity, significantly speeding up circuit execution.
Nonlinear Regularization and Scalable Simulation
To further improve optimization, the researchers applied a tanh activation function to the quantum expectation values within the loss function. This creates a "bistable" landscape that helps the algorithm escape local minima.
To validate these methods at scale, the team utilized the TensorLy-Quantum library. By representing quantum circuits as Matrix Product Operators (MPOs) and states as Matrix Product States (MPS), they maintained low "bond dimensions" for shallow circuits. This allowed for the exact simulation of hundreds of qubits on a single GPU (NVIDIA A100), bypassing the exponential scaling limits of traditional quantum simulation.
Results and Performance
The MBE algorithm demonstrated superior accuracy and scalability compared to standard VQE. On 100-vertex graphs, MBE achieved an average approximation ratio of 0.971, compared to 0.921 for traditional VQE, despite using half the qubits.
A key finding was the algorithm's behavior regarding entanglement. As training progressed, the system naturally tended toward "product states" (states with zero entanglement). While counter-intuitive for a quantum algorithm, this characteristic makes MBE highly resistant to noise and exceptionally efficient for classical simulation. This efficiency enabled the successful optimization of a 512-vertex nonlocally connected graph from the DIMACS library—a new record for simulating such complex optimization problems on a single GPU.
Conclusion
By combining multi-basis encodings with nonlinear activation functions and efficient tensor-based simulation, this work provides a robust framework for large-scale quantum optimization. The reduction in required qubits and measurement complexity, alongside the ability to utilize shallow, noise-resistant circuits, marks a significant step toward practical quantum utility in classical optimization.
Summary updated