Nonlinear Quantum Optimization Algorithms via Efficient Ising Model Encodings

Taylor L. Patti, Jean Kossaifi, Anima Anandkumar, Susanne F. YelinResearch 2021 · DOI

Abstract

Despite extensive research efforts, few quantum algorithms for classical optimization demonstrate realizable advantage. The utility of many quantum algorithms is limited by high requisite circuit depth and nonconvex optimization landscapes. We tackle these challenges to quantum advantage with two new variational quantum algorithms, which utilize multi-basis graph encodings and nonlinear activation functions to outperform existing methods with remarkably shallow quantum circuits. Both algorithms provide a polynomial reduction in measurement complexity and either a factor of two speedup or a factor of two reduction in quantum resources. Typically, the classical simulation of such algorithms with many qubits is impossible due to the exponential scaling of traditional quantum formalism and the limitations of tensor networks. Nonetheless, the shallow circuits and moderate entanglement of our algorithms, combined with efficient tensor method-based simulation, enable us to successfully optimize the MaxCut of high-connectivity global graphs with up to 512 nodes (qubits) on a single GPU.

Introduction

Finding the "maximum cut" (MaxCut) of a graph—partitioning its nodes into two sets to maximize the weight of edges between them—is a classic NP-hard problem with broad applications in logistics, circuit design, and network science. While Variational Quantum Algorithms (VQAs) like VQE and QAOA are promising candidates for solving these problems, they are often hindered by the need for deep, noise-sensitive circuits and difficult optimization landscapes characterized by "barren plateaus."

This research introduces two novel algorithms, NP-VQA and ND-VQA, that leverage nonlinear activation functions and multi-basis encodings to overcome these hurdles. These methods achieve higher accuracy with significantly shallower circuits than traditional approaches, enabling record-breaking simulations of large-scale systems.

Novel Algorithmic Frameworks

The authors rethink the mapping of graph problems onto quantum hardware through two distinct strategies:

  • Nonlinear Parallel VQA (NP-VQA): This method encodes two different graph problems into the same set of qubits simultaneously—one in the $z$-basis and one in the $x$-basis. By applying a nonlinear activation function (specifically tanh) to the measurement results on the classical side, the algorithm can optimize both graphs in parallel without violating the Heisenberg uncertainty principle.
  • Nonlinear Dense VQA (ND-VQA): This approach uses the $z$ and $x$ bases of each physical qubit to represent two different logical nodes of a single graph. This effectively halves the number of physical qubits required to solve a problem of a given size, providing a factor of two reduction in quantum resources.
Overview of the variational quantum optimization workflow, from problem encoding to circuit execution and iterative optimization.

Scalable Simulation with TensorLy-Quantum

To validate these algorithms at scale, the researchers developed TensorLy-Quantum, a framework utilizing Tensor Train (TT) decompositions. By representing quantum states as Matrix Product States (MPS), the team achieved exact classical simulation of shallow, moderately entangled circuits. This allowed for the optimization of high-connectivity graphs with up to 512 nodes on a single NVIDIA A100 GPU—a feat previously thought to require massive supercomputing resources.

Key Insights: Nonlinearity and Multi-Basis Encoding

A central innovation is the use of nonlinear activations. In classical deep learning, functions like ReLU or Sigmoid are essential; here, the authors show that applying tanh to quantum expectation values creates "bistable" points in the optimization landscape. This helps the algorithm "push" qubits toward clear 0 or 1 states, effectively escaping local minima that trap traditional linear VQAs.

Furthermore, by utilizing both the $x$ and $z$ axes of the Bloch sphere, the researchers demonstrate that current quantum resources are underutilized. We can either double the throughput (NP-VQA) or double the problem density (ND-VQA). Surprisingly, the $L=1$ version of NP-VQA, which lacks entangling gates, outperformed standard VQE, suggesting that multi-basis superposition acts as a powerful optimization regularizer.

Key Results and Performance

The proposed algorithms demonstrate significant advantages over traditional methods:

  • Performance Boost: NP-VQA showed a 5-7% accuracy increase over traditional VQE across various register sizes.
  • Probabilistic Success: For 100-qubit graphs, NP-VQA found optimal cuts with a 97% success rate in fewer than 100 training steps, whereas traditional VQE was significantly less reliable.
  • Classical Superiority: The approximation ratios achieved by these shallow circuits exceeded those of standard polynomial-time classical algorithms, such as the Goemans-Williamson algorithm.
Performance metrics showing the convergence of the approximation ratio and energy for different graph sizes (n=8, 20, 100).

Limitations and Future Work

While these results are a major step forward, performance still degrades as the number of nodes ($n$) increases, suggesting that circuit depth may need to scale logarithmically with $n$ to maintain high accuracy for even larger graphs. Additionally, the classical simulation advantage depends on maintaining "moderate" entanglement; deep circuits with high all-to-all connectivity would eventually exceed memory limits. Future research will explore applying these nonlinear encodings to other combinatorial problems and testing them on actual Noisy Intermediate-Scale Quantum (NISQ) hardware.

Summary updated

Abstract

Abstract Despite extensive research efforts, few quantum algorithms for classical optimization demonstrate realizable advantage. The utility of many quantum algorithms is limited by high requisite circuit depth and nonconvex optimization landscapes. We tackle these challenges to quantum advantage with two new variational quantum algorithms, which utilize multi-basis graph encodings and nonlinear activation functions to outperform existing methods with remarkably shallow quantum circuits. Both algorithms provide a polynomial reduction in measurement complexity and either a factor of two speedup a factor of two reduction in quantum resources. Typically, the classical simulation of such algorithms with many qubits is impossible due to the exponential scaling of traditional quantum formalism and the limitations of tensor networks. Nonetheless, the shallow circuits and moderate entanglement of our algorithms, combined with efficient tensor method-based simulation, enable us to successfully optimize the MaxCut of high-connectivity global graphs with up to 512 nodes (qubits) on a single GPU.
BibTeX
@inproceedings{patti2021nonlinear,
  author = {Taylor L. Patti and Jean Kossaifi and Anima Anandkumar and Susanne F. Yelin},
  title = {{Nonlinear Quantum Optimization Algorithms via Efficient Ising Model Encodings}},
  booktitle = {Research},
  year = {2021},
  doi = {10.21203/rs.3.rs-654802/v1},
}
Figure