Institute of Information Science, Academia Sinica

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 designing protocols for proof of quantumness. These protocols enable a classical client to check whether a remote server can complete some classical intractable problem and thus can be used to distinguish quantum from classical computers.
In this talk, we want to go one step further by showing a protocol that can distinguish machines with different quantum depths. We call such protocols Classical Verification of Quantum Depth (CVQD). Roughly speaking, if the server has quantum circuit depth at most d, the classical client will reject; otherwise, the classical client will accept. Note that a malicious server, in general, can use classical computers to cheat. Thus, the 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) under weaker assumptions.