Sumcheck-based delegation of quantum computing to rational server

Abstract

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. 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 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 between $rational$ and $ordinary$ delegated quantum computing protocols. This equivalence then serves as a basis for a reward-gap amplification method.

32 pages, 2 figures, close to published version in Theor. Comput. Sci., Because of the character limitation, the abstract was shortened compared with the PDF file

References in corpus (16)

• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• 18-qubit entanglement with photon's three degrees of freedom
• Observation of Entangled States of a Fully Controlled 20-Qubit System
• 16-qubit IBM universal quantum computer can be fully entangled
• Interactive Proofs For Quantum Computations
• Verification of Many-Qubit States
• Resource-efficient verification of quantum computing using Serfling's bound
• Low-degree testing for quantum states, and a quantum entangled games PCP for QMA
• QFactory: classically-instructed remote secret qubits preparation
• A quantum algorithm for additive approximation of Ising partition functions
• Approximating Turaev-Viro 3-manifold invariants is universal for quantum computation
• BQP-complete Problems Concerning Mixing Properties of Classical Random Walks on Sparse Graphs
• Merlin-Arthur with efficient quantum Merlin and quantum supremacy for the second level of the Fourier hierarchy
• Sumcheck-based delegation of quantum computing to rational server
• A Quantum inspired proof of $P^{\#P}\subseteq IP$
• Interactive Proofs with Polynomial-Time Quantum Prover for Computing the Order of Solvable Groups

Cited by in corpus (1)

• Sumcheck-based delegation of quantum computing to rational server