Complexity-Theoretic Limitations on Blind Delegated Quantum Computation

Scott Aaronson, Alexandru Cojocaru, Alexandru Gheorghiu, Elham Kashefi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 information-theoretic security (provided the client and the server exchange some amount of quantum information). In this paper we prove, provided certain complexity-theoretic conjectures are true, that the power of information-theoretically secure blind delegation protocols for quantum computation (ITS-BQC protocols) is in a number of ways constrained.

In the first part of our paper we provide some indication that ITS-BQC protocols for delegating polynomial-time 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(nd) bits of communication, implies that BQP ⊂ MA/O(nd). We conjecture that this containment is unlikely by proving that there exists an oracle relative to which BQP ⊄ MA/O(nd). We then show that if an ITS-BQC 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 non-uniform circuits of size 2n - Ω(n/log(n)), making polynomially-sized queries to an NPNP oracle, for computing the permanent of an n x n matrix.

The second part of our paper concerns ITS-BQC 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 complexity-theoretic 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 NP-hard functions implies coNPNP^{NP} ⊆ NPNP^{PromiseQMA}.
Original languageEnglish
Title of host publication46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
EditorsChristel Baier, Ioannis Chatzigiannakis, Paola Flocchini, Stefano Leonardi
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Germany
Pages6:1-6:13
Number of pages13
ISBN (Print)978-3-95977-109-2
DOIs
Publication statusPublished - 4 Jul 2019
Event46th International Colloquium on Automata, Languages and Programming - Patras, Greece
Duration: 8 Jul 201912 Jul 2019
https://icalp2019.upatras.gr/index.php#welcome

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Volume132
ISSN (Electronic)1868-8969

Conference

Conference46th International Colloquium on Automata, Languages and Programming
Abbreviated titleICALP 2019
CountryGreece
CityPatras
Period8/07/1912/07/19
Internet address

Fingerprint Dive into the research topics of 'Complexity-Theoretic Limitations on Blind Delegated Quantum Computation'. Together they form a unique fingerprint.

Cite this