Shaydulin Ruslan, Li Changhao, Chakrabarti Shouvanik, DeCross Matthew, Herman Dylan, Kumar Niraj, Larson Jeffrey, Lykov Danylo, Minssen Pierre, Sun Yue, Alexeev Yuri, Dreiling Joan M, Gaebler John P, Gatterman Thomas M, Gerber Justin A, Gilmore Kevin, Gresh Dan, Hewitt Nathan, Horst Chandler V, Hu Shaohan, Johansen Jacob, Matheny Mitchell, Mengle Tanner, Mills Michael, Moses Steven A, Neyenhuis Brian, Siegfried Peter, Yalovetzky Romina, Pistoia Marco
Global Technology Applied Research, JPMorgan Chase, New York, NY 10017, USA.
Quantinuum, Broomfield, CO 80021, USA.
Sci Adv. 2024 May 31;10(22):eadm6761. doi: 10.1126/sciadv.adm6761. Epub 2024 May 29.
The quantum approximate optimization algorithm (QAOA) is a leading candidate algorithm for solving optimization problems on quantum computers. However, the potential of QAOA to tackle classically intractable problems remains unclear. Here, we perform an extensive numerical investigation of QAOA on the low autocorrelation binary sequences (LABS) problem, which is classically intractable even for moderately sized instances. We perform noiseless simulations with up to 40 qubits and observe that the runtime of QAOA with fixed parameters scales better than branch-and-bound solvers, which are the state-of-the-art exact solvers for LABS. The combination of QAOA with quantum minimum finding gives the best empirical scaling of any algorithm for the LABS problem. We demonstrate experimental progress in executing QAOA for the LABS problem using an algorithm-specific error detection scheme on Quantinuum trapped-ion processors. Our results provide evidence for the utility of QAOA as an algorithmic component that enables quantum speedups.
量子近似优化算法（QAOA）是用于在量子计算机上解决优化问题的主要候选算法。然而，QAOA解决经典难处理问题的潜力仍不明确。在此，我们对低自相关二进制序列（LABS）问题进行了广泛的QAOA数值研究，该问题即使对于中等规模的实例在经典情况下也是难处理的。我们使用多达40个量子比特进行无噪声模拟，并观察到具有固定参数的QAOA的运行时间比分支定界求解器的扩展性更好，分支定界求解器是LABS问题的当前最优精确求解器。QAOA与量子最小化搜索的结合给出了LABS问题所有算法中最佳的经验扩展性。我们展示了在使用Quantinuum俘获离子处理器上的特定算法错误检测方案执行LABS问题的QAOA方面的实验进展。我们的结果为QAOA作为实现量子加速的算法组件的效用提供了证据。
