Sumcheck-based delegation of quantum computing to rational server
share
Delegated quantum computing enables a client with a weak computational power to delegate quantum computing to a remote quantum server in such a way that the integrity of the server is 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. 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. The construction of the previous rational protocols depends on gate sets, while our sumcheck technique can be easily realized with any local gate set. Furthermore, as with the previous protocols, our reward function satisfies natural requirements. 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. Although our sumcheck-based protocols have only exponentially small reward gaps as with the previous protocols, we show that a constant reward gap can be achieved if two non-communicating but entangled rational servers are allowed. We also discuss that 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 between rational and ordinary delegated quantum computing protocols. Based on this equivalence, we give a reward-gap amplification method.
READ FULL TEXT