สถาบันฟิสิกส์ทฤษฎี ETH Zürich ประเทศสวิสเซอร์แลนด์
พบบทความนี้ที่น่าสนใจหรือต้องการหารือ? Scite หรือแสดงความคิดเห็นใน SciRate.
นามธรรม
เมื่อเร็ว ๆ นี้ Renes ได้เสนออัลกอริทึมควอนตัมที่เรียกว่าการถ่ายทอดความเชื่อด้วยข้อความควอนตัม (BPQM) สำหรับการถอดรหัสข้อมูลแบบคลาสสิกที่เข้ารหัสโดยใช้รหัสเชิงเส้นแบบไบนารีพร้อมกราฟแทนเนอร์ต้นไม้ที่ส่งผ่านช่อง CQ แบบบริสุทธิ์1] เช่น ช่องสัญญาณที่มีอินพุตแบบคลาสสิกและเอาต์พุตควอนตัมแบบบริสุทธิ์ อัลกอริธึมนำเสนอคู่ควอนตัมของแท้ในการถอดรหัสโดยอิงตามอัลกอริธึมการเผยแพร่ความเชื่อแบบคลาสสิก ซึ่งพบความสำเร็จอย่างกว้างขวางในทฤษฎีการเข้ารหัสแบบคลาสสิกเมื่อใช้ร่วมกับรหัส LDPC หรือ Turbo ล่าสุด Rengaswamy $et$ $al.$ [2] สังเกตว่า BPQM ใช้ตัวถอดรหัสที่เหมาะสมที่สุดกับโค้ดตัวอย่างขนาดเล็ก โดยจะใช้การวัดที่เหมาะสมที่สุดเพื่อแยกแยะสถานะเอาต์พุตควอนตัมสำหรับชุดของโค้ดเวิร์ดอินพุตที่มีความน่าจะเป็นสูงสุด ที่นี่เราขยายความเข้าใจ ความเป็นทางการ และการบังคับใช้ของอัลกอริทึม BPQM อย่างมีนัยสำคัญด้วยการสนับสนุนต่อไปนี้ อันดับแรก เราพิสูจน์เชิงวิเคราะห์ว่า BPQM ตระหนักถึงการถอดรหัสที่เหมาะสมที่สุดสำหรับโค้ดเชิงเส้นแบบไบนารีใดๆ ที่มีกราฟแทนเนอร์แบบต้นไม้ เรายังให้คำอธิบายอย่างเป็นทางการครั้งแรกของอัลกอริทึม BPQM โดยละเอียดและปราศจากความคลุมเครือ ในการทำเช่นนั้น เราระบุข้อบกพร่องสำคัญที่ถูกมองข้ามในอัลกอริธึมดั้งเดิมและงานต่อมาซึ่งบอกเป็นนัยว่าวงจรควอนตัมสำนึกจะมีขนาดใหญ่แบบทวีคูณในมิติโค้ด แม้ว่า BPQM จะส่งข้อความควอนตัม ข้อมูลอื่น ๆ ที่อัลกอริทึมต้องการจะได้รับการประมวลผลทั่วโลก เราแก้ไขปัญหานี้ด้วยการกำหนดอัลกอริทึมการส่งข้อความอย่างแท้จริงซึ่งใกล้เคียงกับ BPQM และมีความซับซ้อนของวงจรควอนตัม $mathcal{O}(text{poly } n, text{polylog } frac{1}{epsilon})$ โดยที่ $n$ คือความยาวของโค้ด และ $epsilon$ คือข้อผิดพลาดในการประมาณ สุดท้าย เรายังเสนอวิธีการใหม่ในการขยาย BPQM ไปยังกราฟตัวประกอบที่มีวัฏจักรโดยใช้การโคลนนิ่งโดยประมาณ เราแสดงผลตัวเลขที่น่ามีแนวโน้มซึ่งบ่งชี้ว่า BPQM บนกราฟปัจจัยที่มีวัฏจักรสามารถทำงานได้ดีกว่าตัวถอดรหัสคลาสสิกที่ดีที่สุด
► ข้อมูล BibTeX
► ข้อมูลอ้างอิง
[1] Joseph M. Renes "การถอดรหัสการขยายพันธุ์ความเชื่อของช่องควอนตัมโดยการส่งข้อความควอนตัม" วารสารฟิสิกส์ฉบับใหม่ 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, “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/articles/s41534-021-00422-1
[3] S. Kudekar, T. Richardson และ RL Urbanke, “Spatially Coupled Ensembles Universally Achievement Under Belief Propagation” ธุรกรรม IEEE บนทฤษฎีข้อมูล 59, 7761–7813 (2013)
https://doi.org/10.1109/TIT.2013.2280915
arXiv: 1201.2999
[4] HA Loeliger และ PO Vontobel "กราฟปัจจัยสำหรับความน่าจะเป็นควอนตัม" ธุรกรรม IEEE บนทฤษฎีข้อมูล 63, 5642–5665 (2017)
https://doi.org/10.1109/TIT.2017.2716422
arXiv: 1508.00689
[5] MX Cao และ PO Vontobel “กราฟปัจจัยสองขอบ: คำจำกัดความ คุณสมบัติ และตัวอย่าง” 2017 การประชุมเชิงปฏิบัติการทฤษฎีข้อมูล IEEE (ITW) 136–140 (2017)
https://doi.org/10.1109/ITW.2017.8277985
arXiv: 1706.00752
[6] Hans-Andrea Loeliger “An Introduction to Factor Graphs” นิตยสารการประมวลผลสัญญาณ 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, “การวัดที่เหมาะสมที่สุดสำหรับการเลือกปฏิบัติระหว่างสถานะควอนตัมสมมาตรและการประมาณค่าพารามิเตอร์” วารสารนานาชาติของฟิสิกส์เชิงทฤษฎี 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 “ในการตรวจจับควอนตัมและการวัดรากที่สอง” ธุรกรรม IEEE บนทฤษฎีข้อมูล 47, 858–872 (2001)
https://doi.org/10.1109/18.915636
[13] Tom Richardson และRüdiger Urbanke "ทฤษฎีการเข้ารหัสสมัยใหม่" สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์ (2008)
https://doi.org/10.1017/CBO9780511791338
[14] David Poulin "การถอดรหัสรหัสบล็อกควอนตัมที่เชื่อมต่อกันอย่างเหมาะสมและมีประสิทธิภาพ" การตรวจสอบทางกายภาพ A 74, 052333 (2006)
https://doi.org/10.1103/PhysRevA.74.052333
[15] David Poulin และ Yeojin Chung “ในการถอดรหัสซ้ำของรหัสควอนตัมกระจัดกระจาย” ข้อมูลควอนตัมและการคำนวณ 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, “Enhanced Feedback Iterative Decoding of Sparse Quantum Codes” ธุรกรรม IEEE บนทฤษฎีข้อมูล 58, 1231–1241 (2012)
https://doi.org/10.1109/TIT.2011.2169534
arXiv: 0912.4546
[17] Ben Criger และ Imran Ashraf “การรวมหลายเส้นทางสำหรับการถอดรหัสรหัสทอพอโลยี 2 มิติ” ควอนตัม 2, 102 (2018)
https://doi.org/10.22331/q-2018-10-19-102
arXiv: 1709.02154
[18] Ye-Hua Liu และ David Poulin“ ตัวถอดรหัสความเชื่อ - การแพร่กระจายของระบบประสาทสำหรับรหัสแก้ไขข้อผิดพลาดควอนตัม” จดหมายทบทวนทางกายภาพ 122, 200501 (2019)
https://doi.org/10.1103/PhysRevLett.122.200501
arXiv: 1811.07835
[19] Alex Rigby, JC Olivier และ Peter Jarvis “ตัวถอดรหัสการขยายพันธุ์ความเชื่อที่ดัดแปลงสำหรับรหัสตรวจสอบความเท่าเทียมกันของควอนตัมความหนาแน่นต่ำ” การตรวจสอบทางกายภาพ 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] กรกฎาคม X. Li และ 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
[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] กรกฎาคม X. Li, Joseph M. Renes และ Pascal O. Vontobel, “Pseudocodeword-Based Decoding of Quantum Color Codes” (2020)
https://doi.org/10.48550/arXiv.2010.10845
arXiv: 2010.10845
[24] Srikar Kasi และ Kyle Jamieson "Towards Quantum Belief Propagation for LDPC Decoding in Wireless Networks" การประชุมนานาชาติประจำปีครั้งที่ 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/science/article/pii/S0003491607001509
[26] HA Bethe "ทฤษฎีทางสถิติของ Superlattices" การดำเนินการของ 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 "ทฤษฎีทางสถิติของ Superlattices ที่มีความเข้มข้นไม่เท่ากันของส่วนประกอบ" การดำเนินการของ Royal Society 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, “Understanding Belief Propagation and its Generalizations” Morgan Kaufmann Publishers Inc. (2003)
https://www.merl.com/publications/docs/TR2001-22.pdf
[30] JS Yedidia, WT Freeman และ Y. Weiss, “Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms” ทฤษฎีข้อมูล, ธุรกรรมของ IEEE เมื่อวันที่ 51, 2282–2312 (2005)
https://doi.org/10.1109/TIT.2005.850085
[31] MB Hastings "การขยายพันธุ์ความเชื่อควอนตัม: อัลกอริธึมสำหรับระบบควอนตัมความร้อน" การทบทวนทางกายภาพ B 76, 201102 (2007)
https://doi.org/10.1103/PhysRevB.76.201102
arXiv: 0706.4094
[32] David Poulin และ Matthew B. Hastings "การสลายตัวของ Markov Entropy: Variational Dual for Quantum Belief Propagation" จดหมายทบทวนทางกายภาพ 106, 080403 (2011)
https://doi.org/10.1103/PhysRevLett.106.080403
arXiv: 1012.2050
[33] MX Cao และ PO Vontobel "กราฟปัจจัยควอนตัม: การดำเนินการปิดกล่องและวิธีการเปลี่ยนแปลง" การประชุมวิชาการระดับนานาชาติประจำปี 2016 เกี่ยวกับทฤษฎีข้อมูลและการประยุกต์ (ISITA) 651–655 (2016)
https://ieeexplore.ieee.org/document/7840505
[34] FR Kschischang, BJ Frey และ HA Loeliger, “Factor Graphs and the Sum-Product Algorithm” ธุรกรรม 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" จดหมายทบทวนทางกายภาพ 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 "การโบกมือและการตีความ: หลักสูตรเบื้องต้นเกี่ยวกับเครือข่ายเทนเซอร์" วารสารฟิสิกส์ A: คณิตศาสตร์และทฤษฎี 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, “Quantum Circuits with Uniformly Controlled One-Qubit Gates” Physical Review A 71, 052330 (2005)
https://doi.org/10.1103/PhysRevA.71.052330
http://arxiv.org/abs/quant-ph/0410066
[41] CH Bennett “การย้อนกลับทางตรรกะของการคำนวณ” IBM Journal of Research and Development 17, 525–532 (1973)
https://doi.org/10.1147/rd.176.0525
[42] Richard P. Brent "วิธีการหาศูนย์ที่มีความแม่นยำหลายจุดและความซับซ้อนของการประเมินฟังก์ชันเบื้องต้น" สำนักพิมพ์เชิงวิชาการ (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)” พงศาวดารของคณิตศาสตร์ 193, 563 (2021)
https://doi.org/10.4007/annals.2021.193.2.4
[44] Yudong Cao, Anargyros Papageorgiou, Iasonas Petras, Joseph Traub และ 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 และ 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
[46] Thomas Häner, Martin Roetteler และ Krysta M. Svore, “Optimizing Quantum Circuits for Arithmetic” (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 “ทฤษฎีข้อมูลควอนตัม” สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์ (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 และ 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
[50] E. Arıkan "ช่องโพลาไรเซชัน: วิธีสำหรับการสร้างรหัสบรรลุความจุสำหรับช่องสัญญาณ Memoryless Binary-Input สมมาตร" ธุรกรรม IEEE บนทฤษฎีข้อมูล 55, 3051–3073 (2009)
https://doi.org/10.1109/TIT.2009.2021379
arXiv: 0807.3917
[51] Mark M. Wilde และ Saikat Guha “Polar Codes for Classical-Quantum Channels” ธุรกรรม IEEE บนทฤษฎีข้อมูล 59, 1175–1187 (2013)
https://doi.org/10.1109/TIT.2012.2218792
arXiv: 1109.2591
[52] Joseph M. Renes และ Mark M. Wilde “Polar Codes for Private and Quantum Communication Over Arbitrary Channels” ธุรกรรม IEEE บนทฤษฎีข้อมูล 60, 3090–3103 (2014)
https://doi.org/10.1109/TIT.2014.2314463
arXiv: 1212.2537
[53] S. Guha และ MM Wilde “Polar Coding เพื่อให้ได้ความจุ Holevo ของช่องสัญญาณออปติคัลการสูญเสียที่บริสุทธิ์” การประชุมวิชาการ IEEE International Symposium on Information Theory (ISIT) ประจำปี 2012 546–550 (2012)
https://doi.org/10.1109/ISIT.2012.6284250
arXiv: 1202.0533
อ้างโดย
[1] S. Brandsen, Avijit Mandal และ Henry D. Pfister, “การเผยแพร่ความเชื่อด้วยข้อความควอนตัมสำหรับช่องสัญญาณคลาสสิก-ควอนตัมสมมาตร”, arXiv: 2207.04984.
การอ้างอิงข้างต้นมาจาก are อบต./นาซ่าโฆษณา (ปรับปรุงล่าสุดสำเร็จ 2022-08-23 14:04:15 น.) รายการอาจไม่สมบูรณ์เนื่องจากผู้จัดพิมพ์บางรายไม่ได้ให้ข้อมูลอ้างอิงที่เหมาะสมและครบถ้วน
ไม่สามารถดึงข้อมูล Crossref อ้างโดย data ระหว่างความพยายามครั้งล่าสุด 2022-08-23 14:04:14 น.: ไม่สามารถดึงข้อมูลที่อ้างถึงสำหรับ 10.22331/q-2022-08-23-784 จาก Crossref นี่เป็นเรื่องปกติหาก DOI ได้รับการจดทะเบียนเมื่อเร็วๆ นี้
บทความนี้เผยแพร่ใน Quantum ภายใต้ the ครีเอทีฟคอมมอนส์แบบแสดงที่มา 4.0 สากล (CC BY 4.0) ใบอนุญาต ลิขสิทธิ์ยังคงอยู่กับผู้ถือลิขสิทธิ์ดั้งเดิม เช่น ผู้เขียนหรือสถาบันของพวกเขา
