EAGER: QSA: Solving Optimization Problems on NISQ Computers

最优化问题普遍存在于科学和工程的各个领域。化学、物理和材料科学中的许多重要问题可以归结为在特定约束下的成本函数的最优化。传统上，经典的数值优化方法是研究这类问题的主要工具，但众所周知，这些方法在处理这类问题时效率非常低，因为需要探索的配置空间呈指数级增长。量子算法--原本打算在量子计算机上执行的协议--为解决这类问题提供了一种很有前途的方法。具体地说，经典-量子混合方法是近年来在这一背景下备受关注的焦点。本项目旨在开发和实验实现一种新的混合方法来解决优化问题，该方法超出了当前最先进技术的能力范围，并且能够以显著减少的经典量子迭代和每次迭代的重复实验实现更快的收敛。开发的协议将反过来允许对问题达成更准确的解决方案，以及处理比当前算法能力所允许的更大的问题。QAOA和VQE等传统量子优化协议的主要瓶颈之一是需要多次经典-量子迭代才能收敛。这个项目的主要目标是大幅减少经典-量子迭代的次数。这种方法依赖于将先进的参数最小化工具与量子信息论的最新结果相结合，能够有效地估计物理量(可观测)，并精确控制估计误差。本发明的基于参数的最小化本质上不同于现有技术的方法，其中优化是基于可用数据的，因此它有望显著减少经典量子迭代的次数。这些节省的资源反过来将增强我们在当前NISQ设备上解决优化问题的能力。这个项目是由化学部共同资助的。这个奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Optimization problems are ubiquitous in all areas of science and engineering. Many important problems in chemistry, physics, and materials science can be cast as the optimization of a cost function under specific constraints. Traditionally, classical numerical optimization methods are the main go-to tool for studying such problems, but these methods are known to be grossly inefficient when tackling problems of this sort due to the exponentially increasing configuration space that needs to be explored. Quantum algorithms — protocols meant to be executed on quantum computers — provide a promising approach to solving such problems. Specifically, hybrid classical-quantum methods have been the focus of much attention in this context recently. The present project seeks to develop and experimentally implement a novel hybrid approach to solving optimization problems that reaches beyond the capabilities of the current state-of-the-art and that enables faster convergence with significantly fewer classical-quantum iterations and considerably fewer repeated experiments per iteration. The developed protocol will in turn allow reaching more accurate solutions to problems as well as the handling of larger problems than allowed by current algorithmic capabilities. One of the main bottlenecks of traditional quantum optimization protocols, such as QAOA and VQE, is that they require many classical-quantum iterations to converge. The main objective of this project is to dramatically reduce the number of classical-quantum iterations. This approach, which relies on combining advanced parametric minimization tools together with recent results in quantum information theory, enables the efficient estimation of physical quantities (observables) with precise control over estimation errors. The present parametric-based minimization is inherently different than state-of-the-art approaches wherein the optimization is based on available data and as such it is expected to substantially reduce the number of classical-quantum iterations. These savings in resources will in turn enhance our ability to solve optimization problems on current NISQ devices. This project is being co-funded by the Division of Chemistry.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.