Nai-Hui Chia

Title: Classical Verification of Quantum Depth

Abstract: Verifying if a remote server has sufficient quantum resources to demonstrate quantum advantage is a fascinating question in complexity theory as well as a practical challenge. One approach is asking the server to solve some classically intractable problem, such as factoring. Another approach is the proof of quantumness protocols. These protocols enable a classical client to check whether a remote server can complete some classically intractable problem and thus can be used to distinguish quantum from classical computers. However, these two approaches mainly focus on distinguishing quantum computers from classical ones. They do not directly translate into ones that separate quantum computers with different quantum resources. In this talk, we want to go one step further by showing protocols that can distinguish machines with different quantum depths. We call such protocols Classical Verification of Quantum Depth (CVQD). Roughly speaking, if a server has quantum circuit depth at most d, the classical client will reject it; otherwise, the classical client will accept it. Note that a malicious server, in general, can use classical computers to cheat. Thus, CVQD protocols shall be able to distinguish hybrid quantum-classical computers with different quantum depths. We will see two CVQD protocols: the first protocol can separate hybrid quantum-classical computers with quantum depth d and d+c (for c some fixed constant) assuming quantum LWE, and the second protocol is a two-prover protocol that achieves sharper separation (d versus d+3).

Bio: Nai-Hui Chia is an Assistant Professor in the Department of Computer Science at Rice University. Before that, he was an Assistant Professor in the Luddy School of Informatics, Computing, and Engineering at Indiana University Bloomington from 2021 to 2022, a Hartree Postdoctoral Fellow in the Joint Center for Quantum Information and Computer Science (QuICS) at the University of Maryland from 2020 to 2021, supervised by Dr. Andrew Childs, and a Postdoctoral Fellow at UT Austin from 2018 to 2020, working under the supervision of Dr. Scott Aaronson. he received my Ph.D. in Computer Science and Engineering at Penn State University, where he was fortunate to have Dr. Sean Hallgren as his advisor.

Contact the speaker: