Instytut Fizyki Teoretycznej, ETH Zürich, Szwajcaria
Czy ten artykuł jest interesujący czy chcesz dyskutować? Napisz lub zostaw komentarz do SciRate.
Abstrakcyjny
Niedawno Renes zaproponował algorytm kwantowy zwany propagacją wierzeń z wiadomościami kwantowymi (BPQM) do dekodowania klasycznych danych zakodowanych za pomocą binarnego kodu liniowego z grafem Tannera, który jest przesyłany przez kanał CQ w stanie czystym [1], czyli kanał z klasycznym wejściem i czystostanowym wyjściem kwantowym. Algorytm stanowi prawdziwy kwantowy odpowiednik dekodowania opartego na klasycznym algorytmie propagacji przekonań, który w połączeniu z kodami LDPC lub Turbo odniósł duży sukces w klasycznej teorii kodowania. Ostatnio Rengaswamy $et$ $al.$ [2] zaobserwowali, że BPQM implementuje optymalny dekoder na małym przykładowym kodzie, ponieważ implementuje optymalny pomiar, który rozróżnia stany kwantowego wyjścia dla zestawu wejściowych słów kodowych o najwyższym możliwym do osiągnięcia prawdopodobieństwie. W tym miejscu znacznie poszerzamy zrozumienie, formalizm i stosowalność algorytmu BPQM z następującymi wkładami. Po pierwsze, udowadniamy analitycznie, że BPQM realizuje optymalne dekodowanie dla dowolnego binarnego kodu liniowego z grafem Tannera drzewa. Przedstawiamy również pierwszy formalny opis algorytmu BPQM w sposób szczegółowy i bez żadnych niejasności. W ten sposób identyfikujemy kluczową wadę przeoczoną w oryginalnym algorytmie i kolejnych pracach, które implikują, że realizacje obwodów kwantowych będą wykładniczo duże w wymiarze kodu. Chociaż BPQM przekazuje wiadomości kwantowe, inne informacje wymagane przez algorytm są przetwarzane globalnie. Rozwiązujemy ten problem, formułując prawdziwy algorytm przekazywania wiadomości, który przybliża BPQM i ma złożoność obwodu kwantowego $mathcal{O}(text{poly } n, text{polylog } frac{1}{epsilon})$, gdzie $n$ to długość kodu, a $epsilon$ to błąd aproksymacji. Na koniec proponujemy również nową metodę rozszerzania BPQM na wykresy czynnikowe zawierające cykle poprzez wykorzystanie przybliżonego klonowania. Przedstawiamy kilka obiecujących wyników liczbowych, które wskazują, że BPQM na wykresach czynnikowych z cyklami może znacznie przewyższyć najlepszy możliwy klasyczny dekoder.
► Dane BibTeX
► Referencje
[1] Joseph M. Renes „Dekodowanie propagacji przekonań kanałów kwantowych poprzez przekazywanie wiadomości kwantowych” 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, „Propagacja przekonań za pomocą wiadomości kwantowych dla komunikacji klasycznej wzmocnionej kwantowo” npj Quantum Information 7, 97 (2021).
https://doi.org/10.1038/s41534-021-00422-1
arXiv: 2003.04356
https: // www.nature.com/ article / 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 „Wykresy czynnikowe dla prawdopodobieństwa kwantowego” IEEE Transactions on Information Theory 63, 5642-5665 (2017).
https: / / doi.org/ 10.1109 / TIT.2017.2716422
arXiv: 1508.00689
[5] MX Cao i PO Vontobel „Double-Edge Factor Graphs: Definition, Properties, and Example” 2017 IEEE Information Theory Workshop (ITW) 136–140 (2017).
https:///doi.org/10.1109/ITW.2017.8277985
arXiv: 1706.00752
[6] Hans-Andrea Loeliger „An Introduction to Factor Graphs” IEEE Signal Processing Magazine 21, 28–41 (2004).
https: // doi.org/ 10.1109 / MSP.2004.1267047
[7] VP Belavkin „Optymalne wielokrotne kwantowe testowanie statystycznej hipotezy” Stochastics 1, 315 (1975).
https: / / doi.org/ 10.1080 / 17442507508833114
[8] Paul Hausladen i William K. Wootters „Dość dobry pomiar dla rozróżnienia stanów kwantowych” Journal of Modern Optics 41, 2385 (1994).
https: / / doi.org/ 10.1080 / 09500349414552221
[9] Narayanan Rengaswamy i Henry D. Pfister „Półklasyczny dowód dualności między klasycznym BSC a kwantowym PSC” (2021).
https:///doi.org/10.48550/arXiv.2103.09225
arXiv: 2103.09225
[10] Masashi Ban, Keiko Kurokawa, Rei Momose i Osamu Hirota, „Optymalne pomiary dyskryminacji wśród symetrycznych stanów kwantowych i szacowanie parametrów” International Journal of Theoretical Physics 36, 1269-1288 (1997).
https: / / doi.org/ 10.1007 / BF02435921
[11] Masahide Sasaki, Kentaro Kato, Masayuki Izutsu i Osamu Hirota, „Kanały kwantowe wykazujące superaddytywność w klasycznej pojemności” Przegląd fizyczny A 58, 146–158 (1998).
https: / / doi.org/ 10.1103 / PhysRevA.58.146
[12] YC Eldar and Jr. Forney „On Quantum Detection and the Square-Root Measurement” IEEE Transactions on Information Theory 47, 858-872 (2001).
https: / / doi.org/ 10.1109 / 18.915636
[13] Tom Richardson i Rüdiger Urbanke „Nowoczesna teoria kodowania” Cambridge University Press (2008).
https: / / doi.org/ 10.1017 / CBO9780511791338
[14] David Poulin „Optymalne i wydajne dekodowanie połączonych kodów bloków kwantowych” Przegląd fizyczny A 74, 052333 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.052333
[15] David Poulin i Yeojin Chung „O iteracyjnym dekodowaniu rzadkich kodów kwantowych” Informacje i obliczenia kwantowe 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 „Podsumowanie wielościeżkowe do dekodowania kodów topologicznych 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 „Dekodery neuronowej propagacji przekonań do kwantowych kodów korygujących błędy” 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, „Zmodyfikowane dekodery propagacji przekonań dla kodów kontroli parzystości kwantowej o niskiej gęstości” Przegląd fizyczny A 100, 012330 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.100.012330
arXiv: 1903.07404
[20] Pavel Panteleev i Gleb Kalachev „Zdegenerowane kwantowe kody LDPC o dobrej wydajności skończonej długości” Quantum 5, 585 (2021).
https://doi.org/10.22331/q-2021-11-22-585
[21] Lipiec X. Li i Pascal O. Vontobel „Pseudocodeword-Based Decoding of Quantum Stabilizer Codes” 2019 Międzynarodowe sympozjum IEEE dotyczące teorii informacji (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 through 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] Lipiec X. Li, Joseph M. Renes i 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 i Kyle Jamieson „Towards Quantum Belief Propagation for LDPC Decoding in Wireless Networks” Materiały 26. dorocznej międzynarodowej konferencji na temat komputerów mobilnych i sieci 1–14 (2020).
https: / / doi.org/ 10.1145 / 3372224.3419207
arXiv: 2007.11069
[25] MS Leifer i D. Poulin „Kwantowe modele graficzne i propagacja przekonań” Roczniki fizyki 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 „Statystyczna teoria supersieci” Materiały Towarzystwa Królewskiego A 150, 552–575 (1935).
https: / / doi.org/ 10.1098 / rspa.1935.0122
http:///rspa.royalsocietypublishing.org/content/150/871/552
[27] Rudolf Peierls „Statystyczna teoria supersieci o nierównych stężeniach składników” Materiały Towarzystwa Królewskiego 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 13th International Conference on Neural Information Processing Systems 668–674 (2000).
[29] Jonathan S. Yedidia, William T. Freeman i Yair Weiss, „Zrozumienie propagacji przekonań i jej uogólnień” Morgan Kaufmann Publishers Inc. (2003).
https:///www.merl.com/publikacje/docs/TR2001-22.pdf
[30] JS Yedidia, WT Freeman i Y. Weiss, „Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms” Information Theory, IEEE Transactions on 51, 2282-2312 (2005).
https: / / doi.org/ 10.1109 / TIT.2005.850085
[31] MB Hastings „Propagacja wierzeń kwantowych: algorytm dla termicznych systemów kwantowych” Przegląd fizyczny B 76, 201102 (2007).
https: / / doi.org/ 10.1103 / PhysRevB.76.201102
arXiv: 0706.4094
[32] David Poulin i Matthew B. Hastings „Dekompozycja entropii Markowa: podwójna odmiana propagacji wiary kwantowej” Physical Review Letters 106, 080403 (2011).
https: / / doi.org/ 10.1103 / PhysRevLett.106.080403
arXiv: 1012.2050
[33] MX Cao i PO Vontobel „Quantum Factor Graphs: Closing-the-Box Operation and Variational Approaches” 2016 Międzynarodowe sympozjum na temat teorii informacji i jej zastosowań (ISITA) 651–655 (2016).
https: // ieeexplore.ieee.org/ document / 7840505
[34] FR Kschischang, BJ Frey i HA Loeliger, „Wykresy czynnikowe i algorytm sum-produktów” 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 „Teoria wykrywania i szacowania kwantowego” (1976).
https://doi.org/10.1016/S0076-5392(08)60247-7
http:///www.sciencedirect.com/science/bookseries/00765392/123
[37] Saikat Guha „Ustrukturyzowane odbiorniki optyczne w celu osiągnięcia superaddytywnej pojemności i limitu 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, „Które kody mają bezcyklowe wykresy opalania?” IEEE Transactions on Information Theory 45, 2173-2181 (1999).
https: / / doi.org/ 10.1109 / 18.782170
[39] Jacob C. Bridgeman i Christopher T. Chubb „Machanie rękami i taniec interpretacyjny: kurs wprowadzający w sieciach tensorowych” 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, „Obwody kwantowe z jednolicie kontrolowanymi bramkami jednokubitowymi” Przegląd fizyczny A 71, 052330 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.052330
http: // arxiv.org/ abs / quant-ph / 0410066
[41] CH Bennett „Logiczna odwracalność obliczeń” 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 „Mnożenie liczb całkowitych w czasie 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, „Algorytm kwantowy i projektowanie obwodów rozwiązujących równanie Poissona” 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, „Algorytmy i obwody kwantowe do obliczeń naukowych” Informacje i obliczenia kwantowe 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, „Optymalizacja obwodów kwantowych dla arytmetyki” (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, „Projektowanie obwodów kwantowych do oceny funkcji transcendentalnych w oparciu o metodę rozszerzenia binarnego funkcji wartości” Przetwarzanie informacji kwantowych 19, 347 (2020).
https://doi.org/10.1007/s11128-020-02855-7
arXiv: 2001.00807
[48] John Watrous „Teoria informacji kwantowej” 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, Przegląd fizyczny „Optimal Universal and State-Dependent Quantum Cloning” A 57, 2368–2378 (1998).
https: / / doi.org/ 10.1103 / PhysRevA.57.2368
[50] E. Arıkan „Polaryzacja kanału: metoda konstruowania kodów osiągających pojemność dla symetrycznych kanałów bez pamięci z wejściem binarnym” IEEE Transactions on Information Theory 55, 3051-3073 (2009).
https: / / doi.org/ 10.1109 / TIT.2009.2021379
arXiv: 0807.3917
[51] Mark M. Wilde i 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 i 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 i MM Wilde „Kodowanie polarne w celu osiągnięcia pojemności Holevo kanału optycznego o czystej utracie” Materiały z Międzynarodowego Sympozjum Teorii Informacji (ISIT) z 2012 r. (ISIT) 546-550 (2012).
https: / / doi.org/ 10.1109 / ISIT.2012.6284250
arXiv: 1202.0533
Cytowany przez
[1] S. Brandsen, Avijit Mandal i Henry D. Pfister, „Propagacja przekonań za pomocą wiadomości kwantowych dla symetrycznych klasycznych kanałów kwantowych”, arXiv: 2207.04984.
Powyższe cytaty pochodzą z Reklamy SAO / NASA (ostatnia aktualizacja pomyślnie 2022-08-23 14:04:15). Lista może być niekompletna, ponieważ nie wszyscy wydawcy podają odpowiednie i pełne dane cytowania.
Nie można pobrać Przywołane przez Crossref dane podczas ostatniej próby 2022-08-23 14:04:14: Nie można pobrać cytowanych danych dla 10.22331 / q-2022-08-23-784 z Crossref. Jest to normalne, jeśli DOI zostało niedawno zarejestrowane.
Niniejszy artykuł opublikowano w Quantum pod Creative Commons Uznanie autorstwa 4.0 Międzynarodowe (CC BY 4.0) licencja. Prawa autorskie należą do pierwotnych właścicieli praw autorskich, takich jak autorzy lub ich instytucje.
