Institut de physique théorique, ETH Zürich, Suisse
Vous trouvez cet article intéressant ou souhaitez en discuter? Scite ou laisse un commentaire sur SciRate.
Abstract
Récemment, Renes a proposé un algorithme quantique appelé propagation de croyance avec messages quantiques (BPQM) pour décoder des données classiques codées à l'aide d'un code linéaire binaire avec un graphe arborescent de Tanner qui est transmis sur un canal CQ à l'état pur.1], c'est-à-dire un canal avec une entrée classique et une sortie quantique à l'état pur. L'algorithme présente une véritable contrepartie quantique au décodage basé sur l'algorithme de propagation de croyance classique, qui a rencontré un large succès dans la théorie du codage classique lorsqu'il est utilisé en conjonction avec des codes LDPC ou Turbo. Plus récemment Rengaswamy $et$ $al.$ [2] ont observé que BPQM implémente le décodeur optimal sur un petit exemple de code, en ce sens qu'il implémente la mesure optimale qui distingue les états de sortie quantiques pour l'ensemble de mots de code d'entrée avec la probabilité réalisable la plus élevée. Ici, nous élargissons considérablement la compréhension, le formalisme et l'applicabilité de l'algorithme BPQM avec les contributions suivantes. Tout d'abord, nous prouvons analytiquement que BPQM réalise un décodage optimal pour tout code linéaire binaire avec graphe arborescent de Tanner. Nous fournissons également la première description formelle de l'algorithme BPQM en détail et sans aucune ambiguïté. Ce faisant, nous identifions un défaut clé négligé dans l'algorithme original et les travaux ultérieurs qui impliquent que les réalisations de circuits quantiques seront exponentiellement grandes dans la dimension du code. Bien que BPQM transmette des messages quantiques, d'autres informations requises par l'algorithme sont traitées globalement. Nous remédions à ce problème en formulant un véritable algorithme de transmission de messages qui se rapproche de BPQM et a une complexité de circuit quantique $mathcal{O}(text{poly } n, text{polylog } frac{1}{epsilon})$, where $n$ est la longueur du code et $epsilon$ est l'erreur d'approximation. Enfin, nous proposons également une nouvelle méthode pour étendre BPQM aux graphes factoriels contenant des cycles en utilisant le clonage approximatif. Nous montrons des résultats numériques prometteurs qui indiquent que BPQM sur des graphes factoriels avec des cycles peut nettement surpasser le meilleur décodeur classique possible.
► Données BibTeX
► Références
Joseph M. Renes "Décodage de la propagation des croyances des canaux quantiques en passant des messages quantiques" 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
Narayanan Rengaswamy, Kaushik P. Seshadreesan, Saikat Guha et Henry D. Pfister, « Propagation des croyances avec des messages quantiques pour les communications classiques améliorées quantiques » 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
S. Kudekar, T. Richardson et RL Urbanke, "Les ensembles spatialement couplés atteignent universellement la capacité sous la propagation des croyances" Transactions IEEE sur la théorie de l'information 59, 7761–7813 (2013).
https: / / doi.org/ 10.1109 / TIT.2013.2280915
arXiv: 1201.2999
HA Loeliger et 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
MX Cao et PO Vontobel « Graphes factoriels à double tranchant : définition, propriétés et exemples » 2017 IEEE Information Theory Workshop (ITW) 136–140 (2017).
https:///doi.org/10.1109/ITW.2017.8277985
arXiv: 1706.00752
Hans-Andrea Loeliger "Une introduction aux graphes factoriels" IEEE Signal Processing Magazine 21, 28–41 (2004).
https: / / doi.org/ 10.1109 / MSP.2004.1267047
VP Belavkin "Test optimal d'hypothèses statistiques quantiques multiples" Stochastics 1, 315 (1975).
https: / / doi.org/ 10.1080 / 17442507508833114
Paul Hausladen et William K. Wootters "Une mesure "assez bonne" pour distinguer les états quantiques" Journal of Modern Optics 41, 2385 (1994).
https: / / doi.org/ 10.1080 / 09500349414552221
Narayanan Rengaswamy et Henry D. Pfister "Une preuve semi-classique de la dualité entre le BSC classique et le PSC quantique" (2021).
https:///doi.org/10.48550/arXiv.2103.09225
arXiv: 2103.09225
Masashi Ban, Keiko Kurokawa, Rei Momose et Osamu Hirota, "Mesures optimales pour la discrimination entre les états quantiques symétriques et l'estimation des paramètres" International Journal of Theoretical Physics 36, 1269–1288 (1997).
https: / / doi.org/ 10.1007 / BF02435921
Masahide Sasaki, Kentaro Kato, Masayuki Izutsu et Osamu Hirota, "Canaux quantiques montrant une superadditivité dans une capacité classique" Physical Review A 58, 146–158 (1998).
https: / / doi.org/ 10.1103 / PhysRevA.58.146
YC Eldar et Jr. Forney "Sur la détection quantique et la mesure de la racine carrée" Transactions IEEE sur la théorie de l'information 47, 858–872 (2001).
https: / / doi.org/ 10.1109 / 18.915636
Tom Richardson et Rüdiger Urbanke "Théorie du codage moderne" Cambridge University Press (2008).
https: / / doi.org/ 10.1017 / CBO9780511791338
David Poulin "Décodage optimal et efficace des codes de blocs quantiques concaténés" Examen physique A 74, 052333 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.052333
David Poulin et Yeojin Chung "Sur le décodage itératif des codes quantiques clairsemés" Quantum Information and Computation 8, 987–1000 (2008).
https: / / doi.org/ 10.26421 / QIC8.10-8
arXiv: 0801.1241
Yun-Jiang Wang, Barry C. Sanders, Bao-Ming Bai et Xin-Mei Wang, "Décodage itératif à rétroaction améliorée des codes quantiques clairsemés" Transactions IEEE sur la théorie de l'information 58, 1231–1241 (2012).
https: / / doi.org/ 10.1109 / TIT.2011.2169534
arXiv: 0912.4546
Ben Criger et Imran Ashraf "Sommation multi-chemins pour décoder les codes topologiques 2D" Quantum 2, 102 (2018).
https://doi.org/10.22331/q-2018-10-19-102
arXiv: 1709.02154
Ye-Hua Liu et David Poulin « Décodeurs de propagation de croyance neurale pour les codes de correction d'erreurs quantiques » Lettres d'examen physique 122, 200501 (2019).
https: / / doi.org/ 10.1103 / PhysRevLett.122.200501
arXiv: 1811.07835
Alex Rigby, JC Olivier et 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
Pavel Panteleev et Gleb Kalachev « Codes LDPC quantiques dégénérés avec de bonnes performances de longueur finie » Quantum 5, 585 (2021).
https://doi.org/10.22331/q-2021-11-22-585
July X. Li et Pascal O. Vontobel "Décodage basé sur des pseudo-mots de code des codes de stabilisateur quantique" 2019 Symposium international IEEE sur la théorie de l'information (ISIT) 2888–2892 (2019).
https: / / doi.org/ 10.1109 / ISIT.2019.8849833
arXiv: 1903.01202
Joschka Roffe, David R. White, Simon Burton et Earl Campbell, "Décodage dans le paysage du code de contrôle de parité à faible densité quantique" Physical Review Research 2, 043423 (2020).
https: / / doi.org/ 10.1103 / PhysRevResearch.2.043423
arXiv: 2005.07016
July X. Li, Joseph M. Renes et Pascal O. Vontobel, "Décodage basé sur des pseudo-mots de code des codes de couleur quantiques" (2020).
https:///doi.org/10.48550/arXiv.2010.10845
arXiv: 2010.10845
Srikar Kasi et Kyle Jamieson "Vers la propagation des croyances quantiques pour le décodage LDPC dans les réseaux sans fil" Actes de la 26e Conférence internationale annuelle sur l'informatique mobile et les réseaux 1–14 (2020).
https: / / doi.org/ 10.1145 / 3372224.3419207
arXiv: 2007.11069
MS Leifer et D. Poulin "Modèles graphiques quantiques et propagation des croyances" 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
HA Bethe "Théorie statistique des super-réseaux" Actes de la Royal Society A 150, 552–575 (1935).
https: / / doi.org/ 10.1098 / rspa.1935.0122
http:///rspa.royalsocietypublishing.org/content/150/871/552
Rudolf Peierls "Théorie statistique des super-réseaux avec des concentrations inégales des composants" Actes de la Royal Society A 154, 207–222 (1936).
https: / / doi.org/ 10.1098 / rspa.1936.0047
Jonathan S. Yedidia, William T. Freeman et Yair Weiss, "Propagation généralisée des croyances" Actes de la 13e Conférence internationale sur les systèmes de traitement de l'information neuronale 668–674 (2000).
Jonathan S. Yedidia, William T. Freeman et Yair Weiss, « Comprendre la propagation des croyances et ses généralisations » Morgan Kaufmann Publishers Inc. (2003).
https:///www.merl.com/publications/docs/TR2001-22.pdf
JS Yedidia, WT Freeman et Y. Weiss, "Construction d'approximations d'énergie libre et d'algorithmes de propagation de croyances généralisées" Théorie de l'information, IEEE Transactions on 51, 2282–2312 (2005).
https: / / doi.org/ 10.1109 / TIT.2005.850085
MB Hastings « Propagation des croyances quantiques : un algorithme pour les systèmes quantiques thermiques » Examen physique B 76, 201102 (2007).
https: / / doi.org/ 10.1103 / PhysRevB.76.201102
arXiv: 0706.4094
David Poulin et Matthew B. Hastings «Décomposition de l'entropie de Markov: un double variationnel pour la propagation des croyances quantiques» Lettres d'examen physique 106, 080403 (2011).
https: / / doi.org/ 10.1103 / PhysRevLett.106.080403
arXiv: 1012.2050
MX Cao et PO Vontobel "Graphes de facteurs quantiques : opération de fermeture de la boîte et approches variationnelles" 2016 Symposium international sur la théorie de l'information et ses applications (ISITA) 651–655 (2016).
https: / / ieeexplore.ieee.org/ document / 7840505
FR Kschischang, BJ Frey et HA Loeliger, "Graphes factoriels et algorithme somme-produit" IEEE Transactions on Information Theory 47, 498–519 (2001).
https: / / doi.org/ 10.1109 / 18.910572
G. David Forney "Codes sur les graphiques : réalisations normales" Transactions IEEE sur la théorie de l'information 47, 520–548 (2001).
https: / / doi.org/ 10.1109 / 18.910573
CW Helstrom "Théorie de la détection et de l'estimation quantiques" Academic (1976).
https://doi.org/10.1016/S0076-5392(08)60247-7
http:///www.sciencedirect.com/science/bookseries/00765392/123
Saikat Guha "Récepteurs optiques structurés pour atteindre la capacité superadditive et la limite Holevo" Lettres d'examen physique 106, 240502 (2011).
https: / / doi.org/ 10.1103 / PhysRevLett.106.240502
arXiv: 1101.1550
T. Etzion, A. Trachtenberg et A. Vardy, "Which Codes Have Cycle-Free Tanner Graphs?" Transactions IEEE sur la théorie de l'information 45, 2173–2181 (1999).
https: / / doi.org/ 10.1109 / 18.782170
Jacob C. Bridgeman et Christopher T. Chubb "Hand-Waving and Interpretive Dance: An Introduction 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
Ville Bergholm, Juha J. Vartiainen, Mikko Mottonen et Martti M. Salomaa, "Circuits quantiques avec des portes à un qubit uniformément contrôlées" Examen physique A 71, 052330 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.052330
http:///arxiv.org/abs/quant-ph/0410066
CH Bennett "Réversibilité logique du calcul" IBM Journal of Research and Development 17, 525–532 (1973).
https: / / doi.org/ 10.1147 / rd.176.0525
Richard P. Brent "Méthodes de recherche de zéro à précision multiple et complexité de l'évaluation des fonctions élémentaires" 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
Harvey et van der Hoeven "Multiplication d'entiers dans le temps O (n Log n)" Annals of Mathematics 193, 563 (2021).
https: / / doi.org/ 10.4007 / annals.2021.193.2.4
Yudong Cao, Anargyros Papageorgiou, Iasonas Petras, Joseph Traub et Saber Kais, "Algorithme quantique et conception de circuits résolvant l'équation de Poisson" New Journal of Physics 15, 013021 (2013).
https://doi.org/10.1088/1367-2630/15/1/013021
arXiv: 1207.2485
Mihir K. Bhaskar, Stuart Hadfield, Anargyros Papageorgiou et Iasonas Petras, "Algorithmes et circuits quantiques pour le calcul scientifique" Quantum Information & Computation 16, 197–236 (2016).
https: / / doi.org/ 10.26421 / QIC16.3-4-2
arXiv: 1511.08253
Thomas Häner, Martin Roetteler et Krysta M. Svore, "Optimisation des circuits quantiques pour l'arithmétique" (2018).
https:///doi.org/10.48550/arXiv.1805.12445
arXiv: 1805.12445
Shengbin Wang, Zhimin Wang, Wendong Li, Lixin Fan, Guolong Cui, Zhiqiang Wei et Yongjian Gu, "Conception de circuits quantiques pour l'évaluation de fonctions transcendantales basée sur une méthode d'expansion binaire fonction-valeur" Traitement de l'information quantique 19, 347 (2020).
https://doi.org/10.1007/s11128-020-02855-7
arXiv: 2001.00807
John Watrous "La théorie de l'information quantique" Cambridge University Press (2018).
https: / / doi.org/ 10.1017 / 9781316848142
https:///www.cambridge.org/core/product/identifier/9781316848142/type/book
Dagmar Bruß, David P. DiVincenzo, Artur Ekert, Christopher A. Fuchs, Chiara Macchiavello et 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
E. Arıkan "Polarisation des canaux : une méthode de construction de codes de capacité pour les canaux symétriques à entrée binaire sans mémoire" Transactions IEEE sur la théorie de l'information 55, 3051–3073 (2009).
https: / / doi.org/ 10.1109 / TIT.2009.2021379
arXiv: 0807.3917
Mark M. Wilde et Saikat Guha "Codes polaires pour les canaux quantiques classiques" Transactions IEEE sur la théorie de l'information 59, 1175–1187 (2013).
https: / / doi.org/ 10.1109 / TIT.2012.2218792
arXiv: 1109.2591
Joseph M. Renes et Mark M. Wilde "Codes polaires pour la communication privée et quantique sur des canaux arbitraires" Transactions IEEE sur la théorie de l'information 60, 3090–3103 (2014).
https: / / doi.org/ 10.1109 / TIT.2014.2314463
arXiv: 1212.2537
S. Guha et MM Wilde «Codage polaire pour atteindre la capacité Holevo d'un canal optique à perte pure», Actes du Symposium international IEEE 2012 sur la théorie de l'information (ISIT) 546–550 (2012).
https: / / doi.org/ 10.1109 / ISIT.2012.6284250
arXiv: 1202.0533
Cité par
[1] S. Brandsen, Avijit Mandal et Henry D. Pfister, "Propagation des croyances avec des messages quantiques pour les canaux quantiques classiques symétriques", arXiv: 2207.04984.
Les citations ci-dessus proviennent de SAO / NASA ADS (dernière mise à jour réussie 2022-08-23 14:04:15). La liste peut être incomplète car tous les éditeurs ne fournissent pas de données de citation appropriées et complètes.
Impossible de récupérer Données de référence croisée lors de la dernière tentative 2022-08-23 14:04:14: Impossible de récupérer les données citées par 10.22331 / q-2022-08-23-784 de Crossref. C'est normal si le DOI a été enregistré récemment.
Cet article est publié dans Quantum sous le Creative Commons Attribution 4.0 International (CC BY 4.0) Licence. Le droit d'auteur reste la propriété des détenteurs d'origine tels que les auteurs ou leurs institutions.
