Department of Combinatorics and Optimization, and Institute for Quantum Computing, University of Waterloo, 200 University Ave. W., Waterloo, ON, N2L 3G1, Canada.
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
We revisit the task of visible compression of an ensemble of quantum states with entanglement assistance in the one-shot setting. The protocols achieving the best compression use many more qubits of shared entanglement than the number of qubits in the states in the ensemble. Other compression protocols, with potentially larger communication cost, have entanglement cost bounded by the number of qubits in the given states. This motivates the question as to whether entanglement is truly necessary for compression, and if so, how much of it is needed.
Motivated by questions in communication complexity, we lift certain restrictions that are placed on compression protocols in tasks such as state-splitting and channel simulation. We show that an ensemble of the form designed by Jain, Radhakrishnan, and Sen (ICALP’03) saturates the known bounds on the sum of communication and entanglement costs, even with the relaxed compression protocols we study.
The ensemble and the associated one-way communication protocol have several remarkable properties. The ensemble is incompressible by more than a constant number of qubits without shared entanglement, even when constant error is allowed. Moreover, in the presence of shared entanglement, the communication cost of compression can be arbitrarily smaller than the entanglement cost. The quantum information cost of the protocol can thus be arbitrarily smaller than the cost of compression without shared entanglement. The ensemble can also be used to show the impossibility of reducing, via compression, the shared entanglement used in two-party protocols for computing Boolean functions.
► BibTeX data
► References
[1] Anurag Anshu and Rahul Jain. Efficient methods for one-shot quantum communication. Technical Report arXiv:1809.07056 [quant-ph], arXiv.org, https://arxiv.org/abs/1809.07056, September 2018.
arXiv:1809.07056
[2] Anurag Anshu, Rahul Jain, Priyanka Mukhopadhyay, Ala Shayeghi, and Penghui Yao. New one shot quantum protocols with application to communication complexity. IEEE Transactions on Information Theory, 62 (12): 7566–7577, 2016. 10.1109/TIT.2016.2616125.
https://doi.org/10.1109/TIT.2016.2616125
[3] Anurag Anshu, Dave Touchette, Penghui Yao, and Nengkun Yu. Exponential separation of quantum communication and classical information. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 277–288, New York, NY, USA, 2017. ACM. ISBN 978-1-4503-4528-6. 10.1145/3055399.3055401.
https://doi.org/10.1145/3055399.3055401
[4] Shima Bab Hadiashar, Ashwin Nayak, and Renato Renner. Communication complexity of one-shot remote state preparation. IEEE Transactions on Information Theory, 64 (7): 4709–4728, July 2018. 10.1109/TIT.2018.2811509.
https://doi.org/10.1109/TIT.2018.2811509
[5] Howard Barnum, Carlton M. Caves, Christopher A. Fuchs, Richard Jozsa, and Benjamin Schumacher. On quantum coding for ensembles of mixed states. Journal of Physics A: Mathematical and General, 34 (35): 6767–6785, August 2001. 10.1088/0305-4470/34/35/304.
https://doi.org/10.1088/0305-4470/34/35/304
[6] Charles H. Bennett, Igor Devetak, Aram W. Harrow, Peter W. Shor, and Andreas Winter. The quantum reverse Shannon theorem and resource tradeoffs for simulating quantum channels. IEEE Transactions on Information Theory, 60 (5): 2926–2959, May 2014. ISSN 0018-9448. 10.1109/TIT.2014.2309968.
https://doi.org/10.1109/TIT.2014.2309968
[7] Mario Berta, Matthias Christandl, and Renato Renner. The quantum reverse Shannon theorem based on one-shot information theory. Communications in Mathematical Physics, 306 (3): 579–615, August 2011. ISSN 1432-0916. 10.1007/s00220-011-1309-7.
https://doi.org/10.1007/s00220-011-1309-7
[8] Mario Berta, Matthias Christandl, and Dave Touchette. Smooth entropy bounds on one-shot quantum state redistribution. IEEE Transactions on Information Theory, 62 (3): 1425–1439, March 2016. 10.1109/TIT.2016.2516006.
https://doi.org/10.1109/TIT.2016.2516006
[9] Igor Devetak. Triangle of dualities between quantum communication protocols. Physical Review Letters, 97: 140503, Oct 2006. 10.1103/PhysRevLett.97.140503.
https://doi.org/10.1103/PhysRevLett.97.140503
[10] Igor Devetak and Jon Yard. Exact cost of redistributing multipartite quantum states. Physical Review Letters, 100 (230501), June 2008. 10.1103/PhysRevLett.100.230501.
https://doi.org/10.1103/PhysRevLett.100.230501
[11] Christopher A. Fuchs and Jeroen van de Graaf. Cryptographic distinguishability measures for quantum-mechanical states. IEEE Transactions on Information Theory, 45 (4): 1216–1227, May 1999. ISSN 1557-9654. 10.1109/18.761271.
https://doi.org/10.1109/18.761271
[12] Alexei Gilchrist, Nathan K. Langford, and Michael A. Nielsen. Distance measures to compare real and ideal quantum processes. Physical Review A, 71: 062310, Jun 2005. 10.1103/PhysRevA.71.062310.
https://doi.org/10.1103/PhysRevA.71.062310
[13] Carl W. Helstrom. Detection theory and quantum mechanics. Information and Control, 10 (3): 254–291, 1967. 10.1016/S0019-9958(67)90302-6.
https://doi.org/10.1016/S0019-9958(67)90302-6
[14] Alexander S. Holevo. An analogue of statistical decision theory and noncommutative probability theory. Trudy Moskovskogo Matematicheskogo Obshchestva, 26: 133–149, 1972.
[15] Michał Horodecki, Jonathan Oppenheim, and Andreas Winter. Partial quantum information. Nature, 436 (7051): 673–676, August 2005. 10.1038/nature03909.
https://doi.org/10.1038/nature03909
[16] Michał Horodecki, Jonathan Oppenheim, and Andreas Winter. Quantum state merging and negative information. Communications in Mathematical Physics, 269 (1): 107–136, January 2007. 10.1007/s00220-006-0118-x.
https://doi.org/10.1007/s00220-006-0118-x
[17] Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. A direct sum theorem in communication complexity via message compression. In Jos C. M. Baeten, Jan Karel Lenstra, Joachim Parrow, and Gerhard J. Woeginger, editors, Automata, Languages and Programming, volume 2719 of Lecture Notes in Computer Science, pages 300–315, Berlin, Heidelberg, 2003. Springer Berlin Heidelberg. ISBN 978-3-540-45061-0. 10.1007/3-540-45061-0_26.
https://doi.org/10.1007/3-540-45061-0_26
[18] Rahul Jain, Jaikumar Radhakrishnan, and Pranab Sen. Prior entanglement, message compression and privacy in quantum communication. In Proceedings of the 20th Annual IEEE Conference on Computational Complexity, pages 285–296. IEEE Computer Society, 2005. 10.1109/CCC.2005.24.
https://doi.org/10.1109/CCC.2005.24
[19] Rahul Jain, Pranab Sen, and Jaikumar Radhakrishnan. Optimal direct sum and privacy trade-off results for quantum and classical communication complexity. Technical Report arXiv:0807.1267v1 [cs.DC], arXiv.org, https://arxiv.org/abs/0807.1267, July 2008.
arXiv:0807.1267v1
https://arxiv.org/abs/0807.1267
[20] Zahra B. Khanian and Andreas Winter. Entanglement-assisted quantum data compression. In 2019 IEEE International Symposium on Information Theory (ISIT), pages 1147–1151, 2019. 10.1109/ISIT.2019.8849352.
https://doi.org/10.1109/ISIT.2019.8849352
[21] Troy Lee and Adi Shraibman. Lower bounds in communication complexity. Foundations and Trends in Theoretical Computer Science, 3 (4): 263–399, 2009. ISSN 1551-305X. 10.1561/0400000040.
https://doi.org/10.1561/0400000040
[22] Zi-Wen Liu, Christopher Perry, Yechao Zhu, Dax Enshan Koh, and Scott Aaronson. Doubly infinite separation of quantum information and communication. Phys. Rev. A, 93: 012347, Jan 2016. 10.1103/PhysRevA.93.012347.
https://doi.org/10.1103/PhysRevA.93.012347
[23] Zhicheng Luo and Igor Devetak. Channel simulation with quantum side information. IEEE Transactions on Information Theory, 55 (3): 1331–1342, March 2009. ISSN 0018-9448. 10.1109/TIT.2008.2011424.
https://doi.org/10.1109/TIT.2008.2011424
[24] Jiří Matoušek. Lectures on Discrete Geometry, volume 212 of Graduate Texts in Mathematics. Springer-Verlag New York, 1st edition, 2002. ISBN 978-0-387-95373-1. 10.1007/978-1-4613-0039-7.
https://doi.org/10.1007/978-1-4613-0039-7
[25] Elizabeth S. Meckes. The Random Matrix Theory of the Classical Compact Groups, volume 218 of Cambridge Tracts in Mathematics. Cambridge University Press, July 2019. 10.1017/9781108303453.
https://doi.org/10.1017/9781108303453
[26] Vitali D. Milman and Gideon Schechtman. Asymptotic Theory of Finite Dimensional Normed Spaces, volume 1200 of Lecture notes in mathematics. Springer-Verlag Berlin Heidelberg, 1986. 10.1007/978-3-540-38822-7.
https://doi.org/10.1007/978-3-540-38822-7
[27] Marco Tomamichel, Roger Colbeck, and Renato Renner. Duality between smooth min- and max-entropies. IEEE Transactions on Information Theory, 56 (9): 4674–4681, September 2010. ISSN 0018-9448, 1557-9654. 10.1109/TIT.2010.2054130.
https://doi.org/10.1109/TIT.2010.2054130
[28] Dave Touchette. Quantum information complexity. In Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC ’15, pages 317–326, New York, NY, USA, 2015. ACM. ISBN 978-1-4503-3536-2. 10.1145/2746539.2746613.
https://doi.org/10.1145/2746539.2746613
[29] John Watrous. The Theory of Quantum Information. Cambridge University Press, May 2018. 10.1017/9781316848142.
https://doi.org/10.1017/9781316848142
[30] Jon T. Yard and Igor Devetak. Optimal quantum source coding with quantum side information at the encoder and decoder. IEEE Transactions on Information Theory, 55 (11): 5339–5351, November 2009. ISSN 0018-9448. 10.1109/TIT.2009.2030494.
https://doi.org/10.1109/TIT.2009.2030494
Cited by
Could not fetch Crossref cited-by data during last attempt 2020-06-25 09:55:43: Could not fetch cited-by data for 10.22331/q-2020-06-25-286 from Crossref. This is normal if the DOI was registered recently. On SAO/NASA ADS no data on citing works was found (last attempt 2020-06-25 09:55:44).
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.
Source: https://quantum-journal.org/papers/q-2020-06-25-286/
