Random access codes via quantum contextual redundancy

Giancarlo Gatti1,2,3, Daniel Huerga1, Enrique Solano1,4,5,6, and Mikel Sanz1,2,5,7

1Department of Physical Chemistry, University of the Basque Country UPV/EHU, Apartado 644, 48080 Bilbao, Spain
2EHU Quantum Center, University of the Basque Country UPV/EHU
3Quantum MADS, Uribitarte Kalea 6, 48001 Bilbao, Spain
4International Center of Quantum Artificial Intelligence for Science and Technology (QuArtist) and Department of Physics, Shanghai University, 200444 Shanghai, China
5IKERBASQUE, Basque Foundation for Science, Plaza Euskadi 5, 48009 Bilbao, Spain
6Kipu Quantum, Greifswalderstrasse 226, 10405 Berlin, Germany
7Basque Center for Applied Mathematics (BCAM), Alameda de Mazarredo 14, 48009 Bilbao, Basque Country, Spain

Abstract

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$.

Quantum Random Access Codes (QRACs) store a number of bits into fewer qubits, showcasing better retrieval success probability than their classical counterpart. To do this, the bits are mapped into a quantum state, and every bit is associated to a type of quantum measurement, which can later be performed to retrieve it. These measurement bases are usually chosen to be mutually unbiased.

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$.

► References

[1] C. E. Shannon, A mathematical theory of communication, The Bell system technical journal 27, 379–423 (1948).
https:/​/​doi.org/​10.1002/​j.1538-7305.1948.tb01338.x

[2] W. C. Huffman and V. Pless, Fundamentals of error-correcting codes (Cambridge University Press, 2012).

[3] H. Al-Bahadili, A novel lossless data compression scheme based on the error correcting Hamming codes, Computers & Mathematics with Applications 56, 143–150 (2008).
https:/​/​doi.org/​10.1016/​j.camwa.2007.11.043

[4] A. R. Calderbank and P. W. Shor, Good quantum error-correcting codes exist, Phys. Rev. A 54, 1098–1105 (1996).
https:/​/​doi.org/​10.1103/​PhysRevA.54.1098

[5] A. M. Steane, Error correcting codes in quantum theory, Phys. Rev. Lett. 77, 793–797 (1996).
https:/​/​doi.org/​10.1103/​PhysRevLett.77.793

[6] 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).
https:/​/​doi.org/​10.1103/​PhysRevLett.113.160504

[7] D. Gottesman, Class of quantum error-correcting codes saturating the quantum Hamming bound, Phys. Rev. A 54, 1862–1868 (1996).
https:/​/​doi.org/​10.1103/​PhysRevA.54.1862

[8] A. Y. Kitaev, Fault-tolerant quantum computation by anyons, Annals of Physics 303, 2–30 (2003).
https:/​/​doi.org/​10.1016/​S0003-4916(02)00018-0

[9] A. Peres, Quantum theory: Concepts and Methods (Springer Science & Business Media, 2006).

[10] 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).
https:/​/​doi.org/​10.1103/​PhysRevLett.70.1895

[11] 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).
https:/​/​doi.org/​10.1103/​PhysRevLett.69.2881

[12] 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).
https:/​/​doi.org/​10.1109/​TIT.2002.802612

[13] S. Wiesner, Conjugate coding, ACM Sigact News 15(1), 78–88 (1983).
https:/​/​doi.org/​10.1145/​1008908.1008920

[14] 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.
https:/​/​doi.org/​10.1145/​301250.301347

[15] A. Ambainis, A. Nayak, A. Ta-Shma, and U. Vazirani, Dense quantum coding and quantum finite automata, Journal of the ACM (JACM) 49(4), 496–511 (2002).
https:/​/​doi.org/​10.1145/​581771.581773

[16] M. Pawłowski and M. Żukowski, Entanglement-assisted random access codes, Phys. Rev. A 81, 042326 (2010).
https:/​/​doi.org/​10.1103/​PhysRevA.81.042326

[17] A. Casaccino, E. F. Galvão, and S. Severini, Extrema of discrete Wigner functions and applications, Phys. Rev. A 78, 022310 (2008).
https:/​/​doi.org/​10.1103/​PhysRevA.78.022310

[18] A. Tavakoli, A. Hameedi, B. Marques, and M. Bourennane, Quantum random access codes using single d-level systems, Phys. Rev. Lett. 114, 170502 (2015).
https:/​/​doi.org/​10.1103/​PhysRevLett.114.170502

[19] J. Pauwels, S. Pironio, E. Woodhead, and A. Tavakoli, Almost qudits in the prepare-and-measure scenario, Phys. Rev. Lett. 129, 250504 (2022).
https:/​/​doi.org/​10.1103/​PhysRevLett.129.250504

[20] W. K. Wootters, and B. D. Fields, Optimal state-determination by mutually unbiased measurements, Annals of Physics 191(2), 363–381 (1989).
https:/​/​doi.org/​10.1016/​0003-4916(89)90322-9

[21] A. Ambainis, D. Leung, L. Mancinska, and M. Ozols, Quantum random access codes with shared randomness, arXiv 0810.2937 (2009).
https:/​/​doi.org/​10.48550/​arXiv.0810.2937

[22] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information (Cambridge University Press, 2010).

[23] S. Cheng, J. Chen, and L. Wang, Information perspective to probabilistic modeling: Boltzmann machines versus Born machines, Entropy 20, 583 (2018).
https:/​/​doi.org/​10.3390/​e20080583

[24] F. Lardinois, Google drive will hit a billion users this week, TechCrunch (2018).