论文标题
量子后的关联记忆
A Post-Quantum Associative Memory
论文作者
论文摘要
关联记忆是存储信息的设备，可以完全检索到它的部分披露。我们检查了一个相关记忆的玩具模型及其在一般概率理论（GPT）框架内受到的最终局限性，该框架代表了满足某些基本操作公理的最通用的物理理论类别。我们问自己，GPT的尺寸应该是多大的，以便它可以容纳$ 2^m $的状态，并具有其财产的任何$ n $都是完全可区分的。调用$ d（n，m）$最小的维度。援引Danzer和Grünbaum的旧结果，我们证明$ d（2，m）= m+1 $，将与$ O（2^m）$进行比较，当时GPT必须是经典的或量子。这产生了一个任务的示例，其中GPT的表现呈指数级优于经典和量子理论。更普遍地，我们解决了固定$ n $和渐近较大的$ m $的情况，证明了$ d（n，m）\ leq m^{1+o_n（1）} $（如$ n \ geq 2 $，$ m \ to \ infty $）对每一个$ n \ geq 2 $又产生了一项超出类别的提高分类和量级的量子。最后，我们开发了一种数字方法，用于在给定的GPT中找到最大的$ n $ wise相互区分集的总体问题，这可以看作是$ n $ regrigard HyperGraphs上最大集团问题的实例。
Associative memories are devices storing information that can be fully retrieved given partial disclosure of it. We examine a toy model of associative memory and the ultimate limitations it is subjected to within the framework of general probabilistic theories (GPTs), which represent the most general class of physical theories satisfying some basic operational axioms. We ask ourselves how large the dimension of a GPT should be so that it can accommodate $2^m$ states with the property that any $N$ of them are perfectly distinguishable. Call $d(N,m)$ the minimal such dimension. Invoking an old result by Danzer and Grünbaum, we prove that $d(2,m)=m+1$, to be compared with $O(2^m)$ when the GPT is required to be either classical or quantum. This yields an example of a task where GPTs outperform both classical and quantum theory exponentially. More generally, we resolve the case of fixed $N$ and asymptotically large $m$, proving that $d(N,m) \leq m^{1+o_N(1)}$ (as $m\to\infty$) for every $N\geq 2$, which yields again an exponential improvement over classical and quantum theories. Finally, we develop a numerical approach to the general problem of finding the largest $N$-wise mutually distinguishable set for a given GPT, which can be seen as an instance of the maximum clique problem on $N$-regular hypergraphs.
