Асимптотически хорошие семейства классических и квантовых LDPC кодов

Классические LDPC коды являются важными компонентами современных систем хранения и передачи данных, а их квантовые аналоги (qLDPC коды) обещают значительную экономию ресурсов в протоколах для отказоустойчивых квантовых вычислений. Сотрудниками кафедры МаТИС механико-математического факультета МГУ П.А. Пантелеевым и Г.В. Калачевым представлена работа (arXiv: 2111.03654), показывающая существование асимптотически хороших семейств квантовых LDPC кодов, что доказывает qLDPC гипотезу, остававшуюся открытой уже более двадцати лет. Кроме того, следствием работы является существование локально-тестируемых кодов (LTC) с оптимальными асимптотическими характеристиками, что решает другую известную открытую проблему в области классических LDPC кодов, называемую c^3-гипотезой, ответ на которую также недавно независимо был получен в работе arXiv: 2111.04808.

Новая конструкция П.А. Пантелеева и Г.В. Калачева основана на оригинальной идее авторов, предложенной в 2020 году, позволяющей объединять два симметричных LDPC кода при помощи тензорного произведения над групповой алгеброй в двумерный цепной комплекс. Данная идея в более общем виде также изучалась в последующих работах Николоса Брукмана и Йенса Эберхардта в 2020-2021 годах. В своей новой работе, принятой на международную конференцию STOC 2022, П.А. Пантелеев и Г.В. Калачев показывают, что первые группы гомологий подобных комплексов позволяют строить асимптотически хорошие квантовые LDPC коды. В то же время вторые группы гомологий дают пример локально-тестируемых классических кодов с оптимальными асимптотическими свойствами.

Доклад о данных результатах можно послушать 2 марта 2022 г. в 18.30 на спецсеминаре «Теория автоматов» по zoom конференции:
https://us02web.zoom.us/j/88665141982?pwd=N3NoVmFKdlV..
Meeting ID: 886 6514 1982
Passcode: 965515

Популярное изложением данных результатов можно найти в статье журнала Quanta Magazine:
Qubits Can Be as Safe as Bits (Кубиты могут быть настолько же надежными, как и биты)

https://www.quantamagazine.org/qubits-can-be-as-safe-as-bits-researchers...

Категория: