Sumcheck-Based Delegation of Quantum Computing to Rational Server
Sumcheck-Based Delegation of Quantum Computing to Rational Server
复制标题
基于 Sumcheck 的量子计算委托给 Rational Server
DOI：
10.1007/978-3-030-59267-7_7
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Seiichiro Tani
中科院分区：
文献类型：
--
作者：
Yuki Takeuchi;Tomoyuki Morimae;Seiichiro Tani
委派量子计算使具有弱计算能力的客户端能够将量子计算委托给远程量子服务器，使得客户端可以有效地验证服务器的完整性。最近，一种新的委托量子计算模型被提出，即理性委托量子计算。在该模型中，在客户端与服务器交互后，客户端根据服务器的消息和客户端的随机比特向服务器支付报酬。Rational服务器发送使奖励的期望值最大化的消息。众所周知，经典客户端可以一轮将普适量子计算委托给有理量子服务器。在本文中，我们通过推广经典的有理Sumcheck协议，提出了新的单轮有理委托量子计算协议。我们协议的一个优点是它们是与门集合无关的：以前Rational协议的构建依赖于门集合，而我们的Sumcheck技术可以很容易地使用任何局部门集合(其每个基本门可以用多项式比特数指定)来实现。此外，与以前的协议一样，我们的奖励函数满足自然要求(奖励是非负的，上界为常量，其最大期望值为常量的下界)。我们还讨论了报酬差距。简单地说，奖励差距是由于服务器的行为导致客户端接受错误答案而导致的服务器奖励的期望值的最小损失。因此，奖励差距应该足够大，以激励服务器以最佳方式运行。尽管我们的基于Sumcheck的协议像以前的协议一样只有指数级的小奖励差距，但我们证明了，如果允许两个不通信但相互纠缠的Rational服务器，就可以实现恒定的奖励差距。我们还讨论了在(普遍认为)多项式时间量子计算中错误学习问题是困难的假设下，单个Rational服务器是否足够。除此之外，我们还证明了在一定条件下，理性委托量子计算协议与常规委托量子计算协议之间的等价性。然后，这种等价性成为奖励差距放大方法的基础。
Delegated quantum computing enables a client with weak computational power to delegate quantum computing to a remote quantum server in such a way that the integrity of the server can be efficiently verified by the client. Recently, a new model of delegated quantum computing has been proposed, namely, rational delegated quantum computing. In this model, after the client interacts with the server, the client pays a reward to the server depending on the server's messages and the client's random bits. The rational server sends messages that maximize the expected value of the reward. It is known that the classical client can delegate universal quantum computing to the rational quantum server in one round. In this paper, we propose novel one-round rational delegated quantum computing protocols by generalizing the classical rational sumcheck protocol. An advantage of our protocols is that they are gate-set independent: the construction of the previous rational protocols depends on gate sets, while our sumcheck technique can be easily realized with any local gate set (each of whose elementary gates can be specified with a polynomial number of bits). Furthermore, as with the previous protocols, our reward function satisfies natural requirements (the reward is non-negative, upper-bounded by a constant, and its maximum expected value is lower-bounded by a constant). We also discuss the reward gap. Simply speaking, the reward gap is a minimum loss on the expected value of the server's reward incurred by the server's behavior that makes the client accept an incorrect answer. The reward gap should therefore be large enough to incentivize the server to behave optimally. Although our sumcheck-based protocols have only exponentially small reward gaps as in the previous protocols, we show that a constant reward gap can be achieved if two noncommunicating but entangled rational servers are allowed. We also discuss whether a single rational server is sufficient under the (widely believed) assumption that the learning-with-errors problem is hard for polynomial-time quantum computing. Apart from these results, we show, under a certain condition, the equivalence betweenrationalandordinarydelegated quantum computing protocols. This equivalence then serves as a basis for a reward-gap amplification method.