论文标题
量子深度的经典验证
Classical verification of quantum depth
论文作者
论文摘要
我们提出了两个用于量子深度的经典验证的方案。我们的协议允许纯粹的经典验证器即使在存在经典计算的情况下，也可以区分具有不同量子电路深度的设备。我们表明，即使称者将其他多项式经典计算应用于作弊，验证者也会拒绝具有量子电路深度的设备。另一方面，验证者接受具有量子电路深度d'd'd'> d的设备。在我们的第一个协议中，我们引入了一台其他不信任的量子机，该机器与目标计算机共享纠缠。采用强大的自我测试，我们的第一个协议通过信息理论安全性和几乎最佳的分离来证明目标机器的深度。该协议依赖于Chia，Chung和Lai [STOC 2020]的量子深度的Oracle分离问题，以及从Oracle分离问题到两个玩家非本地游戏的转换。我们的第二个协议根据错误的学习量子硬度证明了单个设备的量子深度。该协议依赖于嘈杂的无爪功能家族和指针追逐迫使供者保持量子相干性的想法，直到完成所有上述消息交换为止。据我们所知，我们提供了第一个构造，用于区分不偏变模型中具有不同电路深度的混合量子量计算机。
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. In our first protocol, we introduce an additional untrusted quantum machine which shares entanglements with the target machine. Applying a robust self-test, our first protocol certifies the depth of the target machine with information theoretic security and nearly optimal separation. The protocol relies on the oracle separation problem for quantum depth by Chia, Chung and Lai [STOC 2020] and a transformation from an oracle separation problem to a two-player non-local game. Our second protocol certifies the quantum depth of a single device based on quantum hardness of learning with errors. The protocol relies on the noisy trapdoor claw-free function family and the idea of pointer chasing to force the prover to keep quantum coherence until all preceding message exchanges are completed. To our knowledge, we give the first constructions for distinguishing hybrid quantum-classical computers with different circuit depths in unrelativized models.
