A Caltech Library Service

Nonlinear Quantum Optimization Algorithms via Efficient Ising Model Encodings

Patti, Taylor L. and Kossaifi, Jean and Anandkumar, Anima and Yelin, Susanne F. (2021) Nonlinear Quantum Optimization Algorithms via Efficient Ising Model Encodings. . (Unpublished)

[img] PDF - Submitted Version
Creative Commons Attribution.


Use this Persistent URL to link to this item:


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.

Item Type:Report or Paper (Discussion Paper)
Related URLs:
URLURL TypeDescription Paper
Patti, Taylor L.0000-0002-4242-6072
Kossaifi, Jean0000-0002-4445-3429
Additional Information:Attribution 4.0 International (CC BY 4.0) This work was done during T.L.P.'s internship at NVIDIA. At CalTech, A.A. is supported in part by the Bren endowed chair, and Microsoft, Google, Adobe faculty fellowships. S.F.Y. thanks the AFOSR and the NSF for funding through the CUA-PFC grant. The authors would like to thank Brucek Khailany, Johnnie Gray, Garnet Chan, Andreas Hehn, and Adam Jedrych for conversations. AUTHOR CONTRIBUTIONS. T.L.P. and J.K. contributed to all aspects of the work. A.A. contributed context on machine learning and classical algorithms. S.F.Y. contributed context on quantum information-related physics. A.A. and S.F.Y. contributed guidance on the research and manuscript. The authors claim no competing interests.
Funding AgencyGrant Number
Bren Professor of Computing and Mathematical SciencesUNSPECIFIED
Microsoft Faculty FellowshipUNSPECIFIED
Google Faculty Research AwardUNSPECIFIED
Air Force Office of Scientific Research (AFOSR)UNSPECIFIED
Record Number:CaltechAUTHORS:20210831-203924970
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:110653
Deposited By: George Porter
Deposited On:01 Sep 2021 14:05
Last Modified:01 Sep 2021 14:05

Repository Staff Only: item control page