量子科技中心_量科网

量子近似优化算法（QAOA）是一种混合量子-经典算法，用于在基于门的量子计算机中解决优化问题。该算法基于一个变分量子电路，可以解释为量子退火器在寻找给定哈密顿量最低能量状态时所遵循的退火过程的离散化。这确保了当变分量子电路中使用的层数p趋近于无穷大时，QAOA必须为任何给定的优化问题找到最优解。然而，在实际应用中，层数通常被限制在一个较小的范围内。在当前NISQ时代的量子计算机中，这是必须的，因为为了避免退相干和噪声问题，这些计算机能够运行的电路深度是有限的。本文中，研究团队提供了数学证据，表明当层数小于线性函数的不同系数数量n时，QAOA需要指数级时间来解决线性函数。研究团队推测，对于任何常数p，QAOA都需要指数级时间才能找到线性函数的全局最优解，并且只有当p≥n时，运行时间才是线性的。研究团队得出结论，为了在量子优化领域实现量子霸权，需要开发新的量子算法。