Security and Efficiency of Delegated Quantum Computing

Quantum information promises to revolutionize our world, from the way in which we communicate to the way in which we compute, deriving its power directly from the laws that govern the behavior of nature on extremely small scales - quantum mechanics. In the near future, the hardware of possibly useful quantum computers is expected to remain very expensive and thus out of reach for most interested end users. In such a world, it is an important problem to provide security guarantees for customers who wish to remotely instruct quantum servers, by keeping their data private (blindness) and checking the correctness of the results (verification). This functionality of secure delegated quantum computing received a lot of attention during recent years, but still admits many open questions.

In this thesis, we explore the (im)possibility of securing delegated quantum computations in different settings: what is the hardware that the client needs trusted access to, what is the minimum hardware required by the server, and how must the parties communicate? This work is driven by the motivation to break down the barriers that keep us from securing and verifying quantum computations in practice, by identifying and removing unnecessary overheads.

We set out by questioning the necessity of quantum communication between the client and the server, and find that, while in specific situations classical communication is entirely sufficient, most generally the security of delegation protocols relies irreplaceably on the very quantumness of the information exchanged between the parties. This proves that quantum communication is indeed an essential asset in our cryptographic toolbox.

We then shift our focus to the server that was suffering from impractical overheads in previous attempts at quantum verification. We show that for a large class of interesting quantum computations, there is no fundamental need to reserve extra hardware for any cryptographic techniques. Indeed, we give concrete constructions of secure protocols that achieve blindness and verification on hardware of the same size that would be required to perform the original, unsecured computation, and provide a systematic way of optimizing their efficiency in customized settings.

Our journey then takes us to the problem of quantum secure multi-party computation, a generalization of the previous functionality to more than two participating, mutually distrusting parties. We explore how the improvements that we obtained in the two-party setting can be transferred to the multi-party case, and finish with the presentation of two actual experiments that demonstrate the practical impact and real-world feasibility of the results obtained during the course of this thesis.