标题： 如何无条件地验证一个小设备是否是量子的 显示英文标题

标题： How to Verify that a Small Device is Quantum, Unconditionally

摘要： 一个量子性证明（PoQ）允许一个经典验证者有效地测试量子机器是否执行了对于任何经典机器都难以完成的计算。 在这项工作中，我们提出了一种新的构建PoQ协议的方法，在假设证明者的内存有界的情况下，该方法的可靠性无条件成立，但对其运行时间没有其他限制。 在此模型下，我们提出了两种协议： 1. 一种简单的协议，诚实方所需的内存与对手的内存界限之间存在二次差距。此协议的可靠性依赖于Raz关于矩阵求逆的经典内存下界（Raz, FOCS 2016）。 2. 借助有界存储模型文献中的技术（Dodis等人，Eurocrypt 2023），实现了一个具有指数级差距的协议。 这两种协议也都可以高效地被验证。 尽管我们的第一个协议具有较差的渐进性能，但它概念上简单，并且仅依赖于模2算术运算，这可以通过一比特的Hadamard门和CNOT门以及一个单比特非Clifford门来实现。 显示英文摘要

摘要： A proof of quantumness (PoQ) allows a classical verifier to efficiently test if a quantum machine is performing a computation that is infeasible for any classical machine. In this work, we propose a new approach for constructing PoQ protocols where soundness holds unconditionally assuming a bound on the memory of the prover, but otherwise no restrictions on its runtime. In this model, we propose two protocols: 1. A simple protocol with a quadratic gap between the memory required by the honest parties and the memory bound of the adversary. The soundness of this protocol relies on Raz's (classical) memory lower bound for matrix inversion (Raz, FOCS 2016). 2. A protocol that achieves an exponential gap, building on techniques from the literature on the bounded storage model (Dodis et al., Eurocrypt 2023). Both protocols are also efficiently verifiable. Despite having worse asymptotics, our first protocol is conceptually simple and relies only on arithmetic modulo 2, which can be implemented with one-qubit Hadamard and CNOT gates, plus a single one-qubit non-Clifford gate.