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.
翻译:在最近的一项突破中,Mahadev为一位古典客户创建了典型的量计算(CVPQC)协议,将BQP中的决定问题委托给计算假设下的不信任量检验器。在这项工作中,我们进一步探索CVQC的可行性,在BQP和理想失明属性中存在更普遍的抽样问题。我们为这两种应用提供了肯定的解决办法如下:(1) 受许多量应用(例如机器学习和量级最高任务的量级P量级算法)的抽样性质驱动,我们开始研究CVQC量取样问题(由SampBQP注意到)。更准确地说,在SampBQPP问题的一个C协议中,CVQC和校准者被输入了 $x\in 0.1 美元和量级电路路路。 经典客户的目标是首先从输出 $z preportorroform C(xx) 美元到一个小错误,从它与一个不可靠的验证者互动(由SampBPQPQ),我们通过构建一个纯的 C-C 测试程序来证明其可行性,因此将C的碳化的碳化的客户的代码变成一个协议。