Simple constructions of linear-depth t-designs and pseudorandom unitaries

均匀随机酉矩阵，即从哈尔测度中绘制的酉矩阵具有许多有用的属性，但无法高效实现。这激发了长期以来对“看起来”足够哈尔随机的随机酉矩阵的研究，同时也要高效实现。出现了两种不同的去随机化概念：$t$-设计是信息理论上重现哈尔测度前$t$个矩的随机酉矩阵，而伪随机酉矩阵（PRUs）是计算上无法区分与哈尔随机的随机酉矩阵。 在这项工作中，我们采用统一的方法来构建$t$-设计和PRUs。为此，我们介绍并分析“$PFC$集合”，即随机计算基础置换$P$，随机二进制相位算子$F$和随机克利福德酉矩阵$C$的乘积。我们证明了该集合重现了哈尔测度的指数高矩。然后我们可以去随机化$PFC$集合，以展示以下内容： （1）线性深度$t$-设计。我们首次构建了一个在$t$的线性深度下具有（钻石误差）近似$t$-设计的结构。这可以通过将随机相位和置换算子替换为它们的$2t$-独立对应物来自$PFC$集合中得出。 （2）非自适应PRUs。我们首次构建了具有非自适应安全性的PRUs，即我们构建了与Haar随机无法区分的酉矩阵，对于在任意状态上并行查询酉矩阵的多项式时间区分器。这可以通过将随机相位和置换算子替换为它们的伪随机对应物来自$PFC$集合中得出。 （3）自适应伪随机等距变换。我们展示了，如果考虑从$n$到$n + \omega(\log n)$量子比特的等距变换（而不是酉矩阵），那么我们PRU构造的一个小修改就可以实现一般自适应安全性。

构建有效的随机酉矩阵

通过引入PFC集合并分别替换随机相位和置换运算，构建出可用于构建线性深度t-designs和非自适应PRUs的随机酉矩阵

1. 首次构建出线性深度t-designs和非自适应PRUs；2. 使用PFC集合可以构建出多项式时间可区分的PRUs；3. 对于n到n+log(n)量子比特的等距映射，可以使用类似的构造方法得到自适应伪随机等距映射；

最近的相关研究包括“Efficient Quantum Pseudo-Randomness with Nearly Optimal Dependence on the Error”和“Explicit Two-Source Extractors and Resilient Functions”.