On the implausibility of classical client blind quantum computing

Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu, Elham Kashefi

Research output: Contribution to conferencePaperpeer-review

Abstract / Description of output

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.
Original languageEnglish
Number of pages42
Publication statusE-pub ahead of print - 22 Sept 2017
Event7th International Conference on Quantum Cryptography - University of Cambridge, Cambridge, United Kingdom
Duration: 18 Sept 201722 Sept 2017


Conference7th International Conference on Quantum Cryptography
Abbreviated titleQCrypt 2017
Country/TerritoryUnited Kingdom
Internet address


Dive into the research topics of 'On the implausibility of classical client blind quantum computing'. Together they form a unique fingerprint.

Cite this