Instituto de Física Teórica, ETH Zürich, Suíça
Acha este artigo interessante ou deseja discutir? Scite ou deixe um comentário no SciRate.
Sumário
Recentemente, Renes propôs um algoritmo quântico chamado propagação de crenças com mensagens quânticas (BPQM) para decodificar dados clássicos codificados usando um código linear binário com gráfico de Tanner de árvore que é transmitido por um canal CQ de estado puro.1], ou seja, um canal com entrada clássica e saída quântica de estado puro. O algoritmo apresenta uma contrapartida quântica genuína à decodificação baseada no algoritmo clássico de propagação de crenças, que obteve grande sucesso na teoria clássica de codificação quando usado em conjunto com códigos LDPC ou Turbo. Mais recentemente Rengaswamy $et$ $al.$ [2] observaram que o BPQM implementa o decodificador ótimo em um pequeno código de exemplo, na medida em que implementa a medida ótima que distingue os estados de saída quântica para o conjunto de palavras de código de entrada com maior probabilidade alcançável. Aqui expandimos significativamente o entendimento, formalismo e aplicabilidade do algoritmo BPQM com as seguintes contribuições. Primeiro, provamos analiticamente que o BPQM realiza a decodificação ótima para qualquer código linear binário com grafo de Tanner em árvore. Também fornecemos a primeira descrição formal do algoritmo BPQM com todos os detalhes e sem qualquer ambiguidade. Ao fazê-lo, identificamos uma falha chave negligenciada no algoritmo original e trabalhos subsequentes que implicam que as realizações de circuitos quânticos serão exponencialmente grandes na dimensão do código. Embora o BPQM passe mensagens quânticas, outras informações exigidas pelo algoritmo são processadas globalmente. Remediamos esse problema formulando um algoritmo verdadeiramente de passagem de mensagens que se aproxima de BPQM e tem complexidade de circuito quântico $mathcal{O}(text{poly} n, text{polylog } frac{1}{epsilon})$, onde $n$ é o comprimento do código e $epsilon$ é o erro de aproximação. Finalmente, também propomos um novo método para estender BPQM para grafos fatoriais contendo ciclos fazendo uso de clonagem aproximada. Mostramos alguns resultados numéricos promissores que indicam que BPQM em gráficos de fatores com ciclos pode superar significativamente o melhor decodificador clássico possível.
► dados BibTeX
► Referências
[1] Joseph M. Renes “Decodificação de Propagação de Crenças de Canais Quânticos Passando Mensagens Quânticas” 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 e Henry D. Pfister, “Propagação de Crenças com Mensagens Quânticas para Comunicações Clássicas Quantum-Enhanced” 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
[3] S. Kudekar, T. Richardson e RL Urbanke, “Spatially Coupled Ensembles Universally Reach 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 e PO Vontobel “Gráficos de Fator para Probabilidades Quânticas” IEEE Transactions on Information Theory 63, 5642–5665 (2017).
https: / / doi.org/ 10.1109 / TIT.2017.2716422
arXiv: 1508.00689
[5] MX Cao e PO Vontobel “Gráficos de fator de borda dupla: definição, propriedades e exemplos” 2017 IEEE Information Theory Workshop (ITW) 136–140 (2017).
https: / / doi.org/ 10.1109 / ITW.2017.8277985
arXiv: 1706.00752
[6] Hans-Andrea Loeliger “Uma Introdução aos Gráficos de Fatores” Revista de Processamento de Sinais IEEE 21, 28–41 (2004).
https: / / doi.org/ 10.1109 / MSP.2004.1267047
[7] VP Belavkin "Teste de hipótese estatística quântica múltipla ideal" Stochastics 1, 315 (1975).
https: / / doi.org/ 10.1080 / 17442507508833114
[8] Paul Hausladen e William K. Wootters “Uma Medição 'Muito Boa' para Distinguir Estados Quânticos” Journal of Modern Optics 41, 2385 (1994).
https: / / doi.org/ 10.1080 / 09500349414552221
[9] Narayanan Rengaswamy e Henry D. Pfister “Uma prova semiclássica da dualidade entre o BSC clássico e o PSC quântico” (2021).
https:///doi.org/10.48550/arXiv.2103.09225
arXiv: 2103.09225
[10] Masashi Ban, Keiko Kurokawa, Rei Momose e Osamu Hirota, “Medidas ótimas para discriminação entre estados quânticos simétricos e estimativa 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 e Osamu Hirota, “Canais Quânticos Mostrando Superaditividade na Capacidade Clássica” Revisão Física A 58, 146–158 (1998).
https: / / doi.org/ 10.1103 / PhysRevA.58.146
[12] 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
[13] Tom Richardson e Rüdiger Urbanke “Modern Coding Theory” Cambridge University Press (2008).
https: / / doi.org/ 10.1017 / CBO9780511791338
[14] David Poulin “Decodificação ideal e eficiente de códigos de blocos quânticos concatenados” Revisão física A 74, 052333 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.052333
[15] David Poulin e Yeojin Chung “Sobre a decodificação iterativa de códigos quânticos esparsos” 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 e Xin-Mei Wang, “Decodificação iterativa de feedback aprimorado de códigos quânticos esparsos” 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 “Soma de vários caminhos 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 e David Poulin “Decodificadores de Propagação de Crença Neural para Códigos de Correção de Erros Quânticos” Cartas de Revisão Física 122, 200501 (2019).
https: / / doi.org/ 10.1103 / PhysRevLett.122.200501
arXiv: 1811.07835
[19] Alex Rigby, JC Olivier e Peter Jarvis, “Modified Belief Propagation Decoders for Quantum Low-Density Parity-Check Codes” Revisão Física A 100, 012330 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.100.012330
arXiv: 1903.07404
[20] Pavel Panteleev e Gleb Kalachev “Códigos LDPC quânticos degenerados com bom desempenho de comprimento finito” Quantum 5, 585 (2021).
https://doi.org/10.22331/q-2021-11-22-585
[21] July X. Li e Pascal O. Vontobel “Decodificação baseada em pseudocódigo de códigos de estabilizador quântico” 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 e 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] July X. Li, Joseph M. Renes e Pascal O. Vontobel, “Decodificação baseada em pseudocódigo de códigos de cores quânticas” (2020).
https:///doi.org/10.48550/arXiv.2010.10845
arXiv: 2010.10845
[24] Srikar Kasi e Kyle Jamieson “Towards Quantum Belief Propagation for LDPC Decoding in Wireless Networks” Anais da 26ª Conferência Internacional Anual sobre Computação Móvel e Rede 1–14 (2020).
https: / / doi.org/ 10.1145 / 3372224.3419207
arXiv: 2007.11069
[25] MS Leifer e D. Poulin “Modelos Gráficos Quânticos e Propagação de Crenças” 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 “Teoria Estatística das Superredes” 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 "Teoria Estatística de Superredes com Concentrações Desiguais dos Componentes" 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 e Yair Weiss, “Propagação de Crenças Generalizadas” Anais da 13ª Conferência Internacional sobre Sistemas de Processamento de Informação Neural 668–674 (2000).
[29] Jonathan S. Yedidia, William T. Freeman e Yair Weiss, “Entendendo a Propagação de Crenças e Suas Generalizações” Morgan Kaufmann Publishers Inc. (2003).
https:///www.merl.com/publications/docs/TR2001-22.pdf
[30] JS Yedidia, WT Freeman e Y. Weiss, “Construindo Aproximações de Energia Livre e Algoritmos de Propagação de Crenças Generalizadas” Teoria da Informação, Transações IEEE em 51, 2282–2312 (2005).
https: / / doi.org/ 10.1109 / TIT.2005.850085
[31] MB Hastings “Propagação de Crenças Quânticas: Um Algoritmo para Sistemas Quânticos Térmicos” Revisão Física B 76, 201102 (2007).
https: / / doi.org/ 10.1103 / PhysRevB.76.201102
arXiv: 0706.4094
[32] David Poulin e Matthew B. Hastings “Decomposição de Entropia de Markov: Um Dual Variacional para Propagação de Crenças Quânticas” Cartas de Revisão Física 106, 080403 (2011).
https: / / doi.org/ 10.1103 / PhysRevLett.106.080403
arXiv: 1012.2050
[33] MX Cao e PO Vontobel “Gráficos de fatores quânticos: operação de fechamento de caixa e abordagens variacionais” 2016 Simpósio Internacional sobre Teoria da Informação e suas Aplicações (ISITA) 651–655 (2016).
https: / / ieeexplore.ieee.org/ document / 7840505
[34] FR Kschischang, BJ Frey e HA Loeliger, “Gráficos de fator e o algoritmo de produto de soma” IEEE Transactions on Information Theory 47, 498–519 (2001).
https: / / doi.org/ 10.1109 / 18.910572
[35] G. David Forney “Códigos em Gráficos: Realizações Normais” IEEE Transactions on Information Theory 47, 520–548 (2001).
https: / / doi.org/ 10.1109 / 18.910573
[36] CW Helstrom “Detecção Quântica e Teoria da Estimativa” Academic (1976).
https://doi.org/10.1016/S0076-5392(08)60247-7
http: / / www.sciencedirect.com/ science / bookseries / 00765392/123
[37] Saikat Guha “Receptores Ópticos Estruturados para Alcançar a Capacidade Superaditiva e o Limite de Holevo” Cartas de Revisão Física 106, 240502 (2011).
https: / / doi.org/ 10.1103 / PhysRevLett.106.240502
arXiv: 1101.1550
[38] T. Etzion, A. Trachtenberg, e A. Vardy, "Que códigos têm gráficos de Tanner sem ciclo?" IEEE Transactions on Information Theory 45, 2173-2181 (1999).
https: / / doi.org/ 10.1109 / 18.782170
[39] 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
[40] Ville Bergholm, Juha J. Vartiainen, Mikko Mottonen e Martti M. Salomaa, “Circuitos Quânticos com Portões de Um Qubit uniformemente controlados” Revisão Física A 71, 052330 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.052330
http: // arxiv.org/ abs / quant-ph / 0410066
[41] CH Bennett “Reversibilidade Lógica de Computação” 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 determinação de zero de precisão múltipla e a complexidade da avaliação de função elementar" 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 e van der Hoeven “Multiplicação de inteiros no tempo 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 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
[45] Mihir K. Bhaskar, Stuart Hadfield, Anargyros Papageorgiou e Iasonas Petras, “Algoritmos Quânticos e Circuitos para Computação Científica” 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 e Krysta M. Svore, “Otimizando circuitos quânticos para 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 e Yongjian Gu, “Projeto de circuitos quânticos para avaliar funções transcendentais com base em um método de expansão binária de valor de função” Quantum Information Processing 19, 347 (2020).
https://doi.org/10.1007/s11128-020-02855-7
arXiv: 2001.00807
[48] John Watrous “A Teoria da Informação Quâ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 e John A. Smolin, “Optimal Universal and State-Dependent Quantum Cloning” Revisão Física A 57, 2368–2378 (1998).
https: / / doi.org/ 10.1103 / PhysRevA.57.2368
[50] E. Arıkan “Polarização de Canal: Um Método para Construir Códigos de Alcance de Capacidade para Canais Sem Memória de Entrada Binária Simétrica” IEEE Transactions on Information Theory 55, 3051–3073 (2009).
https: / / doi.org/ 10.1109 / TIT.2009.2021379
arXiv: 0807.3917
[51] Mark M. Wilde e Saikat Guha “Códigos Polares para Canais Quânticos Clássicos” IEEE Transactions on Information Theory 59, 1175–1187 (2013).
https: / / doi.org/ 10.1109 / TIT.2012.2218792
arXiv: 1109.2591
[52] Joseph M. Renes e Mark M. Wilde “Códigos Polares para Comunicação Privada e Quântica em Canais Arbitrários” IEEE Transactions on Information Theory 60, 3090–3103 (2014).
https: / / doi.org/ 10.1109 / TIT.2014.2314463
arXiv: 1212.2537
[53] S. Guha e MM Wilde “Codificação Polar para Alcançar a Capacidade Holevo de um Canal Óptico de Perda Pura” Anais do Simpósio Internacional IEEE 2012 sobre Teoria da Informação (ISIT) 546–550 (2012).
https: / / doi.org/ 10.1109 / ISIT.2012.6284250
arXiv: 1202.0533
Citado por
[1] S. Brandsen, Avijit Mandal e Henry D. Pfister, “Propagação de Crenças com Mensagens Quânticas para Canais Quânticos Clássicos Simétricos”, arXiv: 2207.04984.
As citações acima são de SAO / NASA ADS (última atualização com êxito 2022-08-23 14:04:15). A lista pode estar incompleta, pois nem todos os editores fornecem dados de citação adequados e completos.
Não foi possível buscar Dados citados por referência cruzada durante a última tentativa 2022-08-23 14:04:14: Não foi possível buscar os dados citados por 10.22331 / q-2022-08-23-784 do Crossref. Isso é normal se o DOI foi registrado recentemente.
Este artigo é publicado na Quantum sob o Atribuição 4.0 do Creative Commons Internacional (CC BY 4.0) licença. Os direitos autorais permanecem com os detentores originais, como os autores ou suas instituições.
