Institutul de fizică teoretică, ETH Zürich, Elveția
Găsiți această lucrare interesant sau doriți să discutați? Scite sau lasă un comentariu la SciRate.
Abstract
Recent, Renes a propus un algoritm cuantic numit propagarea credinței cu mesaje cuantice (BPQM) pentru decodarea datelor clasice codificate folosind un cod liniar binar cu grafic Tanner arbore care este transmis pe un canal CQ în stare pură.1], adică un canal cu intrare clasică și ieșire cuantică în stare pură. Algoritmul prezintă o adevărată contrapartidă cuantică la decodare bazată pe algoritmul clasic de propagare a credinței, care a găsit un mare succes în teoria clasică a codificării atunci când este utilizat împreună cu codurile LDPC sau Turbo. Mai recent, Rengaswamy $et$ $al.$ [2] a observat că BPQM implementează decodorul optim pe un exemplu de cod mic, prin faptul că implementează măsurarea optimă care distinge stările de ieșire cuantice pentru setul de cuvinte de cod de intrare cu cea mai mare probabilitate realizabilă. Aici extindem semnificativ înțelegerea, formalismul și aplicabilitatea algoritmului BPQM cu următoarele contribuții. În primul rând, demonstrăm analitic că BPQM realizează decodarea optimă pentru orice cod liniar binar cu graficul Tanner arbore. De asemenea, oferim prima descriere formală a algoritmului BPQM în detaliu și fără nicio ambiguitate. Procedând astfel, identificăm un defect cheie trecut cu vederea în algoritmul original și lucrările ulterioare care implică realizările circuitelor cuantice vor fi exponențial mari în dimensiunea codului. Deși BPQM transmite mesaje cuantice, alte informații solicitate de algoritm sunt procesate la nivel global. Remediem această problemă prin formularea unui algoritm cu adevărat de transmitere a mesajelor care aproximează BPQM și are complexitatea circuitului cuantic $mathcal{O}(text{poly } n, text{polylog } frac{1}{epsilon})$, unde $n$ este lungimea codului și $epsilon$ este eroarea de aproximare. În cele din urmă, propunem, de asemenea, o nouă metodă pentru extinderea BPQM la grafice factorizate care conțin cicluri prin utilizarea clonării aproximative. Arătăm câteva rezultate numerice promițătoare care indică faptul că BPQM pe graficele factorilor cu cicluri poate depăși semnificativ cel mai bun decodor clasic posibil.
► Date BibTeX
► Referințe
[1] Joseph M. Renes „Belief Propagation Decoding of Quantum Channels by Passing Quantum Messages” New Journal of Physics 19, 072001 (2017).
https://doi.org/10.1088/1367-2630/aa7c78
arXiv: 1607.04833
http://stacks.iop.org/1367-2630/19/i=7/a=072001
[2] Narayanan Rengaswamy, Kaushik P. Seshadreesan, Saikat Guha și Henry D. Pfister, „Propagarea credinței cu mesaje cuantice pentru comunicații clasice îmbunătățite cuantic” npj Quantum Information 7, 97 (2021).
https://doi.org/10.1038/s41534-021-00422-1
arXiv: 2003.04356
https:///www.nature.com/articles/s41534-021-00422-1
[3] S. Kudekar, T. Richardson și RL Urbanke, „Spatially Coupled Ensembles Universally Achieve Capacity Under Belief Propagation” IEEE Transactions on Information Theory 59, 7761–7813 (2013).
https: / / doi.org/ 10.1109 / TIT.2013.2280915
arXiv: 1201.2999
[4] HA Loeliger și PO Vontobel „Grafice factori pentru probabilități cuantice” Tranzacții IEEE privind teoria informației 63, 5642–5665 (2017).
https: / / doi.org/ 10.1109 / TIT.2017.2716422
arXiv: 1508.00689
[5] MX Cao și PO Vontobel „Grafice de factori cu două margini: definiție, proprietăți și exemple” 2017 IEEE Information Theory Workshop (ITW) 136–140 (2017).
https:///doi.org/10.1109/ITW.2017.8277985
arXiv: 1706.00752
[6] Hans-Andrea Loeliger „O introducere în graficele factorilor” IEEE Signal Processing Magazine 21, 28–41 (2004).
https: / / doi.org/ 10.1109 / MSP.2004.1267047
[7] VP Belavkin „Optimal Multiple Quantum Statistical Hypothesis Testing” Stochastics 1, 315 (1975).
https: / / doi.org/ 10.1080 / 17442507508833114
[8] Paul Hausladen și William K. Wootters „A `Pretty Good' Measurement for Distinguishing Quantum States” Journal of Modern Optics 41, 2385 (1994).
https: / / doi.org/ 10.1080 / 09500349414552221
[9] Narayanan Rengaswamy și Henry D. Pfister „O dovadă semiclasică a dualității între BSC clasic și PSC cuantic” (2021).
https:///doi.org/10.48550/arXiv.2103.09225
arXiv: 2103.09225
[10] Masashi Ban, Keiko Kurokawa, Rei Momose și Osamu Hirota, „Măsurări optime pentru discriminarea între statele cuantice simetrice și estimarea parametrilor” Jurnalul Internațional de Fizică Teoretică 36, 1269–1288 (1997).
https: / / doi.org/ 10.1007 / BF02435921
[11] Masahide Sasaki, Kentaro Kato, Masayuki Izutsu și Osamu Hirota, „Canale cuantice care arată superadditivitatea în capacitatea clasică” Physical Review A 58, 146–158 (1998).
https: / / doi.org/ 10.1103 / PhysRevA.58.146
[12] YC Eldar și Jr. Forney „Despre detectarea cuantică și măsurarea rădăcinii pătrate” IEEE Transactions on Information Theory 47, 858–872 (2001).
https: / / doi.org/ 10.1109 / 18.915636
[13] Tom Richardson și Rüdiger Urbanke „Modern Coding Theory” Cambridge University Press (2008).
https: / / doi.org/ 10.1017 / CBO9780511791338
[14] David Poulin „Decodificarea optimă și eficientă a codurilor de blocuri cuantice concatenate” Physical Review A 74, 052333 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.052333
[15] David Poulin și Yeojin Chung „Despre decodificarea iterativă a codurilor cuantice rare” Informații și calcule cuantice 8, 987–1000 (2008).
https: / / doi.org/ 10.26421 / QIC8.10-8
arXiv: 0801.1241
[16] Yun-Jiang Wang, Barry C. Sanders, Bao-Ming Bai și Xin-Mei Wang, „Enhanced Feedback Iterative Decoding of Sparse Quantum Codes” IEEE Transactions on Information Theory 58, 1231–1241 (2012).
https: / / doi.org/ 10.1109 / TIT.2011.2169534
arXiv: 0912.4546
[17] Ben Criger și Imran Ashraf „Sumare cu mai multe căi pentru decodarea codurilor topologice 2D” Quantum 2, 102 (2018).
https://doi.org/10.22331/q-2018-10-19-102
arXiv: 1709.02154
[18] Ye-Hua Liu și David Poulin „Decodoare de propagare a credințelor neuronale pentru coduri de corectare a erorilor cuantice” Physical Review Letters 122, 200501 (2019).
https: / / doi.org/ 10.1103 / PhysRevLett.122.200501
arXiv: 1811.07835
[19] Alex Rigby, JC Olivier și Peter Jarvis, „Decodoare modificate de propagare a credinței pentru coduri de verificare a parității cu densitate scăzută” Physical Review A 100, 012330 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.100.012330
arXiv: 1903.07404
[20] Pavel Panteleev și Gleb Kalachev „Coduri LDPC cuantice degenerate cu performanțe bune de lungime finită” Quantum 5, 585 (2021).
https://doi.org/10.22331/q-2021-11-22-585
[21] July X. Li și Pascal O. Vontobel „Decodarea pe bază de pseudocod a codurilor stabilizatoarelor cuantice” 2019 Simpozionul internațional IEEE privind teoria informației (ISIT) 2888–2892 (2019).
https: / / doi.org/ 10.1109 / ISIT.2019.8849833
arXiv: 1903.01202
[22] Joschka Roffe, David R. White, Simon Burton și Earl Campbell, „Decoding across the Quantum Low-Density Parity-Check Code Landscape” Physical Review Research 2, 043423 (2020).
https: / / doi.org/ 10.1103 / PhysRevResearch.2.043423
arXiv: 2005.07016
[23] July X. Li, Joseph M. Renes și Pascal O. Vontobel, „Decodarea pe bază de pseudocod a codurilor de culoare cuantice” (2020).
https:///doi.org/10.48550/arXiv.2010.10845
arXiv: 2010.10845
[24] Srikar Kasi și Kyle Jamieson „Către propagarea credinței cuantice pentru decodarea LDPC în rețelele fără fir” Proceedings of the 26th Annual International Conference on Mobile Computing and Networking 1–14 (2020).
https: / / doi.org/ 10.1145 / 3372224.3419207
arXiv: 2007.11069
[25] MS Leifer și D. Poulin „Modele grafice cuantice și propagarea credințelor” Annals of Physics 323, 1899–1946 (2008).
https: / / doi.org/ 10.1016 / j.aop.2007.10.001
arXiv: 0708.1337
http: / / www.sciencedirect.com/ știință / article / PII / S0003491607001509
[26] HA Bethe „Teoria statistică a superrețelelor” Proceedings of the Royal Society A 150, 552–575 (1935).
https: / / doi.org/ 10.1098 / rspa.1935.0122
http:///rspa.royalsocietypublishing.org/content/150/871/552
[27] Rudolf Peierls „Teoria statistică a superrețelelor cu concentrații inegale ale componentelor” Proceedings of the Royal Society A 154, 207–222 (1936).
https: / / doi.org/ 10.1098 / rspa.1936.0047
[28] Jonathan S. Yedidia, William T. Freeman și Yair Weiss, „Generalized Belief Propagation” Proceedings of the 13th International Conference on Neural Information Processing Systems 668–674 (2000).
[29] Jonathan S. Yedidia, William T. Freeman și Yair Weiss, „Understanding Belief Propagation and Its Generalizations” Morgan Kaufmann Publishers Inc. (2003).
https:///www.merl.com/publications/docs/TR2001-22.pdf
[30] JS Yedidia, WT Freeman și Y. Weiss, „Constructing Free-Energy Aproximations and Generalized Belief Propagation Algorithms” Teoria informațiilor, IEEE Transactions on 51, 2282–2312 (2005).
https: / / doi.org/ 10.1109 / TIT.2005.850085
[31] MB Hastings „Propagarea credinței cuantice: un algoritm pentru sistemele cuantice termice” Revista fizică B 76, 201102 (2007).
https: / / doi.org/ 10.1103 / PhysRevB.76.201102
arXiv: 0706.4094
[32] David Poulin și Matthew B. Hastings „Markov Entropy Descomposition: A Variational Dual for Quantum Belief Propagation” Physical Review Letters 106, 080403 (2011).
https: / / doi.org/ 10.1103 / PhysRevLett.106.080403
arXiv: 1012.2050
[33] MX Cao și PO Vontobel „Grafici cuantici ai factorilor: operațiune de închidere a cutiei și abordări variaționale” Simpozion internațional 2016 privind teoria informației și aplicațiile sale (ISITA) 651–655 (2016).
https:///ieeexplore.ieee.org/document/7840505
[34] FR Kschischang, BJ Frey și HA Loeliger, „Grafice factorial și algoritmul sumă-produs” IEEE Transactions on Information Theory 47, 498–519 (2001).
https: / / doi.org/ 10.1109 / 18.910572
[35] G. David Forney „Codes on Graphs: Normal Realizations” IEEE Transactions on Information Theory 47, 520–548 (2001).
https: / / doi.org/ 10.1109 / 18.910573
[36] CW Helstrom „Detecția cuantică și teoria estimării” Academic (1976).
https://doi.org/10.1016/S0076-5392(08)60247-7
http:///www.sciencedirect.com/science/bookseries/00765392/123
[37] Saikat Guha „Receptorii optici structurați pentru a atinge capacitatea superaditivă și limita Holevo” Physical Review Letters 106, 240502 (2011).
https: / / doi.org/ 10.1103 / PhysRevLett.106.240502
arXiv: 1101.1550
[38] T. Etzion, A. Trachtenberg și A. Vardy, „Which Codes Have Cycle-Free Tanner Graphs?” IEEE Transactions on Information Theory 45, 2173–2181 (1999).
https: / / doi.org/ 10.1109 / 18.782170
[39] Jacob C. Bridgeman și Christopher T. Chubb „Hand-Waving and Interpretative Dance: An Introductory Course on Tensor Networks” Journal of Physics A: Mathematical and Theoretical 50, 223001 (2017).
https://doi.org/10.1088/1751-8121/aa6dc3
arXiv: 1603.03039
http://stacks.iop.org/1751-8121/50/i=22/a=223001
[40] Ville Bergholm, Juha J. Vartiainen, Mikko Mottonen și Martti M. Salomaa, „Circuite cuantice cu porți de un qubit controlate uniform” Physical Review A 71, 052330 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.052330
http: / / arxiv.org/ abs / quant-ph / 0410066
[41] CH Bennett „Reversibilitatea logică a calculului” IBM Journal of Research and Development 17, 525–532 (1973).
https: / / doi.org/ 10.1147 / rd.176.0525
[42] Richard P. Brent „Multiple-Precision Zero-Finding Methods and the Complexity of Elementary Function Evaluation” Academic Press (1976).
https://doi.org/10.1016/B978-0-12-697560-4.50014-9
arXiv: 1004.3412
https:///www.sciencedirect.com/science/article/pii/B9780126975604500149
[43] Harvey și van der Hoeven „Înmulțirea întregului în timp O(n Log n)” Annals of Mathematics 193, 563 (2021).
https: / / doi.org/ 10.4007 / annals.2021.193.2.4
[44] Yudong Cao, Anargyros Papageorgiou, Iasonas Petras, Joseph Traub și Sabre Kais, „Algoritmul cuantic și proiectarea circuitelor Solving the Poisson Equation” New Journal of Physics 15, 013021 (2013).
https://doi.org/10.1088/1367-2630/15/1/013021
arXiv: 1207.2485
[45] Mihir K. Bhaskar, Stuart Hadfield, Anargyros Papageorgiou și Iasonas Petras, „Quantum Algorithms and Circuits for Scientific Computing” Quantum Information & Computation 16, 197–236 (2016).
https: / / doi.org/ 10.26421 / QIC16.3-4-2
arXiv: 1511.08253
[46] Thomas Häner, Martin Roetteler și Krysta M. Svore, „Optimizing Quantum Circuits for Arithmetic” (2018).
https:///doi.org/10.48550/arXiv.1805.12445
arXiv: 1805.12445
[47] Shengbin Wang, Zhimin Wang, Wendong Li, Lixin Fan, Guolong Cui, Zhiqiang Wei și Yongjian Gu, „Proiectarea circuitelor cuantice pentru evaluarea funcțiilor transcendentale pe baza unei metode de expansiune binară a valorii funcției” Procesarea informațiilor cuantice 19, 347 (2020).
https://doi.org/10.1007/s11128-020-02855-7
arXiv: 2001.00807
[48] John Watrous „Theory of Quantum Information” Cambridge University Press (2018).
https: / / doi.org/ 10.1017 / 9781316848142
https:///www.cambridge.org/core/product/identifier/9781316848142/type/book
[49] Dagmar Bruß, David P. DiVincenzo, Artur Ekert, Christopher A. Fuchs, Chiara Macchiavello și John A. Smolin, „Optimal Universal and State-Dependent Quantum Cloning” Physical Review A 57, 2368–2378 (1998).
https: / / doi.org/ 10.1103 / PhysRevA.57.2368
[50] E. Arıkan „Polarizarea canalului: o metodă de construire a codurilor de realizare a capacității pentru canalele fără memorie cu intrare binară simetrică” Tranzacții IEEE privind teoria informației 55, 3051–3073 (2009).
https: / / doi.org/ 10.1109 / TIT.2009.2021379
arXiv: 0807.3917
[51] Mark M. Wilde și Saikat Guha „Coduri polare pentru canalele clasice-cuantice” IEEE Transactions on Information Theory 59, 1175–1187 (2013).
https: / / doi.org/ 10.1109 / TIT.2012.2218792
arXiv: 1109.2591
[52] Joseph M. Renes și Mark M. Wilde „Coduri polare pentru comunicare privată și cuantică prin canale arbitrare” Tranzacții IEEE privind teoria informației 60, 3090–3103 (2014).
https: / / doi.org/ 10.1109 / TIT.2014.2314463
arXiv: 1212.2537
[53] S. Guha și MM Wilde „Polar Coding to Achieve the Holevo Capacity of a Pure-Loss Optical Channel” Proceedings of the 2012 IEEE International Symposium on Information Theory (ISIT) 546–550 (2012).
https: / / doi.org/ 10.1109 / ISIT.2012.6284250
arXiv: 1202.0533
Citat de
[1] S. Brandsen, Avijit Mandal și Henry D. Pfister, „Belief Propagation with Quantum Messages for Symmetric Classical-Quantum Channels”, arXiv: 2207.04984.
Citatele de mai sus sunt din ADS SAO / NASA (ultima actualizare cu succes 2022-08-23 14:04:15). Lista poate fi incompletă, deoarece nu toți editorii furnizează date de citare adecvate și complete.
Nu a putut să aducă Date citate încrucișate în ultima încercare 2022-08-23 14:04:14: Nu s-au putut prelua date citate pentru 10.22331 / q-2022-08-23-784 de la Crossref. Acest lucru este normal dacă DOI a fost înregistrat recent.
Acest Lucru este publicat în Quantum sub Creative Commons Atribuire 4.0 internațională (CC BY 4.0) licență. Drepturile de autor rămân la deținătorii de drepturi de autor originale, precum autorii sau instituțiile lor.
