Abstract In the standard oracle model, an oracle efficiently evaluates an unknown classical function independent of the quantum algorithm itself. Quantum algorithms have a complex interrelationship to their oracles; for example the possibility of quantum speedup is affected by the manner by which oracles are implemented. Therefore, it is physically meaningful to separate oracles from their quantum algorithms, and we introduce one such separation here. We define the blind oracular quantum computation (BOQC) scheme, in which the oracle is a distinct node in a quantum network. Our work augments the client–server setting of quantum computing, in which a powerful quantum computer server is available on the network for discreet use by clients on the network with low quantum power. In BOQC, an oracle is another client that cooperates with the main client so that an oracular quantum algorithm is run on the server. The cooperation between the main client and the oracle takes place (almost) without communication. We prove BOQC to be blind: the server cannot learn anything about the clients’ computation. This proof is performed within the composable security definitions provided by the formalism of abstract cryptography. We enhance the BOQC scheme to be runnable with minimal physical qubits when run on a solid-state quantum network; we prove that this scheme, which we refer to as BOQCo (BOQC-optimized), possesses the same security as BOQC.
Abstract In the standard oracle model, an oracle efficiently evaluates an unknown classical function independent of the quantum algorithm itself. Quantum algorithms have a complex interrelationship to their oracles; for example the possibility of quantum speedup is affected by the manner by which oracles are implemented. Therefore, it is physically meaningful to separate oracles from their quantum algorithms, and we introduce one such separation here. We define the blind oracular quantum computation (BOQC) scheme, in which the oracle is a distinct node in a quantum network. Our work augments the client–server setting of quantum computing, in which a powerful quantum computer server is available on the network for discreet use by clients on the network with low quantum power. In BOQC, an oracle is another client that cooperates with the main client so that an oracular quantum algorithm is run on the server. The cooperation between the main client and the oracle takes place (almost) without communication. We prove BOQC to be blind: the server cannot learn anything about the clients’ computation. This proof is performed within the composable security definitions provided by the formalism of abstract cryptography. We enhance the BOQC scheme to be runnable with minimal physical qubits when run on a solid-state quantum network; we prove that this scheme, which we refer to as BOQCo (BOQC-optimized), possesses the same security as BOQC.
Recent years have seen much excitement for application of quantum computing, triggered by substantial — and ongoing — advances in experimental realizations of quantum computing. It is widely believed that client-server is the setting for quantum computers that will prevail in the future, where privacy becomes crucial in the application. Moreover, a recent experiment by Barz et al. [1] successfully demonstrated a blind quantum computation scheme: a client-server quantum computation in which a client with limited quantum power controls the execution of a quantum computation on a powerful server, without revealing valuable details of the computation. In this thesis, we discuss the Blind Oracular Quantum Computation (BOQC) scheme, a blind quantum computing scheme in which a third party (the oracle)with limited quantum power, assists the execution of a client’s oracular quantum computations by implementing oracle evaluations. In BOQC, a client with limited quantum power and without the capacity to construct the oracle, can delegate her oracular quantum computations to a powerful yet untrustworthy server, with the help of the oracle. We show that BOQC is provably blind within a composable definition such that the server cannot learn about the clients’ computation. We provide a realization of BOQC in a physical setting, particularly in a diamond nitrogen-vacancy (NV) center platform. In BOQC, the server has a One-Way Quantum Computer (1WQC) that is resource-demanding. To lower the resource-requirements, we develop the BOQCo protocol, a BOQC that employs lazy 1WQC to minimize the number of qubits needed. We also provide systematic numerical optimization to find resource states that are BOQC-compatible by admitting BOQC security criteria. Finally, we give explicit oracular quantum algorithms that are BOQC-compatible to be executed on the NV-center platform. The algorithms include 2-qubit Grover’s algorithm using three qubits, 3-qubit exact Grover’s algorithm using four qubits, 2-qubit Simon’s algorithm with a useless oracle using four qubits, and Deutsch’s algorithm using three physical qubits. We hope that these BOQC algorithms intrigue some experimentalists to try to implement them.[1] S. Barz et al. “Demonstration of Blind Quantum Computing”. In: Science 335.6066 (2012), pp. 303–308.
Here we extend the concept of blind client-server quantum computation, in which a client with limited quantum power controls the execution of a quantum computation on a powerful server, without revealing any details of the computation. Our extension is to introduce a three-node setting in which an oracular quantum computation can be executed blindly. In this Blind Oracular Quantum Computation (BOQC), the oracle (Oscar) is another node, with limited power, who acts in cooperation with the client (Alice) to supply quantum information to the server so that the oracle part of the quantum computation can also be executed blindly. We develop tests of this protocol using two- and three-qubit versions of the exact Grover algorithm (i.e., with database sizes 4≤N≤8), obtaining optimal implementations of these algorithms within a gate array scheme and the blinded cluster-state scheme. We discuss the feasibility of executing these protocols in state-of-the-art three-node experiments using NV-diamond electronic and nuclear qubits.
Here we put into practice the concept of blind client-server quantum computation, in which a client with limited quantum power controls the execution of a quantum computation on a powerful server, without revealing any details of the computation. In particular, it is a three-node setting in which an oracular quantum computation can be executed blindly. In this Blind Oracular Quantum Computation (BOQC), the oracle (Oscar) is another node, with limited power, who acts in cooperation with the client (Alice) to supply quantum information to the server so that the oracle part of the quantum computation can also be executed blindly. We develop tests of this protocol using two- and three-qubit versions of the exact Grover algorithm (i.e., with database sizes $4\ensuremath{\le}N\ensuremath{\le}8$), obtaining optimal implementations of these algorithms within a gate array scheme and the blinded cluster-state scheme. We discuss the feasibility of executing these protocols in state-of-the-art three-node experiments using nitrogen-vacancy diamond electronic and nuclear qubits.
In the universal blind quantum computation problem, a client wants to make use of a single quantum server to evaluate C|0⟩ where C is an arbitrary quantum circuit while keeping C secret. The client’s goal is to use as few resources as possible. This problem, first raised by Broadbent, Fitzsimons and Kashefi [FOCS 2009], has become fundamental to the study of quantum cryptography, not only because of its own importance, but also because it provides a testbed for new techniques that can be later applied to related problems (for example, quantum computation verification). Known protocols on this problem are mainly either information-theoretically (IT) secure or based on trapdoor assumptions (public key encryptions). In this paper we study how the availability of symmetric-key primitives, modeled by a random oracle, changes the complexity of universal blind quantum computation. We give a new universal blind quantum computation protocol. Similar to previous works on IT-secure protocols (for example, Broadbent-Fitzsimons-Kashefi), our protocol can be divided into two phases. In the first phase the client prepares some quantum gadgets with relatively simple quantum gates and sends them to the server, and in the second phase the client is entirely classical — it does not even need quantum storage. Crucially, the protocol’s first phase is succinct, that is, its complexity is independent of the circuit size. Given the security parameter κ, its complexity is only a fixed polynomial of κ, and can be used to evaluate any circuit (or several circuits) of size up to a subexponential of κ. In contrast, known schemes either require the client to perform quantum computations that scale with the size of the circuit, or require trapdoor assumptions.
Suppose a large scale quantum computer becomes available over the Internet. Could we delegate universal quantum computations to this server, using only classical communication between client and server, in a way that is information-theoretically blind (i.e., the server learns nothing about the input apart from its size, with no cryptographic assumptions required)? In this paper we give strong indications that the answer is no. This contrasts with the situation where quantum communication between client and server is allowed --- where we know that such information-theoretically blind quantum computation is possible. It also contrasts with the case where cryptographic assumptions are allowed: there again, it is now known that there are quantum analogues of fully homomorphic encryption. In more detail, we observe that, if there exist information-theoretically secure classical schemes for performing universal quantum computations on encrypted data, then we get unlikely containments between complexity classes, such as BQP⊂NP/poly. Moreover, we prove that having such schemes for delegating quantum sampling problems, such as Boson Sampling, would lead to a collapse of the polynomial hierarchy. We then consider encryption schemes which allow one round of quantum communication and polynomially many rounds of classical communication, yielding a generalization of blind quantum computation. We give a complexity theoretic upper bound, namely QCMA/qpoly∩coQCMA/qpoly, on the types of functions that admit such a scheme. This upper bound then lets us show that, under plausible complexity assumptions, such a protocol is no more useful than classical schemes for delegating NP-hard problems to the server. Lastly, we comment on the implications of these results for the prospect of verifying a quantum computation through classical interaction with the server.
Blind quantum computation is a new secure quantum computing protocol where a client, who does not have enough quantum technologies at her disposal, can delegate her quantum computation to a server, who has a fully fledged quantum computer, in such a way that the server cannot learn anything about the client's input, output, and program. If the client interacts with only a single server, the client has to have some minimum quantum power, such as the ability of emitting randomly rotated single-qubit states or the ability of measuring states. If the client interacts with two servers who share Bell pairs but cannot communicate with each other, the client can be completely classical. For such a double-server scheme, two servers have to share clean Bell pairs, and therefore the entanglement distillation is necessary in a realistic noisy environment. In this Letter, we show that it is possible to perform entanglement distillation in the double-server scheme without degrading the security of blind quantum computing.