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.