A Post-Quantum Associative Memory

Abstract

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)\le m^{1+o_N(1)}$ (as $m\to \infty$) for every $N\ge 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.

arXiv comment27 pages, 5 figures. v2: Extended with new analytical and numerical results for N>2, showing that an exponential advantage persists for large post-quantum memories. v3 is close to the published version

References in corpus (33)

• Quantum entanglement
• Separability Criterion for Density Matrices
• Probabilistic theories with purification
• Thermodynamics and the Measure of Entanglement
• A complete family of separability criteria
• The entanglement cost under operations preserving the positivity of partial transpose
• No quantum advantage for nonlocal computation
• Entropy in general physical theories
• Limits on non-local correlations from the structure of the local state space
• Generalized Probabilistic Theories Without the No-Restriction Hypothesis
• The Characterization of Noncontextuality in the Framework of Generalized Probabilistic Theories
• Cost of quantum entanglement simplified
• Ultimate data hiding in quantum mechanics and beyond
• High-Dimensional Entanglement in States with Positive Partial Transposition
• Entanglement and superposition are equivalent concepts in any physical theory
• If no information gain implies no disturbance, then any discrete physical theory is classical
• Quantum phase estimation using a multi-headed cat state
• Extendibility limits the performance of quantum processors
• Entangleability of cones
• Irreversibility of Asymptotic Entanglement Manipulation Under Quantum Operations Completely Preserving Positivity of Partial Transpose
• Contextuality of general probabilistic theories
• Classical theories with entanglement
• Towards The Ultimate Brain: Exploring Scientific Discovery with ChatGPT AI
• Exploring the geometry of qutrit state space using symmetric informationally complete probabilities
• Quantum computation is the unique reversible circuit model for which bits are balls
• Information and communication in polygon theories
• Resource theory of unextendibility and non-asymptotic quantum capacity
• Universal gaps for XOR games from estimates on tensor norm ratios
• Extendibility of bosonic Gaussian states
• No-free-information principle in general probabilistic theories
• Perfect Discrimination of Non-Orthogonal Separable Pure States on Bipartite System in General Probabilistic Theory
• Perfect Discrimination in Approximate Quantum Theory of General Probabilistic Theories
• On the equivalence of separability and extendability of quantum states