A post-quantum associative memory

DOI10.1088/1751-8121/ACFEB7MaRDI QIDQ6063372zbMATH OpenOpenAlexFDO

Authors Ludovico Lami, Gerardo Adesso

Publication date 7 November 2023

Published in Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2201.12305

zbMATH Keywords

associative memorygeneralised probabilistic theoryquantum theory

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Hypergraphs (05C65) Operations and polynomials in algebraic structures, primal algebras (08A40) Formal methods and deformations in algebraic geometry (14D15) Probability theory on linear topological spaces (60B11) Kinematics of a particle (70B05) General and philosophical questions in quantum theory (81P05) Quantum state tomography, quantum state discrimination (81P18)

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"unbaum, 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 $moinfty$) for every $Ngeq2$, 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.

Recommendations

• Quantum associative pattern retrieval
• The capacity of the Hopfield associative memory
• Quantum associative memory with distributed queries
• QUANTUM ASSOCIATIVE MEMORY
• Quantum systems can realize content-addressable associative memory.

Cites work

• hClique: An exact algorithm for maximum clique problem in uniform hypergraphs
• A note on the measurability of convex sets
• A note on the problem of reporting maximal cliques
• A review on algorithms for maximum clique problems
• An exact algorithm for the maximum clique problem
• An exact bit-parallel algorithm for the maximum clique problem
• An operational approach to quantum probability
• Coexistence on reflecting hyperplane in generalized probability theories
• Efficient algorithms for clique problems
• Entangleability of cones
• Entanglement and the three-dimensionality of the Bloch ball
• Entropy in general physical theories
• Foundations of quantum mechanics and ordered linear spaces. Advanced Study Institute, Marburg 1973
• scientific article; zbMATH DE number 3931797 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 3320765 (Why is no real title available?)
• Implausible consequences of superstrong nonlocality
• Limits on nonlocal correlations from the structure of the local state space
• Neural networks and physical systems with emergent collective computational abilities
• On the equivalence of separability and extendability of quantum states
• Perfect discrimination of non-orthogonal separable pure states on bipartite system in general probabilistic theory
• Proofs from THE BOOK
• Quantum entanglement
• Quantum nonlocality and beyond: limits from nonlocal computation
• Reducibility among combinatorial problems
• Relaxed uncertainty relations and information processing
• Separability Criterion for Density Matrices
• The probabilistic method
• Ultimate data hiding in quantum mechanics and beyond
• Universal gaps for XOR games from estimates on tensor norm ratios
• Über zwei Probleme bezüglich konvexer Körper von P. Erdős und von V.L. Klee

Cited in

(3)

• Concise quantum associative memories with nonlinear search algorithm
• QUANTUM WAVE-PACKETS IN FUZZY AUTOMATA AND NEURAL ASSOCIATIVE MEMORIES
• Higher rank antipodality

This page was built for publication: A post-quantum associative memory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6063372)