XiaoMi-AI文件搜索系统
World File Search Systemstoquatic
![arXiv:2004.08681v3 [quant-ph] 2020 年 10 月 21 日](/simg/g:\will\search\icon\source\5\54629a20e2a980c7278538293c6c1948ab71ba1c.webp)
arXiv:2004.08681v3 [quant-ph] 2020 年 10 月 21 日
所有已知例子都表明经典模拟算法与量子绝热量子计算（StoqAQC）之间存在指数分离，这些例子都利用了将绝热动力学限制在有效对称子空间的对称性。对称性产生较大的有效特征值间隙，从而使得绝热计算高效。我们提出了一种经典算法，从任何 k 局部量子汉密尔顿量 H 的有效子空间中进行亚指数采样，而无需先验了解其对称性（或近似对称性）。我们的算法将任何 k 局部汉密尔顿量映射到图 G = ( V, E )，且 | V | = O (poly( n ))，其中 n 是量子比特的数量。鉴于 Babai [ 1 ] 的著名结果，我们利用图同构来研究 G 的自同构，并得出 | V | 中的算法准多项式。用于从 H 的有效子空间本征态中生成样本。我们的结果排除了 StoqAQC 与经典计算之间的指数分离，这种分离是由 k -局部汉密尔顿函数中的隐藏对称性引起的。我们对 H 的图形表示不限于 stoquatic 汉密尔顿函数，并且可以排除非 stoquatic 情况下的相应障碍，或者有助于研究 k -局部汉密尔顿函数的其他属性。
无符号问题的绝热量子计算的（亚）指数优势
只要绝热演化的运行时间是绝热路径上任何哈密顿量的最小谱隙的倒数的多项式大，量子绝热定理就能保证计算与所需基态高度重叠 [3]。该模型得到了深入研究，不仅因为它本身很有趣，还因为它是量子退火的零温度极限。一般来说，已知绝热量子计算等同于基于标准电路的量子计算 [1]。然而，一个非常有趣的问题是，当所有哈密顿量都是“stoquatic”的，即限制为没有符号问题时，绝热量子计算的威力有多大。这意味着在某个基础上，𝐻的所有非对角线项都非正。没有符号问题的绝热量子计算包括最自然的情况，其中最终的哈密顿量是对角的，表示要优化的目标函数，初始哈密顿量由作用于每个量子位的泡利𝑋算子组成，基态是所有𝑛位串的均匀叠加。这个问题也是通过理解 D-Wave 公司实现的量子退火器的计算极限而产生的，其中所有的哈密顿量都是 stoquatic 的。Bravyi 和 Terhal [ 8 ] 证明，对于没有符号问题的无挫折哈密顿量，计算基态是经典可处理的，从而提出了一个问题，即对于没有符号问题的一般哈密顿量来说这是否也是如此。事实上，一个更有力的猜想是，量子蒙特卡罗（一种广泛用于计算凝聚态物理学的启发式方法）已经提供了一种有效的经典模拟技术。后一种可能性被 Hastings 和 Freedman [20] 的结果排除，他们证明了在此类问题上量子蒙特卡罗收敛存在拓扑障碍。对于没有符号问题的一般哈密顿量，经典可处理性问题一直悬而未决，直到 Hastings [19] 的最新突破性进展解决了这个问题，他证明了经典算法和绝热量子计算之间的拟多项式 Oracle 分离，没有符号问题。随后，Gilyén 和 Vazirani [18] 扩展并简化了 Hastings 的结果。他们证明了存在形式为 2 𝑛 𝛿 的（亚）指数 Oracle 分离