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 $\sf 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(n^d)$ bits of classical communication implies that $\mathsf{BQP} \subset \mathsf{MA/O(n^d)}$ . We conjecture that this containment is unlikely by providing an oracle relative to which $\mathsf{BQP} \not\subset \mathsf{MA/O(n^d)}$ . 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 $2^{n - \mathsfΩ(n/log(n))}$ , making polynomially-sized queries to an $\sf NP^{NP}$ oracle, for computing the permanent of an $n \times 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 $\mathsf{QCMA/qpoly \cap coQCMA/qpoly}$ . Then, we show that having such a protocol for delegating $\mathsf{NP}$ -hard functions implies $\mathsf{coNP^{NP^{NP}}} \subseteq \mathsf{NP^{NP^{PromiseQMA}}}$ .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 $\sf 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(n^d)$ bits of classical communication implies that $\mathsf{BQP} \subset \mathsf{MA/O(n^d)}$. We conjecture that this containment is unlikely by providing an oracle relative to which $\mathsf{BQP} \not\subset \mathsf{MA/O(n^d)}$. 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 $2^{n - \mathsfΩ(n/log(n))}$, making polynomially-sized queries to an $\sf NP^{NP}$ oracle, for computing the permanent of an $n \times 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 $\mathsf{QCMA/qpoly \cap coQCMA/qpoly}$. Then, we show that having such a protocol for delegating $\mathsf{NP}$-hard functions implies $\mathsf{coNP^{NP^{NP}}} \subseteq \mathsf{NP^{NP^{PromiseQMA}}}$.

arXiv:1704.08482Leibniz international proceedings in informaticsApr 27, 20179 citations

Composable secure multi-client delegated quantum computation

Monireh Houshmand, Mahboobeh Houshmand, Si-Hui Tan +1 more

The engineering challenges involved in building large scale quantum computers, and the associated infrastructure requirements, mean that when such devices become available it is likely that this will be in limited numbers and in limited geographic locations. It is likely that many users will need to rely on remote access to delegate their computation to the available hardware. In such a scenario, the privacy and reliability of the delegated computations are important concerns. On the other hand, the distributed nature of modern computations has led to a widespread class of applications in which a group of parties attempt to perform a joint task over their inputs, e.g., in cloud computing. In this paper, we study the multi-client delegated quantum computation problem where we consider the global computation be made up of local computations that are individually decided by the clients. Each client part is kept secret from the server and the other clients. We construct a composable secure multi-client delegated quantum computation scheme from any composable secure single-client delegated quantum computation protocol and quantum authentication codes.The engineering challenges involved in building large scale quantum computers, and the associated infrastructure requirements, mean that when such devices become available it is likely that this will be in limited numbers and in limited geographic locations. It is likely that many users will need to rely on remote access to delegate their computation to the available hardware. In such a scenario, the privacy and reliability of the delegated computations are important concerns. On the other hand, the distributed nature of modern computations has led to a widespread class of applications in which a group of parties attempt to perform a joint task over their inputs, e.g., in cloud computing. In this paper, we study the multi-client delegated quantum computation problem where we consider the global computation be made up of local computations that are individually decided by the clients. Each client part is kept secret from the server and the other clients. We construct a composable secure multi-client delegated quantum computation scheme from any composable secure single-client delegated quantum computation protocol and quantum authentication codes.

arXiv:1811.11929Nov 29, 20185 citations

Quantum protocols for untrusted computations

Takashi Mihara

Journal of Discrete AlgorithmsMay 5, 20061 citation

Secure Quantum Computation with Classical Communication

James Bartusek

Lecture notes in computer scienceJan 1, 202115 citations

\sf 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(n^d)

bits of classical communication implies that

\mathsf{BQP} \subset \mathsf{MA/O(n^d)}

. We conjecture that this containment is unlikely by providing an oracle relative to which

\mathsf{BQP} \not\subset \mathsf{MA/O(n^d)}

. 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

2^{n - \mathsfΩ(n/log(n))}

, making polynomially-sized queries to an

\sf NP^{NP}

oracle, for computing the permanent of an

n \times 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

\mathsf{QCMA/qpoly \cap coQCMA/qpoly}

. Then, we show that having such a protocol for delegating

\mathsf{NP}

-hard functions implies

\mathsf{coNP^{NP^{NP}}} \subseteq \mathsf{NP^{NP^{PromiseQMA}}}