论文标题
在线性时间内对量子计算的经典验证
Classical Verification of Quantum Computations in Linear Time
论文作者
论文摘要
在量子计算验证问题中，量子服务器希望说服客户端评估量子电路$ c $的输出是其声称的结果。在量子计算[Arxiv：1709.06984]，[Arxiv：1704.04487]，[Arxiv：1209.0449]中，理论上和实际上都认为这个问题非常重要。客户端被认为是限制的计算能力，一个理想的属性是客户可以完全经典，这导致了量子计算（CVQC）问题的经典验证。就总时间复杂性而言，到目前为止，最快的单人服务器CVQC协议具有复杂性$ O（poly（κ）| c |^3）$，其中$ | c | $是要验证的电路的大小，$κ$是安全参数，由Mahadev [arxiv [arxiv：1804.01082]提供。 在这项工作中，通过开发新技术，我们提供了一个具有复杂性$ O（poly（κ）| C |）$的新CVQC协议，该协议的速度明显要比现有协议快得多。假设存在嘈杂的无链门无爪函数[arxiv：1804.00640]，我们的协议在量子随机甲骨文模型[arxiv：1008.0931]中是安全的，它们在量子加密术中都是广泛使用的假设。一路走来，我们还为状态提供了一个新的经典频道远程状态准备协议，以$ \ {|+_θ\ rangle = \ frac {1} {\ sqrt {2}}（| 0 \ rangle+e^{i+e^{iθπ/4} | 1 \ rangle）：量子密码学的原始。我们的协议允许以这种形式（可持续的总误差和可能无限的服务器端模拟器）对$ l $独立随机状态进行并行验证准备，并且仅以$ o（poly（poly（κ）L）$时间和恒定回合运行；为了进行比较，现有的作品（即使对于可能更简单的国家家庭）都需要非常大或不估计的时间和圆形复杂性[ARXIV：1904.06320] [ARXIV：1904.06303] [ARXIV：2201.13445] [ARXIV] [arxiv：2201.13430]。
In the quantum computation verification problem, a quantum server wants to convince a client that the output of evaluating a quantum circuit $C$ is some result that it claims. This problem is considered very important both theoretically and practically in quantum computation [arXiv:1709.06984], [arXiv:1704.04487], [arXiv:1209.0449]. The client is considered to be limited in computational power, and one desirable property is that the client can be completely classical, which leads to the classical verification of quantum computation (CVQC) problem. In terms of the total time complexity, the fastest single-server CVQC protocol so far has complexity $O(poly(κ)|C|^3)$ where $|C|$ is the size of the circuit to be verified and $κ$ is the security parameter, given by Mahadev [arXiv:1804.01082]. In this work, by developing new techniques, we give a new CVQC protocol with complexity $O(poly(κ)|C|)$, which is significantly faster than existing protocols. Our protocol is secure in the quantum random oracle model [arXiv:1008.0931] assuming the existence of noisy trapdoor claw-free functions [arXiv:1804.00640], which are both extensively used assumptions in quantum cryptography. Along the way, we also give a new classical channel remote state preparation protocol for states in $\{|+_θ\rangle=\frac{1}{\sqrt{2}}(|0\rangle+e^{iθπ/4}|1\rangle):θ\in \{0,1\cdots 7\}\}$, another basic primitive in quantum cryptography. Our protocol allows for parallel verifiable preparation of $L$ independently random states in this form (up to a constant overall error and a possibly unbounded server-side simulator), and runs in only $O(poly(κ)L)$ time and constant rounds; for comparison, existing works (even for possibly simpler state families) all require very large or unestimated time and round complexities [arXiv:1904.06320][arXiv:1904.06303][arXiv:2201.13445][arXiv:2201.13430].
