이론 물리 연구소, ETH 취리히, 스위스
이 논문이 흥미 롭거나 토론하고 싶습니까? SciRate에 댓글을 달거나 댓글 남기기.
추상
최근 Renes는 순수 상태 CQ 채널을 통해 전송되는 트리 태너 그래프가 있는 이진 선형 코드를 사용하여 인코딩된 고전 데이터를 디코딩하기 위해 BPQM(Believe Propagation with Quantum Messages)이라는 양자 알고리즘을 제안했습니다.1], 즉 클래식 입력 및 순수 상태 양자 출력이 있는 채널입니다. 이 알고리즘은 LDPC 또는 터보 코드와 함께 사용할 때 고전 코딩 이론에서 널리 성공한 고전적 신념 전파 알고리즘을 기반으로 하는 디코딩에 대한 진정한 양자 대응물을 제시합니다. 최근 Rengaswamy $et$ $al.$ [2]는 BPQM이 달성 가능한 확률이 가장 높은 입력 코드워드 집합에 대한 양자 출력 상태를 구별하는 최적의 측정을 구현한다는 점에서 작은 예제 코드에서 최적의 디코더를 구현하는 것을 관찰했습니다. 여기서 우리는 다음 기여를 통해 BPQM 알고리즘의 이해, 형식 및 적용 가능성을 크게 확장합니다. 첫째, 우리는 BPQM이 트리 Tanner 그래프를 사용하여 모든 이진 선형 코드에 대해 최적의 디코딩을 실현한다는 것을 분석적으로 증명합니다. 또한 BPQM 알고리즘에 대한 최초의 공식적인 설명을 모호함 없이 자세히 제공합니다. 그렇게 함으로써 우리는 양자 회로 구현이 코드 차원에서 기하급수적으로 커질 것임을 암시하는 원래 알고리즘과 후속 작업에서 간과된 주요 결함을 식별합니다. BPQM은 양자 메시지를 전달하지만 알고리즘에 필요한 다른 정보는 전역적으로 처리됩니다. 우리는 BPQM에 근접하고 양자 회로 복잡성 $mathcal{O}(text{poly } n, text{polylog } frac{1}{epsilon})$을 갖는 진정한 메시지 전달 알고리즘을 공식화하여 이 문제를 해결합니다. 여기서 $n$ 는 코드 길이이고 $epsilon$은 근사 오차입니다. 마지막으로 근사 복제를 사용하여 주기를 포함하는 요인 그래프로 BPQM을 확장하는 새로운 방법도 제안합니다. 사이클이 있는 요인 그래프의 BPQM이 가능한 최상의 클래식 디코더를 훨씬 능가할 수 있음을 나타내는 몇 가지 유망한 수치 결과를 보여줍니다.
► BibTeX 데이터
► 참고 문헌
[1] Joseph M. Renes "양자 메시지를 전달하여 양자 채널의 믿음 전파 디코딩" 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 및 Henry D. Pfister, "양자 강화 고전 커뮤니케이션을 위한 양자 메시지를 통한 믿음 전파" 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 및 RL Urbanke, "신념 전파 하에서 공간적으로 결합된 앙상블이 보편적으로 용량 달성" IEEE 트랜잭션 정보 이론 59, 7761–7813(2013).
https : / //doi.org/10.1109/TIT.2013.2280915
arXiv : 1201.2999
[4] HA Loeliger 및 PO Vontobel "양자 확률에 대한 요인 그래프" 정보 이론 63, 5642–5665(2017)에 관한 IEEE 거래.
https : / //doi.org/10.1109/TIT.2017.2716422
arXiv : 1508.00689
[5] MX Cao 및 PO Vontobel "Double-Edge Factor Graphs: Definition, Properties, and Examples" 2017 IEEE 정보 이론 워크숍(ITW) 136–140(2017).
https : / / doi.org/ 10.1109 / ITW.2017.8277985
arXiv : 1706.00752
[6] Hans-Andrea Loeliger "요인 그래프 소개" IEEE 신호 처리 잡지 21, 28–41(2004).
https:// / doi.org/ 10.1109/ MSP.2004.1267047
[7] VP Belavkin "최적 다중 양자 통계 가설 테스트" Stochastics 1, 315(1975).
https : / /doi.org/ 10.1080 / 17442507508833114
[8] Paul Hausladen 및 William K. Wootters "양자 상태 구별을 위한 '매우 좋은' 측정" Journal of Modern Optics 41, 2385(1994).
https : / /doi.org/ 10.1080 / 09500349414552221
[9] Narayanan Rengaswamy 및 Henry D. Pfister "고전 BSC와 양자 PSC 사이의 이중성에 대한 준고전적 증거"(2021).
https:///doi.org/10.48550/arXiv.2103.09225
arXiv : 2103.09225
[10] Masashi Ban, Keiko Kurokawa, Rei Momose 및 Osamu Hirota, "대칭 양자 상태 및 매개변수 추정 간 판별을 위한 최적의 측정" International Journal of Theoretical Physics 36, 1269–1288(1997).
https : / /doi.org/ 10.1007 / BF02435921
[11] Masahide Sasaki, Kentaro Kato, Masayuki Izutsu, 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 및 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 및 Rüdiger Urbanke "현대 코딩 이론" Cambridge University Press(2008).
https : / /doi.org/ 10.1017 / CBO9780511791338
[14] David Poulin "연결된 양자 블록 코드의 최적 및 효율적인 디코딩" Physical Review A 74, 052333(2006).
https : / /doi.org/10.1103/ PhysRevA.74.052333
[15] David Poulin 및 정여진 "희소 양자 코드의 반복적 디코딩에 관하여" 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 및 Xin-Mei Wang, "희소 양자 코드의 향상된 피드백 반복 디코딩" 정보 이론 58에 대한 IEEE 트랜잭션, 1231–1241(2012).
https : / //doi.org/10.1109/TIT.2011.2169534
arXiv : 0912.4546
[17] Ben Criger 및 Imran Ashraf "2D 토폴로지 코드 디코딩을 위한 다중 경로 합계" Quantum 2, 102(2018).
https://doi.org/10.22331/q-2018-10-19-102
arXiv : 1709.02154
[18] Ye-Hua Liu 및 David Poulin "양자 오류 수정 코드를 위한 신경 믿음 전파 디코더" Physical Review Letters 122, 200501(2019).
https : / /doi.org/10.1103/ PhysRevLett.122.200501
arXiv : 1811.07835
[19] Alex Rigby, JC Olivier 및 Peter Jarvis, "양자 저밀도 패리티 검사 코드를 위한 수정된 신념 전파 디코더" Physical Review A 100, 012330(2019).
https : / /doi.org/10.1103/ PhysRevA.100.012330
arXiv : 1903.07404
[20] Pavel Panteleev 및 Gleb Kalachev "유한 길이 성능이 우수한 퇴화 양자 LDPC 코드" Quantum 5, 585(2021).
https://doi.org/10.22331/q-2021-11-22-585
[21] July X. Li 및 Pascal O. Vontobel "Quantum Stabilizer Codes의 Pseudocodeword-Based Decoding" 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 및 Earl Campbell, "양자 저밀도 패리티 검사 코드 환경에서 디코딩" 물리적 검토 연구 2, 043423(2020).
https : / /doi.org/10.1103/ PhysRevResearch.2.043423
arXiv : 2005.07016
[23] July X. Li, Joseph M. Renes 및 Pascal O. Vontobel, "양자 색상 코드의 의사 코드워드 기반 디코딩"(2020).
https:///doi.org/10.48550/arXiv.2010.10845
arXiv : 2010.10845
[24] Srikar Kasi 및 Kyle Jamieson "무선 네트워크에서 LDPC 디코딩을 위한 양자 믿음 전파를 향하여" 제26회 모바일 컴퓨팅 및 네트워킹에 관한 연례 국제 회의 1–14(2020) 간행물.
https : / /doi.org/ 10.1145 / 3372224.3419207
arXiv : 2007.11069
[25] MS Leifer 및 D. Poulin "Quantum Graphical Models and Belief Propagation" Annals of Physics 323, 1899–1946 (2008).
https : / /doi.org/ 10.1016 / j.aop.2007.10.001
arXiv : 0708.1337
http : / /www.sciencedirect.com/ 과학 / article / pii / S0003491607001509
[26] HA Bethe "초격자의 통계 이론" 왕립 학회 회보 A 150, 552–575 (1935).
https : / /doi.org/ 10.1098 / rspa.1935.0122
http:/ / rspa.royalsocietypublishing.org/ content/ 150/ 871/ 552
[27] Rudolf Peierls "성분의 농도가 다른 초격자의 통계 이론" 왕립 학회 회보 A 154, 207–222(1936).
https : / /doi.org/ 10.1098 / rspa.1936.0047
[28] Jonathan S. Yedidia, William T. Freeman 및 Yair Weiss, 신경 정보 처리 시스템에 관한 제13회 국제 회의 668–674(2000)의 "일반화된 신념 전파" 절차.
[29] Jonathan S. Yedidia, William T. Freeman 및 Yair Weiss, "믿음 전파 및 일반화 이해" Morgan Kaufmann Publishers Inc.(2003).
https:/ / www.merl.com/ publications/ docs/ TR2001-22.pdf
[30] JS Yedidia, WT Freeman 및 Y. Weiss, "자유 에너지 근사화 및 일반화된 믿음 전파 알고리즘 구성" 정보 이론, IEEE Transactions on 51, 2282–2312(2005).
https : / //doi.org/10.1109/TIT.2005.850085
[31] 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
[32] David Poulin과 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
[33] MX Cao 및 PO Vontobel "Quantum Factor Graphs: Closing-the-Box Operation and Variational Approaches" 2016 International Symposium on Information Theory and Its Applications (ISITA) 651–655 (2016).
https : / /ieeieere.ieee.org/document/ 7840505
[34] FR Kschischang, BJ Frey 및 HA Loeliger, "요인 그래프 및 합계 곱 알고리즘" IEEE 트랜잭션 정보 이론 47, 498–519(2001).
https : / /doi.org/ 10.1109 / 18.910572
[35] G. David Forney "그래프의 코드: 정상적인 실현" 정보 이론에 관한 IEEE 거래 47, 520–548(2001).
https : / /doi.org/ 10.1109 / 18.910573
[36] CW Helstrom "양자 검출 및 추정 이론" 학술(1976).
https://doi.org/10.1016/S0076-5392(08)60247-7
http:// / www.sciencedirect.com/ science/ bookseries/ 00765392/ 123
[37] Saikat Guha "Superadditive 용량 및 Holevo 한계를 달성하기 위한 구조화된 광 수신기" Physical Review Letters 106, 240502(2011).
https : / /doi.org/10.1103/ PhysRevLett.106.240502
arXiv : 1101.1550
[38] T. Etzion, A. Trachtenberg 및 A. Vardy, "무순환 태너 그래프가 있는 코드는 무엇입니까?" 정보 이론에 관한 IEEE 거래 45, 2173–2181(1999).
https : / /doi.org/ 10.1109 / 18.782170
[39] Jacob C. Bridgeman 및 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 및 Martti M. Salomaa, "균일하게 제어되는 71-Qubit 게이트가 있는 양자 회로" 물리적 검토 A 052330, 2005(XNUMX).
https : / /doi.org/10.1103/ PhysRevA.71.052330
http://arxiv.org/abs/quant-ph/0410066
[41] CH Bennett "계산의 논리적 가역성" IBM 연구 개발 저널 17, 525–532(1973).
https : / //doi.org/10.1147/rd.176.0525
[42] Richard P. Brent "다중 정밀도 영점 찾기 방법 및 기본 기능 평가의 복잡성" 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 및 van der Hoeven "시간 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, Sabre Kais, "양자 알고리즘 및 푸아송 방정식을 푸는 회로 설계" 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 및 Iasonas Petras, "과학 컴퓨팅을 위한 양자 알고리즘 및 회로" 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, Krysta M. Svore, "산술을 위한 양자 회로 최적화"(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, Yongjian Gu, "함수 값 이진 확장 방법을 기반으로 초월 함수를 평가하기 위한 양자 회로 설계" 양자 정보 처리 19, 347(2020).
https://doi.org/10.1007/s11128-020-02855-7
arXiv : 2001.00807
[48] John Watrous "The Theory of Quantum Information" 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, Arthur Ekert, Christopher A. Fuchs, Chiara Macchiavello 및 John A. Smolin, "최적의 범용 및 상태 의존적 양자 복제" 물리적 검토 A 57, 2368–2378(1998).
https : / /doi.org/10.1103/ PhysRevA.57.2368
[50] E. Arıkan "채널 분극화: 대칭 이진 입력 메모리리스 채널을 위한 용량 달성 코드를 구성하는 방법" IEEE 정보 이론 55 트랜잭션, 3051–3073(2009).
https : / //doi.org/10.1109/TIT.2009.2021379
arXiv : 0807.3917
[51] Mark M. Wilde 및 Saikat Guha "고전적 양자 채널에 대한 극지 부호" 정보 이론 59, 1175–1187(2013)에 관한 IEEE 거래.
https : / //doi.org/10.1109/TIT.2012.2218792
arXiv : 1109.2591
[52] Joseph M. Renes 및 Mark M. Wilde "임의 채널을 통한 개인 및 양자 통신을 위한 폴라 코드" 정보 이론 60, 3090–3103(2014)에 관한 IEEE 트랜잭션.
https : / //doi.org/10.1109/TIT.2014.2314463
arXiv : 1212.2537
[53] S. Guha 및 MM Wilde "정보 이론에 관한 2012 IEEE 국제 심포지엄(ISIT) 546–550(2012)"의 "순수 손실 광 채널의 Holevo 용량을 달성하기 위한 극지 부호화" 절차.
https : / /doi.org/10.1109/ ISIT.2012.6284250
arXiv : 1202.0533
인용
[1] S. Brandsen, Avijit Mandal 및 Henry D. Pfister, "대칭 고전 양자 채널에 대한 양자 메시지를 통한 믿음 전파", arXiv : 2207.04984.
위의 인용은 SAO / NASA ADS (마지막으로 성공적으로 업데이트 됨 2022-08-23 14:04:15). 모든 출판사가 적절하고 완전한 인용 데이터를 제공하지는 않기 때문에 목록이 불완전 할 수 있습니다.
가져올 수 없습니다 Crossref 인용 자료 마지막 시도 중 2022-08-23 14:04:14 : Crossref에서 10.22331 / q-2022-08-23-784에 대한 인용 데이터를 가져올 수 없습니다. DOI가 최근에 등록 된 경우 이는 정상입니다.
이 백서는 Quantum에서 Creative Commons Attribution 4.0 International(CC BY 4.0) 특허. 저작권은 저자 또는 기관과 같은 원래 저작권 보유자에게 있습니다.
