AF: Small: Toward Applications and Verification of Early Quantum Computers

量子计算机有可能比普通的经典计算机更快地解决某些问题，为那些难以解决的问题提供了有效解决方案的前景。最近在量子计算机的实验实现方面取得了重大进展，这表明在未来十年内可能会有数十个控制良好的量子位的设备。因此，现在是研究如何最好地利用早期设备的有限能力的关键时刻，并开发方法来验证它们在难以经典模拟的情况下的正确行为。量子计算机的一个主要潜在应用是模拟量子物理。由于它接近量子计算机的原生行为，量子模拟的开销相对较低，因此很可能是早期的实际应用。该项目将研究如何使用近期设备最好地应用量子模拟。该项目团队将更广泛地发展量子模拟算法的理论，并将探索使用量子模拟来解决其他计算问题，研究包括量子态制备和微分方程解在内的挑战。早期量子计算机面临的一个重大挑战是难以确保它们正确工作。本项目将研究验证量子计算正确性的方法。由于许多量子计算可能没有有效的可检查证明，研究人员将考虑更一般的交互式验证框架，其中经典验证者试图通过交换消息来建立有效量子证明器的正确性。基于最近在计算假设下的交互式验证方面取得的进展，项目团队将调查执行此类验证所需的通信回合数，探索电路混淆作为交互式验证工具的力量，并研究改变证明者和验证者的权力的影响（以及它们之间的相互作用）确保正确性的能力。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的评估被认为值得支持影响审查标准。

Quantum computers have the potential to solve certain problems much faster than ordinary classical computers, offering the prospect of efficient solutions to problems that would otherwise be intractable. There has recently been significant progress toward the experimental realization of quantum computers, suggesting that devices with tens of well-controlled qubits may be available in the next decade. Therefore, now is a crucial time to investigate how to best take advantage of the limited capabilities of early devices, and to develop methods for verifying that they behave correctly in a regime where they are difficult to simulate classically. A major potential application of quantum computers is the task of simulating quantum physics. Since it is close to the native behavior of quantum computers, quantum simulation has relatively low overhead, so it is likely to be an early practical application. This project will investigate how to best apply quantum simulation using near-term devices. The project team will develop the theory of quantum simulation algorithms more generally, and will explore using quantum simulation to solve other computational problems, studying challenges including quantum state preparation and solutions of differential equations. A significant challenge for early quantum computers is the difficulty of ensuring that they work correctly. This project will investigate methods for certifying the correctness of quantum computations. Since many quantum computations may not have efficiently checkable proofs, the researchers will consider the more general framework of interactive verification, where a classical verifier seeks to establish the correctness of an efficient quantum prover through an exchange of messages. Building on recent progress toward interactive verification under computational assumptions, the project team will investigate the number of rounds of communication needed to perform such verification, explore the power of circuit obfuscation as a tool for interactive verification, and study the impact of varying the power of the prover and verifier (and the interaction between them) on their ability to ensure correctness.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.