证明了伪随机酉矩阵存在，为量子密码学提供理论基础
How to Construct Random Unitaries
- 基于量子安全单向函数构造伪随机酉矩阵
- 可高效模拟对哈尓随机酉的查询，误差小于反指数级
- 适用于量子密码、复杂性理论研究者
伪随机酉矩阵（PRUs）——即在计算上无法与哈尓随机酉区分的高效量子电路——的存在性是一个核心开放问题，对量子密码学、复杂性理论和基础物理具有重要意义。本文在假设存在任何量子安全单向函数的前提下，证明了PRUs的存在性。该结果同时涵盖两种情形：(1) 标准定义下的PRUs，对任意能查询酉矩阵 $U$ 的高效敌手保持安全；(2) 更强定义下的PRUs，即使敌手能同时查询 $U$ 与逆矩阵 $U^ op$ 也保持安全。过程中我们还证明，任何对哈尓随机酉进行查询的算法，均可在量子计算机上被高效模拟，其迹距离误差不超过反指数级。
原文摘要 · Abstract (English)
The existence of pseudorandom unitaries (PRUs) -- efficient quantum circuits that are computationally indistinguishable from Haar-random unitaries -- has been a central open question, with significant implications for cryptography, complexity theory, and fundamental physics. In this work, we close this question by proving that PRUs exist, assuming that any quantum-secure one-way function exists. We establish this result for both (1) the standard notion of PRUs, which are secure against any efficient adversary that makes queries to the unitary $U$, and (2) a stronger notion of PRUs, which are secure even against adversaries that can query both the unitary $U$ and its inverse $U^\dagger$. In the process, we prove that any algorithm that makes queries to a Haar-random unitary can be efficiently simulated on a quantum computer, up to inverse-exponential trace distance.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。