Document Open Access Logo

Optimal Bounds for Parity-Oblivious Random Access Codes with Applications

Authors André Chailloux, Iordanis Kerenidis, Srijita Kundu, Jamie Sikora

PDF
Thumbnail PDF

File

LIPIcs.TQC.2014.76.pdf
  • Filesize: 403 kB
  • 12 pages

Document Identifiers

Author Details

André Chailloux
Iordanis Kerenidis
Srijita Kundu
Jamie Sikora

Cite As Get BibTex

André Chailloux, Iordanis Kerenidis, Srijita Kundu, and Jamie Sikora. Optimal Bounds for Parity-Oblivious Random Access Codes with Applications. In 9th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 27, pp. 76-87, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014) https://doi.org/10.4230/LIPIcs.TQC.2014.76

Abstract

Random Access Codes is an information task that has been extensively studied and found many applications in quantum information. In this scenario, Alice receives an n-bit string x, and wishes to encode x into a quantum state rho_x, such that Bob, when receiving the state rho_x, can choose any bit i in [n] and recover the input bit x_i with high probability. Here we study a variant called parity-oblivious random acres codes, where we impose the cryptographic property that Bob cannot infer any information about the parity of any subset of bits of the input, apart form the single bits x_i.

We provide the optimal quantum parity-oblivious random access codes and show that they are asymptotically better than the optimal classical ones. For this, we relate such encodings to a non-local game and provide tight bounds for the success probability of the non-local game via semi-definite programming. Our results provide a large non-contextuality inequality violation and resolve the main open question in [Spekkens et al., Phys. Review Letters, 2009].

Subject Classification

Keywords
  • quantum information theory
  • contextuality
  • semidefinite programming

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. 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 31st Annual ACM Symposium on Theory of Computing, pages 376 - 383, 1999. Google Scholar
  2. A. Ambainis, A. Nayak, A. Ta-Shma, and U. Vazirani. Dense quantum coding and quantum finite automata. Journal of the ACM, 49(4):496-511, 2002. Google Scholar
  3. Z. Bar-Yossef, T. S. Jayram, and I. Kerenidis. Exponential separation of quantum and classical one-way communication complexity. In Proceedings of 36th ACM STOC, pages 128-137, 2004. Google Scholar
  4. Avraham Ben-Aroya, Oded Regev, and Ronald de Wolf. A hypercontractive inequality for matrix-valued functions with applications to quantum computing and ldcs. In FOCS'08, pages 477-486, 2008. Google Scholar
  5. H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf. Quantum fingerprinting. Phys. Rev. Lett., 87:167902, Sep 2001. Google Scholar
  6. Harry Buhrman, Oded Regev, Giannicola Scarpa, and Ronald de Wolf. Near-optimal and explicit bell inequality violations. Theory of Computing, 8(27):623-645, 2012. Google Scholar
  7. A. Chailloux, I. Kerenidis, and J. Sikora. Strong connections between quantum encodings, non-locality and quantum cryptography. PRA, to appear., 2014. Google Scholar
  8. J. Clauser, M. Horne, A. Shimony, and R. Holt. Proposed experiment to test local hidden-variable theories. Physical Review Letters, 23(15):880-884, 1969. Google Scholar
  9. R. Cleve, W. Slofstra, F. Unger, and S. Upadhyay. Perfect parallel repetition theroem for quantum XOR proof systems. Computational Complexity, 17(2):282-299, 2008. Google Scholar
  10. Anindya De and Thomas Vidick. Near-optimal extractors against quantum storage. In STOC'10, pages 161-170, 2010. Google Scholar
  11. D. Gavinsky, J. Kempe, I. Kerenidis, R. Raz, and R. de Wolf. Exponential separation for one-way quantum communication complexity, with applications to cryptography. SIAM J. Comput., 38(5):1695-1708, 2008. Google Scholar
  12. 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. Google Scholar
  13. A. Holevo. Some estimates of the information transmitted by quantum communication channels. Problemy Peredachi Informatsii, 9:3-11, 1973. Google Scholar
  14. Kazuo Iwama, Harumichi Nishimura, Rudy Raymond, and Shigeru Yamashita. Unbounded-error one-way classical and quantum communication complexity. In ICALP'07, pages 110-121, 2007. Google Scholar
  15. Hong-Wei Li, Marcin Pawłowski, Zhen-Qiang Yin, Guang-Can Guo, and Zheng-Fu Han. Semi-device-independent randomness certification using n → 1 quantum random access codes. Phys. Rev. A, 85:052308, May 2012. Google Scholar
  16. A. Nayak. Optimal lower bounds for quantum automata and random access codes. Proceedings of 40th IEEE Symposium on Foundations of Computer Science, 0:369-376, 1999. Google Scholar
  17. J. Oppenheim and S. Wehner. The uncertainty principle determines the non-locality of quantum mechanics. Science, 330:6007:1072-1074, 2010. Google Scholar
  18. M. Pawlowski and A. Winter. From qubits to hyperbits. Phys. Rev. A, 85:022331, 2012. Google Scholar
  19. Marcin Pawłowski and Marek \ifmmode \dotZ\else Ż\fiukowski. Entanglement-assisted random access codes. Phys. Rev. A, 81:042326, Apr 2010. Google Scholar
  20. Ran Raz. Exponential separation of quantum and classical communication complexity. In Proc. 31st Annual ACM Symposium on Theory of Computing, pages 358-367, New York, NY, USA, 1999. ACM. Google Scholar
  21. O. Regev and B. Klartag. Quantum one-way communication can be exponentially stronger than classical communication. In STOC'11, pages 31-40, 2011. Google Scholar
  22. 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:010401, 2009. Google Scholar
  23. B. Tsirelson. Quantum analogues of the bell inequalities: The case of two spatially separated domains. Journal of Soviet Mathematics, 36:557-570, 1987. Google Scholar
  24. S. Wiesner. Conjugate coding. SIGACT News, 15(1):78-88, 1983. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact