We propose a protocol to encode classical bits in the measurement statistics of many-body Pauli observables, leveraging quantum correlations for a random access code. Measurement contexts built with these observables yield outcomes with intrinsic redundancy, something we exploit by encoding the data into a set of convenient context eigenstates. This allows to randomly access the encoded data with few resources. The eigenstates used are highly entangled and can be generated by a discretely-parametrized quantum circuit of low depth. Applications of this protocol include algorithms requiring large-data storage with only partial retrieval, as is the case of decision trees. Using $n$-qubit states, this Quantum Random Access Code has greater success probability than its classical counterpart for $n\ge 14$ and than previous Quantum Random Access Codes for $n \ge 16$. Furthermore, for $n\ge 18$, it can be amplified into a nearly-lossless compression protocol with success probability $0.999$ and compression ratio $O(n^2/2^n)$. The data it can store is equal to Google-Drive server capacity for $n= 44$, and to a brute-force solution for chess (what to do on any board configuration) for $n= 100$.
In this paper, we propose the use of measurement bases which are mutually biased instead, so that every bit appears in multiple measurement bases. Rather than posing a drawback, this allows us to encode each bit using the most convenient basis, saving resources for large-scale quantum systems. We employ many-body Pauli observables to convey our bits, and each set of commuting observables that can be constructed defines one measurement basis. Using systems of $n$ qubits, this approach showcases an asymptotic compression ratio of $O(n^2/2^n)$ and better success probability than prior QRACs for $n \ge 16$.
 C. E. Shannon, A mathematical theory of communication, The Bell system technical journal 27, 379–423 (1948).
 W. C. Huffman and V. Pless, Fundamentals of error-correcting codes (Cambridge University Press, 2012).
 H. Al-Bahadili, A novel lossless data compression scheme based on the error correcting Hamming codes, Computers & Mathematics with Applications 56, 143–150 (2008).
 L. A. Rozema, D. H. Mahler, A. Hayat, P. S. Turner, and A. M. Steinberg, Quantum data compression of a qubit ensemble, Phys. Rev. Lett. 113, 160504 (2014).
 A. Peres, Quantum theory: Concepts and Methods (Springer Science & Business Media, 2006).
 C. H. Bennett, G. Brassard, C. Crépeau, R. Jozsa, A. Peres, and W. K. Wootters, Teleporting an unknown quantum state via dual classical and Einstein-Podolsky-Rosen channels, Phys. Rev. Lett. 70, 1895 (1993).
 C. H. Bennett and S. J. Wiesner, Communication via one-and two-particle operators on Einstein-Podolsky-Rosen states, Phys. Rev. Lett. 69, 2881 (1992).
 C. H. Bennett, P. W. Shor, J. A. Smolin, and A. V. Thapliyal, Entanglement-assisted capacity of a quantum channel and the reverse Shannon theorem, IEEE transactions on Information Theory 48.10, 2637–2655 (2002).
 A. Ambainis, A. Nayak, A. Ta-Shma, and U. Vazirani, Dense quantum coding and a lower bound for 1-way quantum automata, in Proceedings of the thirty-first annual ACM symposium on Theory of Computing (1999) pp. 376–383.
 A. Tavakoli, A. Hameedi, B. Marques, and M. Bourennane, Quantum random access codes using single d-level systems, Phys. Rev. Lett. 114, 170502 (2015).
 J. Pauwels, S. Pironio, E. Woodhead, and A. Tavakoli, Almost qudits in the prepare-and-measure scenario, Phys. Rev. Lett. 129, 250504 (2022).
 M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, 2010).
 F. Lardinois, Google drive will hit a billion users this week, TechCrunch (2018).
 A. Levinovitz, The mystery of Go, the ancient game that computers still can't win, Wired Business (2014).
This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.