Effektiv beregning af Quantum Rate-Distortion-funktionen

Effektiv beregning af Quantum Rate-Distortion-funktionen

Tidsstempel: 9. april 2024 kl. 7
Kildeknude: 2540661

Kerry He1, James Saunderson1, og Hamza Fawzi2

1Department of Electrical and Computer System Engineering, Monash University, Clayton VIC 3800, Australien
2Institut for anvendt matematik og teoretisk fysik, University of Cambridge, Cambridge CB3 0WA, Storbritannien

Finder du denne artikel interessant eller vil du diskutere? Scite eller efterlade en kommentar på SciRate.

Abstrakt

Kvantehastighedsforvrængningsfunktionen spiller en fundamental rolle i kvanteinformationsteorien, men der er i øjeblikket ingen praktisk algoritme, som effektivt kan beregne denne funktion med høj nøjagtighed for moderate kanaldimensioner. I dette papir viser vi, hvordan symmetrireduktion markant kan forenkle almindelige forekomster af problemer med sammenfiltringsassisteret kvantehastighedsforvrængning. Dette giver os mulighed for bedre at forstå egenskaberne af kvantekanalerne, som opnår den optimale hastighed-forvrængning-afvejning, samtidig med at det tillader mere effektiv beregning af kvantehastighedsforvrængningsfunktionen uanset den numeriske algoritme, der anvendes. Derudover foreslår vi en upræcis variant af spejlnedstigningsalgoritmen til at beregne kvantehastighedsforvrængningsfunktionen med beviselige sublineære konvergenshastigheder. Vi viser, hvordan denne spejldescent-algoritme er relateret til Blahut-Arimoto og forventningsmaksimeringsmetoder, der tidligere blev brugt til at løse lignende problemer i informationsteori. Ved hjælp af disse teknikker præsenterer vi de første numeriske eksperimenter til at beregne en multi-qubit kvantehastighedsforvrængningsfunktion og viser, at vores foreslåede algoritme løser hurtigere og med højere nøjagtighed sammenlignet med eksisterende metoder.

Populært resumé

Kvantehastighedsforvrængningsfunktionen beskriver den maksimale mængde en kvanteinformationskilde kan komprimeres af en kvantekanal uden at overskride en maksimalt tilladt forvrængning. Generelt skal denne funktion beregnes numerisk ved at løse et konveks optimeringsproblem. Dette kan dog være udfordrende af to grunde. For det første bliver problemdimensionen af ​​optimeringsproblemet hurtigt stor i takt med at størrelsen af ​​kvantekanalen øges. For almindelige metoder til måling af forvrængning af kvanteinformationskilden viser vi, hvordan symmetrier i optimeringsproblemet kan udnyttes til at reducere dimensionen af ​​optimeringsproblemet væsentligt, hvilket giver os mulighed for at løse problemet meget hurtigere. For det andet fungerer standard gradient descent-algoritmer ikke godt, når man beregner kvantehastighedsforvrængningsfunktionen, på grund af de kvanteentropi-lignende funktioner, der opstår i optimeringsproblemet. I stedet viser vi, hvordan en entropisk variation af gradientnedstigning, kendt som entropisk spejlnedstigning, kan bruges til at udlede en effektiv algoritme til at beregne kvantehastighedsforvrængningsfunktionen.

► BibTeX-data

► Referencer

[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 og Mark M. Wilde, "Kvantehastighedsforvrængning, omvendte Shannon-sætninger og kildekanalseparation" 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 og 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 "Beregning af kanalkapacitet og hastighedsforvrængningsfunktioner" IEEE Transactions on Information Theory 18, 460-473 (1972).
https://​/​doi.org/​10.1109/​tit.1972.1054855

[5] Suguru Arimoto "En algoritme til beregning af kapaciteten af ​​vilkårlige diskrete hukommelsesløse kanaler" IEEE Transactions on Information Theory 18, 14-20 (1972).
https://​/​doi.org/​10.1109/​tit.1972.1054753

[6] Kerry He, James Saunderson og Hamza Fawzi, "Et Bregman proksimalt perspektiv på klassiske og kvante Blahut-Arimoto-algoritmer" (2023).
arXiv: 2306.04492

[7] Arkadij Semenovič Nemirovskijan og David Borisovich Yudin "Problemkompleksitet og metodeeffektivitet i optimering" Wiley (1983).

[8] Amir Beckand Marc Teboulle "Mirror descent and non-linear 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 accelererede proksimale gradientmetoder til konveks-konkav optimering" rapport (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 og 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 og Yurii Nesterov, "Relativ glat konveks optimering ved første-ordens metoder og applikationer" 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 divergens baseret em-algoritme og dens anvendelse på klassisk og kvantehastighedsforvrængningsteori" IEEE Transactions on Information Theory 69, 3460–3492 (2023).
https://​/​doi.org/​10.1109/​tit.2023.3239955

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

[16] Venkat Chandrasekaran og Parikshit Shah "Relativ entropioptimering og dens applikationer" Matematisk 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 og Pablo A Parrilo, "Semidefinite approximations of the matrix logaritm" Fundamenter for beregningsmatematik 19, 259-296 (2019).
https:/​/​doi.org/​10.1007/​s10208-018-9385-0

[19] Chris Coey, Lea Kapelevich og Juan Pablo Vielma, "Ydeevneforbedringer for en generisk konisk indvendig punktalgoritme" Mathematical Programming Computation 15, 53-101 (2023).
https:/​/​doi.org/​10.1007/​s12532-022-00226-0

[20] Mehdi Karimiand Levent Tunçel "Primal-dobbelt indre-punkt metoder til domænedrevne formuleringer" Mathematics of Operations Research 45, 591-621 (2020).
https://​/​doi.org/​10.1287/​moor.2019.1003

[21] Mehdi Karimiand Levent Tuncel "Effektiv implementering af indre-punkt metoder til kvante relativ entropi" (2023).
arXiv: 2312.07438

[22] Lei Yangand Kim-Chuan Toh "Bregman proksimale punktalgoritme revisited: A new unexact 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 og 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 og Andreas Winter "A rate-distortion perspective on quantum state redistribution" (2021).
arXiv: 2112.11952

[26] Zahra Baghali Khanian, Kohdai Kuroiwa og 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 og Isaac L. Chuang "Kvanteberegning og kvanteinformation: 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 "Konveks analyse" Princeton University Press (1970).
https:/​/​doi.org/​10.1007/​bfb0110040

[31] Lev M Bregman "Afslapningsmetoden til at finde det fælles punkt for konvekse sæt og dets anvendelse på løsning af problemer i konveks 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 og 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 "Konveks optimeringsteori" Athena Scientific (2009).

[34] Theodor Bröcker og Tammo Tom Dieck "Repræsentationer af kompakte Lie-grupper" Springer Science & Business Media (2013).
https:/​/​doi.org/​10.1007/​978-3-662-12918-0

[35] William Fulton og Joe Harris "Repræsentationsteori: Et første kursus" Springer Science & Business Media (2013).
https:/​/​doi.org/​10.1007/​978-1-4612-0979-9

[36] Glen E Bredon "Introduktion til kompakte transformationsgrupper" Academic Press (1972).
https:/​/​doi.org/​10.1016/​s0079-8169(08)x6007-6

[37] Persi Diaconis og Steven Evans "Lineære funktionaler af egenværdier af tilfældige matricer" Transaktioner fra American Mathematical Society 353, 2615-2633 (2001).
https:/​/​doi.org/​10.1090/​S0002-9947-01-02800-8

[38] Masahito Hayashi og Yuxiang Yang "Effektive algoritmer til flaskehals med kvanteinformation" 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 "Emner i matrixanalyse" Cambridge University Press (1991).
https://​/​doi.org/​10.1017/​cbo9780511840371

[41] Mikhail V Solodovand Benar Fux Svaiter "Fejlgrænser for proksimale punktunderproblemer og tilhørende upræcise proksimale punktalgoritmer" Mathematical Programming 88, 371-389 (2000).
https://doi.org/​10.1007/​s101070050022

[42] Mark Schmidt, Nicolas Roux og Francis Bach, "Konvergenshastigheder for upræcise proksimale gradientmetoder til konveks optimering" Fremskridt i Neurale Informationsbehandlingssystemer 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 "Numerisk optimering" 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 og Reha H Tütüncü, "SDPT3 — En MATLAB-softwarepakke til semidefinite programmering, version 1.3" Optimization Methods and Software 11, 545-581 (1999).
https://​/​doi.org/​10.1080/​10556789908805762

[46] Masahito Hayashi og Geng Liu "Generaliseret kvante Arimoto-Blahut-algoritme og dens anvendelse på kvanteinformationsflaskehals" (2023).
arXiv: 2311.11188

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

[50] Haobo Liand Ning Cai “A Blahut-Arimoto type algoritme 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 og 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 og Jonathan M Borwein "Legendre-funktioner og metoden til tilfældige Bregman-projektioner" Journal of Convex Analysis 4, 27-67 (1997).

[53] Rajendra Bhatia "Matrix analyse" Springer Science & Business Media (2013).
https:/​/​doi.org/​10.1007/​978-1-4612-0653-8

Citeret af

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

[2] Masahito Hayashi og Geng Liu, "Generaliseret kvante Arimoto-Blahut algoritme og dens anvendelse på kvanteinformation flaskehals", arXiv: 2311.11188, (2023).

Ovenstående citater er fra SAO/NASA ADS (sidst opdateret 2024-04-10 11:56:15). Listen kan være ufuldstændig, da ikke alle udgivere leverer passende og fuldstændige citatdata.

On Crossrefs citeret af tjeneste ingen data om at citere værker blev fundet (sidste forsøg 2024-04-10 11:56:14).

Dette papir er udgivet i Quantum under Creative Commons Attribution 4.0 International (CC BY 4.0) licens. Ophavsretten forbliver hos de originale copyright-indehavere, såsom forfatterne eller deres institutioner.

Tidsstempel:

Mere fra Quantum Journal