中央研究院 資訊科學研究所

活動訊息

友善列印

列印可使用瀏覽器提供的(Ctrl+P)功能

On Classical Verification of Quantum Depth

:::

On Classical Verification of Quantum Depth

  • 講者賈乃輝 先生 (美國印第安那大學)
    邀請人:鐘楷閔
  • 時間2022-07-07 (Thu.) 10:15 – 12:30
  • 地點資訊所新館101演講廳
摘要
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.