Teoreetilise Füüsika Instituut, ETH Zürich, Šveits
Kas see artikkel on huvitav või soovite arutada? Scite või jätke SciRate'i kommentaar.
Abstraktne
Hiljuti pakkus Renes välja kvantalgoritmi, mida nimetatakse uskumuste levitamiseks kvantsõnumitega (BPQM), et dekodeerida klassikalisi andmeid, mis on kodeeritud binaarse lineaarse koodi abil koos puu Tanneri graafikuga, mis edastatakse puhta oleku CQ kanali kaudu [1], st klassikalise sisendi ja puhta oleku kvantväljundiga kanal. Algoritm kujutab endast tõelist kvantvastast dekodeerimisele, mis põhineb klassikalisel uskumuse levitamise algoritmil, mis on klassikalise kodeerimise teoorias leidnud laialdast edu, kui seda kasutatakse koos LDPC või Turbo koodidega. Viimasel ajal Rengaswamy $et$ $al.$ [2] täheldas, et BPQM rakendab väikesel näitekoodil optimaalset dekoodrit, kuna see rakendab optimaalset mõõtmist, mis eristab sisendkoodisõnade komplekti kvantväljundi olekuid suurima saavutatava tõenäosusega. Siin laiendame oluliselt BPQM-i algoritmi mõistmist, formalismi ja rakendatavust järgmiste panustega. Esiteks tõestame analüütiliselt, et BPQM realiseerib puu Tanneri graafikuga mis tahes binaarse lineaarse koodi optimaalse dekodeerimise. Pakume ka BPQM-i algoritmi esimest ametlikku kirjeldust üksikasjalikult ja ilma ühegi kahemõttelisuseta. Seda tehes tuvastame algses algoritmis tähelepanuta jäetud peamise vea ja järgnevad tööd, mis eeldavad, et kvantahela realisatsioonid on koodi mõõtmes eksponentsiaalselt suured. Kuigi BPQM edastab kvantsõnumeid, töödeldakse muud algoritmi nõutavat teavet globaalselt. Lahendame selle probleemi, formuleerides tõelise sõnumiedastusalgoritmi, mis on ligikaudne BPQM ja mille kvantahela keerukus on $mathcal{O}(text{poly } n, text{polylog } frac{1}{epsilon})$, kus $n$ on koodi pikkus ja $epsilon$ on lähendusviga. Lõpuks pakume välja ka uudse meetodi BPQM laiendamiseks tsükleid sisaldavatele faktorigraafikutele, kasutades ligikaudset kloonimist. Näitame mõningaid paljutõotavaid arvulisi tulemusi, mis näitavad, et BPQM tsüklitega faktorigraafikutel võib märkimisväärselt ületada parimat võimalikku klassikalist dekoodrit.
► BibTeX-i andmed
► Viited
[1] Joseph M. Renes “Kvantkanalite uskumuste levitamise dekodeerimine kvantsõnumite edastamise teel” 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 ja Henry D. Pfister, „Uskumuste levitamine kvantsõnumitega kvant-täiustatud klassikalise suhtluse jaoks” 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 ja 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 ja PO Vontobel “Kvanttõenäosuste faktorigraafikud” IEEE Transactions on Information Theory 63, 5642–5665 (2017).
https:///doi.org/10.1109/TIT.2017.2716422
arXiv: 1508.00689
[5] MX Cao ja PO Vontobel “Kaheservalised tegurigraafikud: definitsioon, omadused ja näited” 2017 IEEE teabeteooria töötuba (ITW) 136–140 (2017).
https:///doi.org/10.1109/ITW.2017.8277985
arXiv: 1706.00752
[6] Hans-Andrea Loeliger “Sissejuhatus faktorigraafikutesse” IEEE Signal Processing Magazine 21, 28–41 (2004).
https:///doi.org/10.1109/MSP.2004.1267047
[7] VP Belavkin “Optimaalne mitme kvantstatistilise hüpoteesi testimine” Stochastics 1, 315 (1975).
https:///doi.org/10.1080/17442507508833114
[8] Paul Hausladen ja William K. Wootters "Päris hea mõõtmine kvantseisundite eristamiseks" Journal of Modern Optics 41, 2385 (1994).
https:///doi.org/10.1080/09500349414552221
[9] Narayanan Rengaswamy ja Henry D. Pfister “A Semiclassical Proof of Duality Between the Classical BSC and the Quantum PSC” (2021).
https:///doi.org/10.48550/arXiv.2103.09225
arXiv: 2103.09225
[10] Masashi Ban, Keiko Kurokawa, Rei Momose ja Osamu Hirota, “Optimum Measurements for Discrimination among Symmetric Quantum States and Parameter Estimation” International Journal of Theoretical Physics 36, 1269–1288 (1997).
https:///doi.org/10.1007/BF02435921
[11] Masahide Sasaki, Kentaro Kato, Masayuki Izutsu ja Osamu Hirota, "Quantum Channels Showing Superadditiivity in Classical Capacity" Physical Review A 58, 146–158 (1998).
https:///doi.org/10.1103/PhysRevA.58.146
[12] YC Eldar ja Jr. Forney "Kvanttuvastusest ja ruutjuure mõõtmisest" IEEE Transactions on Information Theory 47, 858–872 (2001).
https:///doi.org/10.1109/18.915636
[13] Tom Richardson ja Rüdiger Urbanke “Modern Coding Theory” Cambridge University Press (2008).
https:///doi.org/10.1017/CBO9780511791338
[14] David Poulin “Konkateneeritud kvantplokikoodide optimaalne ja tõhus dekodeerimine” füüsiline ülevaade A 74, 052333 (2006).
https:///doi.org/10.1103/PhysRevA.74.052333
[15] David Poulin ja Yeojin Chung “Hõredate kvantkoodide iteratiivsest dekodeerimisest” Quantum Information and Computation 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 ja 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 ja Imran Ashraf "Multi-Path Summation for Decoding 2D topological Codes" Quantum 2, 102 (2018).
https://doi.org/10.22331/q-2018-10-19-102
arXiv: 1709.02154
[18] Ye-Hua Liu ja David Poulin “Neuraalsed uskumuste leviku dekoodrid kvantviga parandavate koodide jaoks” Physical Review Letters 122, 200501 (2019).
https:///doi.org/10.1103/PhysRevLett.122.200501
arXiv: 1811.07835
[19] Alex Rigby, JC Olivier ja Peter Jarvis, „Modifitseeritud uskumuste levitamise dekoodrid kvant-madala tihedusega paarsuskontrolli koodide jaoks” Physical Review A 100, 012330 (2019).
https:///doi.org/10.1103/PhysRevA.100.012330
arXiv: 1903.07404
[20] Pavel Panteleev ja Gleb Kalatšev “Degenereerunud kvant-LDPC koodid hea piiratud pikkusega jõudlusega” Quantum 5, 585 (2021).
https://doi.org/10.22331/q-2021-11-22-585
[21] juuli X. Li ja Pascal O. Vontobel “Pseudocodeword-Based Decoding of Quantum Stabilizer Codes” 2019 IEEE International Symposium on Information Theory (ISIT) 2888–2892 (2019).
https:///doi.org/10.1109/ISIT.2019.8849833
arXiv: 1903.01202
[22] Joschka Roffe, David R. White, Simon Burton ja Earl Campbell, „Dekodeerimine üle kvant-madala tihedusega pariteedikontrolli koodi maastiku” Physical Review Research 2, 043423 (2020).
https:///doi.org/10.1103/PhysRevResearch.2.043423
arXiv: 2005.07016
[23] Juuli X. Li, Joseph M. Renes ja Pascal O. Vontobel, "Pseudocodeword-Based Decoding of Quantum Color Codes" (2020).
https:///doi.org/10.48550/arXiv.2010.10845
arXiv: 2010.10845
[24] Srikar Kasi ja Kyle Jamieson “Towards Quantum Belief Propagation for LDPC Decoding in Wireless Networks” 26. rahvusvahelise mobiilse andmetöötluse ja -võrkude aastakonverentsi materjalid 1–14 (2020).
https:///doi.org/10.1145/3372224.3419207
arXiv: 2007.11069
[25] MS Leifer ja D. Poulin “Quantum Graphical Models and Belief Propagation” Annals of Physics 323, 1899–1946 (2008).
https:///doi.org/10.1016/j.aop.2007.10.001
arXiv: 0708.1337
http:///www.sciencedirect.com/science/article/pii/S0003491607001509
[26] HA Bethe “Statistical Theory of Superlattices” 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 “Ebavõrdsete komponentide kontsentratsiooniga ülivõrede statistiline teooria” 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 ja Yair Weiss, “Generalized Belief Propagation” Proceedings of 13th International Conference on Neural Information Processing Systems 668–674 (2000).
[29] Jonathan S. Yedidia, William T. Freeman ja Yair Weiss, "Uskumuste leviku mõistmine ja selle üldistused" Morgan Kaufmann Publishers Inc. (2003).
https:///www.merl.com/publications/docs/TR2001-22.pdf
[30] JS Yedidia, WT Freeman ja Y. Weiss, "Vabaenergia lähenduste ja üldistatud uskumuste levitamise algoritmide ehitamine" teabeteooria, IEEE tehingud, 51, 2282–2312 (2005).
https:///doi.org/10.1109/TIT.2005.850085
[31] MB Hastings “Kvantide uskumuste levitamine: termiliste kvantsüsteemide algoritm” Physical Review B 76, 201102 (2007).
https:///doi.org/10.1103/PhysRevB.76.201102
arXiv: 0706.4094
[32] David Poulin ja Matthew B. Hastings “Markovi entroopia lagunemine: variatsiooniline duaal kvantusundi levitamiseks” Physical Review Letters 106, 080403 (2011).
https:///doi.org/10.1103/PhysRevLett.106.080403
arXiv: 1012.2050
[33] MX Cao ja PO Vontobel „Quantum Factor Graphs: Closing-the-Box Operation and Variational Approaches” 2016 International Symposium on Information Theory and Its Applications (ISITA) 651–655 (2016).
https:///ieeexplore.ieee.org/document/7840505
[34] FR Kschischang, BJ Frey ja HA Loeliger, "Factor Graphs and the Sum-Product Algorithm" IEEE Transactions on Information Theory 47, 498–519 (2001).
https:///doi.org/10.1109/18.910572
[35] G. David Forney “Graafikute koodid: normaalsed teostused” IEEE Transactions on Information Theory 47, 520–548 (2001).
https:///doi.org/10.1109/18.910573
[36] CW Helstrom “Kvantide tuvastamise ja hindamise teooria” akadeemiline (1976).
https://doi.org/10.1016/S0076-5392(08)60247-7
http:///www.sciencedirect.com/science/bookseries/00765392/123
[37] Saikat Guha "Struktureeritud optilised vastuvõtjad üliadditiivse võimsuse ja Holevo piiri saavutamiseks" Physical Review Letters 106, 240502 (2011).
https:///doi.org/10.1103/PhysRevLett.106.240502
arXiv: 1101.1550
[38] T. Etzion, A. Trachtenberg ja A. Vardy, „Millistel koodidel on tsüklivabad pruunistusgraafikud?” IEEE Transactions on Information Theory 45, 2173–2181 (1999).
https:///doi.org/10.1109/18.782170
[39] Jacob C. Bridgeman ja Christopher T. Chubb “Käega lehvitav ja tõlgendav tants: sissejuhatav kursus tensorvõrkude kohta” 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 ja Martti M. Salomaa, "Kvantahelad ühtlaselt juhitud ühe kubiti väravatega" Physical Review A 71, 052330 (2005).
https:///doi.org/10.1103/PhysRevA.71.052330
http:///arxiv.org/abs/quant-ph/0410066
[41] CH Bennett “Arvutamise loogiline pöörduvus” 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 ja van der Hoeven “Täisarvuline korrutamine ajas 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 ja Sabre Kais, "Kvantalgoritm ja vooluringide projekteerimine Poissoni võrrandi lahendamisel" 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 ja Iasonas Petras, "Kvantalgoritmid ja vooluringid teaduslikuks arvutamiseks" 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 ja Krysta M. Svore, "Optimizing Quantum Circuits for Aritmetic" (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 ja Yongjian Gu, "Kvantahelate disain transtsendentaalsete funktsioonide hindamiseks funktsiooni-väärtuse binaarlaienduse meetodil" Kvantinformatsiooni töötlemine (19, 347).
https://doi.org/10.1007/s11128-020-02855-7
arXiv: 2001.00807
[48] John Watrous “Kvantinformatsiooni teooria” 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 ja 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 „Kanalite polarisatsioon: sümmeetriliste binaarsisendiga mäluta kanalite suutlikkust tagavate koodide konstrueerimise meetod” IEEE Transactions on Information Theory 55, 3051–3073 (2009).
https:///doi.org/10.1109/TIT.2009.2021379
arXiv: 0807.3917
[51] Mark M. Wilde ja Saikat Guha „Polar Codes for Classical-Quantum Channels” IEEE Transactions on Information Theory 59, 1175–1187 (2013).
https:///doi.org/10.1109/TIT.2012.2218792
arXiv: 1109.2591
[52] Joseph M. Renes ja Mark M. Wilde “Polar Codes for Private and Quantum Communication Over Arbitrary Channels” IEEE Transactions on Information Theory 60, 3090–3103 (2014).
https:///doi.org/10.1109/TIT.2014.2314463
arXiv: 1212.2537
[53] S. Guha ja MM Wilde “Polar Coding to Achieve the Holevo Capacity of a Pure-Loss Optical Channel” 2012. aasta IEEE rahvusvahelise teabeteooria sümpoosioni (ISIT) toimetised, 546–550 (2012).
https:///doi.org/10.1109/ISIT.2012.6284250
arXiv: 1202.0533
Viidatud
[1] S. Brandsen, Avijit Mandal ja Henry D. Pfister, "Uskumuste levik kvantsõnumitega sümmeetriliste klassikaliste-kvantkanalite jaoks", arXiv: 2207.04984.
Ülaltoodud tsitaadid on pärit SAO/NASA KUULUTUSED (viimati edukalt värskendatud 2022-08-23 14:04:15). Loend võib olla puudulik, kuna mitte kõik väljaandjad ei esita sobivaid ja täielikke viiteandmeid.
Ei saanud tuua Ristviide viidatud andmete alusel viimase katse ajal 2022-08-23 14:04:14: 10.22331/q-2022-08-23-784 viidatud andmeid ei saanud Crossrefist tuua. See on normaalne, kui DOI registreeriti hiljuti.
See raamat on avaldatud Quantum all Creative Commons Attribution 4.0 International (CC BY 4.0) litsents. Autoriõigus jääb algsetele autoriõiguste valdajatele, näiteks autoritele või nende institutsioonidele.
