在本文中,我们介绍了分布式交互式证明的量子对应物:现在可以是量子位,网络的节点可以执行量子计算。本文的第一个结果表明,通过使用分布式量子交互式证明,可以大大减少相互作用的数量。更确切地说,我们的结果表明,对于任何常数K,可以由k-turn classical(即非量词)分布式交互式协议决定的语言类别,具有F(n)-bit证书大小中包含的语言中包含,可以由5-Turn分布式量子交互协议与O(f(f(f(f))),可以决定使用5-Turn分布式交互协议。我们还表明,如果我们允许使用共享的随机性,则可以将转弯数减少到三个。由于目前尚无类似的转向还原经典技术,因此我们的结果也证明了在分布式交互式证明的设置中量子计算的力量。
主要关键词