How well can a classical client delegate quantum computation?

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

quantum computing and information

Audience: researchers in the topic

Comments: Hosted by Prof Zhengfeng Ji, UTS Centre for Quantum Software and Information.

---

Centre for Quantum Software and Information Seminar Series

Series comments: To request the zoom link, please send a message to: cqsiadmin@uts.edu.au using your business/organisation/institution email address. Watch previous seminars on YouTube: - QSI Seminar Series 2021 (https://youtube.com/playlist?list=PLux7B14QYkPbDDOpqKSWScHXHodiBwr48) - QSI Seminar Series 2020 (https://youtube.com/playlist?list=PLux7B14QYkPZREUXReOq01ewLl02QXBXa)

---