Институт теоретической физики, ETH Zürich, Швейцария
Находите эту статью интересной или хотите обсудить? Scite или оставить комментарий на SciRate.
Абстрактные
Недавно Ренес предложил квантовый алгоритм, называемый распространением убеждений с помощью квантовых сообщений (BPQM), для декодирования классических данных, закодированных с использованием двоичного линейного кода с древовидным графом Таннера, которые передаются по каналу CQ в чистом состоянии.1], т. е. канал с классическим входом и чисто квантовым выходом. Алгоритм представляет собой подлинный квантовый аналог декодирования, основанного на классическом алгоритме распространения убеждений, который добился большого успеха в классической теории кодирования при использовании в сочетании с LDPC или турбокодами. Совсем недавно Ренгасвами $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] Джозеф М. Ренес «Расшифровка распространения убеждений в квантовых каналах путем передачи квантовых сообщений» 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] Нараянан Ренгасвами, Каушик П. Сешадрисан, Сайкат Гуха и Генри Д. Пфистер, «Распространение убеждений с помощью квантовых сообщений для классических коммуникаций с квантовым расширением», npj Quantum Information 7, 97 (2021).
https://doi.org/10.1038/s41534-021-00422-1
Arxiv: 2003.04356
https: / / www.nature.com/ статьи / 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] Х. А. Лелигер и П. О. Вонтобель «Факторные графы для квантовых вероятностей» IEEE Transactions on Information Theory 63, 5642–5665 (2017).
https: / / doi.org/ 10.1109 / TIT.2017.2716422
Arxiv: 1508.00689
[5] М. Х. Цао и П. О. Вонтобель «Двухгранные факторные графы: определение, свойства и примеры», Семинар по теории информации IEEE (ITW), 2017 г., 136–140 (2017 г.).
https: / / doi.org/ 10.1109 / ITW.2017.8277985
Arxiv: 1706.00752
[6] Ханс-Андреа Лелигер «Введение в факторные графы» Журнал обработки сигналов IEEE 21, 28–41 (2004).
https: / / doi.org/ 10.1109 / MSP.2004.1267047
[7] В.П. Белавкин "Оптимальная множественная квантовая статистическая проверка гипотез" Стохастика 1, 315 (1975).
https: / / doi.org/ 10.1080 / 17442507508833114
[8] Пол Хаусладен и Уильям К. Вуттерс «Довольно хорошее измерение для различения квантовых состояний» Journal of Modern Optics 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] Масахидэ Сасаки, Кентаро Като, Масаюки Изуцу и Осаму Хирота, «Квантовые каналы, демонстрирующие супераддитивность в классической емкости», Physical Review 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] Дэвид Пулин «Оптимальное и эффективное декодирование каскадных квантовых блочных кодов» Physical Review 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 Transactions on Information Theory 58, 1231–1241 (2012).
https: / / doi.org/ 10.1109 / TIT.2011.2169534
Arxiv: 0912.4546
[17] Бен Кригер и Имран Ашраф «Многопутевое суммирование для декодирования двумерных топологических кодов» Quantum 2, 2 (102).
https://doi.org/10.22331/q-2018-10-19-102
Arxiv: 1709.02154
[18] Йе-Хуа Лю и Дэвид Пулин «Нейронные декодеры распространения убеждений для кодов с исправлением квантовых ошибок» Physical Review Letters 122, 200501 (2019).
https: / / doi.org/ 10.1103 / PhysRevLett.122.200501
Arxiv: 1811.07835
[19] Алекс Ригби, Дж. К. Оливье и Питер Джарвис, «Модифицированные декодеры распространения достоверности для квантовых кодов проверки на четность с низкой плотностью», Physical Review A 100, 012330 (2019).
https: / / doi.org/ 10.1103 / PhysRevA.100.012330
Arxiv: 1903.07404
[20] Павел Пантелеев и Глеб Калачев «Вырожденные квантовые LDPC-коды с хорошими характеристиками конечной длины» Quantum 5, 585 (2021).
https://doi.org/10.22331/q-2021-11-22-585
[21] Июль X. Ли и Паскаль О. Вонтобель «Декодирование кодов квантовых стабилизаторов на основе псевдокодовых слов», Международный симпозиум IEEE по теории информации (ISIT) 2019–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/ наука / статьи / PII / S0003491607001509
[26] Г. А. Бете «Статистическая теория сверхрешеток» 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] Рудольф Пайерлс «Статистическая теория сверхрешеток с неравными концентрациями компонентов» Труды Королевского общества 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] Дж. С. Йедидия, В. Т. Фриман и Ю. Вайс, «Построение приближений свободной энергии и обобщенных алгоритмов распространения убеждений», Теория информации, IEEE Transactions on 51, 2282–2312 (2005).
https: / / doi.org/ 10.1109 / TIT.2005.850085
[31] М.Б. Гастингс «Распространение квантовой веры: алгоритм для тепловых квантовых систем» 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] М. Х. Цао и П. О. Вонтобель «Графики квантовых факторов: операции закрытия коробки и вариационные подходы», Международный симпозиум по теории информации и ее приложениям (ISITA), 2016 г., 651–655 (2016 г.).
https: / / ieeexplore.ieee.org/ документ / 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 «Квантовая теория обнаружения и оценки», академический (1976).
https://doi.org/10.1016/S0076-5392(08)60247-7
http: / / www.sciencedirect.com/ science / bookseries / 00765392/123
[37] Сайкат Гуха «Структурированные оптические приемники для достижения сверхаддитивной емкости и предела Холево» Письма о физическом обзоре 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: 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] Вилле Бергхольм, Юха Дж. Вартиайнен, Микко Моттонен и Мартти М. Саломаа, «Квантовые схемы с однокубитными вентилями с равномерным управлением», 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] Ричард П. Брент «Методы поиска нуля с множественной точностью и сложность оценки элементарных функций» 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] Харви и ван дер Хувен «Целочисленное умножение за время O (n Log n)» Annals of Mathematics 193, 563 (2021).
https: / / doi.org/ 10.4007 / annals.2021.193.2.4
[44] Юдонг Цао, Анаргирос Папагеоргиу, Ясонас Петрас, Джозеф Трауб и Сабер Кайс, «Квантовый алгоритм и схема решения уравнения Пуассона», Новый журнал физики, 15, 013021 (2013).
https://doi.org/10.1088/1367-2630/15/1/013021
Arxiv: 1207.2485
[45] Михир К. Бхаскар, Стюарт Хэдфилд, Анаргирос Папагеоргиу и Ясонас Петрас, «Квантовые алгоритмы и схемы для научных вычислений», Quantum Information & Computation 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] Дагмар Брус, Дэвид П. ДиВинченцо, Артур Экерт, Кристофер А. Фукс, Кьяра Маккиавелло и Джон А. Смолин, «Оптимальное универсальное и зависящее от состояния квантовое клонирование» Physical Review A 57, 2368–2378 (1998).
https: / / doi.org/ 10.1103 / PhysRevA.57.2368
[50] Э. Арикан «Поляризация канала: метод построения кодов достижения пропускной способности для симметричных каналов без памяти с двоичным вводом» 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] С. Гуха и М. М. Уайлд «Полярное кодирование для достижения пропускной способности Холево оптического канала с чистыми потерями», Материалы Международного симпозиума IEEE по теории информации (ISIT) 2012 г. 546–550 (2012 г.).
https: / / doi.org/ 10.1109 / ISIT.2012.6284250
Arxiv: 1202.0533
Цитируется
[1] С. Брандсен, Авиджит Мандал и Генри Д. Пфистер, «Распространение убеждений с помощью квантовых сообщений для симметричных классически-квантовых каналов», Arxiv: 2207.04984.
Приведенные цитаты из САО / НАСА 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 BY 4.0) лицензия. Авторское право остается за первоначальными правообладателями, такими как авторы или их учреждения.
