1Department of Electrical and Computer System Engineering, Monash University, Clayton VIC 3800, Australia
2Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Cambridge CB3 0WA, United Kingdom
Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.
Abstract
The quantum rate-distortion function plays a fundamental role in quantum information theory, however there is currently no practical algorithm which can efficiently compute this function to high accuracy for moderate channel dimensions. In this paper, we show how symmetry reduction can significantly simplify common instances of the entanglement-assisted quantum rate-distortion problems. This allows us to better understand the properties of the quantum channels which obtain the optimal rate-distortion trade-off, while also allowing for more efficient computation of the quantum rate-distortion function regardless of the numerical algorithm being used. Additionally, we propose an inexact variant of the mirror descent algorithm to compute the quantum rate-distortion function with provable sublinear convergence rates. We show how this mirror descent algorithm is related to Blahut-Arimoto and expectation-maximization methods previously used to solve similar problems in information theory. Using these techniques, we present the first numerical experiments to compute a multi-qubit quantum rate-distortion function, and show that our proposed algorithm solves faster and to higher accuracy when compared to existing methods.
Popular summary
► BibTeX data
► References
[1] Claude Elwood 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] Nilanjana Datta, Min-Hsiu Hsieh, and Mark M. Wilde, “Quantum rate distortion, reverse Shannon theorems, and source-channel separation” IEEE Transactions on Information Theory 59, 615–630 (2013).
https://doi.org/10.1109/tit.2012.2215575
[3] Mark M Wilde, Nilanjana Datta, Min-Hsiu Hsieh, and Andreas Winter, “Quantum rate-distortion coding with auxiliary resources” IEEE Transactions on Information Theory 59, 6755–6773 (2013).
https://doi.org/10.1109/tit.2013.2271772
[4] Richard Blahut “Computation of channel capacity and rate-distortion functions” IEEE Transactions on Information Theory 18, 460–473 (1972).
https://doi.org/10.1109/tit.1972.1054855
[5] Suguru Arimoto “An algorithm for computing the capacity of arbitrary discrete memoryless channels” IEEE Transactions on Information Theory 18, 14–20 (1972).
https://doi.org/10.1109/tit.1972.1054753
[6] Kerry He, James Saunderson, and Hamza Fawzi, “A Bregman proximal perspective on classical and quantum Blahut-Arimoto algorithms” (2023).
arXiv:2306.04492
[7] Arkadij Semenovič Nemirovskijand David Borisovich Yudin “Problem complexity and method efficiency in optimization” Wiley (1983).
[8] Amir Beckand Marc Teboulle “Mirror descent and nonlinear projected subgradient methods for convex optimization” Operations Research Letters 31, 167–175 (2003).
https://doi.org/10.1016/s0167-6377(02)00231-6
[9] Paul Tseng “On accelerated proximal gradient methods for convex-concave optimization” report (2008).
https://pages.cs.wisc.edu/~brecht/cs726docs/Tseng.APG.pdf
[10] Amir Beck “First-order methods in optimization” SIAM (2017).
https://doi.org/10.1137/1.9781611974997
[11] Heinz H Bauschke, Jérôme Bolte, and Marc Teboulle, “A descent lemma beyond Lipschitz gradient continuity: First-order methods revisited and applications” Mathematics of Operations Research 42, 330–348 (2017).
https://doi.org/10.1287/moor.2016.0817
[12] Haihao Lu, Robert M Freund, and Yurii Nesterov, “Relatively smooth convex optimization by first-order methods, and applications” SIAM Journal on Optimization 28, 333–354 (2018).
https://doi.org/10.1137/16M1099546
[13] Marc Teboulle “A simplified view of first order methods for optimization” Mathematical Programming 170, 67–96 (2018).
https://doi.org/10.1007/s10107-018-1284-2
[14] Masahito Hayashi “Bregman divergence based em algorithm and its application to classical and quantum rate distortion theory” IEEE Transactions on Information Theory 69, 3460–3492 (2023).
https://doi.org/10.1109/tit.2023.3239955
[15] Masahito Hayashi “Iterative minimization algorithm on mixture family” (2023).
arXiv:2302.06905
[16] Venkat Chandrasekaranand Parikshit Shah “Relative entropy optimization and its applications” Mathematical Programming 161, 1–32 (2017).
https://doi.org/10.1007/s10107-016-0998-2
[17] Hamza Fawziand Omar Fawzi “Efficient optimization of the quantum relative entropy” Journal of Physics A: Mathematical and Theoretical 51, 154003 (2018).
https://doi.org/10.1088/1751-8121/aab285
[18] Hamza Fawzi, James Saunderson, and Pablo A Parrilo, “Semidefinite approximations of the matrix logarithm” Foundations of Computational Mathematics 19, 259–296 (2019).
https://doi.org/10.1007/s10208-018-9385-0
[19] Chris Coey, Lea Kapelevich, and Juan Pablo Vielma, “Performance enhancements for a generic conic interior point algorithm” Mathematical Programming Computation 15, 53–101 (2023).
https://doi.org/10.1007/s12532-022-00226-0
[20] Mehdi Karimiand Levent Tunçel “Primal–dual interior-point methods for domain-driven formulations” Mathematics of Operations Research 45, 591–621 (2020).
https://doi.org/10.1287/moor.2019.1003
[21] Mehdi Karimiand Levent Tuncel “Efficient implementation of interior-point methods for quantum relative entropy” (2023).
arXiv:2312.07438
[22] Lei Yangand Kim-Chuan Toh “Bregman proximal point algorithm revisited: A new inexact version and its inertial variant” SIAM Journal on Optimization 32, 1523–1554 (2022).
https://doi.org/10.1137/20M1360748
[23] Nilanjana Datta, Min-Hsiu Hsieh, Mark M Wilde, and Andreas Winter, “Quantum-to-classical rate distortion coding” Journal of Mathematical Physics 54 (2013).
https://doi.org/10.1063/1.4798396
[24] Howard Barnum “Quantum rate-distortion coding” Physical Review A 62, 042309 (2000).
https://doi.org/10.1103/physreva.62.042309
[25] Zahra Baghali Khanianand Andreas Winter “A rate-distortion perspective on quantum state redistribution” (2021).
arXiv:2112.11952
[26] Zahra Baghali Khanian, Kohdai Kuroiwa, and Debbie Leung, “Rate-distortion theory for mixed states” 2023 IEEE International Symposium on Information Theory 749–754 (2023).
https://doi.org/10.1109/isit54713.2023.10206960
[27] Michael A. Nielsenand Isaac L. Chuang “Quantum computation and quantum information: 10th anniversary edition” Cambridge University Press (2010).
https://doi.org/10.1017/cbo9780511976667
[28] Mark M. Wilde “Quantum information theory” Cambridge University Press (2017).
https://doi.org/10.1017/9781316809976
[29] John Watrous “The theory of quantum information” Cambridge University Press (2018).
https://doi.org/10.1017/9781316848142
[30] R Tyrrell Rockafellar “Convex analysis” Princeton University Press (1970).
https://doi.org/10.1007/bfb0110040
[31] Lev M Bregman “The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming” USSR Computational Mathematics and Mathematical Physics 7, 200–217 (1967).
https://doi.org/10.1016/0041-5553(67)90040-7
[32] Chris J Maddison, Daniel Paulin, Yee Whye Teh, and Arnaud Doucet, “Dual space preconditioning for gradient descent” SIAM Journal on Optimization 31, 991–1016 (2021).
https://doi.org/10.1137/19M130858X
[33] Dimitri Bertsekas “Convex optimization theory” Athena Scientific (2009).
[34] Theodor Bröckerand Tammo Tom Dieck “Representations of compact Lie groups” Springer Science & Business Media (2013).
https://doi.org/10.1007/978-3-662-12918-0
[35] William Fultonand Joe Harris “Representation theory: A first course” Springer Science & Business Media (2013).
https://doi.org/10.1007/978-1-4612-0979-9
[36] Glen E Bredon “Introduction to compact transformation groups” Academic Press (1972).
https://doi.org/10.1016/s0079-8169(08)x6007-6
[37] Persi Diaconisand Steven Evans “Linear functionals of eigenvalues of random matrices” Transactions of the American Mathematical Society 353, 2615–2633 (2001).
https://doi.org/10.1090/S0002-9947-01-02800-8
[38] Masahito Hayashiand Yuxiang Yang “Efficient algorithms for quantum information bottleneck” Quantum 7, 936 (2023).
https://doi.org/10.22331/q-2023-03-02-936
[39] Stephen Boydand Lieven Vandenberghe “Convex optimization” Cambridge University Press (2004).
https://doi.org/10.1017/cbo9780511804441
[40] Roger A. Hornand Charles R. Johnson “Topics in matrix analysis” Cambridge University Press (1991).
https://doi.org/10.1017/cbo9780511840371
[41] Mikhail V Solodovand Benar Fux Svaiter “Error bounds for proximal point subproblems and associated inexact proximal point algorithms” Mathematical Programming 88, 371–389 (2000).
https://doi.org/10.1007/s101070050022
[42] Mark Schmidt, Nicolas Roux, and Francis Bach, “Convergence rates of inexact proximal-gradient methods for convex optimization” Advances in Neural Information Processing Systems Proceedings of the 24th International Conference on Neural Information Processing Systems 24, 1458–1466 (2011).
https://dl.acm.org/doi/10.5555/2986459.2986622
[43] Jorge Nocedaland Stephen J Wright “Numerical optimization” Springer (1999).
https://doi.org/10.1007/b98874
[44] Nathaniel Johnston “QETLAB: A MATLAB toolbox for quantum entanglement, version 0.9” http://qetlab.com (2016).
https://doi.org/10.5281/zenodo.44637
http://qetlab.com
[45] Kim-Chuan Toh, Michael J Todd, and Reha H Tütüncü, “SDPT3 — A MATLAB software package for semidefinite programming, version 1.3” Optimization Methods and Software 11, 545–581 (1999).
https://doi.org/10.1080/10556789908805762
[46] Masahito Hayashiand Geng Liu “Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck” (2023).
arXiv:2311.11188
[47] Thomas M. Coverand Joy A. Thomas “Elements of information theory” John Wiley & Sons (1999).
https://doi.org/10.1002/047174882X
[48] Aram V Arutyunovand Valeri Obukhovskii “Convex and set-valued analysis” De Gruyter (2017).
https://doi.org/10.1515/9783110460308
[49] Martin Jaggi “Revisiting Frank-Wolfe: Projection-free sparse convex optimization” Proceedings of the 30th International Conference on International Conference on Machine Learning – Volume 28 427–435 (2013).
https://dl.acm.org/doi/10.5555/3042817.3042867
[50] Haobo Liand Ning Cai “A Blahut-Arimoto type algorithm for computing classical-quantum channel capacity” International Symposium on Information Theory 2019 IEEE International Symposium on Information Theory 255–259 (2019).
https://doi.org/10.1109/isit.2019.8849608
[51] Navneeth Ramakrishnan, Raban Iten, Volkher B Scholz, and Mario Berta, “Computing quantum channel capacities” IEEE Transactions on Information Theory 67, 946–960 (2020).
https://doi.org/10.1109/tit.2020.3034471
[52] Heinz H Bauschkeand Jonathan M Borwein “Legendre functions and the method of random Bregman projections” Journal of Convex Analysis 4, 27–67 (1997).
[53] Rajendra Bhatia “Matrix analysis” Springer Science & Business Media (2013).
https://doi.org/10.1007/978-1-4612-0653-8
Cited by
[1] Mehdi Karimi and Levent Tuncel, “Efficient Implementation of Interior-Point Methods for Quantum Relative Entropy”, arXiv:2312.07438, (2023).
[2] Masahito Hayashi and Geng Liu, “Generalized quantum Arimoto-Blahut algorithm and its application to quantum information bottleneck”, arXiv:2311.11188, (2023).
The above citations are from SAO/NASA ADS (last updated successfully 2024-04-09 11:49:40). The list may be incomplete as not all publishers provide suitable and complete citation data.
Could not fetch Crossref cited-by data during last attempt 2024-04-09 11:49:38: Could not fetch cited-by data for 10.22331/q-2024-04-09-1314 from Crossref. This is normal if the DOI was registered recently.
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.
- SEO Powered Content & PR Distribution. Get Amplified Today.
- PlatoData.Network Vertical Generative Ai. Empower Yourself. Access Here.
- PlatoAiStream. Web3 Intelligence. Knowledge Amplified. Access Here.
- PlatoESG. Carbon, CleanTech, Energy, Environment, Solar, Waste Management. Access Here.
- PlatoHealth. Biotech and Clinical Trials Intelligence. Access Here.
- Source: https://quantum-journal.org/papers/q-2024-04-09-1314/
