Delegated quantum computing enables a client with weak computational power to delegate quantum computing to a remote quantum server in such a way that the integrity of the server can be efficiently verified by the client. Recently, a new model of delegated quantum computing has been proposed, namely, rational delegated quantum computing. In this model, after the client interacts with the server, the client pays a reward to the server depending on the server's messages and the client's random bits. The rational server sends messages that maximize the expected value of the reward. It is known that the classical client can delegate universal quantum computing to the rational quantum server in one round. In this paper, we propose novel one-round rational delegated quantum computing protocols by generalizing the classical rational sumcheck protocol. An advantage of our protocols is that they are gate-set independent: the construction of the previous rational protocols depends on gate sets, while our sumcheck technique can be easily realized with any local gate set (each of whose elementary gates can be specified with a polynomial number of bits). Furthermore, as with the previous protocols, our reward function satisfies natural requirements (the reward is non-negative, upper-bounded by a constant, and its maximum expected value is lower-bounded by a constant). We also discuss the reward gap. Simply speaking, the reward gap is a minimum loss on the expected value of the server's reward incurred by the server's behavior that makes the client accept an incorrect answer. The reward gap should therefore be large enough to incentivize the server to behave optimally. Although our sumcheck-based protocols have only exponentially small reward gaps as in the previous protocols, we show that a constant reward gap can be achieved if two noncommunicating but entangled rational servers are allowed. We also discuss whether a single rational server is sufficient under the (widely believed) assumption that the learning-with-errors problem is hard for polynomial-time quantum computing. Apart from these results, we show, under a certain condition, the equivalence between rational and ordinary delegated quantum computing protocols. This equivalence then serves as a basis for a reward-gap amplification method.
Delegated quantum computing enables a client with weak computational power to delegate quantum computing to a remote quantum server in such a way that the integrity of the server can be efficiently verified by the client. Recently, a new model of delegated quantum computing has been proposed, namely, rational delegated quantum computing. In this model, after the client interacts with the server, the client pays a reward to the server depending on the server's messages and the client's random bits. The rational server sends messages that maximize the expected value of the reward. It is known that the classical client can delegate universal quantum computing to the rational quantum server in one round. In this paper, we propose novel one-round rational delegated quantum computing protocols by generalizing the classical rational sumcheck protocol. An advantage of our protocols is that they are gate-set independent: the construction of the previous rational protocols depends on gate sets, while our sumcheck technique can be easily realized with any local gate set (each of whose elementary gates can be specified with a polynomial number of bits). Furthermore, as with the previous protocols, our reward function satisfies natural requirements (the reward is non-negative, upper-bounded by a constant, and its maximum expected value is lower-bounded by a constant). We also discuss the reward gap. Simply speaking, the reward gap is a minimum loss on the expected value of the server's reward incurred by the server's behavior that makes the client accept an incorrect answer. The reward gap should therefore be large enough to incentivize the server to behave optimally. Although our sumcheck-based protocols have only exponentially small reward gaps as in the previous protocols, we show that a constant reward gap can be achieved if two noncommunicating but entangled rational servers are allowed. We also discuss whether a single rational server is sufficient under the (widely believed) assumption that the learning-with-errors problem is hard for polynomial-time quantum computing. Apart from these results, we show, under a certain condition, the equivalence between rational and ordinary delegated quantum computing protocols. This equivalence then serves as a basis for a reward-gap amplification method.
It is an open problem whether a classical client can delegate quantum computing to an efficient remote quantum server in such a way that the correctness of quantum computing is somehow guaranteed. Several protocols for verifiable delegated quantum computing have been proposed, but the client is not completely free from any quantum technology: the client has to generate or measure single-qubit states. In this paper, we show that the client can be completely classical if the server is rational (i.e., economically motivated), following the ``rational proofs" framework of Azar and Micali. More precisely, we consider the following protocol. The server first sends the client a message allegedly equal to the solution of the problem that the client wants to solve. The client then gives the server a monetary reward whose amount is calculated in classical probabilistic polynomial-time by using the server's message as an input. The reward function is constructed in such a way that the expectation value of the reward (the expectation over the client's probabilistic computing) is maximum when the server's message is the correct solution to the problem. The rational server who wants to maximize his/her profit therefore has to send the correct solution to the client.
The rapid evolution of quantum technologies is likely to cause major shifts in the mainstream computing landscape. In order to fully reach their potential in a wide base accessible to any user, remote access of quantum computers and manipulation of data with strong privacy and integrity guarantees are essential. Consider a setting where a client having a fully classical computer wants to determine the result of some quantum computation, but lacks the necessary resources to perform the computation herself. She has access to a more powerful server which has quantum resources and can solve the problem and send the outcome back to the client. However, the client does not trust the powerful server, so she needs to find a way to hide her data. Therefore, the main question that arises is how can we guarantee the client’s privacy of the input and even the computation itself against the server possessing quantum computational capabilities. In the present thesis, we study this problem, denoted here as classical secure delegation of quantum computations (CSDQC) between a fully classical honest client and a quantum untrusted server. We focus on different models of security, analyzing the limitations and potential of each of the settings. Concretely, we first study the CSDQC problem under information-theoretic security. We analyse two categories of quantum computations, decision and sampling problems and in both cases we provide evidence indicating the impossibility of achieving information-theoretic security. Subsequently, we consider relaxing the security framework and specifically, we will analyze this task in the computational security setting (against quantum polynomial-time adversaries). As a result, in the second part of the thesis we put forward the remote state preparation as a key component that would allow us to achieve classical secure delegation of universal quantum computations. We present two protocols realizing the remote state preparation primitive assuming only a classical channel between client and server. The first candidate is shown to be secure in the honest-but-curious model, while the second candidate is proven secure against the server in the malicious setting. The security of both constructions relies on the hardness of the learning with errors problem. Finally, given the important role the remote state preparation plays not only in CSDQC, but also in other quantum communication protocols, we analyze its composable security to determine the privacy loss as a result of using remote state preparation as a sub-module in different protocols.
Blind quantum computing enables a client, who can only generate or measure single-qubit states, to delegate quantum computing to a remote quantum server in such a way that the input, output, and program are hidden from the server. It is an open problem whether a completely classical client can delegate quantum computing blindly (in the information theoretic sense). In this paper, we show that if a completely classical client can blindly delegate sampling of subuniversal models, such as the DQC1 model and the IQP model, then the polynomial-time hierarchy collapses to the third level. Our delegation protocol is the one where the client first sends a polynomial-length bit string to the server and then the server returns a single bit to the client. Generalizing the no-go result to more general setups is an open problem.
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.
The importance of being able to verify quantum computation delegated to remote servers increases with recent development of quantum technologies. In some of the proposed protocols for this task, a client delegates her quantum computation to non-communicating servers. The fact that the servers do not communicate is not physically justified and it is essential for the proof of security of such protocols. For the best of our knowledge, we present in this work the first verifiable delegation scheme where a classical client delegates her quantum computation to two entangled servers that are allowed to communicate, but respecting the plausible assumption that information cannot be propagated faster than speed of light. We achieve this result by proposing the first one-round two-prover game for the Local Hamiltonian problem where provers only need polynomial time quantum computation and access to copies of the groundstate of the Hamiltonian.
Quantum computers can make use of quantum mechanics to achieve surprising speed-ups relative to classical computers, for important computational problems. Quantum computers are gradually coming into reality, but the current implementations are big, require advanced facilities and could only be used as a cloud service in the foreseeable future. If we want to run quantum computations on secret data, we require protocols for performing computations on a remote quantum server without leaking information to the server about the data being processed. In the quantum computation delegation problem, a client with limited quantum computing resources wishes to evaluate a secret quantum circuit C with the help of a more powerful remote server. The protocol is deemed secure if the server learns nothing about either the circuit or the input state even if the server acts maliciously. This problem, first raised in (Childs05), has become fundamental to the study of quantum cryptography, because of its practical importance, and because it provides a testbed for new techniques that can be later applied to related problems (for example, quantum computation verification [FK12]). Prior to our work, known protocols for this problem were either proven secure against all possible attackers, without any complexity-theoretic assumptions, but highly inefficient for the client; or efficient but proven secure only based on strong cryptographic assumptions. This second category of protocols is only secure if there exist public-key encryption schemes that are secure against quantum attacks and that have special additional properties. Very few candidates for such schemes are known, and their security remains poorly understood. We seek to understand how efficient quantum delegation schemes can be designed based on weaker or different complexity assumptions. We study how the availability of symmetric-key primitives, modeled by a random oracle, changes the complexity of quantum computation delegation. In contrast with public-key primitives, there are many candidates for symmetric-key schemes secure against quantum attacks. We aim for protocols that require as little quantum computing as possible for the client. Specifically, we ask that the client only needs to run a quantum circuit of size independent of the circuit being evaluated. Known unconditionally-secure protocols all require the client to evaluate quantum circuits of size at least linear in the original circuit size. In this thesis, we construct two new quantum computation delegation protocols. The first protocol is for the delegation of a large special circuit family, which we call "C+P circuits". This scheme is non-interactive, and can be used to delegate a very important quantum algorithm---Shor's algorithm (Shor,97) for integer factorization and discrete logarithms. Our second protocol requires interaction---one quantum message from the client to the server, and many rounds of classical computation---but supports arbitrary quantum computation (instead of a specific circuit family), and is thus much more general than the first protocol in both theory and practice. Both protocols are proved secure in the quantum random oracle model. The protocols can be instantiated in practice with a symmetric-key cipher such as AES.