量子科技中心_量科网

量子情境性被广泛认为是量子技术背后一种必不可少的非经典资源，然而阐明其转化为无条件计算优势的具体机制仍然是一个持续的挑战。本文证明了基于图论方法的情境性能够为量子有限自动机带来指数级且抗噪声的记忆优势。我们在一个排他性图 \(G\) 上定义了一个承诺问题，对于该问题，任何经典确定型自动机都充当一个需要至少 \(N = \chi(G)\) 个状态的非情境隐变量模型，其中 \(\chi(G)\) 是该图的色数。相比之下，通过利用一种被称为“表征情境性”的结构现象，量子有限自动机仅使用维度至多为 \(d = \xi(G) + 1\) 的记忆即可解决该任务，其中 \(\xi(G)\) 是图的正交秩。对于布尔正交图，这种分离呈指数级增长（\(d = \mathcal{O}(n)\) 对比 \(N = 2^{\Omega(n)}\)）。关键在于，这种记忆优势在面对去极化噪声和相干噪声时均能保持 \(\mathcal{O}(1)\) 的阈值。