伪随机态由 Ji、Liu 和 Song (Crypto'18) 引入,是可高效计算的量子态,在计算上与 Haar 随机态无法区分。单向函数意味着伪随机态的存在,但 Kretschmer (TQC'20) 最近构建了一个 oracle,相对于该 oracle 不存在单向函数,但伪随机态仍然存在。受此启发,我们研究了基于伪随机态执行有趣的加密任务的有趣可能性。假设存在将 𝜆 位种子映射到 𝜔 (log 𝜆 ) 量子比特状态的伪随机态生成器,我们构建了 (a) 统计上具有约束力且计算上具有隐藏性的承诺和 (b) 伪一次性加密方案。(a) 的结果是,伪随机态足以在多数不诚实的情况下构建恶意安全的多方计算协议。我们的构造是通过一种称为伪随机函数类状态 (PRFS) 的新概念得出的,这是伪随机状态的泛化,与经典的伪随机函数概念相似。除了上述两种应用之外,我们相信我们的概念可以有效地取代许多其他加密应用中的伪随机函数。
随机量子电路和随机电路采样 (RCS) 最近引起了量子信息界所有子领域的极大关注,尤其是在谷歌于 2019 年宣布量子霸权之后。虽然 RCS 科学吸收了从纯数学到电子工程等不同学科的思想,但本论文从理论计算机科学的角度探讨了这一主题。我们首先对随机量子电路的 t 设计和反集中特性进行严格处理,以便各种中间引理将在后续讨论中找到进一步的应用。具体而言,我们证明了形式为 EV ⟨ 0 n | V σ p V † | 0 n ⟩ 2 的表达式的新上限,其中 1D 随机量子电路 V 和 n 量子比特泡利算子 σ p 。接下来,我们将从高层次讨论 RCS 至上猜想,该猜想构成了复杂性理论的主要基础,支持了以下观点:深度随机量子电路可能与任意量子电路一样难以进行经典模拟。最后,我们研究了量子和经典欺骗算法在线性交叉熵基准 (XEB) 上的性能,这是 Google 为验证 RCS 实验而提出的统计测试。我们考虑了 Barak、Chou 和 Gao 最近提出的经典算法的扩展,并尝试证明扩展算法可以获得更高的 XEB 分数 [BCG20]。虽然我们无法证明具有 Haar 随机 2 量子比特门的随机量子电路的关键猜想,但我们确实在其他相关设置中建立了结果,包括 Haar 随机幺正、随机 Cliūford 电路和随机费米子高斯幺正。
量子计算机可用于模拟动力学并学习量子系统的光谱,例如由某些哈密顿h h描述的构成复合分子或伴侣的相互作用粒子。相位估计[1]在统一的u = e iht上有效地解决了计算基态启用的常见光谱问题,只要我们能够有效地准备一个具有非平凡(非指数性的小)重叠的试验状态。标准相位估计的每次运行都会返回单个特征值,其精度和成功概率取决于使用u的次数。最近,已经提出了相位估计的统计方法[2-4],其中每次运行仅使用少数几个Ancillae和较短的电路。因此,统计阶段估计可能更适合于固定和深度限制的早期耐断层量子计算机。但是,在这些方法中,单次运行给出了某些运行时j的估计器的样本,仅此运行时J,仅此操作不足以推断光谱属性。需要具有不同J值的多个运行,并且统计分析给出了表格信息,并有信心随着获得的数据量而增加。这些运行可以在多个量子计算机上大规模平行。相关地,Lin&Tong [4]的方法不仅是其分析中的实力,而且还会从随机的集合中产生Runtimes J,因此也会产生电路。基于使用Trotter公式实现U的简单方案具有O(L)门复杂性[5-9]。阶段估计的成本(统计或标准)通常取决于哈密顿的稀疏性L,在适当的基础上分解时,诸如Pauli的基础时,哈密顿量中的术语数量。这对于化学和伴侣科学中的电子结构问题可能会过时,在n-轨道问题上,我们通常具有L = O(n 4)[10]。使用经远比轨道[11,12]来更好地求解电子电子相互作用时,这会增加到l = o(n 6)。有趣的是,下线性非cli效率o(√
能量幺正动力学驱使量子多体系统进入高度纠缠态,其特征是子系统纠缠熵的体积定律缩放。当这种动力学被快速局部测量所拦截时,各个量子轨迹预计会坍缩为低纠缠态,其特征是子系统纠缠熵的面积定律缩放。最近发现,至少在一类模型中,这两个阶段由一个有限测量速率 1 – 3 的尺度不变的“临界点”分隔。近期,人们对这种转变及其概括的几个方面进行了研究 4 – 19 。在无限快速局部测量的极限下,系统的状态关键取决于测量基的选择。假设只测量交换的单量子比特算子,波函数就会坍缩为无纠缠的平凡积态。然而,如果选择测量一组稳定拓扑或对称保护拓扑 (SPT) 波函数的稳定算子,那么得到的状态——尽管也具有纠缠面积律标度——在拓扑上将不同于乘积状态 20 , 21 。在本文中,我们考虑这两类测量之间的竞争,以及它们与幺正动力学的竞争。这就引发了一个问题,即拓扑相的概念是否在包含幺正动力学和局部测量的随机量子电路中得到很好的定义。为了回答这个问题,我们考虑一个 (1 + 1)D 量子电路模型,它包含三个元素:(1) 稳定 Z 2 ´ Z 2 的稳定算子的测量
为了获得更好的近似值,减少项 log ( M / q ) 被更新为每个字符串的项之和(好像 q = 1 做了 q 次)。值 q 是允许对手 ( A ) 满足 FP 条件的最小值。如果预采样预算 β = b · N 足够大(> √
为什么这一点很重要?为了证明量子霸权,我们最终要证明 Pr(S) 和 Pr(Scl) 之间存在可测量的差异。这是基于这样一个事实:量子电路的状态空间大小是 n 的指数,因此即使对于适中的 n = 50 个量子比特(大约是 Google 实验中使用的数字),状态 |ψ⟩ 也由 250≈1015 个复数描述。因此,在经典计算机上完美模拟量子电路是一个棘手的问题,因此我们假设经典算法具有关于 n 的多项式资源,而不是关于 n 的指数资源。换句话说,从经典计算机获得的样本 Scl 是从实际量子电路的近似值中提取的,当我们增加量子比特的数量时,该近似值不会适当扩展。那么,直观地看,我们可能会认为从经典算法获得的位串与从实际量子电路获得的位串在某种程度上“不同”,因为我们只能粗略地近似电路以获得这些位串。量化这种差异的一个合理方法如下:我们首先问,“如果我对电路的输出状态 | ψ ⟩ 有一个完美的表示,那么我获得样本 S cl 的可能性有多大?”这个概率可以通过计算 | x cl ⟩ 和 | ψ ⟩ 的内积来找到,其中 | ψ ⟩ 表示“完美”的输出状态(即,从完美、无错误的量子计算机的实验实现中获得的输出状态)。然后,我们可以将 Pr(S cl) 与获得量子计算机 Pr(S) 生成的集合 S 的概率进行比较。如果我们为经典算法提供更多资源和/或增加量子电路中的错误率(因此我们的输出状态 | ψ ⟩ 不是“完美”),我们应该看到这些概率相互收敛,因此 Pr( S ) ≈ Pr( S cl )。
与图相关的自然过渡矩阵的混合(或准随机)属性可以通过其与完全图的距离来量化。不同的混合属性对应于测量此距离的不同范数。对于密集图,Chung、Graham 和 Wilson 在 1989 年的开创性工作中证明了两个这样的属性(称为谱扩展和均匀性)是等价的。最近,Conlon 和 Zhao 使用著名的 Grothendieck 不等式将这种等价性扩展到稀疏顶点传递图的情况。在这里,我们将这些结果推广到非交换或“量子”情况,其中过渡矩阵成为量子信道。特别是,我们表明,对于不可约协变量子信道,扩展等同于图的均匀性的自然类似物,推广了 Conlon 和 Zhao 的结果。此外,我们表明,在这些结果中,非交换和交换的格罗滕迪克不等式产生了最佳常数。
我们用数值方法研究了 1 + 1 维 Haar 随机量子电路的测量驱动量子相变。通过分析三部分互信息,我们能够精确估计临界测量率 pc = 0 . 17(1)。我们提取了与渗透值以及稳定器电路值一致的相关体积临界指数的估计值,但与 Haar 随机情况的先前估计值不同。我们对表面序参数指数的估计似乎与稳定器电路或渗透的估计值不同,但我们不能明确排除三种情况下所有指数都匹配的情况。此外,在 Haar 情况下,纠缠熵 S n 的前因子强烈依赖于 Rényi 指数 n ;对于稳定器电路和渗透,这种依赖性不存在。稳定器电路的结果用于指导我们的研究并识别具有弱有限尺寸效应的度量。我们讨论了我们的数值估计如何限制转变理论。
我们研究了 (Haar) 随机幺正量子电路中投影测量引起的纠缠跃迁的临界行为。使用复制方法,我们将此类电路中纠缠熵的计算映射到二维统计力学模型上。在这种语言中,面积到体积定律纠缠跃迁可以解释为统计力学模型中的有序跃迁。我们使用共形不变性推导出跃迁附近的纠缠熵和互信息的一般缩放特性。我们详细分析了统计力学模型映射到渗流的无限现场希尔伯特空间维度的极限。具体来说,我们使用描述二维渗流临界理论的共形场论的相对较新的结果,计算了子系统大小对数在 n ≥ 1 的 n 次 R'enyi 熵中的普适系数的精确值,并讨论了如何从这个极限访问有限现场希尔伯特空间维度的通用转换,这与二维渗流属于不同的普适性类。我们还评论了与先前在参考文献 1 中研究过的随机张量网络中纠缠转换的关系。