Projects per year
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 informationtheoretically 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 informationtheoretically 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 informationtheoretically 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 NPhard 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 language  English 

Number of pages  42 
Publication status  Epub ahead of print  22 Sept 2017 
Event  7th International Conference on Quantum Cryptography  University of Cambridge, Cambridge, United Kingdom Duration: 18 Sept 2017 → 22 Sept 2017 http://2017.qcrypt.net/ 
Conference
Conference  7th International Conference on Quantum Cryptography 

Abbreviated title  QCrypt 2017 
Country/Territory  United Kingdom 
City  Cambridge 
Period  18/09/17 → 22/09/17 
Internet address 
Fingerprint
Dive into the research topics of 'On the implausibility of classical client blind quantum computing'. Together they form a unique fingerprint.Projects
 1 Finished
Profiles

Elham Kashefi
 School of Informatics  Personal Chair in Quantum Computing
 Laboratory for Foundations of Computer Science
 Foundations of Computation
Person: Academic: Research Active