1Quantum Engineering Centre for Doctoral Training, University of Bristol, United Kingdom
2School of Mathematics, University of Bristol, United Kingdom
3Phasecraft Ltd.
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
An $noverset{p}{mapsto}m$ random access code (RAC) is an encoding of $n$ bits into $m$ bits such that any initial bit can be recovered with probability at least $p$, while in a quantum RAC (QRAC), the $n$ bits are encoded into $m$ qubits. Since its proposal, the idea of RACs was generalized in many different ways, e.g. allowing the use of shared entanglement (called entanglement-assisted random access code, or simply EARAC) or recovering multiple bits instead of one. In this paper we generalize the idea of RACs to recovering the value of a given Boolean function $f$ on any subset of fixed size of the initial bits, which we call $f$-random access codes. We study and give protocols for $f$-random access codes with classical ($f$-RAC) and quantum ($f$-QRAC) encoding, together with many different resources, e.g. private or shared randomness, shared entanglement ($f$-EARAC) and Popescu-Rohrlich boxes ($f$-PRRAC). The success probability of our protocols is characterized by the $textit{noise stability}$ of the Boolean function $f$. Moreover, we give an $textit{upper bound}$ on the success probability of any $f$-QRAC with shared randomness that matches its success probability up to a multiplicative constant (and $f$-RACs by extension), meaning that quantum protocols can only achieve a limited advantage over their classical counterparts.
Featured image: The main idea of our scheme: the initial data is broken into different blocks and each is encoded using a well established random access code.
Popular summary
► BibTeX data
► References
[1] S. Aaronson. The learnability of quantum states. Proc. R. Soc. Lond. Ser. A Math. Phys. Eng. Sci., 463 (2088): 3089–3114, 2007. ISSN 1364-5021. 10.1098/rspa.2007.0113.
https://doi.org/10.1098/rspa.2007.0113
[2] E. A. Aguilar, M. Farkas, D. Martínez, M. Alvarado, J. Cariñe, G. B Xavier, J. F. Barra, G. Cañas, M. Pawłowski, and G. Lima. Certifying an irreducible 1024-dimensional photonic state using refined dimension witnesses. Physical Review Letters, 120 (23): 230503, 2018. 10.1103/PhysRevLett.120.230503.
https://doi.org/10.1103/PhysRevLett.120.230503
[3] J. Ahrens, P. Badziąg, M. Pawłowski, M. Żukowski, and M. Bourennane. Experimental tests of classical and quantum dimensionality. Physical review letters, 112 (14): 140401, 2014. 10.1103/PhysRevLett.112.140401.
https://doi.org/10.1103/PhysRevLett.112.140401
[4] 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, pages 376–383, 1999. 10.1145/301250.301347.
https://doi.org/10.1145/301250.301347
[5] A. Ambainis, D. Leung, L. Mancinska, and M. Ozols. Quantum random access codes with shared randomness. arXiv preprint arXiv:0810.2937, 2008.
arXiv:0810.2937
[6] A. Ambainis, D. Kravchenko, and A. Rai. Optimal classical random access codes using single $d$-level systems. arXiv preprint arXiv:1510.03045, 2015.
arXiv:1510.03045
[7] A. Ambainis, M. Banik, A. Chaturvedi, D. Kravchenko, and A. Rai. Parity oblivious $d$-level random access codes and class of noncontextuality inequalities. Quantum Information Processing, 18 (4): 111, 2019. 10.1007/s11128-019-2228-3.
https://doi.org/10.1007/s11128-019-2228-3
[8] A. Ben-Aroya, O. Regev, and R. de Wolf. A hypercontractive inequality for matrix-valued functions with applications to quantum computing and LDCs. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 477–486. IEEE, 2008. 10.1109/FOCS.2008.45. arXiv:0705.3806.
https://doi.org/10.1109/FOCS.2008.45
arXiv:0705.3806
[9] I. Benjamini, G. Kalai, and O. Schramm. Noise sensitivity of Boolean functions and applications to percolation. Publications Mathématiques de l’Institut des Hautes Études Scientifiques, 90 (1): 5–43, 1999. 10.1007/978-1-4419-9675-6_12.
https://doi.org/10.1007/978-1-4419-9675-6_12
[10] H. Buhrman and R. de Wolf. Communication complexity lower bounds by polynomials. In Proceedings 16th Annual IEEE Conference on Computational Complexity, pages 120–130. IEEE, 2001. 10.1109/CCC.2001.933879.
https://doi.org/10.1109/CCC.2001.933879
[11] C. Calabro. The exponential complexity of satisfiability problems. PhD thesis, UC San Diego, 2009.
[12] A. Casaccino, E. F. Galvão, and S. Severini. Extrema of discrete Wigner functions and applications. Physical Review A, 78 (2): 022310, 2008. 10.1103/PhysRevA.78.022310.
https://doi.org/10.1103/PhysRevA.78.022310
[13] A. Chailloux, I. Kerenidis, S. Kundu, and J. Sikora. Optimal bounds for parity-oblivious random access codes. New Journal of Physics, 18 (4): 045003, 2016. 10.1088/1367-2630/18/4/045003.
https://doi.org/10.1088/1367-2630/18/4/045003
[14] G. Cohen. A nonconstructive upper bound on covering radius. IEEE Transactions on Information Theory, 29 (3): 352–353, 1983. 10.1109/TIT.1983.1056678.
https://doi.org/10.1109/TIT.1983.1056678
[15] R. Coleman. On Krawtchouk polynomials. arXiv preprint arXiv:1101.1798, 2011.
arXiv:1101.1798
[16] W. van Dam. Implausible consequences of superstrong nonlocality. Natural Computing, 12 (1): 9–12, 2013. 10.1007/s11047-012-9353-6.
https://doi.org/10.1007/s11047-012-9353-6
[17] D. Dominici. Asymptotic analysis of the Krawtchouk polynomials by the WKB method. The Ramanujan Journal, 15 (3): 303–338, 2008. 10.1007/s11139-007-9078-9.
https://doi.org/10.1007/s11139-007-9078-9
[18] P.-E. Emeriau, M. Howard, and S. Mansfield. Quantum advantage in information retrieval. arXiv preprint arXiv:2007.15643, 2020.
arXiv:2007.15643
[19] M. Farkas and J. Kaniewski. Self-testing mutually unbiased bases in the prepare-and-measure scenario. Physical Review A, 99 (3): 032316, 2019. 10.1103/PhysRevA.99.032316.
https://doi.org/10.1103/PhysRevA.99.032316
[20] M. Farkas, N. Guerrero, J. Cariñe, G. Cañas, and G. Lima. Self-testing mutually unbiased bases in higher dimensions with space-division multiplexing optical fiber technology. Phys. Rev. Applied, 15: 014028, Jan 2021. 10.1103/PhysRevApplied.15.014028.
https://doi.org/10.1103/PhysRevApplied.15.014028
[21] G. Foletto, L. Calderaro, G. Vallone, and P. Villoresi. Experimental demonstration of sequential quantum random access codes. Phys. Rev. Research, 2: 033205, Aug 2020. 10.1103/PhysRevResearch.2.033205.
https://doi.org/10.1103/PhysRevResearch.2.033205
[22] D. Gavinsky, J. Kempe, O Regev, and R. de Wolf. Bounded-error quantum state identification and exponential separations in communication complexity. SIAM J. Comput., 39 (1): 1–24, 2009. ISSN 0097-5397. 10.1137/060665798.
https://doi.org/10.1137/060665798
[23] A. Grudka, K. Horodecki, M. Horodecki, W. Kłobus, and M. Pawłowski. When are Popescu-Rohrlich boxes and random access codes equivalent? Physical review letters, 113 (10): 100401, 2014. 10.1103/PhysRevLett.113.100401.
https://doi.org/10.1103/PhysRevLett.113.100401
[24] A. Grudka, M. Horodecki, R. Horodecki, and A. Wójcik. Nonsignaling quantum random access-code boxes. Physical Review A, 92 (5): 052312, 2015. 10.1103/PhysRevA.92.052312.
https://doi.org/10.1103/PhysRevA.92.052312
[25] A. Hameedi, D. Saha, P. Mironowicz, M. Pawłowski, and M. Bourennane. Complementarity between entanglement-assisted and quantum distributed random access code. Physical Review A, 95 (5): 052345, 2017. 10.1103/PhysRevA.95.052345.
https://doi.org/10.1103/PhysRevA.95.052345
[26] M. Hayashi, K. Iwama, H. Nishimura, R. Raymond, and S. Yamashita. (4, 1)-quantum random access coding does not exist—one qubit is not enough to recover one of four bits. New Journal of Physics, 8 (8): 129, 2006. 10.1088/1367-2630/8/8/129.
https://doi.org/10.1088/1367-2630/8/8/129
[27] M. Hayashi, K. Iwama, H. Nishimura, R. Raymond, and S. Yamashita. Quantum network coding. In Annual Symposium on Theoretical Aspects of Computer Science, pages 610–621. Springer, 2007. 10.1007/978-3-540-70918-3_52.
https://doi.org/10.1007/978-3-540-70918-3_52
[28] C. W. Helstrom. Quantum detection and estimation theory, volume 3. Academic press New York, 1976. 10.1007/BF01007479.
https://doi.org/10.1007/BF01007479
[29] A. S. Holevo. Bounds for the quantity of information transmitted by a quantum communication channel. Problemy Peredachi Informatsii, 9 (3): 3–11, 1973.
[30] B. D. Hughes. Random walks and random environments: random walks, volume 1. Oxford University Press, 1995.
[31] T. Imamichi and R. Raymond. Constructions of quantum random access codes. In Asian Quantum Information Symposium (AQIS), 2018.
[32] K. Iwama, H. Nishimura, R. Raymond, and S. Yamashita. Unbounded-error one-way classical and quantum communication complexity. In International Colloquium on Automata, Languages, and Programming, pages 110–121. Springer, 2007. 10.1007/978-3-540-73420-8_12.
https://doi.org/10.1007/978-3-540-73420-8_12
[33] I. Kerenidis. Quantum encodings and applications to locally decodable codes and communication complexity. University of California, Berkeley, 2004.
[34] I. Kerenidis and R. de Wolf. Exponential lower bound for 2-query locally decodable codes via a quantum argument. Journal of Computer and System Sciences, 69 (3): 395–420, 2004. ISSN 0022-0000. https://doi.org/10.1016/j.jcss.2004.04.007.
https://doi.org/10.1016/j.jcss.2004.04.007
[35] H. Klauck. On quantum and probabilistic communication: Las Vegas and one-way protocols. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pages 644–651. ACM, New York, 2000. 10.1145/335305.335396.
https://doi.org/10.1145/335305.335396
[36] H. Klauck. One-way communication complexity and the Nečiporuk lower bound on formula size. SIAM Journal on Computing, 37 (2): 552–583, 2007. 10.1137/S009753970140004X.
https://doi.org/10.1137/S009753970140004X
[37] E. Kushilevitz and N. Nisan. Communication Complexity. Cambridge University Press, New York, NY, USA, 1997. ISBN 0-521-56067-5. 10.1017/CBO9780511574948.
https://doi.org/10.1017/CBO9780511574948
[38] H.-W. Li, Z.-Q. Yin, Y.-C. Wu, X.-B. Zou, S. Wang, W. Chen, G.-C. Guo, and Z.-F. Han. Semi-device-independent random-number expansion without entanglement. Physical Review A, 84 (3): 034301, 2011. 10.1103/PhysRevA.84.034301.
https://doi.org/10.1103/PhysRevA.84.034301
[39] O. Liabøtrø. Improved classical and quantum random access codes. Physical Review A, 95 (5): 052315, 2017. 10.1103/PhysRevA.95.052315.
https://doi.org/10.1103/PhysRevA.95.052315
[40] F. J. MacWilliams and N. J. A. Sloane. The theory of error correcting codes, volume 16. Elsevier, 1977.
[41] E. Mossel and R. O’Donnell. On the noise sensitivity of monotone functions. Random Structures & Algorithms, 23 (3): 333–350, 2003. 10.1007/978-3-0348-8211-8_30.
https://doi.org/10.1007/978-3-0348-8211-8_30
[42] S. Muhammad, A. Tavakoli, M. Kurant, M. Pawłowski, M. Żukowski, and M. Bourennane. Quantum bidding in bridge. Physical Review X, 4 (2): 021047, 2014. 10.1103/PhysRevX.4.021047.
https://doi.org/10.1103/PhysRevX.4.021047
[43] A. Nayak. Optimal lower bounds for quantum automata and random access codes. In Proceedings of the 40th Annual Symposium on Foundations of Computer Science, page 369, 1999. 10.1109/SFFCS.1999.814608.
https://doi.org/10.1109/SFFCS.1999.814608
[44] I. Newman. Private vs. common random bits in communication complexity. Information Processing Letters, 39 (2): 67–71, 1991. 10.1016/0020-0190(91)90157-D.
https://doi.org/10.1016/0020-0190(91)90157-D
[45] R. O’Donnell. Computational applications of noise sensitivity. PhD thesis, Massachusetts Institute of Technology, 2003.
[46] R. O’Donnell. Analysis of Boolean functions. Cambridge University Press, 2014. 10.1017/CBO9781139814782.
https://doi.org/10.1017/CBO9781139814782
[47] M. Pawłowski and N. Brunner. Semi-device-independent security of one-way quantum key distribution. Physical Review A, 84 (1): 010302, 2011. 10.1103/PhysRevA.84.010302.
https://doi.org/10.1103/PhysRevA.84.010302
[48] M. Pawłowski and M. Żukowski. Entanglement-assisted random access codes. Physical Review A, 81 (4): 042326, 2010. 10.1103/PhysRevA.81.042326.
https://doi.org/10.1103/PhysRevA.81.042326
[49] M. Pawłowski, T. Paterek, D. Kaszlikowski, V. Scarani, A. Winter, and M. Żukowski. Information causality as a physical principle. Nature, 461 (7267): 1101–1104, 2009. 10.1038/nature08400.
https://doi.org/10.1038/nature08400
[50] S. Popescu and D. Rohrlich. Quantum nonlocality as an axiom. Foundations of Physics, 24 (3): 379–385, 1994. 10.1007/BF02058098.
https://doi.org/10.1007/BF02058098
[51] A. Rao and A. Yehudayoff. Communication Complexity: and Applications. Cambridge University Press, 2020. 10.1017/9781108671644.
https://doi.org/10.1017/9781108671644
[52] R. Rubinfeld and A. Vasilyan. Approximating the noise sensitivity of a monotone boolean function. arXiv preprint arXiv:1904.06745, 2019.
arXiv:1904.06745
[53] D. Saha and J. J. Borkała. Multiparty quantum random access codes. EPL (Europhysics Letters), 128 (3): 30005, 2020. 10.1209/0295-5075/128/30005.
https://doi.org/10.1209/0295-5075/128/30005
[54] A. A. Sherstov. Separating $AC^{0}$ from depth-2 majority circuits. SIAM Journal on Computing, 38 (6): 2113–2129, 2009. 10.1137/08071421X.
https://doi.org/10.1137/08071421X
[55] A. A. Sherstov. The pattern matrix method. SIAM Journal on Computing, 40 (6): 1969–2000, 2011. 10.1137/080733644.
https://doi.org/10.1137/080733644
[56] R. W. Spekkens, D. H. Buzacott, A. J. Keehn, B. Toner, and G. J. Pryde. Preparation contextuality powers parity-oblivious multiplexing. Physical review letters, 102 (1): 010401, 2009. 10.1103/PhysRevLett.102.010401.
https://doi.org/10.1103/PhysRevLett.102.010401
[57] G. Ver Steeg and S. Wehner. Relaxed uncertainty relations and information processing. arXiv preprint arXiv:0811.3771, 2008.
arXiv:0811.3771
[58] A. Tănăsescu, V.-F. Iliescu, and P. G. Popescu. Optimal entanglement-assisted almost-random access codes. Physical Review A, 101 (4): 042309, 2020. 10.1103/PhysRevA.101.042309.
https://doi.org/10.1103/PhysRevA.101.042309
[59] A. Tavakoli, A. Hameedi, B. Marques, and M. Bourennane. Quantum random access codes using single $d$-level systems. Physical review letters, 114 (17): 170502, 2015. 10.1103/PhysRevLett.114.170502.
https://doi.org/10.1103/PhysRevLett.114.170502
[60] A. Tavakoli, B. Marques, M. Pawłowski, and M. Bourennane. Spatial versus sequential correlations for random access coding. Physical Review A, 93 (3): 032336, 2016. 10.1103/PhysRevA.93.032336.
https://doi.org/10.1103/PhysRevA.93.032336
[61] X.-R. Wang, L.-Y. Wu, C.-X. Liu, T.-J. Liu, J. Li, and Q. Wang. Experimental generation of entanglement-assisted quantum random access code. Physical Review A, 99 (5): 052313, 2019. 10.1103/PhysRevA.99.052313.
https://doi.org/10.1103/PhysRevA.99.052313
[62] S. Wehner and R. de Wolf. Improved lower bounds for locally decodable codes and private information retrieval. In Automata, languages and programming, volume 3580 of Lecture Notes in Comput. Sci., pages 1424–1436. Springer, Berlin, 2005. 10.1007/11523468_115.
https://doi.org/10.1007/11523468_115
[63] S. Wehner, M. Christandl, and A. C. Doherty. Lower bound on the dimension of a quantum system given measured data. Physical Review A, 78 (6): 062112, 2008. 10.1103/PhysRevA.78.062112.
https://doi.org/10.1103/PhysRevA.78.062112
[64] S. Wiesner. Conjugate coding. ACM Sigact News, 15 (1): 78–88, 1983. 10.1145/1008908.1008920.
https://doi.org/10.1145/1008908.1008920
[65] R. de Wolf. A brief introduction to Fourier analysis on the Boolean cube. Theory of Computing, pages 1–20, 2008. 10.4086/toc.gs.2008.001.
https://doi.org/10.4086/toc.gs.2008.001
[66] S. Wolf and J. Wullschleger. Oblivious transfer and quantum non-locality. In Proceedings. International Symposium on Information Theory, 2005. ISIT 2005., pages 1745–1748. IEEE, 2005. 10.1109/ISIT.2005.1523644.
https://doi.org/10.1109/ISIT.2005.1523644
Cited by
[1] Pierre-Emmanuel Emeriau, Mark Howard, and Shane Mansfield, “Quantum Advantage in Information Retrieval”, arXiv:2007.15643.
The above citations are from SAO/NASA ADS (last updated successfully 2021-03-08 01:14:02). The list may be incomplete as not all publishers provide suitable and complete citation data.
On Crossref’s cited-by service no data on citing works was found (last attempt 2021-03-08 01:14:00).
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.
Checkout PrimeXBT
Trade with the Official CFD Partners of AC Milan
Source: https://quantum-journal.org/papers/q-2021-03-07-402/
