Known protocols for secure delegation of quantum computations from a client to a server in an information theoretic setting require quantum communication. In this work, we investigate methods to reduce communication overhead. First, we establish an impossibility result by proving that server-side local processes cannot decrease quantum communication requirements of secure delegation protocols. We develop no-go results that prohibit such processes within an information theoretic framework. Second, we present a possibility result by introducing Selectively Blind Quantum Computing (SBQC), a novel functionality that allows the client to hide one among a known set of possible computations. We characterize how differences between computations in the protected set influence the number of qubits sent during our SBQC implementation, yielding a communication-optimal protocol. This approach reduces qubit communication drastically and demonstrates the trade-off between information leaked to the server and communication cost.
Known protocols for secure delegation of quantum computations from a client to a server in an information theoretic setting require quantum communication. In this work, we investigate methods to reduce communication overhead. First, we establish an impossibility result by proving that server-side local processes cannot decrease quantum communication requirements of secure delegation protocols. We develop no-go results that prohibit such processes within an information theoretic framework. Second, we present a possibility result by introducing Selectively Blind Quantum Computing (SBQC), a novel functionality that allows the client to hide one among a known set of possible computations. We characterize how differences between computations in the protected set influence the number of qubits sent during our SBQC implementation, yielding a communication-optimal protocol. This approach reduces qubit communication drastically and demonstrates the trade-off between information leaked to the server and communication cost.
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.
Blind quantum computation (BQC) protocol allows a client having partial quantum ability to delegate his quantum computation to a remote quantum server without leaking any information about the input, the output and the intended computation to the server. Several BQC protocols have been proposed, e.g., Li et al. in [1] proposed a triple-server BQC protocol and Xu et al. in [2] proposed a single-server BQC protocol. Though both papers claimed that their protocols can satisfy the requirement of privacy, this paper points out a security loophole in their protocols. With that the server can reveal the private information of the client.
The question of whether a fully classical client can delegate a quantum computation to an untrusted quantum server while fully maintaining privacy (blindness) is one of the big open questions in quantum cryptography. Both yes and no answers have important practical and theoretical consequences, and the question seems genuinely hard. The state-of-the-art approaches to securely delegating quantum computation, without exception, rely on granting the client modest quantum powers, or on additional, non-communicating, quantum servers. In this work, we consider the single server setting, and push the boundaries of the minimal devices of the client, which still allow for blind quantum computation. Our approach is based on the observation that, in many blind quantum computing protocols, the "quantum" part of the protocol, from the clients perspective, boils down to the establishing classical-quantum correlations (independent from the computation) between the client and the server, following which the steering of the computation itself requires only classical communication. Here, we abstract this initial preparation phase, specifically for the Universal Blind Quantum Computation protocol of Broadbent, Fitzsimons and Kashefi. We identify sufficient criteria on the powers of the client, which still allow for secure blind quantum computation. We work in a universally composable framework, and provide a series of protocols, where each step reduces the number of differing states the client needs to be able to prepare. As the limit of such reductions, we show that the capacity to prepare just two pure states, which have an arbitrarily high overlap (thus are arbitrarily close to identical), suffices for efficient and secure blind quantum computation.
hile quantum computers might offer several computational benefits, their application within a quantum network is also of interest in regard to privacy, data protection and computational security. One promising application is blind quantum computing, where a client with limited quantum capacities utilizes the computational power of a quantum computer located at a quantum computing center without revealing any information about the computation or data involved. Several schemes for blind quantum computation have emerged, with the most advanced relying on measurement-based quantum computing [1]. However, many current quantum computer designs are based on gate-based state manipulation. While blind quantum computing is also possible in this scenario, it requires a permanent exchange of quantum information between client and server [2]. To reduce the communication overhead for the involved parties, we study a relaxed scenario of blind quantum computing, where the server gets some information about the algorithm. In particular, we propose a protocol to hide an n-qubit Grover search algorithm by utilizing additional qubits on a quantum server which are initialized by the clients. [1] Fitzsimons, J. F. (2017), npj Quantum Information, 3(1), 23. [2] A. Childs, A. (2005), Quantum Inform. Comput., 5, 456-466.
Blind quantum computation (BQC) allows low-resource clients to securely delegate computations to a quantum server, but server resource costs scale with the computation size, posing a bottleneck for implementations. By leveraging Pauli-based computation (PBC), we achieve BQC with a server whose size depends only on the non-Clifford gate count. Our protocol inherits fault tolerance and qubit virtualization from PBC and reveals that classical-client BQC is possible even in the absence of classical simulability. Finally, we present an entanglement-based dual protocol that performs a resource state computation with a dramatically reduced execution cost.
The universal blind quantum computation (UBQC) protocol [A. Broadbent, J. Fitzsimons, and E. Kashefi, in Proceedings of the 50th Annual IEEE Symposiumon Foundations of Computer Science (IEEE Computer Society, Los Alamitos, CA, USA, 2009), pp. 517-526.] allows a client to perform quantum computation on a remote server. In an ideal setting, perfect privacy is guaranteed if the client is capable of producing specific, randomly chosen single qubit states. While from a theoretical point of view, this may constitute the lowest possible quantum requirement, from a pragmatic point of view, generation of such states to be sent along long distances can never be achieved perfectly. We introduce the concept of ϵ blindness for UBQC, in analogy to the concept of ϵ security developed for other cryptographic protocols, allowing us to characterize the robustness and security properties of the protocol under possible imperfections. We also present a remote blind single qubit preparation protocol with weak coherent pulses for the client to prepare, in a delegated fashion, quantum states arbitrarily close to perfect random single qubit states. This allows us to efficiently achieve ϵ-blind UBQC for any ϵ>0, even if the channel between the client and the server is arbitrarily lossy.