Abstract / Description of output
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 ⊂ MA/O(n^{d}). We conjecture that this containment is unlikely by proving that there exists an oracle relative to which BQP ⊄ 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  Ω(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 ∩ coQCMA/qpoly. Then, we show that having such a protocol for delegating NPhard functions implies coNP^{NP^{NP}} ⊆ NP^{NP^{PromiseQMA}}.
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 ⊂ MA/O(n^{d}). We conjecture that this containment is unlikely by proving that there exists an oracle relative to which BQP ⊄ 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  Ω(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 ∩ coQCMA/qpoly. Then, we show that having such a protocol for delegating NPhard functions implies coNP^{NP^{NP}} ⊆ NP^{NP^{PromiseQMA}}.
Original language  English 

Title of host publication  46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) 
Editors  Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, Stefano Leonardi 
Place of Publication  Dagstuhl, Germany 
Publisher  Schloss Dagstuhl  LeibnizZentrum fuer Informatik, Germany 
Pages  6:16:13 
Number of pages  13 
ISBN (Print)  9783959771092 
DOIs  
Publication status  Published  4 Jul 2019 
Event  46th International Colloquium on Automata, Languages and Programming  Patras, Greece Duration: 8 Jul 2019 → 12 Jul 2019 https://icalp2019.upatras.gr/index.php#welcome 
Publication series
Name  Leibniz International Proceedings in Informatics (LIPIcs) 

Publisher  Schloss DagstuhlLeibnizZentrum fuer Informatik 
Volume  132 
ISSN (Electronic)  18688969 
Conference
Conference  46th International Colloquium on Automata, Languages and Programming 

Abbreviated title  ICALP 2019 
Country/Territory  Greece 
City  Patras 
Period  8/07/19 → 12/07/19 
Internet address 
Fingerprint
Dive into the research topics of 'ComplexityTheoretic Limitations on Blind Delegated Quantum Computation'. Together they form a unique fingerprint.Profiles

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