Інститут теоретичної фізики, ETH Zürich, Швейцарія
Вам цей документ цікавий чи ви хочете обговорити? Скайте або залиште коментар на SciRate.
абстрактний
Нещодавно Ренес запропонував квантовий алгоритм під назвою «розповсюдження віри з квантовими повідомленнями» (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] Джозеф М. Ренес «Поширення переконань, декодування квантових каналів шляхом передачі квантових повідомлень» Новий журнал фізики 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] С. Кудекар, Т. Річардсон і Р. Л. Урбанке, «Просторово пов’язані ансамблі універсально досягають потужності за умови поширення переконань» IEEE Transactions on Information Theory 59, 7761–7813 (2013).
https:///doi.org/10.1109/TIT.2013.2280915
arXiv: 1201.2999
[4] HA Loeliger і PO Vontobel «Графи факторів для квантових ймовірностей» IEEE Transactions on Information Theory 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 «Вступ до факторних графіків» Журнал IEEE Signal Processing Magazine 21, 28–41 (2004).
https:///doi.org/10.1109/MSP.2004.1267047
[7] В. П. Бєлавкін “Перевірка оптимальної мультиквантової статистичної гіпотези” Стохастика 1, 315 (1975).
https: / / doi.org/ 10.1080 / 17442507508833114
[8] Пол Хаусладен і Вільям К. Вуттерс “Досить хороше” вимірювання для розрізнення квантових станів” Журнал сучасної оптики 41, 2385 (1994).
https: / / doi.org/ 10.1080 / 09500349414552221
[9] Нараянан Ренгасвамі та Генрі Д. Пфістер «Напівкласичний доказ подвійності між класичним BSC і квантовим PSC» (2021).
https:///doi.org/10.48550/arXiv.2103.09225
arXiv: 2103.09225
[10] Масасі Бан, Кейко Курокава, Рей Момосе та Осаму Хірота, «Оптимальні вимірювання для розрізнення симетричних квантових станів та оцінки параметрів» Міжнародний журнал теоретичної фізики 36, 1269–1288 (1997).
https: / / doi.org/ 10.1007 / BF02435921
[11] Масахіде Сасакі, Кентаро Като, Масаюкі Ізуцу та Осаму Хірота, «Квантові канали, що демонструють суперадитивність у класичній здатності», Фізичний огляд A 58, 146–158 (1998).
https: / / doi.org/ 10.1103 / PhysRevA.58.146
[12] Ю. К. Елдар і молодший Форні «Про квантове виявлення та вимірювання квадратного кореня» IEEE Transactions on Information Theory 47, 858–872 (2001).
https: / / doi.org/ 10.1109 / 18.915636
[13] Том Річардсон і Рюдігер Урбанке «Сучасна теорія кодування» Cambridge University Press (2008).
https:///doi.org/10.1017/CBO9780511791338
[14] Девід Пулен «Оптимальне та ефективне декодування конкатенованих квантових блокових кодів», Фізичний огляд A 74, 052333 (2006).
https: / / doi.org/ 10.1103 / PhysRevA.74.052333
[15] Девід Пулін і Йоджін Чун «Про ітераційне декодування розріджених квантових кодів» Квантова інформація та обчислення 8, 987–1000 (2008).
https:///doi.org/10.26421/QIC8.10-8
arXiv: 0801.1241
[16] Юн-Цзян Ван, Баррі С. Сандерс, Бао-Мінг Бай і Сінь-Мей Ван, «Покращене ітераційне декодування розріджених квантових кодів зі зворотним зв’язком» Транзакції IEEE з теорії інформації 58, 1231–1241 (2012).
https:///doi.org/10.1109/TIT.2011.2169534
arXiv: 0912.4546
[17] Бен Крігер та Імран Ашраф «Багатоканальне підсумовування для декодування 2D топологічних кодів» Квант 2, 102 (2018).
https://doi.org/10.22331/q-2018-10-19-102
arXiv: 1709.02154
[18] Ye-Hua Liu і David Poulin “Decoders Neural Belief-Propagation Decoders for Quantum Error-Correcting Codes” Physical Review Letters 122, 200501 (2019).
https: / / doi.org/ 10.1103 / PhysRevLett.122.200501
arXiv: 1811.07835
[19] Алекс Рігбі, Дж. К. Олів’є та Пітер Джарвіс, «Модифіковані декодери поширення переконань для квантових кодів перевірки парності з низькою щільністю», Фізичний огляд A 100, 012330 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.100.012330
arXiv: 1903.07404
[20] Павло Пантелеєв і Гліб Калачов «Вироджені квантові коди LDPC з хорошою продуктивністю кінцевої довжини» Квант 5, 585 (2021).
https://doi.org/10.22331/q-2021-11-22-585
[21] Липень X. Лі та Паскаль О. Вонтобель «Декодування кодів квантових стабілізаторів на основі псевдокодового слова» 2019 Міжнародний симпозіум IEEE з теорії інформації (ISIT) 2888–2892 (2019).
https:///doi.org/10.1109/ISIT.2019.8849833
arXiv: 1903.01202
[22] Йошка Роффе, Девід Р. Уайт, Саймон Бертон та Ерл Кемпбелл, «Декодування в квантовому ландшафті коду перевірки парності з низькою щільністю», Physical Review Research 2, 043423 (2020).
https: / / doi.org/ 10.1103 / PhysRevResearch.2.043423
arXiv: 2005.07016
[23] Джулі X. Лі, Джозеф М. Ренес і Паскаль О. Вонтобель, «Декодування квантових колірних кодів на основі псевдокодового слова» (2020).
https:///doi.org/10.48550/arXiv.2010.10845
arXiv: 2010.10845
[24] Шрікар Касі та Кайл Джеймісон «До розповсюдження квантової віри для декодування LDPC у бездротових мережах» Матеріали 26-ї щорічної міжнародної конференції з мобільних комп’ютерів та мереж 1–14 (2020).
https: / / doi.org/ 10.1145 / 3372224.3419207
arXiv: 2007.11069
[25] М. С. Лейфер і Д. Пулен «Квантові графічні моделі та поширення переконань» 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] Х. А. Бете “Статистична теорія суперґраток” Праці Королівського товариства A 150, 552–575 (1935).
https: / / doi.org/ 10.1098 / rspa.1935.0122
http:///rspa.royalsocietypublishing.org/content/150/871/552
[27] Рудольф Пайерлз «Статистична теорія суперґраток з нерівними концентраціями компонентів» Праці Королівського товариства A 154, 207–222 (1936).
https: / / doi.org/ 10.1098 / rspa.1936.0047
[28] Джонатан С. Єдідія, Вільям Т. Фрімен і Яір Вайс, «Поширення узагальнених вірувань» Матеріали 13-ї Міжнародної конференції з нейронних систем обробки інформації 668–674 (2000).
[29] Джонатан С. Єдідія, Вільям Т. Фрімен і Яір Вайс, «Розуміння поширення переконань та їх узагальнень» Morgan Kaufmann Publishers Inc. (2003).
https:///www.merl.com/publications/docs/TR2001-22.pdf
[30] JS Yedidia, WT Freeman, and Y. Weiss, “Constructing Free-Energy Approximations and Generalized Belief Propagation Algorithms” Information Theory, 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] Девід Пулін і Метью Б. Гастінгс «Розклад ентропії Маркова: варіаційний дуал для квантового поширення переконань» Physical Review Letters 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] Ф. Р. Кшишанг, Б. Дж. Фрей і Х. А. Лоелігер, «Графи факторів і алгоритм сумарного добутку» IEEE Transactions on Information Theory 47, 498–519 (2001).
https: / / doi.org/ 10.1109 / 18.910572
[35] Г. Девід Форні «Коди на графах: нормальні реалізації» IEEE Transactions on Information Theory 47, 520–548 (2001).
https: / / doi.org/ 10.1109 / 18.910573
[36] CW Helstrom “Quantum Detection and Estimation Theory” Академічний (1976).
https://doi.org/10.1016/S0076-5392(08)60247-7
http:///www.sciencedirect.com/science/bookseries/00765392/123
[37] Saikat Guha «Структуровані оптичні приймачі для досягнення суперадитивної здатності та межі Holevo» Physical Review Letters 106, 240502 (2011).
https: / / doi.org/ 10.1103 / PhysRevLett.106.240502
arXiv: 1101.1550
[38] Т. Етціон, А. Трахтенберг і А. Варді, «Які коди мають графи Таннера без циклів?» IEEE Transactions on Information Theory 45, 2173–2181 (1999).
https: / / doi.org/ 10.1109 / 18.782170
[39] Джейкоб К. Бріджмен і Крістофер Т. Чабб «Розмахування руками та інтерпретаційний танець: Вступний курс про тензорні мережі» Журнал фізики 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] Вілле Бергхольм, Юха Дж. Вартіайнен, Мікко Моттонен і Мартті М. Саломаа, «Квантові схеми з рівномірно керованими однокубітними вентилями», Фізичний огляд A 71, 052330 (2005).
https: / / doi.org/ 10.1103 / PhysRevA.71.052330
http:///arxiv.org/abs/quant-ph/0410066
[41] CH Bennett “Logical Reversibility of Computation” IBM Journal of Research and Development 17, 525–532 (1973).
https:///doi.org/10.1147/rd.176.0525
[42] Річард П. Брент «Методи визначення нуля з різною точністю та складність оцінки елементарної функції» Академічна преса (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] Харві та ван дер Хувен «Множення цілих чисел за час 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, and Saber Kais, “Quantum Algorithm and Circuit Design Solying the Poisson Equation” New Journal of Physics 15, 013021 (2013).
https://doi.org/10.1088/1367-2630/15/1/013021
arXiv: 1207.2485
[45] Міхір К. Бхаскар, Стюарт Хедфілд, Анаргірос Папагеоргіу та Ясонас Петрас, «Квантові алгоритми та схеми для наукових обчислень» Квантова інформація та обчислення 16, 197–236 (2016).
https:///doi.org/10.26421/QIC16.3-4-2
arXiv: 1511.08253
[46] Томас Хенер, Мартін Роттлер і Кріста М. Своре, «Оптимізація квантових схем для арифметики» (2018).
https:///doi.org/10.48550/arXiv.1805.12445
arXiv: 1805.12445
[47] Шенгбінь Ван, Чжімінь Ван, Вендун Лі, Лісінь Фан, Гуолун Цуй, Чжицян Вей та Юнцзянь Гу, «Дизайн квантових схем для оцінки трансцендентних функцій на основі методу двійкового розширення значення функції» Квантова обробка інформації 19, 347 (2020).
https://doi.org/10.1007/s11128-020-02855-7
arXiv: 2001.00807
[48] Джон Вотрус «Теорія квантової інформації», Cambridge University Press (2018).
https: / / doi.org/ 10.1017 / 9781316848142
https:///www.cambridge.org/core/product/identifier/9781316848142/type/book
[49] Дагмар Брусс, Девід П. ДіВінченцо, Артур Екерт, Крістофер А. Фукс, К’яра Маккіавелло та Джон А. Смолін, «Оптимальне універсальне квантове клонування, що залежить від стану», Фізичний огляд A 57, 2368–2378 (1998).
https: / / doi.org/ 10.1103 / PhysRevA.57.2368
[50] E. Arıkan “Поляризація каналів: метод побудови кодів досягнення ємності для симетричних двійкових вхідних каналів без пам’яті” IEEE Transactions on Information Theory 55, 3051–3073 (2009).
https:///doi.org/10.1109/TIT.2009.2021379
arXiv: 0807.3917
[51] Марк М. Уайлд і Сайкат Гуха «Полярні коди для класично-квантових каналів» IEEE Transactions on Information Theory 59, 1175–1187 (2013).
https:///doi.org/10.1109/TIT.2012.2218792
arXiv: 1109.2591
[52] Джозеф М. Ренес і Марк М. Уайлд «Полярні коди для приватної та квантової комунікації через довільні канали» IEEE Transactions on Information Theory 60, 3090–3103 (2014).
https:///doi.org/10.1109/TIT.2014.2314463
arXiv: 1212.2537
[53] S. Guha та MM Wilde «Полярне кодування для досягнення Holevo Capacity оптичного каналу з чистими втратами» Матеріали Міжнародного симпозіуму IEEE з теорії інформації (ISIT) 2012 р. 546–550 (2012).
https:///doi.org/10.1109/ISIT.2012.6284250
arXiv: 1202.0533
Цитується
[1] С. Брандсен, Авіджит Мандал і Генрі Д. Пфістер, «Поширення віри за допомогою квантових повідомлень для симетричних класично-квантових каналів», arXiv: 2207.04984.
Вищезазначені цитати від SAO / NASA ADS (останнє оновлення успішно 2022-08-23 14:04:15). Список може бути неповним, оскільки не всі видавці надають відповідні та повні дані про цитування.
Не вдалося отримати Перехресне посилання, наведене за даними під час останньої спроби 2022-08-23 14:04:14: Не вдалося отримати цитовані дані для 10.22331/q-2022-08-23-784 з Crossref. Це нормально, якщо DOI був зареєстрований нещодавно.
Ця стаття опублікована в Quantum під Creative Commons Attribution 4.0 International (CC на 4.0) ліцензія. Авторське право залишається за оригінальними власниками авторських прав, такими як автори або їх установи.
