Given that reliable cloud quantum computers are becoming closer to reality, the concept of delegation of quantum computations and its verifiability is of central interest. Many models have been proposed, each with specific strengths and weaknesses. Here, we put forth a new model where the client trusts only its classical processing, makes no computational assumptions, and interacts with a quantum server in a single round. In addition, during a set-up phase, the client specifies the size $n$ of the computation and receives an untrusted, off-the-shelf (OTS) quantum device that is used to report the outcome of a single constant-sized measurement from a predetermined logarithmic-sized input. In the OTS model, we thus picture that a single quantum server does the bulk of the computations, while the OTS device is used as an untrusted and generic verification device, all in a single round. We show how to delegate polynomial-time quantum computations in the OTS model. Scaling up the technique also yields an interactive proof system for all of QMA, which, furthermore, we show can be accomplished in statistical zero-knowledge. This yields the first relativistic (one-round), two-prover zero-knowledge proof system for QMA. As a proof approach, we provide a new self-test for $n$-EPR pairs using only constant-sized Pauli measurements, and show how it provides a new avenue for the use of simulatable codes for local Hamiltonian verification. Along the way, we also provide an enhanced version of a well-known stability result due to Gowers and Hatami and show how it completes a common argument used in self-testing.
翻译:鉴于可靠的云量子计算机与现实越来越接近,量子计算的委派概念及其可验证性成为中心问题。已经提出了许多模型,每个模型都有特定的优缺点。在这里,我们提出了一个新模型,即客户端仅信任其经典处理,不做任何计算假设,并在单个回合中与量子服务器进行交互。此外,在设置阶段,客户端指定计算的大小 $n$,并接收一个不可信的、现成的 (OTS) 量子设备,该设备用于报告来自预先确定的对数级别输入的单个恒定大小的测量结果。在OTS模型中,因此我们认为一个单一的量子服务器完成大部分计算,而OTS设备作为一个不可信的、通用的验证设备,在单个回合中使用。我们展示了如何在OTS模型中委派多项式时间的量子计算。将这种技术扩大到规模,则可以获得所有 QMA 的交互式证明系统,而且我们还展示这可以在统计零知识下完成。这产生了第一个 QMA 的相对论性 (单回合)、两个证明人零知识证明系统。作为证明方法,我们提供了一个使用仅恒定大小的 Pauli 测量来进行 $n$ 个 EPR 对的自测试的新方法,并展示了它如何为本地哈密顿验证的模拟可证代码的使用提供新的途径。顺便提一句,我们还提供了一个著名的 Gowers 和Hatami稳定性结果的增强版本,并展示了它是自测中使用的常见论据的完整。