Effektiv beräkning av Quantum Rate-Distortion-funktionen

Effektiv beräkning av Quantum Rate-Distortion-funktionen

Tidsstämpel: 9 april 2024 7:42
Efficient Computation of the Quantum Rate-Distortion Function PlatoBlockchain Data Intelligence. Vertical Search. Ai.

Kerry He1, James Saunderson1, och Hamza Fawzi2

1Institutionen för el- och datorsystemteknik, Monash University, Clayton VIC 3800, Australien
2Institutionen för tillämpad matematik och teoretisk fysik, University of Cambridge, Cambridge CB3 0WA, Storbritannien

Hitta det här uppsatsen intressant eller vill diskutera? Scite eller lämna en kommentar på SciRate.

Abstrakt

Kvanthastighetsdistorsionsfunktionen spelar en grundläggande roll i kvantinformationsteorin, men det finns för närvarande ingen praktisk algoritm som effektivt kan beräkna denna funktion med hög noggrannhet för måttliga kanaldimensioner. I den här artikeln visar vi hur symmetrireduktion avsevärt kan förenkla vanliga förekomster av de intrasslingsassisterade kvanthastighetsdistorsionsproblemen. Detta gör det möjligt för oss att bättre förstå egenskaperna hos kvantkanalerna som erhåller den optimala avvägningen mellan hastighet och distorsion, samtidigt som vi tillåter mer effektiv beräkning av kvanthastighetsdistorsionsfunktionen oavsett vilken numerisk algoritm som används. Dessutom föreslår vi en inexakt variant av spegelnedstigningsalgoritmen för att beräkna kvanthastighetsdistorsionsfunktionen med bevisbara sublinjära konvergenshastigheter. Vi visar hur denna spegelnedstigningsalgoritm är relaterad till Blahut-Arimoto och förväntningsmaximeringsmetoder som tidigare använts för att lösa liknande problem inom informationsteorin. Med hjälp av dessa tekniker presenterar vi de första numeriska experimenten för att beräkna en multi-qubit kvanthastighetsdistorsionsfunktion och visar att vår föreslagna algoritm löser snabbare och med högre noggrannhet jämfört med befintliga metoder.

Populär sammanfattning

Kvanthastighetsdistorsionsfunktionen beskriver den maximala mängd en kvantinformationskälla kan komprimeras av en kvantkanal, utan att överskrida en maximal tillåten distorsion. I allmänhet måste denna funktion beräknas numeriskt genom att lösa ett konvext optimeringsproblem. Detta kan dock vara utmanande av två skäl. För det första blir problemdimensionen av optimeringsproblemet snabbt stor när storleken på kvantkanalen ökar. För vanliga metoder för att mäta distorsionen av kvantinformationskällan visar vi hur symmetrier i optimeringsproblemet kan utnyttjas för att avsevärt reducera dimensionen av optimeringsproblemet, vilket gör att vi kan lösa problemet mycket snabbare. För det andra fungerar inte standardgradientnedstigningsalgoritmer bra när man beräknar kvanthastighetsdistorsionsfunktionen, på grund av de kvantentropiliknande funktionerna som uppstår i optimeringsproblemet. Istället visar vi hur en entropisk variation av gradientnedstigning, känd som entropisk spegelnedstigning, kan användas för att härleda en effektiv algoritm för att beräkna kvanthastighetsdistorsionsfunktionen.

► BibTeX-data

► Referenser

[1] Claude Elwood Shannon "A matematical 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 och 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 och 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 "Beräkning av kanalkapacitet och hastighetsdistorsionsfunktioner" IEEE Transactions on Information Theory 18, 460–473 (1972).
https: / / doi.org/ 10.1109 / tit.1972.1054855

[5] Suguru Arimoto "En algoritm för att beräkna kapaciteten hos godtyckliga diskreta minneslösa kanaler" IEEE Transactions on Information Theory 18, 14–20 (1972).
https: / / doi.org/ 10.1109 / tit.1972.1054753

[6] Kerry He, James Saunderson och Hamza Fawzi, "A Bregman proximal perspective on classical and quantum Blahut-Arimoto algorithms" (2023).
arXiv: 2306.04492

[7] Arkadij Semenovič Nemirovskijand David Borisovich Yudin "Problemkomplexitet och metodeffektivitet vid optimering" Wiley (1983).

[8] Amir Beck och Marc Teboulle "Mirror descent and nonlinar 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 "Om accelererade proximala gradientmetoder för konvex-konkav optimering" rapport (2008).
https://​/​pages.cs.wisc.edu/​~brecht/​cs726docs/​Tseng.APG.pdf

[10] Amir Beck ”Första ordningens metoder i optimering” SIAM (2017).
https: / / doi.org/ 10.1137 / 1.9781611974997

[11] Heinz H Bauschke, Jérôme Bolte och Marc Teboulle, "A descent lemma beyond Lipschitz gradient continuity: First-orders 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 och Yurii Nesterov, "Relativt jämn konvex optimering genom första ordningens metoder och tillämpningar" 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 divergensbaserad em-algoritm och dess tillämpning på klassisk och kvanthastighetsförvrängningsteori" IEEE Transactions on Information Theory 69, 3460–3492 (2023).
https: / / doi.org/ 10.1109 / tit.2023.3239955

[15] Masahito Hayashi "Iterativ minimeringsalgoritm på blandningsfamiljen" (2023).
arXiv: 2302.06905

[16] Venkat Chandrasekaran och Parikshit Shah "Relativ entropioptimering och dess tillämpningar" Mathematical Programmering 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 och 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 och Juan Pablo Vielma, "Prestandaförbättringar för en generisk konisk inre punktalgoritm" 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 domändrivna formuleringar” Mathematics of Operations Research 45, 591–621 (2020).
https: / ⠀ </ ⠀ <doi.org/†<10.1287 / ⠀ <moor.2019.1003

[21] Mehdi Karimiand Levent Tuncel "Effektiv implementering av inre punktmetoder för kvantrelativ entropi" (2023).
arXiv: 2312.07438

[22] Lei Yangand Kim-Chuan Toh "Bregman proximal punktalgoritm återbesökt: En ny inexakt version och dess tröghetsvariant" SIAM Journal on Optimization 32, 1523–1554 (2022).
https: / / doi.org/ 10.1137 / 20M1360748

[23] Nilanjana Datta, Min-Hsiu Hsieh, Mark M Wilde och 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 Khanian och Andreas Winter "A rate-distortion perspective on quantum state redistribution" (2021).
arXiv: 2112.11952

[26] Zahra Baghali Khanian, Kohdai Kuroiwa och 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. Nielsen och 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 "Konvex analys" Princeton University Press (1970).
https://​/​doi.org/​10.1007/​bfb0110040

[31] Lev M Bregman "The relaxation method of find the common point of convex sets and its application to the solution of problem in convex programmering" 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 och 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öcker och 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 Fulton och 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 "Introduktion till kompakta transformationsgrupper" Academic Press (1972).
https:/​/​doi.org/​10.1016/​s0079-8169(08)x6007-6

[37] Persi Diaconis och Steven Evans "Linjära funktionaler av egenvärden för slumpmässiga matriser" Transaktioner från American Mathematical Society 353, 2615–2633 (2001).
https:/​/​doi.org/​10.1090/​S0002-9947-01-02800-8

[38] Masahito Hayashi och Yuxiang Yang "Effektiva algoritmer för kvantinformationsflaskhals" 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 ”Ämnen i matrisanalys” Cambridge University Press (1991).
https: / / doi.org/ 10.1017 / cbo9780511840371

[41] Mikhail V Solodovand Benar Fux Svaiter "Felgränser för proximala punkts underproblem och associerade inexakta proximala punktalgoritmer" Mathematical Programming 88, 371–389 (2000).
https: / ⠀ </ ⠀ <doi.org/†<10.1007 / ⠀ <s101070050022

[42] Mark Schmidt, Nicolas Roux och Francis Bach, "Konvergenshastigheter för inexakta proximala gradientmetoder för konvex optimering" Framsteg i 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 och Reha H Tütüncü, "SDPT3 — A MATLAB-programpaket för semidefinite programmering, version 1.3" Optimization Methods and Software 11, 545–581 (1999).
https: / / doi.org/ 10.1080 / 10556789908805762

[46] Masahito Hayashi och Geng Liu "Generaliserad kvant Arimoto-Blahut-algoritm och dess tillämpning på kvantinformationsflaskhals" (2023).
arXiv: 2311.11188

[47] Thomas M. Cover och 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 – Volym 28 427–435 (2013).
https: / / dl.acm.org/ doi / 10.5555 / 3042817.3042867

[50] Haobo Liand Ning Cai "A Blahut-Arimoto-typalgoritm för beräkning av klassisk kvantkanalkapacitet" 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 och 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 Bauschke och Jonathan M Borwein "Legendre-funktioner och metoden för slumpmässiga Bregman-projektioner" 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

Citerad av

[1] Mehdi Karimi och Levent Tuncel, "Effektiv implementering av Interior-Point Methods for Quantum Relative Entropy", arXiv: 2312.07438, (2023).

[2] Masahito Hayashi och Geng Liu, "Generaliserad kvant Arimoto-Blahut-algoritm och dess tillämpning på kvantinformationsflaskhals", arXiv: 2311.11188, (2023).

Ovanstående citat är från SAO / NASA ADS (senast uppdaterad framgångsrikt 2024-04-10 23:59:34). Listan kan vara ofullständig eftersom inte alla utgivare tillhandahåller lämpliga och fullständiga citatdata.

On Crossrefs citerade service Inga uppgifter om citerande verk hittades (sista försök 2024-04-10 23:59:33).

Detta papper publiceras i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Upphovsrätten kvarstår med de ursprungliga upphovsrättsinnehavarna som författarna eller deras institutioner.

Tidsstämpel:

Mer från Quantum Journal