Title:
ENHANCING COMBINATORIAL OPTIMIZATION WITH QUANTUM GENERATIVE MODELS
Document Type and Number:
WIPO Patent Application WO/2022/173497
Kind Code:
A3
Abstract:
A system and method for a quantum-enhanced optimizer (QEO) using quantum generative models to achieve lower minimum cost functions than classical or other known optimizers. In a first embodiment, the QEO operates as a booster to enhance the performance of known stand-alone optimizers in complex instances where known optimizers have limitations. In a second embodiment, the QEO operates as a stand-alone optimizer for finding a minimum with the least number of cost-function evaluations. The disclosed QEO methods outperform known optimizers, including Bayesian optimizers. The disclosed quantum-enhanced optimization methods may be based on tensor networks. The generative models may also be based on classical, quantum, or hybrid quantum-classical approaches, including Quantum Circuit Associative Adversarial Networks (QC-AAN) and Quantum Circuit Born Machines (QCBM).
Inventors:
ALCAZAR FRANCISCO JAVIER FERNANDEZ (US)
PERDOMO ORTIZ ALEJANDRO (US)
PERDOMO ORTIZ ALEJANDRO (US)
Application Number:
PCT/US2021/062191
Publication Date:
November 10, 2022
Filing Date:
December 07, 2021
Export Citation:
Assignee:
ZAPATA COMPUTING INC (US)
International Classes:
G06N10/60; G06N3/08; G06N10/80; B82Y10/00
Other References:
ZHAO-YU HAN; JUN WANG; HENG FAN; LEI WANG; PAN ZHANG: "Unsupervised Generative Modeling Using Matrix Product States", ARXIV.ORG, CORNELL UNIVERSITY LIBRARY, 201 OLIN LIBRARY CORNELL UNIVERSITY ITHACA, NY 14853, 6 September 2017 (2017-09-06), 201 Olin Library Cornell University Ithaca, NY 14853 , XP081327155, DOI: 10.1103/PhysRevX.8.031012
YANG SHUO, GU ZHENG-CHENG, WEN XIAO-GANG: "Loop Optimization for Tensor Network Renormalization", PHYSICAL REVIEW LETTERS, AMERICAN PHYSICAL SOCIETY, US, vol. 118, no. 11, 1 March 2017 (2017-03-01), US , XP093000183, ISSN: 0031-9007, DOI: 10.1103/PhysRevLett.118.110504
NICHOLAS GAO; MAX WILSON; THOMAS VANDAL; WALTER VINCI; RAMAKRISHNA NEMANI; ELEANOR RIEFFEL: "High-Dimensional Similarity Search with Quantum-Assisted Variational Autoencoder", ARXIV.ORG, CORNELL UNIVERSITY LIBRARY, 201 OLIN LIBRARY CORNELL UNIVERSITY ITHACA, NY 14853, 13 June 2020 (2020-06-13), 201 Olin Library Cornell University Ithaca, NY 14853 , XP081700763
MARCELLO BENEDETTI, DELFINA GARCIA-PINTOS, YUNSEONG NAM, ALEJANDRO PERDOMO-ORTIZ: "A generative modeling approach for benchmarking and training shallow quantum circuits", 23 January 2018 (2018-01-23), XP055593894, Retrieved from the Internet DOI: 10.1038/s41534-019-0157-8
MURPHY YUEZHEN NIU; ANDREW M. DAI; LI LI; AUGUSTUS ODENA; ZHENGLI ZHAO; VADIM SMELYANSKYI; HARTMUT NEVEN; SERGIO BOIXO: "Learnability and Complexity of Quantum Samples", ARXIV.ORG, CORNELL UNIVERSITY LIBRARY, 201 OLIN LIBRARY CORNELL UNIVERSITY ITHACA, NY 14853, 22 October 2020 (2020-10-22), 201 Olin Library Cornell University Ithaca, NY 14853 , XP081795866
YANG SHUO, GU ZHENG-CHENG, WEN XIAO-GANG: "Loop Optimization for Tensor Network Renormalization", PHYSICAL REVIEW LETTERS, AMERICAN PHYSICAL SOCIETY, US, vol. 118, no. 11, 1 March 2017 (2017-03-01), US , XP093000183, ISSN: 0031-9007, DOI: 10.1103/PhysRevLett.118.110504
NICHOLAS GAO; MAX WILSON; THOMAS VANDAL; WALTER VINCI; RAMAKRISHNA NEMANI; ELEANOR RIEFFEL: "High-Dimensional Similarity Search with Quantum-Assisted Variational Autoencoder", ARXIV.ORG, CORNELL UNIVERSITY LIBRARY, 201 OLIN LIBRARY CORNELL UNIVERSITY ITHACA, NY 14853, 13 June 2020 (2020-06-13), 201 Olin Library Cornell University Ithaca, NY 14853 , XP081700763
MARCELLO BENEDETTI, DELFINA GARCIA-PINTOS, YUNSEONG NAM, ALEJANDRO PERDOMO-ORTIZ: "A generative modeling approach for benchmarking and training shallow quantum circuits", 23 January 2018 (2018-01-23), XP055593894, Retrieved from the Internet
MURPHY YUEZHEN NIU; ANDREW M. DAI; LI LI; AUGUSTUS ODENA; ZHENGLI ZHAO; VADIM SMELYANSKYI; HARTMUT NEVEN; SERGIO BOIXO: "Learnability and Complexity of Quantum Samples", ARXIV.ORG, CORNELL UNIVERSITY LIBRARY, 201 OLIN LIBRARY CORNELL UNIVERSITY ITHACA, NY 14853, 22 October 2020 (2020-10-22), 201 Olin Library Cornell University Ithaca, NY 14853 , XP081795866
Attorney, Agent or Firm:
PLOTKIN, Robert (US)
Download PDF:
Previous Patent: TECHNIQUES FOR SIDELINK RESOURCE RESERVATIONS
Next Patent: CABLE ASSEMBLY WITH INTEGRAL SEAL ELEMENT
Next Patent: CABLE ASSEMBLY WITH INTEGRAL SEAL ELEMENT