Online Seminar: Dr Kai-Min Chung, IIS, A.Sinica, Taiwan
Cryptographic protocols for classical clients to verifiably delegate quantum computation to untrusted quantum servers - the desiderata and their feasibility.
Image: Elias Sch. / Pixabay, original edited
How well can a classical client delegate quantum computation?
SPEAKER: Dr Kai-Min Chung
AFFILIATION: Institute of Information Science, Academia Sinica, Taiwan
HOSTED BY: Prof Zhengfeng Ji, UTS Centre for Quantum Software and Information
ABSTRACT:
In a recent breakthrough, Mahadev (FOCS 2018) constructed the first classical verification of quantum computation (CVQC) protocol that allows a classical client to delegate the computation of a BQP language (i.e., a decision problem) to an efficient quantum server.
In this talk, we present several generalizations of Mahadev’s work. In particular, we initiate the study of CVQC protocols for quantum *sampling* problems and construct the first such protocol that allows a classical client to verifiably obtain a sample drawn from a quantum computation from a quantum server. We also construct the first protocol with efficient verification, i.e., the client’s runtime can be sublinear in the quantum time complexity of the delegated computation. Finally, we present a generic compiler that compiles any CVQC protocol to achieve blindness, i.e., the server learns nothing about the client’s input, which leads to the first constant-round blind CVQC protocol.
Based on joint works with Nai-Hui Chia, Takashi Yamakawa, Yi Lee, Han-Husan Lin, and Xiaodi Wu
