论文标题
量子采样的恒定盲目经典验证
Constant-round Blind Classical Verification of Quantum Sampling
论文作者
论文摘要
在最近的突破中，Mahadev构建了经典客户端的量子计算（CVQC）协议的经典验证，以将BQP中的决策问题委托给计算假设下的不受信任的量子示意剂。在这项工作中，我们进一步探索了CVQC的可行性，并具有BQP中更一般的采样问题以及理想的失明特性。我们为两者提供了肯定的解决方案，如下所示。 （1）由许多量子应用的采样性质（例如，用于机器学习和量子至上任务的量子算法）的动机，我们启动了CVQC的量子抽样问题的研究（由SAMPBQP表示）。更准确地说，在用于SAMPBQP问题的CVQC协议中，给出了供应器和验证者在\ {0,1 \}^n $和量子电路$ c $中给输入$ x \，并且经典客户的目标是从输出$ z \ lestarrow c（x）$ for the small for的prower中，从输出$ z \ lestarrow c（x）中学习一个示例。我们通过基于误差假设构建SAMPBQP的四启CVQC协议来证明其可行性。 （2）CVQC协议的失明是指供供者什么都没学会的协议的属性，因此对客户的输入是盲目的。这是一种高度理想的属性，已被深入研究量子计算的授权。我们提供了一个简单而功能强大的通用编译器，该编译器将任何CVQC协议转换为盲目协议，同时保留其完整性和声音错误以及回合的数量。 将我们的编译器应用于Mahadev的BQP的CVQC协议（平行重复）和SAMPBQP的CVQC协议，分别具有BQP和SAMPBQP的第一个恒定回合CVQC协议，分别具有可忽略不计的，并且分别可忽略不计的，并且分别为多项性的声音错误，并且分别是无用的完整性错误。
In a recent breakthrough, Mahadev constructed a classical verification of quantum computation (CVQC) protocol for a classical client to delegate decision problems in BQP to an untrusted quantum prover under computational assumptions. In this work, we explore further the feasibility of CVQC with the more general sampling problems in BQP and with the desirable blindness property. We contribute affirmative solutions to both as follows. (1) Motivated by the sampling nature of many quantum applications (e.g., quantum algorithms for machine learning and quantum supremacy tasks), we initiate the study of CVQC for quantum sampling problems (denoted by SampBQP). More precisely, in a CVQC protocol for a SampBQP problem, the prover and the verifier are given an input $x\in \{0,1\}^n$ and a quantum circuit $C$, and the goal of the classical client is to learn a sample from the output $z \leftarrow C(x)$ up to a small error, from its interaction with an untrusted prover. We demonstrate its feasibility by constructing a four-message CVQC protocol for SampBQP based on the quantum Learning With Error assumption. (2) The blindness of CVQC protocols refers to a property of the protocol where the prover learns nothing, and hence is blind, about the client's input. It is a highly desirable property that has been intensively studied for the delegation of quantum computation. We provide a simple yet powerful generic compiler that transforms any CVQC protocol to a blind one while preserving its completeness and soundness errors as well as the number of rounds. Applying our compiler to (a parallel repetition of) Mahadev's CVQC protocol for BQP and our CVQC protocol for SampBQP yields the first constant-round blind CVQC protocol for BQP and SampBQP respectively, with negligible and inverse polynomial soundness errors respectively, and negligible completeness errors.
