Istituto di Fisica Teorica, ETH Zurigo, Svizzera
Trovi questo documento interessante o vuoi discuterne? Scrivi o lascia un commento su SciRate.
Astratto
Recentemente, Renes ha proposto un algoritmo quantistico chiamato propagazione delle credenze con messaggi quantistici (BPQM) per la decodifica di dati classici codificati utilizzando un codice lineare binario con grafo ad albero Tanner che viene trasmesso su un canale CQ a stato puro [1], cioè un canale con ingresso classico e uscita quantistica allo stato puro. L'algoritmo presenta una vera controparte quantistica alla decodifica basata sul classico algoritmo di propagazione delle credenze, che ha riscontrato un ampio successo nella teoria della codifica classica quando utilizzato insieme ai codici LDPC o Turbo. Più recentemente Rengaswamy $et$ $al.$ [2] ha osservato che BPQM implementa il decodificatore ottimale su un piccolo codice di esempio, in quanto implementa la misurazione ottimale che distingue gli stati quantistici di output per l'insieme di parole di codice di input con la probabilità più alta ottenibile. Qui espandiamo significativamente la comprensione, il formalismo e l'applicabilità dell'algoritmo BPQM con i seguenti contributi. In primo luogo, dimostriamo analiticamente che BPQM realizza la decodifica ottimale per qualsiasi codice binario lineare con grafo di Tanner ad albero. Forniamo anche la prima descrizione formale dell'algoritmo BPQM in dettaglio e senza alcuna ambiguità. In tal modo, identifichiamo un difetto chiave trascurato nell'algoritmo originale e nei lavori successivi che implica che le realizzazioni di circuiti quantistici saranno esponenzialmente grandi nella dimensione del codice. Sebbene BPQM trasmetta messaggi quantistici, altre informazioni richieste dall'algoritmo vengono elaborate a livello globale. Risolviamo questo problema formulando un vero algoritmo di passaggio di messaggi che approssima BPQM e ha complessità del circuito quantistico $mathcal{O}(text{poly } n, text{polylog } frac{1}{epsilon})$, dove $n$ è la lunghezza del codice e $epsilon$ è l'errore di approssimazione. Infine, proponiamo anche un nuovo metodo per estendere BPQM a grafi fattoriali contenenti cicli utilizzando la clonazione approssimata. Mostriamo alcuni risultati numerici promettenti che indicano che BPQM su grafici fattoriali con cicli può sovraperformare significativamente il miglior decodificatore classico possibile.
► dati BibTeX
► Riferimenti
, Joseph M. Renes "Delief Propagation Decoding of Quantum Channels by Passing Quantum Messages" 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 e Henry D. Pfister, "Belief Propagation with Quantum Messages for Quantum-Enhanced Classical Communications" npj Quantum Information 7, 97 (2021).
https://doi.org/10.1038/s41534-021-00422-1
arXiv: 2003.04356
https: / / www.nature.com/ articoli / s41534-021-00422-1
, S. Kudekar, T. Richardson e RL Urbanke, "Gli insiemi accoppiati nello spazio raggiungono universalmente la capacità sotto la propagazione delle credenze" IEEE Transactions on Information Theory 59, 7761–7813 (2013).
https: / / doi.org/ 10.1109 / TIT.2013.2280915
arXiv: 1201.2999
, HA Loeliger e 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 e PO Vontobel "Grafici a fattori a doppio margine: definizione, proprietà ed esempi" 2017 IEEE Information Theory Workshop (ITW) 136–140 (2017).
https:///doi.org/10.1109/ITW.2017.8277985
arXiv: 1706.00752
, Hans-Andrea Loeliger "An Introduction to Factor Graphs" Rivista IEEE Signal Processing 21, 28–41 (2004).
https: / / doi.org/ 10.1109 / MSP.2004.1267047
, VP Belavkin "Test di ipotesi statistiche quantistiche multiple ottimali" Stochastics 1, 315 (1975).
https: / / doi.org/ 10.1080 / 17442507508833114 mila
, Paul Hausladen e William K. Wootters "Una misura 'abbastanza buona' per distinguere gli stati quantistici" Journal of Modern Optics 41, 2385 (1994).
https: / / doi.org/ 10.1080 / 09500349414552221 mila
, Narayanan Rengaswamy e 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
, Masashi Ban, Keiko Kurokawa, Rei Momose e Osamu Hirota, "Misure ottimali per la discriminazione tra stati quantistici simmetrici e stima dei parametri" International Journal of Theoretical Physics 36, 1269–1288 (1997).
https: / / doi.org/ 10.1007 / BF02435921
, Masahide Sasaki, Kentaro Kato, Masayuki Izutsu e Osamu Hirota, "Canali quantistici che mostrano la superadditività nella capacità classica" Revisione fisica A 58, 146–158 (1998).
https: / / doi.org/ 10.1103 / PhysRevA.58.146
, YC Eldar e 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 mila
, Tom Richardson e Rüdiger Urbanke "Teoria della codifica moderna" Cambridge University Press (2008).
https: / / doi.org/ 10.1017 / CBO9780511791338
, David Poulin "Decodifica ottimale ed efficiente di codici a blocchi concatenati" Physical Review A 74, 052333 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.052333
, David Poulin e Yeojin Chung "On the Iterative Decoding of Sparse Quantum Codes" Quantum Information and Computation 8, 987–1000 (2008).
https: / / doi.org/ 10.26421 mila / QIC8.10-8
arXiv: 0801.1241
, Yun-Jiang Wang, Barry C. Sanders, Bao-Ming Bai e Xin-Mei Wang, "Enhanced Feedback Iterative Decoding of Sparse Quantum Codes" Transazioni IEEE sulla teoria dell'informazione 58, 1231–1241 (2012).
https: / / doi.org/ 10.1109 / TIT.2011.2169534
arXiv: 0912.4546
, Ben Criger e Imran Ashraf "Summa multi-percorso per la decodifica di codici topologici 2D" Quantum 2, 102 (2018).
https://doi.org/10.22331/q-2018-10-19-102
arXiv: 1709.02154
, Ye-Hua Liu e David Poulin "Decodificatori di propagazione delle credenze neurali per codici di correzione degli errori quantistici" lettere di revisione fisica 122, 200501 (2019).
https: / / doi.org/ 10.1103 / PhysRevLett.122.200501
arXiv: 1811.07835
, Alex Rigby, JC Olivier e 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 e Gleb Kalachev "Codici LDPC quantistici degenerati con buone prestazioni di lunghezza finita" Quantum 5, 585 (2021).
https://doi.org/10.22331/q-2021-11-22-585
, Luglio X. Li e 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
, Joschka Roffe, David R. White, Simon Burton e 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
, Luglio X. Li, Joseph M. Renes e Pascal O. Vontobel, "Decodifica dei codici colore quantistici basata su pseudocodeword" (2020).
https:///doi.org/10.48550/arXiv.2010.10845
arXiv: 2010.10845
, Srikar Kasi e Kyle Jamieson "Towards Quantum Belief Propagation for LDPC Decoding in Wireless Networks" Atti della 26a conferenza internazionale annuale su Mobile Computing and Networking 1–14 (2020).
https: / / doi.org/ 10.1145 / 3372224.3419207 mila
arXiv: 2007.11069
, MS Leifer e D. Poulin "Modelli grafici quantistici e propagazione delle credenze" Annali di fisica 323, 1899–1946 (2008).
https: / / doi.org/ 10.1016 / j.aop.2007.10.001
arXiv: 0708.1337
http: / / www.sciencedirect.com/ scienza / article / PII / S0003491607001509
, HA Bethe "Teoria statistica dei superreticoli" Atti della 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 "Teoria statistica dei superreticoli con concentrazioni diseguali dei componenti" Atti della Royal Society A 154, 207–222 (1936).
https: / / doi.org/ 10.1098 / rspa.1936.0047
, Jonathan S. Yedidia, William T. Freeman e Yair Weiss, "Propagazione delle credenze generalizzate" Atti della 13a conferenza internazionale sui sistemi di elaborazione delle informazioni neurali 668–674 (2000).
, Jonathan S. Yedidia, William T. Freeman e Yair Weiss, "Capire la propagazione delle credenze e le sue generalizzazioni" Morgan Kaufmann Publishers Inc. (2003).
https:///www.merl.com/publications/docs/TR2001-22.pdf
, JS Yedidia, WT Freeman e Y. Weiss, "Costruire approssimazioni di energia libera e algoritmi di propagazione delle credenze generalizzate" Teoria dell'informazione, Transazioni IEEE su 51, 2282–2312 (2005).
https: / / doi.org/ 10.1109 / TIT.2005.850085
, 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
, David Poulin e 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
, MX Cao e PO Vontobel "Quantum Factor Graphs: Closing-the-Box Operation and Variational Approaches" 2016 Simposio internazionale sulla teoria dell'informazione e le sue applicazioni (ISITA) 651–655 (2016).
https: / / ieeexplore.ieee.org/ documento / 7840505
, FR Kschischang, BJ Frey e 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 mila
, G. David Forney "Codici sui grafici: realizzazioni normali" IEEE Transactions on Information Theory 47, 520–548 (2001).
https: / / doi.org/ 10.1109 / 18.910573 mila
, Accademico CW Helstrom "Rilevamento quantistico e teoria della stima" (1976).
https://doi.org/10.1016/S0076-5392(08)60247-7
http:///www.sciencedirect.com/science/bookseries/00765392/123
, Saikat Guha "Ricevitori ottici strutturati per raggiungere la capacità superadditiva e il limite di Holevo" Lettere di revisione fisica 106, 240502 (2011).
https: / / doi.org/ 10.1103 / PhysRevLett.106.240502
arXiv: 1101.1550
, T. Etzion, A. Trachtenberg e A. Vardy, "Quali codici hanno grafici abbronzanti senza ciclo?" Transazioni IEEE sulla teoria dell'informazione 45, 2173–2181 (1999).
https: / / doi.org/ 10.1109 / 18.782170 mila
, Jacob C. Bridgeman e 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
, Ville Bergholm, Juha J. Vartiainen, Mikko Mottonen e Martti M. Salomaa, "Circuiti quantistici con gate a un Qubit controllati in modo uniforme" Recensione fisica A 71, 052330 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.052330
http: / / arxiv.org/ abs / quant-ph / 0410066
, CH Bennett "Reversibilità logica del calcolo" IBM Journal of Research and Development 17, 525–532 (1973).
https: / / doi.org/ 10.1147 / rd.176.0525
, Richard P. Brent "Metodi di ricerca zero a precisione multipla e complessità della valutazione della funzione elementare" 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 e van der Hoeven "Moltiplicazione intera nel tempo 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 e Saber 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
, Mihir K. Bhaskar, Stuart Hadfield, Anargyros Papageorgiou e 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
, Thomas Häner, Martin Roetteler e Krysta M. Svore, "Ottimizzazione dei circuiti quantistici per l'aritmetica" (2018).
https:///doi.org/10.48550/arXiv.1805.12445
arXiv: 1805.12445
, Shengbin Wang, Zhimin Wang, Wendong Li, Lixin Fan, Guolong Cui, Zhiqiang Wei e Yongjian Gu, "Progettazione di circuiti quantistici per la valutazione di funzioni trascendentali basate su un metodo di espansione binaria del valore di funzione" Elaborazione delle informazioni quantistiche 19, 347 (2020).
https://doi.org/10.1007/s11128-020-02855-7
arXiv: 2001.00807
, John Watrous "The Theory of Quantum Information" Cambridge University Press (2018).
https: / / doi.org/ 10.1017 / 9781316848142 mila
https:///www.cambridge.org/core/product/identifier/9781316848142/type/libro
, Dagmar Bruß, David P. DiVincenzo, Artur Ekert, Christopher A. Fuchs, Chiara Macchiavello e 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 "Polarizzazione del canale: un metodo per la costruzione di codici di raggiungimento della capacità per canali senza memoria con input binario simmetrico" Transazioni IEEE sulla teoria dell'informazione 55, 3051–3073 (2009).
https: / / doi.org/ 10.1109 / TIT.2009.2021379
arXiv: 0807.3917
, Mark M. Wilde e Saikat Guha "Codici polari per i canali quantistici classici" Transazioni IEEE sulla teoria dell'informazione 59, 1175–1187 (2013).
https: / / doi.org/ 10.1109 / TIT.2012.2218792
arXiv: 1109.2591
, Joseph M. Renes e Mark M. Wilde "Codici polari per la comunicazione privata e quantistica su canali arbitrari" IEEE Transactions on Information Theory 60, 3090–3103 (2014).
https: / / doi.org/ 10.1109 / TIT.2014.2314463
arXiv: 1212.2537
, S. Guha e MM Wilde "Polar Coding to Achieve the Holevo Capacity of a Pure-Loss Optical Channel" Atti del 2012 IEEE International Symposium on Information Theory (ISIT) 546–550 (2012).
https: / / doi.org/ 10.1109 / ISIT.2012.6284250
arXiv: 1202.0533
Citato da
[1] S. Brandsen, Avijit Mandal e Henry D. Pfister, "Propagazione delle credenze con messaggi quantistici per canali quantistici classici simmetrici", arXiv: 2207.04984.
Le citazioni sopra sono di ANNUNCI SAO / NASA (ultimo aggiornamento riuscito 2022-08-23 14:04:15). L'elenco potrebbe essere incompleto poiché non tutti gli editori forniscono dati di citazione adeguati e completi.
Impossibile recuperare Crossref citato da dati durante l'ultimo tentativo 2022-08-23 14:04:14: Impossibile recuperare i dati citati per 10.22331 / q-2022-08-23-784 da Crossref. Questo è normale se il DOI è stato registrato di recente.
Questo documento è pubblicato in Quantum sotto il Creative Commons Attribuzione 4.0 Internazionale (CC BY 4.0) licenza. Il copyright rimane dei detentori del copyright originali come gli autori o le loro istituzioni.
