Rational proofs for quantum computing

04/24/2018
by   Tomoyuki Morimae, et al.
0

It is an open problem whether a classical client (verifier) can delegate quantum computing to a remote quantum server (prover) in such a way that the correctness of quantum computing is somehow guaranteed. We show that such a delegation is possible if the prover is rational. More precisely, we introduce the following protocol. The BQP prover first sends the BPP verifier a single bit allegedly equal to the solution of the BQP decision problem that the verifier wants to solve. The verifier then gives the prover a reward whose amount is determined by the bit sent from the prover and some random numbers the verifier samples from certain probability distributions. The reward function is constructed in such a way that the rational prover, who wants to maximize the expected profit, has to send the correct bit to the verifier.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset