Unconditionally verifiable blind quantum computation
Unconditionally verifiable blind quantum computation
复制标题
DOI：
10.1103/physreva.96.012303
复制
发表时间：
2017-07-05
影响因子：
2.9
通讯作者：
Kashefi, Elham
中科院分区：
文献类型：
--
作者：
Fitzsimons, Joseph F.;Kashefi, Elham
盲量子计算（BQC）允许客户端让服务器为他们执行量子计算，使得客户端的输入、输出和计算保持私有。任何BQC协议的理想属性是验证，由此客户端可以以高概率验证服务器是否遵循了协议的指令，或者是否存在导致损坏的输出状态的一些偏差。一个可验证的BQC协议可以被看作是一个交互式的证明系统，导致复杂性理论的后果。我们以前提出[A]。Broadbent、J. Fitzsimons和E. Kashefi，in Proceedings of the 50th Annual Symposium on Foundations of Computer Science，Atlanta，2009（IEEE，皮斯卡特维，2009），p.517]一种通用且无条件安全的BQC方案，其中客户端仅需要能够准备从有限集合中随机选择的处于可分离状态的单个量子位，并将它们发送到服务器，服务器具有所需量子计算资源的平衡。在本文中，我们对该协议进行了扩展，增加了允许盲计算基础测量的额外功能，我们使用这些功能来构建另一个基于不同类型资源状态的可验证BQC协议。我们严格证明，未能检测到一个不正确的输出的概率是指数小的安全参数，而资源开销保持多项式在这个参数。这种资源状态允许在仅具有恒定开销的任意逻辑量子位对之间执行纠缠门。这是对原始方案的重大改进，原始方案要求所有要执行的计算必须首先放入最近邻形式，从而导致量子位数的线性开销。这种改进对效率和容错阈值具有重要影响。
Blind quantum computing (BQC) allows a client to have a server carry out a quantum computation for them such that the client's input, output, and computation remain private. A desirable property for any BQC protocol is verification, whereby the client can verify with high probability whether the server has followed the instructions of the protocol or if there has been some deviation resulting in a corrupted output state. A verifiable BQC protocol can be viewed as an interactive proof system leading to consequences for complexity theory. We previously proposed [A. Broadbent, J. Fitzsimons, and E. Kashefi, in Proceedings of the 50th Annual Symposium on Foundations of Computer Science, Atlanta, 2009 (IEEE, Piscataway, 2009), p. 517] a universal and unconditionally secure BQC scheme where the client only needs to be able to prepare single qubits in separable states randomly chosen from a finite set and send them to the server, who has the balance of the required quantum computational resources. In this paper we extend that protocol with additional functionality allowing blind computational basis measurements, which we use to construct another verifiable BQC protocol based on a different class of resource states. We rigorously prove that the probability of failing to detect an incorrect output is exponentially small in a security parameter, while resource overhead remains polynomial in this parameter. This resource state allows entangling gates to be performed between arbitrary pairs of logical qubits with only constant overhead. This is a significant improvement on the original scheme, which required that all computations to be performed must first be put into a nearest-neighbor form, incurring linear overhead in the number of qubits. Such an improvement has important consequences for efficiency and fault-tolerance thresholds.