Edinburgh Research Explorer

On the implausibility of classical client blind quantum computing

Research output: Contribution to conferencePaper

Related Edinburgh Organisations

Open Access permissions

Open

Documents

Original languageEnglish
Number of pages42
Publication statusE-pub ahead of print - 22 Sep 2017
Event7th International Conference on Quantum Cryptography - University of Cambridge, Cambridge, United Kingdom
Duration: 18 Sep 201722 Sep 2017
http://2017.qcrypt.net/

Conference

Conference7th International Conference on Quantum Cryptography
Abbreviated titleQCrypt 2017
CountryUnited Kingdom
CityCambridge
Period18/09/1722/09/17
Internet address

Abstract

Suppose a large scale quantum computer becomes available over the Internet. Could we delegate universal quantum computations to this server, using only classical communication between client and server, in a way that is information-theoretically blind (i.e., the server learns nothing about the input apart from its size, with no cryptographic assumptions required)? In this paper we give strong indications that the answer is no. This contrasts with the situation where quantum communication between client and server is allowed --- where we know that such information-theoretically blind quantum computation is possible. It also contrasts with the case where cryptographic assumptions are allowed: there again, it is now known that there are quantum analogues of fully homomorphic encryption. In more detail, we observe that, if there exist information-theoretically secure classical schemes for performing universal quantum computations on encrypted data, then we get unlikely containments between complexity classes, such as BQP⊂NP/poly. Moreover, we prove that having such schemes for delegating quantum sampling problems, such as Boson Sampling, would lead to a collapse of the polynomial hierarchy. We then consider encryption schemes which allow one round of quantum communication and polynomially many rounds of classical communication, yielding a generalization of blind quantum computation. We give a complexity theoretic upper bound, namely QCMA/qpoly∩coQCMA/qpoly, on the types of functions that admit such a scheme. This upper bound then lets us show that, under plausible complexity assumptions, such a protocol is no more useful than classical schemes for delegating NP-hard problems to the server. Lastly, we comment on the implications of these results for the prospect of verifying a quantum computation through classical interaction with the server.

Event

7th International Conference on Quantum Cryptography

18/09/1722/09/17

Cambridge, United Kingdom

Event: Conference

Download statistics

No data available

ID: 98145532