Teoreettisen fysiikan instituutti, ETH Zürich, Sveitsi
Onko tämä artikkeli mielenkiintoinen vai haluatko keskustella? Scite tai jätä kommentti SciRate.
Abstrakti
Äskettäin Renes ehdotti kvanttialgoritmia, jota kutsutaan uskomuksen leviämiseksi kvanttiviesteillä (BPQM) klassisen datan dekoodaamiseksi, joka on koodattu käyttämällä binaarista lineaarikoodia puu Tanner-graafin kanssa, joka lähetetään puhtaan tilan CQ-kanavan kautta [1], eli kanava, jossa on klassinen tulo ja puhdastila kvanttilähtö. Algoritmi tarjoaa aidon kvanttivastineen dekoodaukselle, joka perustuu klassiseen uskomuksen leviämisalgoritmiin, joka on saavuttanut laajaa menestystä klassisessa koodausteoriassa, kun sitä käytetään yhdessä LDPC- tai Turbo-koodien kanssa. Viime aikoina Rengaswamy $et$ $al.$ [2] havaitsi, että BPQM toteuttaa optimaalisen dekooderin pienessä esimerkkikoodissa siten, että se toteuttaa optimaalisen mittauksen, joka erottaa sisääntulokoodisanojen joukon kvanttilähtötilat suurimmalla saavutettavissa olevalla todennäköisyydellä. Tässä laajennamme merkittävästi BPQM-algoritmin ymmärtämistä, formalismia ja sovellettavuutta seuraavilla panoksilla. Ensinnäkin todistamme analyyttisesti, että BPQM toteuttaa optimaalisen dekoodauksen mille tahansa binääriselle lineaariselle koodille puu Tanner -graafin avulla. Tarjoamme myös ensimmäisen muodollisen kuvauksen BPQM-algoritmista täysin yksityiskohtaisesti ja ilman epäselvyyksiä. Näin tehdessämme tunnistamme alkuperäisen algoritmin keskeisen puutteen, ja myöhemmät työt, jotka viittaavat siihen, että kvanttipiirin toteutukset ovat eksponentiaalisesti suuria koodiulottuvuuden suhteen. Vaikka BPQM välittää kvanttiviestejä, muita algoritmin vaatimia tietoja käsitellään globaalisti. Korjaamme tämän ongelman muotoilemalla todella viestinvälitysalgoritmin, joka approksimoi BPQM:n ja jonka kvanttipiirin monimutkaisuus on $mathcal{O}(text{poly } n, text{polylog } frac{1}{epsilon})$, missä $n$ on koodin pituus ja $epsilon$ on approksimaatiovirhe. Lopuksi ehdotamme myös uutta menetelmää BPQM:n laajentamiseksi sykliä sisältäviin tekijäkaavioihin käyttämällä likimääräistä kloonausta. Näytämme joitakin lupaavia numeerisia tuloksia, jotka osoittavat, että BPQM syklisillä tekijäkaavioilla voi merkittävästi ylittää parhaan mahdollisen klassisen dekooderin.
► BibTeX-tiedot
► Viitteet
[1] Joseph M. Renes "Kvanttikanavien uskomuksen leviämisen dekoodaus kvanttiviestien kautta" 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, "Uskon leviäminen kvanttiviestien avulla kvanttitehostetussa klassisessa viestinnässä" npj Quantum Information 7, 97 (2021).
https://doi.org/10.1038/s41534-021-00422-1
arXiv: 2003.04356
https: / / www.nature.com/ artikkelia / 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 "Factor Graphs for Quantum Probabilities" 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 "Double-Edge Factor Graphs: Definition, Properties and esimerkit" 2017 IEEE Information Theory Workshop (ITW) 136–140 (2017).
https: / / doi.org/ 10.1109 / ITW.2017.8277985
arXiv: 1706.00752
[6] Hans-Andrea Loeliger "Johdatus tekijägraafiin" 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 ja William K. Wootters "Melko hyvä mittaus kvanttitilojen erottamiseksi" Journal of Modern Optics 41, 2385 (1994).
https: / / doi.org/ 10.1080 / +09500349414552221
[9] Narayanan Rengaswamy ja Henry D. Pfister "Puoliklassinen todiste kaksinaisuudesta klassisen BSC:n ja kvantti-PSC:n välillä" (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 Superadditivity in Classical Capacity" Physical Review A 58, 146–158 (1998).
https: / / doi.org/ 10.1103 / PhysRevA.58.146
[12] YC Eldar ja Jr. Forney "Kvanttitunnistuksesta ja neliöjuurimittauksesta" 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 "Konkatenoitujen kvanttilohkokoodien optimaalinen ja tehokas dekoodaus" Physical Review A 74, 052333 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.052333
[15] David Poulin ja Yeojin Chung "Harvojen kvanttikoodien iteratiivisesta dekoodauksesta" 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 "Neuraalisten uskomusten leviämisen dekooderit kvanttivirheitä korjaaville koodeille" 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, "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 ja Gleb Kalachev "Degeneroituneet kvantti-LDPC-koodit, joilla on hyvä rajallinen pituus" Quantum 5, 585 (2021).
https://doi.org/10.22331/q-2021-11-22-585
[21] Heinäkuu 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, "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] Heinäkuu 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" Proceedings of 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 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/ tiede / artikkeli / pii / S0003491607001509
[26] HA Bethe "Tilastollinen superhilojen teoria" 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 "Tilastollinen teoria superhiloista, joiden komponenttien pitoisuus on epätasainen" 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 the 13th International Conference on Neural Information Processing Systems 668-674 (2000).
[29] Jonathan S. Yedidia, William T. Freeman ja 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 ja Y. Weiss, "Free-Energy Approximations and Generalized Belief Propagation Algorithms" Information Theory, IEEE Transactions, 51, 2282–2312 (2005).
https: / / doi.org/ 10.1109 / TIT.2005.850085
[31] MB Hastings "Quantum Belief Propagation: An Algorithm for Thermal Quantum Systems" Physical Review B 76, 201102 (2007).
https: / / doi.org/ 10.1103 / PhysRevB.76.201102
arXiv: 0706.4094
[32] David Poulin ja Matthew B. Hastings "Markov Entropy Decomposition: 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 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/ asiakirja / 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 "Koodit kuvaajista: Normaalit realisaatiot" IEEE Transactions on Information Theory 47, 520–548 (2001).
https: / / doi.org/ 10.1109 / +18.910573
[36] CW Helstrom "Quantum Detection and Estimation Theory" akateeminen (1976).
https://doi.org/10.1016/S0076-5392(08)60247-7
http://www.sciencedirect.com/ science/bookseries/00765392/123
[37] Saikat Guha "Strukturoidut optiset vastaanottimet superadditiivisen kapasiteetin ja Holevo-rajan saavuttamiseksi" 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, "Millä koodeilla on kiertovapaat rusketuskaaviot?" IEEE Transactions on Information Theory 45, 2173–2181 (1999).
https: / / doi.org/ 10.1109 / +18.782170
[39] Jacob C. Bridgeman ja Christopher T. Chubb "Hand-waving and Interpretive 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, ja Martti M. Salomaa, "Kvanttipiirit tasaisesti ohjatuilla yksikviittisillä porteilla" Fyysinen katsaus 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 "Monitarkkuusnollalöytömenetelmät ja perustoimintojen arvioinnin monimutkaisuus" 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 "Kokonaislukukertolasku ajassa 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, "Quantum Algorithm and Circuit Design 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 ja 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 ja 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 ja Yongjian Gu, "Kvanttipiirien suunnittelu transsendenttisten funktioiden arvioimiseksi funktio-arvon binaarilaajennusmenetelmän perusteella" Kvanttitietojen käsittely (19, 347).
https://doi.org/10.1007/s11128-020-02855-7
arXiv: 2001.00807
[48] John Watrous "Kvanttitiedon teoria" 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 "Kanavien polarisaatio: menetelmä kapasiteettia lisäävien koodien muodostamiseksi symmetrisille binäärituloisille muistittomille kanaville" 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" Proceedings of 2012 IEEE International Symposium on Information Theory (ISIT) 546–550 (2012).
https: / / doi.org/ 10.1109 / ISIT.2012.6284250
arXiv: 1202.0533
Viitattu
[1] S. Brandsen, Avijit Mandal ja Henry D. Pfister, "Uskon leviäminen kvanttiviestien avulla symmetrisille klassis-kvanttikanaville", arXiv: 2207.04984.
Yllä olevat sitaatit ovat peräisin SAO: n ja NASA: n mainokset (viimeksi päivitetty onnistuneesti 2022-08-23 14:04:15). Lista voi olla puutteellinen, koska kaikki julkaisijat eivät tarjoa sopivia ja täydellisiä viittaustietoja.
Ei voitu noutaa Crossref siteeratut tiedot viimeisen yrityksen aikana 2022-08-23 14:04:14: Ei voitu noutaa viittauksia 10.22331 / q-2022-08-23-784 mainittuihin tietoihin Crossrefiltä. Tämä on normaalia, jos DOI rekisteröitiin äskettäin.
Tämä kirja on julkaistu Quantum - lehdessä Creative Commons Nimeäminen 4.0 Kansainvälinen (CC BY 4.0) lisenssin. Tekijänoikeudet säilyvät alkuperäisillä tekijänoikeuksien haltijoilla, kuten tekijöillä tai heidän instituutioillaan.
