arXiv:2410.23969quant-phcs.CC2024-10被引 4

受限学习者通过交互可否提升效率?答案是:经典交互无效,量子交互有效。

Interactive proofs for verifying (quantum) learning and testing

  • 用交互式证明框架分析资源受限下的学习与测试问题
  • 经典交互无法突破内存限制,但量子通信可实现显著优势
  • 适用于量子学习、测试等场景,适合研究可信计算与量子协议的学者

我们研究在资源受限(如有限内存或弱数据访问)条件下进行数据测试与学习的问题。核心问题是:资源受限的学习者或测试者能否通过与一个无约束但不可信的外部方进行交互,比独立操作更高效地解决学习或测试任务?本文从抽象和具体两个层面回答此问题:对于多数场景,证明资源受限学习者无法通过经典交互获得优势;特别地,在量子内存为关键资源的情况下,内存受限的量子算法也无法通过经典通信克服限制。相反,当允许量子通信时,我们构造了多种交互式证明协议,使内存受限的量子验证者可通过委托给不可信提供方而获得显著优势。这些结果揭示了将学习与测试任务外包给资源丰富但不可信第三方的潜力与局限。

原文摘要 · Abstract (English)

We consider the problem of testing and learning from data in the presence of resource constraints, such as limited memory or weak data access, which place limitations on the efficiency and feasibility of testing or learning. In particular, we ask the following question: Could a resource-constrained learner/tester use interaction with a resource-unconstrained but untrusted party to solve a learning or testing problem more efficiently than they could without such an interaction? In this work, we answer this question both abstractly and for concrete problems, in two complementary ways: For a wide variety of scenarios, we prove that a resource-constrained learner cannot gain any advantage through classical interaction with an untrusted prover. As a special case, we show that for the vast majority of testing and learning problems in which quantum memory is a meaningful resource, a memory-constrained quantum algorithm cannot overcome its limitations via classical communication with a memory-unconstrained quantum prover. In contrast, when quantum communication is allowed, we construct a variety of interactive proof protocols, for specific learning and testing problems, which allow memory-constrained quantum verifiers to gain significant advantages through delegation to untrusted provers. These results highlight both the limitations and potential of delegating learning and testing problems to resource-rich but untrusted third parties.

交互证明量子学习资源约束可信计算

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。