Classical verification of quantum depth

Understand

We present two protocols for classical verification of quantum depth.

• Our protocols allow a purely classical verifier to distinguish devices with different quantum circuit depths even in the presence of classical computation.
• We show that a device with quantum circuit depth at most d will be rejected by the verifier even if the prover applies additional polynomial-time classical computation to cheat.
• On the other hand, the verifier accepts a device which has quantum circuit depth d' for some d'>d.