量子科技中心_量科网

连贯量子展开（coherent quantum rollout）解决序贯决策问题需要一个酉模拟器：随机性必须存在于显式量子寄存器中，且基态选择器必须可逆地映射到动作上。对于分支依赖的有效动作，该映射通过以下方式实现：对纠缠的 N 位有效性掩码进行相干秩选择（coherent rank-select）：返回第 r 个有效比特的位置，若 r 超出范围则返回哨兵值。 该工作首次给出了该原语的 reversible-circuit 复杂度分析。对于选择器宽度w=⌈log2(N+1)⌉ ，秩选择算法支持一种O(Nw)门复杂度、低辅助比特、有界跨度的扫描方法（经证明在其模型下门复杂度最优），以及在支持长程门时的一种O(Nlogw)门复杂度、低辅助比特的分块构造；在所有有界扇入布局下，无条件的门复杂度下界为Ω(N)。将秩选择与可逆转移和谓词评估电路组合，可得到一个显式多项式规模的连贯展开预言机，适用于满足这些原语假设的有限时域规划问题。 所得预言机满足 Wang 等人 [1] 的最优臂流水线（best-arm pipeline）的访问模型，相较于经典Ω(k/ε²)臂拉取下界，仅需Õ(k/ε)次相干预言机调用。该工作给出一个有界影响提升定理（bounded-influence lifting theorem），将该下界构造从基础配置扩展到指数级配置族。该工作将构造实例化于 SIR 传染病干预场景，并通过随机放置博弈（stochastic placement game）进行合理性检查，同时在 Lean 4 中机器验证了主要结果。代码与证明：https://github.com/BinRoot/b01t/tree/main/demos/rollout