Ludovico Lami
A Post-Quantum Associative Memory
Lami, Ludovico; Goldwater, Daniel; Adesso, Gerardo
Authors
Daniel Goldwater
Professor GERARDO ADESSO gerardo.adesso@nottingham.ac.uk
PROFESSOR OF MATHEMATICAL PHYSICS
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) ≤ m 1+o N (1) (as m → ∞) for every N ≥ 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.
Citation
Lami, L., Goldwater, D., & Adesso, G. (2023). A Post-Quantum Associative Memory. Journal of Physics A: Mathematical and Theoretical, 56(45), Article 455304. https://doi.org/10.1088/1751-8121/acfeb7
Journal Article Type | Article |
---|---|
Acceptance Date | Sep 27, 2023 |
Online Publication Date | Oct 13, 2023 |
Publication Date | Nov 10, 2023 |
Deposit Date | Sep 29, 2023 |
Publicly Available Date | Oct 14, 2024 |
Journal | Journal of Physics A: Mathematical and Theoretical |
Print ISSN | 1751-8113 |
Publisher | IOP Publishing |
Peer Reviewed | Peer Reviewed |
Volume | 56 |
Issue | 45 |
Article Number | 455304 |
DOI | https://doi.org/10.1088/1751-8121/acfeb7 |
Public URL | https://nottingham-repository.worktribe.com/output/25391629 |
Publisher URL | https://iopscience.iop.org/article/10.1088/1751-8121/acfeb7 |
Files
A post-quantum associative memory
(656 Kb)
PDF
Publisher Licence URL
https://creativecommons.org/licenses/by/4.0/
You might also like
Every quantum helps: Operational advantage of quantum resources beyond convexity
(2024)
Journal Article
Fundamental limitations to key distillation from Gaussian states with Gaussian operations
(2023)
Journal Article
Towards the ultimate brain: Exploring scientific discovery with ChatGPT AI
(2023)
Journal Article
GPT4 : The Ultimate Brain
(2022)
Preprint / Working Paper
Downloadable Citations
About Repository@Nottingham
Administrator e-mail: discovery-access-systems@nottingham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search