Instituto de Física Teórica, ETH Zürich, Suiza
¿Encuentra este documento interesante o quiere discutirlo? Scite o deje un comentario en SciRate.
Resumen
Recientemente, Renes propuso un algoritmo cuántico llamado propagación de creencias con mensajes cuánticos (BPQM) para decodificar datos clásicos codificados utilizando un código lineal binario con un gráfico de árbol de Tanner que se transmite a través de un canal CQ de estado puro.1], es decir, un canal con entrada clásica y salida cuántica en estado puro. El algoritmo presenta una contrapartida cuántica genuina a la decodificación basada en el algoritmo clásico de propagación de creencias, que ha tenido un gran éxito en la teoría de codificación clásica cuando se usa junto con códigos LDPC o Turbo. Más recientemente Rengaswamy $et$ $al.$ [2] observó que BPQM implementa el decodificador óptimo en un código de ejemplo pequeño, ya que implementa la medición óptima que distingue los estados de salida cuánticos para el conjunto de palabras de código de entrada con la mayor probabilidad alcanzable. Aquí ampliamos significativamente la comprensión, el formalismo y la aplicabilidad del algoritmo BPQM con las siguientes contribuciones. Primero, demostramos analíticamente que BPQM realiza una decodificación óptima para cualquier código lineal binario con un gráfico de árbol de Tanner. También proporcionamos la primera descripción formal del algoritmo BPQM con todo detalle y sin ninguna ambigüedad. Al hacerlo, identificamos una falla clave pasada por alto en el algoritmo original y los trabajos posteriores que implican que las realizaciones de circuitos cuánticos serán exponencialmente grandes en la dimensión del código. Aunque BPQM pasa mensajes cuánticos, otra información requerida por el algoritmo se procesa globalmente. Solucionamos este problema formulando un verdadero algoritmo de paso de mensajes que se aproxima a BPQM y tiene una complejidad de circuito cuántico $mathcal{O}(text{poly } n, text{polylog } frac{1}{epsilon})$, donde $n$ es la longitud del código y $epsilon$ es el error de aproximación. Finalmente, también proponemos un método novedoso para extender BPQM a gráficos de factores que contienen ciclos haciendo uso de la clonación aproximada. Mostramos algunos resultados numéricos prometedores que indican que BPQM en gráficos de factores con ciclos puede superar significativamente al mejor decodificador clásico posible.
► datos BibTeX
► referencias
[ 1 ] Joseph M. Renes "Descodificación de propagación de creencias de canales cuánticos mediante la transmisión de mensajes cuánticos" 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 y Henry D. Pfister, "Propagación de creencias con mensajes cuánticos para comunicaciones clásicas mejoradas cuánticamente" npj Información cuántica 7, 97 (2021).
https://doi.org/10.1038/s41534-021-00422-1
arXiv: 2003.04356
https: / / www.nature.com/ articles / s41534-021-00422-1
[ 3 ] S. Kudekar, T. Richardson y RL Urbanke, "Los conjuntos acoplados espacialmente alcanzan capacidad universal bajo la propagación de creencias" IEEE Transactions on Information Theory 59, 7761–7813 (2013).
https: / / doi.org/ 10.1109 / TIT.2013.2280915
arXiv: 1201.2999
[ 4 ] HA Loeliger y PO Vontobel "Factor Graphs for Quantum Probabilidades" IEEE Transactions on Information Theory 63, 5642–5665 (2017).
https: / / doi.org/ 10.1109 / TIT.2017.2716422
arXiv: 1508.00689
[ 5 ] MX Cao y PO Vontobel "Gráficos de factores de doble borde: definición, propiedades y ejemplos" 2017 Taller de teoría de la información IEEE (ITW) 136–140 (2017).
https: / / doi.org/ 10.1109 / ITW.2017.8277985
arXiv: 1706.00752
[ 6 ] Hans-Andrea Loeliger "Una introducción a los gráficos de factores" IEEE Signal Processing Magazine 21, 28–41 (2004).
https: / / doi.org/ 10.1109 / MSP.2004.1267047
[ 7 ] VP Belavkin "Prueba de hipótesis estadística cuántica múltiple óptima" Estocástica 1, 315 (1975).
https: / / doi.org/ 10.1080 / 17442507508833114
[ 8 ] Paul Hausladen y William K. Wootters "Una medida 'bastante buena' para distinguir estados cuánticos" Journal of Modern Optics 41, 2385 (1994).
https: / / doi.org/ 10.1080 / 09500349414552221
[ 9 ] Narayanan Rengaswamy y Henry D. Pfister "Una prueba semiclásica de dualidad entre el BSC clásico y el PSC cuántico" (2021).
https:///doi.org/10.48550/arXiv.2103.09225
arXiv: 2103.09225
[ 10 ] Masashi Ban, Keiko Kurokawa, Rei Momose y Osamu Hirota, "Medidas óptimas para la discriminación entre estados cuánticos simétricos y estimación de parámetros" International Journal of Theoretical Physics 36, 1269–1288 (1997).
https: / / doi.org/ 10.1007 / BF02435921
[ 11 ] Masahide Sasaki, Kentaro Kato, Masayuki Izutsu y 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 y Jr. Forney "Sobre la detección cuántica y la medición de la raíz cuadrada" IEEE Transactions on Information Theory 47, 858–872 (2001).
https: / / doi.org/ 10.1109 / 18.915636
[ 13 ] Tom Richardson y Rüdiger Urbanke "Teoría de la codificación moderna" Cambridge University Press (2008).
https: / / doi.org/ 10.1017 / CBO9780511791338
[ 14 ] David Poulin "Descodificación óptima y eficiente de códigos de bloques cuánticos concatenados" Revisión física A 74, 052333 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.052333
[ 15 ] David Poulin y Yeojin Chung "Sobre la decodificación iterativa de códigos cuánticos dispersos" 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 y Xin-Mei Wang, "Decodificación iterativa de retroalimentación mejorada de códigos cuánticos dispersos" IEEE Transactions on Information Theory 58, 1231–1241 (2012).
https: / / doi.org/ 10.1109 / TIT.2011.2169534
arXiv: 0912.4546
[ 17 ] Ben Criger e Imran Ashraf "Suma de rutas múltiples para decodificar códigos topológicos 2D" Quantum 2, 102 (2018).
https://doi.org/10.22331/q-2018-10-19-102
arXiv: 1709.02154
[ 18 ] Ye-Hua Liu y David Poulin "Decodificadores de propagación de creencias neuronales para códigos de corrección de errores cuánticos" Physical Review Letters 122, 200501 (2019).
https: / / doi.org/ 10.1103 / PhysRevLett.122.200501
arXiv: 1811.07835
[ 19 ] Alex Rigby, JC Olivier y Peter Jarvis, "Decodificadores de propagación de creencias modificados para códigos de verificación de paridad de baja densidad cuántica" Revisión física A 100, 012330 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.100.012330
arXiv: 1903.07404
[ 20 ] Pavel Panteleev y Gleb Kalachev "Códigos LDPC cuánticos degenerados con buen rendimiento de longitud finita" Quantum 5, 585 (2021).
https://doi.org/10.22331/q-2021-11-22-585
[ 21 ] July X. Li y Pascal O. Vontobel "Descodificación basada en pseudopalabras codificadas de códigos estabilizadores cuánticos" Simposio internacional IEEE sobre teoría de la información (ISIT) 2019 2888–2892 (2019).
https: / / doi.org/ 10.1109 / ISIT.2019.8849833
arXiv: 1903.01202
[ 22 ] Joschka Roffe, David R. White, Simon Burton y Earl Campbell, "Decodificación en el panorama del código de verificación de paridad de baja densidad cuántica" Physical Review Research 2, 043423 (2020).
https: / / doi.org/ 10.1103 / PhysRevResearch.2.043423
arXiv: 2005.07016
[ 23 ] July X. Li, Joseph M. Renes y Pascal O. Vontobel, "Descodificación de códigos de colores cuánticos basada en pseudopalabras codificadas" (2020).
https:///doi.org/10.48550/arXiv.2010.10845
arXiv: 2010.10845
[ 24 ] Srikar Kasi y Kyle Jamieson "Hacia la propagación de creencias cuánticas para la decodificación de LDPC en redes inalámbricas" Actas de la 26.ª Conferencia internacional anual sobre informática móvil y redes 1–14 (2020).
https: / / doi.org/ 10.1145 / 3372224.3419207
arXiv: 2007.11069
[ 25 ] MS Leifer y D. Poulin "Modelos gráficos cuánticos y propagación de creencias" 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 "Teoría estadística de las superredes" Actas 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
[ 27 ] Rudolf Peierls "Teoría estadística de superredes con concentraciones desiguales de los componentes" Actas de la Royal Society A 154, 207–222 (1936).
https: / / doi.org/ 10.1098 / rspa.1936.0047
[ 28 ] Jonathan S. Yedidia, William T. Freeman y Yair Weiss, Actas de "Propagación de creencias generalizadas" de la 13.ª Conferencia internacional sobre sistemas de procesamiento de información neuronal 668–674 (2000).
[ 29 ] Jonathan S. Yedidia, William T. Freeman y Yair Weiss, "Comprender la propagación de creencias y sus generalizaciones" Morgan Kaufmann Publishers Inc. (2003).
https://www.merl.com/publications/docs/TR2001-22.pdf
[ 30 ] JS Yedidia, WT Freeman e Y. Weiss, "Construcción de aproximaciones de energía libre y algoritmos de propagación de creencias generalizadas" Teoría de la información, IEEE Transactions on 51, 2282–2312 (2005).
https: / / doi.org/ 10.1109 / TIT.2005.850085
[ 31 ] MB Hastings "Propagación de creencias cuánticas: un algoritmo para sistemas cuánticos térmicos" Revisión física B 76, 201102 (2007).
https: / / doi.org/ 10.1103 / PhysRevB.76.201102
arXiv: 0706.4094
[ 32 ] David Poulin y Matthew B. Hastings "Descomposición de entropía de Markov: un dual variacional para la propagación de creencias cuánticas" Physical Review Letters 106, 080403 (2011).
https: / / doi.org/ 10.1103 / PhysRevLett.106.080403
arXiv: 1012.2050
[ 33 ] MX Cao y PO Vontobel "Gráficos de factores cuánticos: operación de cierre de caja y enfoques variacionales" Simposio internacional sobre teoría de la información y sus aplicaciones (ISITA) 2016 651–655 (2016).
https: / / ieeexplore.ieee.org/ document / 7840505
[ 34 ] FR Kschischang, BJ Frey y 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 "Códigos en gráficos: realizaciones normales" IEEE Transactions on Information Theory 47, 520–548 (2001).
https: / / doi.org/ 10.1109 / 18.910573
[ 36 ] CW Helstrom "Teoría de estimación y detección cuántica" Académico (1976).
https://doi.org/10.1016/S0076-5392(08)60247-7
http: / / www.sciencedirect.com/ science / bookseries / 00765392/123
[ 37 ] Saikat Guha "Receptores ópticos estructurados para lograr una capacidad superaditiva y el límite de Holevo" Physical Review Letters 106, 240502 (2011).
https: / / doi.org/ 10.1103 / PhysRevLett.106.240502
arXiv: 1101.1550
[ 38 ] T. Etzion, A. Trachtenberg y A. Vardy, "¿Qué códigos tienen gráficos de Tanner sin ciclos?" IEEE Transactions on Information Theory 45, 2173–2181 (1999).
https: / / doi.org/ 10.1109 / 18.782170
[ 39 ] Jacob C. Bridgeman y Christopher T. Chubb "Agitar las manos y danza interpretativa: un curso introductorio sobre redes de tensores" 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 y Martti M. Salomaa, "Circuitos cuánticos con puertas de un qubit controladas uniformemente" Revisión física A 71, 052330 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.052330
http: / / arxiv.org/ abs / quant-ph / 0410066
[ 41 ] CH Bennett "Reversibilidad lógica de la computación" IBM Journal of Research and Development 17, 525–532 (1973).
https: / / doi.org/ 10.1147 / rd.176.0525
[ 42 ] Richard P. Brent "Métodos de búsqueda de cero de precisión múltiple y la complejidad de la evaluación de funciones elementales" 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 y van der Hoeven "Multiplicación de enteros en el tiempo 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 y Saber Kais, "Algoritmo cuántico y diseño de circuitos para resolver la ecuación de Poisson" 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 y Iasonas Petras, "Algoritmos y circuitos cuánticos para la computación científica" Información y computación cuántica 16, 197–236 (2016).
https: / / doi.org/ 10.26421 / QIC16.3-4-2
arXiv: 1511.08253
[ 46 ] Thomas Häner, Martin Roetteler y Krysta M. Svore, "Optimización de circuitos cuánticos para la aritmética" (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 y Yongjian Gu, "Diseño de circuitos cuánticos para evaluar funciones trascendentales basado en un método de expansión binaria de función-valor" Procesamiento de información cuántica 19, 347 (2020).
https://doi.org/10.1007/s11128-020-02855-7
arXiv: 2001.00807
[ 48 ] John Watrous “La teoría de la información cuántica” 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 y John A. Smolin, “Clonación cuántica óptima universal y dependiente del estado” Physical Review A 57, 2368–2378 (1998).
https: / / doi.org/ 10.1103 / PhysRevA.57.2368
[ 50 ] E. Arıkan “Channel Polarization: A Method for Construction Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels” IEEE Transactions on Information Theory 55, 3051–3073 (2009).
https: / / doi.org/ 10.1109 / TIT.2009.2021379
arXiv: 0807.3917
[ 51 ] Mark M. Wilde y Saikat Guha "Códigos polares para canales cuánticos clásicos" IEEE Transactions on Information Theory 59, 1175–1187 (2013).
https: / / doi.org/ 10.1109 / TIT.2012.2218792
arXiv: 1109.2591
[ 52 ] Joseph M. Renes y Mark M. Wilde "Códigos polares para comunicaciones privadas y cuánticas a través de canales arbitrarios" IEEE Transactions on Information Theory 60, 3090–3103 (2014).
https: / / doi.org/ 10.1109 / TIT.2014.2314463
arXiv: 1212.2537
[ 53 ] S. Guha y MM Wilde "Codificación polar para lograr la capacidad Holevo de un canal óptico de pérdida pura" Actas del Simposio internacional sobre teoría de la información (ISIT) 2012 del IEEE 546–550 (2012).
https: / / doi.org/ 10.1109 / ISIT.2012.6284250
arXiv: 1202.0533
Citado por
[1] S. Brandsen, Avijit Mandal y Henry D. Pfister, "Propagación de creencias con mensajes cuánticos para canales simétricos clásicos cuánticos", arXiv: 2207.04984.
Las citas anteriores son de ANUNCIOS SAO / NASA (última actualización exitosa 2022-08-23 14:04:15). La lista puede estar incompleta ya que no todos los editores proporcionan datos de citas adecuados y completos.
No se pudo recuperar Crossref citado por datos durante el último intento 2022-08-23 14:04:14: No se pudieron obtener los datos citados por 10.22331 / q-2022-08-23-784 de Crossref. Esto es normal si el DOI se registró recientemente.
Este documento se publica en Quantum bajo el Creative Commons Reconocimiento 4.0 Internacional (CC BY 4.0) licencia. Los derechos de autor permanecen con los titulares de derechos de autor originales, como los autores o sus instituciones.
