Inštitut za teoretično fiziko, ETH Zürich, Švica
Se vam zdi ta članek zanimiv ali želite razpravljati? Zaslišite ali pustite komentar na SciRate.
Minimalizem
Pred kratkim je Renes predlagal kvantni algoritem, imenovan širjenje prepričanj s kvantnimi sporočili (BPQM), za dekodiranje klasičnih podatkov, kodiranih z uporabo binarne linearne kode z drevesnim Tannerjevim grafom, ki se prenaša po kanalu CQ v čistem stanju [1], tj. kanal s klasičnim vhodom in kvantnim izhodom v čistem stanju. Algoritem predstavlja pristno kvantno protipostavko dekodiranju, ki temelji na klasičnem algoritmu širjenja prepričanj, ki je našel velik uspeh v klasični teoriji kodiranja, ko se uporablja v povezavi s kodami LDPC ali Turbo. Nedavno Rengaswamy $et$ $al.$ [2] opazil, da BPQM izvaja optimalni dekoder na majhni vzorčni kodi, tako da izvaja optimalno meritev, ki razlikuje kvantna izhodna stanja za niz vhodnih kodnih besed z največjo dosegljivo verjetnostjo. Tukaj bistveno razširimo razumevanje, formalizem in uporabnost algoritma BPQM z naslednjimi prispevki. Najprej analitično dokažemo, da BPQM realizira optimalno dekodiranje za katero koli binarno linearno kodo z drevesnim Tannerjevim grafom. Ponujamo tudi prvi formalni opis algoritma BPQM v vseh podrobnostih in brez kakršnih koli dvoumnosti. Pri tem ugotovimo ključno napako, ki je bila spregledana v prvotnem algoritmu in nadaljnjih delih, kar pomeni, da bodo realizacije kvantnega vezja eksponentno velike v dimenziji kode. Čeprav BPQM posreduje kvantna sporočila, se druge informacije, ki jih zahteva algoritem, obdelujejo globalno. To težavo odpravimo tako, da oblikujemo algoritem za resnično posredovanje sporočil, ki se približa BPQM in ima kompleksnost kvantnega vezja $mathcal{O}(text{poly } n, text{polylog } frac{1}{epsilon})$, kjer je $n$ je dolžina kode in $epsilon$ je napaka približka. Na koncu predlagamo tudi novo metodo za razširitev BPQM na faktorske grafe, ki vsebujejo cikle, z uporabo približnega kloniranja. Prikazujemo nekaj obetavnih numeričnih rezultatov, ki kažejo, da lahko BPQM na faktorskih grafih s cikli bistveno prekaša najboljši možni klasični dekoder.
► BibTeX podatki
► Reference
[1] Joseph M. Renes »Dekodiranje širjenja prepričanj kvantnih kanalov s posredovanjem kvantnih sporočil« 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 in Henry D. Pfister, »Razširjanje prepričanj s kvantnimi sporočili za kvantno izboljšane klasične komunikacije« npj Kvantne informacije 7, 97 (2021).
https://doi.org/10.1038/s41534-021-00422-1
arXiv: 2003.04356
https: / / www.nature.com/ Članki / s41534-021-00422-1
[3] S. Kudekar, T. Richardson in RL Urbanke, »Prostorsko sklopljeni ansambli univerzalno dosegajo zmogljivost pri širjenju prepričanj« IEEE Transactions on Information Theory 59, 7761–7813 (2013).
https: / / doi.org/ 10.1109 / TIT.2013.2280915
arXiv: 1201.2999
[4] HA Loeliger in PO Vontobel »Faktorski grafi za kvantne verjetnosti« IEEE Transactions on Information Theory 63, 5642–5665 (2017).
https: / / doi.org/ 10.1109 / TIT.2017.2716422
arXiv: 1508.00689
[5] MX Cao in PO Vontobel »Faktorski grafi z dvojnim robom: definicija, lastnosti in primeri« 2017 IEEE Information Theory Workshop (ITW) 136–140 (2017).
https:///doi.org/10.1109/ITW.2017.8277985
arXiv: 1706.00752
[6] Hans-Andrea Loeliger “Uvod v faktorske grafe” Revija IEEE Signal Processing Magazine 21, 28–41 (2004).
https: / / doi.org/ 10.1109 / MSP.2004.1267047
[7] VP Belavkin “Optimalno večkratno kvantno statistično testiranje hipotez” Stohastika 1, 315 (1975).
https: / / doi.org/ 10.1080 / 17442507508833114
[8] Paul Hausladen in William K. Wootters »Precej dobra' meritev za razlikovanje kvantnih stanj« Journal of Modern Optics 41, 2385 (1994).
https: / / doi.org/ 10.1080 / 09500349414552221
[9] Narayanan Rengaswamy in Henry D. Pfister »Polklasični dokaz dvojnosti med klasičnim BSC in kvantnim PSC« (2021).
https:///doi.org/10.48550/arXiv.2103.09225
arXiv: 2103.09225
[10] Masashi Ban, Keiko Kurokawa, Rei Momose in Osamu Hirota, »Optimalne meritve za diskriminacijo med simetričnimi kvantnimi stanji in oceno parametrov« Mednarodni časopis za teoretično fiziko 36, 1269–1288 (1997).
https: / / doi.org/ 10.1007 / BF02435921
[11] Masahide Sasaki, Kentaro Kato, Masayuki Izutsu in Osamu Hirota, »Kvantni kanali, ki kažejo superaditivnost v klasični zmogljivosti«, fizični pregled A 58, 146–158 (1998).
https: / / doi.org/ 10.1103 / PhysRevA.58.146
[12] YC Eldar in Jr. Forney "O kvantnem odkrivanju in merjenju kvadratnega korena" IEEE Transactions on Information Theory 47, 858–872 (2001).
https: / / doi.org/ 10.1109 / 18.915636
[13] Tom Richardson in Rüdiger Urbanke “Modern Coding Theory” Cambridge University Press (2008).
https: / / doi.org/ 10.1017 / CBO9780511791338
[14] David Poulin »Optimalno in učinkovito dekodiranje povezanih kvantnih blokovnih kod« Physical Review A 74, 052333 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.052333
[15] David Poulin in Yeojin Chung "O iterativnem dekodiranju redkih kvantnih kod" Kvantne informacije in računanje 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 in 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 in 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 in David Poulin »Dekoderji nevronskega širjenja prepričanj za kvantne kode za popravljanje napak« Physical Review Letters 122, 200501 (2019).
https: / / doi.org/ 10.1103 / PhysRevLett.122.200501
arXiv: 1811.07835
[19] Alex Rigby, JC Olivier in Peter Jarvis, »Modified Belief Propagation Decoders for Quantum Low-Density Parity-Check Codes« Physical Review A 100, 012330 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.100.012330
arXiv: 1903.07404
[20] Pavel Panteleev in Gleb Kalachev »Degenerirane kvantne kode LDPC z dobro zmogljivostjo končne dolžine« Quantum 5, 585 (2021).
https://doi.org/10.22331/q-2021-11-22-585
[21] Julij X. Li in Pascal O. Vontobel »Pseudocodeword-Based Decoding of Quantum Stabilizer Codes« 2019 Mednarodni simpozij IEEE o teoriji informacij (ISIT) 2888–2892 (2019).
https: / / doi.org/ 10.1109 / ISIT.2019.8849833
arXiv: 1903.01202
[22] Joschka Roffe, David R. White, Simon Burton in Earl Campbell, »Dekodiranje v pokrajini kvantne kode za preverjanje parnosti z nizko gostoto« Physical Review Research 2, 043423 (2020).
https: / / doi.org/ 10.1103 / PhysRevResearch.2.043423
arXiv: 2005.07016
[23] July X. Li, Joseph M. Renes in 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 in Kyle Jamieson »Proti kvantnemu širjenju prepričanj za dekodiranje LDPC v brezžičnih omrežjih« Zbornik 26. letne mednarodne konference o mobilnem računalniku in omrežju 1–14 (2020).
https: / / doi.org/ 10.1145 / 3372224.3419207
arXiv: 2007.11069
[25] MS Leifer in D. Poulin »Kvantni grafični modeli in širjenje prepričanj« 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 “Statistical Theory of Superlattices with Unenaqual Concentrations of the Components” 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 in Yair Weiss, »Splošno širjenje prepričanj«, zbornik 13. mednarodne konference o sistemih za obdelavo nevronskih informacij 668–674 (2000).
[29] Jonathan S. Yedidia, William T. Freeman in Yair Weiss, »Razumevanje širjenja prepričanj in njegovih posploševanj« Morgan Kaufmann Publishers Inc. (2003).
https:///www.merl.com/publications/docs/TR2001-22.pdf
[30] JS Yedidia, WT Freeman in Y. Weiss, »Konstruiranje približkov proste energije in generaliziranih algoritmov širjenja prepričanj« Teorija informacij, IEEE Transactions on 51, 2282–2312 (2005).
https: / / doi.org/ 10.1109 / TIT.2005.850085
[31] MB Hastings »Razširjanje kvantnega prepričanja: Algoritem za toplotne kvantne sisteme« Fizični pregled B 76, 201102 (2007).
https: / / doi.org/ 10.1103 / PhysRevB.76.201102
arXiv: 0706.4094
[32] David Poulin in Matthew B. Hastings »Razpad Markove entropije: variacijski dvojnik za širjenje kvantnega prepričanja« Physical Review Letters 106, 080403 (2011).
https: / / doi.org/ 10.1103 / PhysRevLett.106.080403
arXiv: 1012.2050
[33] MX Cao in PO Vontobel »Grafi kvantnih faktorjev: Operacija zaprtja okvirja in variacijski pristopi« 2016 Mednarodni simpozij o teoriji informacij in njenih aplikacijah (ISITA) 651–655 (2016).
https: / / ieeexplore.ieee.org/ dokument / 7840505
[34] FR Kschischang, BJ Frey in HA Loeliger, »Faktorski grafi in algoritem vsote produkta« IEEE Transactions on Information Theory 47, 498–519 (2001).
https: / / doi.org/ 10.1109 / 18.910572
[35] G. David Forney »Kode na grafih: normalne realizacije« IEEE Transactions on Information Theory 47, 520–548 (2001).
https: / / doi.org/ 10.1109 / 18.910573
[36] CW Helstrom “Teorija kvantnega odkrivanja in ocenjevanja” Academic (1976).
https://doi.org/10.1016/S0076-5392(08)60247-7
http://www.sciencedirect.com/ science/bookseries/00765392/123
[37] Saikat Guha »Strukturirani optični sprejemniki za doseganje superaditivne zmogljivosti in meje Holevo« Physical Review Letters 106, 240502 (2011).
https: / / doi.org/ 10.1103 / PhysRevLett.106.240502
arXiv: 1101.1550
[38] T. Etzion, A. Trachtenberg in A. Vardy, »Katere kode imajo Tannerjeve grafe brez ciklov?« IEEE Transactions on Information Theory 45, 2173–2181 (1999).
https: / / doi.org/ 10.1109 / 18.782170
[39] Jacob C. Bridgeman in Christopher T. Chubb »Mahanje z rokami in interpretativni ples: Uvodni tečaj o tenzorskih omrežjih« 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 in Martti M. Salomaa, »Kvantna vezja z enakomerno nadzorovanimi enokubitnimi vrati«, fizični pregled A 71, 052330 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.052330
http:///arxiv.org/abs/quant-ph/0410066
[41] CH Bennett “Logical Reversibility of Computation” 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 in van der Hoeven »Množenje celih števil v času 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 in Saber Kais, »Kvantni algoritem in zasnova vezja, ki rešujeta Poissonovo enačbo«, 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 in Iasonas Petras, »Kvantni algoritmi in vezja za znanstveno računalništvo« Kvantne informacije in računanje 16, 197–236 (2016).
https: / / doi.org/ 10.26421 / QIC16.3-4-2
arXiv: 1511.08253
[46] Thomas Häner, Martin Roetteler in Krysta M. Svore, »Optimizacija kvantnih vezij za aritmetiko« (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 in Yongjian Gu, »Načrtovanje kvantnih vezij za vrednotenje transcendentalnih funkcij, ki temelji na metodi binarne ekspanzije funkcijske vrednosti« Kvantna obdelava informacij 19, 347 (2020).
https://doi.org/10.1007/s11128-020-02855-7
arXiv: 2001.00807
[48] John Watrous “The 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 in 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 »Polarizacija kanalov: Metoda za konstruiranje kod za doseganje zmogljivosti za simetrične binarne vhodne kanale brez spomina« IEEE Transactions on Information Theory 55, 3051–3073 (2009).
https: / / doi.org/ 10.1109 / TIT.2009.2021379
arXiv: 0807.3917
[51] Mark M. Wilde in Saikat Guha »Polarne kode za klasične kvantne kanale« IEEE Transactions on Information Theory 59, 1175–1187 (2013).
https: / / doi.org/ 10.1109 / TIT.2012.2218792
arXiv: 1109.2591
[52] Joseph M. Renes in Mark M. Wilde »Polarne kode za zasebno in kvantno komunikacijo prek poljubnih kanalov« IEEE Transactions on Information Theory 60, 3090–3103 (2014).
https: / / doi.org/ 10.1109 / TIT.2014.2314463
arXiv: 1212.2537
[53] S. Guha in MM Wilde »Polarno kodiranje za doseganje zmogljivosti Holevo optičnega kanala s čisto izgubo« Zbornik 2012 mednarodnega simpozija IEEE o teoriji informacij (ISIT) 546–550 (2012).
https: / / doi.org/ 10.1109 / ISIT.2012.6284250
arXiv: 1202.0533
Navedel
[1] S. Brandsen, Avijit Mandal in Henry D. Pfister, »Razširjanje prepričanja s kvantnimi sporočili za simetrične klasične-kvantne kanale«, arXiv: 2207.04984.
Zgornji citati so iz SAO / NASA ADS (zadnjič posodobljeno 2022-08-23 14:04:15). Seznam je morda nepopoln, saj vsi založniki ne dajejo ustreznih in popolnih podatkov o citiranju.
Pridobitve ni bilo mogoče Crossref citirani podatki med zadnjim poskusom 2022-08-23 14:04:14: Citiranih podatkov za 10.22331 / q-2022-08-23-784 od Crossrefa ni bilo mogoče pridobiti. To je normalno, če je bil DOI registriran pred kratkim.
Ta dokument je objavljen v Quantumu pod Priznanje avtorstva Creative Commons 4.0 International (CC BY 4.0) licenca. Avtorske pravice ostajajo pri izvirnih imetnikih avtorskih pravic, kot so avtorji ali njihove ustanove.
