Blind quantum computing protocols enable a client, who can generate or measure single-qubit states, to delegate quantum computing to a remote quantum server protecting the client's privacy (i.e., input, output, and program). With current technologies, generations or measurements of single-qubit states are not too much burden for the client. In other words, secure delegated quantum computing is possible for ``almost classical" clients. However, is it possible for a ``completely classical" client? Here we consider a one-round perfectly-secure delegated quantum computing, and show that the protocol cannot satisfy both the correctness (i.e., the correct result is obtained when the server is honest) and the perfect blindness (i.e., the client's privacy is completely protected) simultaneously unless BQP is in NP. Since BQP is not believed to be in NP, the result suggests the impossibility of the one-round perfectly-secure delegated quantum computing.
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 that blind delegation protocols can achieve information-theoretic security. 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
BQP computations in which the client and the server interact only classically are unlikely to exist. We first show that having such a protocol with
O(nd) bits of classical communication implies that
BQP⊂MA/O(nd). We conjecture that this containment is unlikely by providing an oracle relative to which
BQP⊂MA/O(nd). We then show that if an ITS-BQC protocol exists with polynomial classical communication and which allows the client to delegate quantum sampling problems, 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×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, namely
QCMA/qpoly∩coQCMA/qpoly. Then, we show that having such a protocol for delegating
NP-hard functions implies
coNPNPNP⊆NPNPPromiseQMA.
In this paper, we propose a multiparty delegated quantum computing protocol for the completely classical clients. Our protocol is mainly based on the work of Cojocaru et al, in which they proposed a concrete protocol that can make a classical client instruct a quantum server to prepare a random qubit. We simplify their protocol by replacing the one-way functions with the one-way permutations that are post-quantum secure only. Then we extend this improved scheme to multiparty delegated quantum computation, where a group of classical clients can delegate their joint computation task to a distrusted quantum server.