Centrone Federico, Kumar Niraj, Diamanti Eleni, Kerenidis Iordanis
Sorbonne Université, CNRS, LIP6, Paris, France.
Université de Paris, CNRS, IRIF, Paris, France.
Nat Commun. 2021 Feb 8;12(1):850. doi: 10.1038/s41467-021-21119-1.
In recent years, many computational tasks have been proposed as candidates for showing a quantum computational advantage, that is an advantage in the time needed to perform the task using a quantum instead of a classical machine. Nevertheless, practical demonstrations of such an advantage remain particularly challenging because of the difficulty in bringing together all necessary theoretical and experimental ingredients. Here, we show an experimental demonstration of a quantum computational advantage in a prover-verifier interactive setting, where the computational task consists in the verification of an NP-complete problem by a verifier who only gets limited information about the proof sent by an untrusted prover in the form of a series of unentangled quantum states. We provide a simple linear optical implementation that can perform this verification task efficiently (within a few seconds), while we also provide strong evidence that, fixing the size of the proof, a classical computer would take much longer time (assuming only that it takes exponential time to solve an NP-complete problem). While our computational advantage concerns a specific task in a scenario of mostly theoretical interest, it brings us a step closer to potential useful applications, such as server-client quantum computing.
近年来，许多计算任务被提出来作为展现量子计算优势的候选任务，即使用量子计算机而非经典计算机执行任务所需时间方面的优势。然而，由于难以集齐所有必要的理论和实验要素，要实际证明这种优势仍然极具挑战性。在此，我们展示了在证明者 - 验证者交互场景下量子计算优势的实验证明，其中计算任务是由验证者验证一个NP完全问题，该验证者仅以一系列非纠缠量子态的形式获得关于不可信证明者发送的证明的有限信息。我们提供了一种简单的线性光学实现方法，它能够高效地（在几秒内）执行此验证任务，同时我们也提供了有力证据，即在固定证明规模的情况下，经典计算机将花费长得多的时间（仅假设解决一个NP完全问题需要指数时间）。虽然我们的计算优势涉及的是一个主要在理论上感兴趣的场景中的特定任务，但它使我们朝着诸如服务器 - 客户端量子计算等潜在有用应用又迈进了一步。
