Aaronson, Scott ;
Cojocaru, Alexandru ;
Gheorghiu, Alexandru ;
Kashefi, Elham
ComplexityTheoretic Limitations on Blind Delegated Quantum Computation
Abstract
Blind delegation protocols allow a client to delegate a computation to a server so that the server learns nothing about the input to the computation apart from its size. For the specific case of quantum computation we know, from work over the past decade, that blind delegation protocols can achieve informationtheoretic security (provided the client and the server exchange some amount of quantum information). In this paper we prove, provided certain complexitytheoretic conjectures are true, that the power of informationtheoretically secure blind delegation protocols for quantum computation (ITSBQC protocols) is in a number of ways constrained.
In the first part of our paper we provide some indication that ITSBQC protocols for delegating polynomialtime quantum computations in which the client and the server interact only classically are unlikely to exist. We first show that having such a protocol in which the client and the server exchange O(n^d) bits of communication, implies that BQP subset MA/O(n^d). We conjecture that this containment is unlikely by proving that there exists an oracle relative to which BQP not subset MA/O(n^d). We then show that if an ITSBQC protocol exists in which the client and the server interact only classically and which allows the client to delegate quantum sampling problems to the server (such as BosonSampling) then there exist nonuniform circuits of size 2^{n  Omega(n/log(n))}, making polynomiallysized queries to an NP^{NP} oracle, for computing the permanent of an n x n matrix.
The second part of our paper concerns ITSBQC protocols in which the client and the server engage in one round of quantum communication and then exchange polynomially many classical messages. First, we provide a complexitytheoretic upper bound on the types of functions that could be delegated in such a protocol by showing that they must be contained in QCMA/qpoly cap coQCMA/qpoly. Then, we show that having such a protocol for delegating NPhard functions implies coNP^{NP^{NP}} subseteq NP^{NP^{PromiseQMA}}.
BibTeX  Entry
@InProceedings{aaronson_et_al:LIPIcs:2019:10582,
author = {Scott Aaronson and Alexandru Cojocaru and Alexandru Gheorghiu and Elham Kashefi},
title = {{ComplexityTheoretic Limitations on Blind Delegated Quantum Computation}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {6:16:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771092},
ISSN = {18688969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10582},
URN = {urn:nbn:de:0030drops105826},
doi = {10.4230/LIPIcs.ICALP.2019.6},
annote = {Keywords: Quantum cryptography, Complexity theory, Delegated quantum computation, Computing on encrypted data}
}
04.07.2019
Keywords: 

Quantum cryptography, Complexity theory, Delegated quantum computation, Computing on encrypted data 
Seminar: 

46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Issue date: 

2019 
Date of publication: 

04.07.2019 