Cryptographic protocols for classical clients to verifiably delegate quantum computation to untrusted quantum servers – the desiderata and their feasibility.
TITLE: 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
REFERENCES:
Classical Verification of Quantum Computations with Efficient Verifier: https://arxiv.org/abs/1912.00990
Kai-Min Chung Personal Webpage: https://www.iis.sinica.edu.tw/~kmchung/
UTS Centre for Quantum Software and Information: https://www.uts.edu.au/research-and-teaching/our-research/centre-quantum-software-and-information
Zhengfeng Ji: https://www.uts.edu.au/staff/zhengfeng.ji
