Итак, какие же задачи уже именно в квантовой информации были решены при помощи ИИ. Их много, в один прекрасный июльский день вообще сразу пять статей с решениями давних открытых задач опубликовали, не обо всех этих открытых задачах я знал. Я расскажу о двух. Сегодня - о предельных возможностях исправления ошибок в квантовых каналах, если по-научному - строгое обращение теоремы кодирования.

Мы много раз затрагивали коды, исправляющие ошибки, например, здесь. Суть в том, что в битовые строки мы добавляем "избыточные", "проверочные" биты, которые позволяют исправить ошибки, если они возникнут в процессе передачи или хранения информации. Например, как мы обсуждали, можно просто повторить каждый бит три раза. Тогда, если возникнет ошибка в одном бите, то по двум повторениям, которые не поменялись, мы эту ошибку обнаружим и исправим.

Ключевая характеристика здесь - это отношение информационных битов к сумме информационных и проверочных. В данном случае оно равно 1/3: каждый бит повторяется три раза, т.е. именно информацию несут только треть битов, остальные проверочные. Код Хемминга, который упомянут по ссылке, более экономный: на 4 информационных бита приходится 3 проверочных, так что это отношение равно 4/(4+3)=4/7. Это отношение называется "кодовой скоростью" (code rate). А можно ли ещё лучше? Так вот основнополагающая теорема Шеннона из упомянутой в предыдущей записи работы "Математическая теория связи" устанавливает предельную возможность: к какой предельной кодовой скорости теоретически можно приблизиться при заданной вероятности ошибок. Ну то есть одно дело, когда ошибка возникает в каждом третьем бите, а другое - когда только в каждом сотом. Разумеется, во втором случае нам нужно меньше проверочных битов и можно достигнуть более высоких кодовых скоростей. Теорема Шеннона говорит, каких именно. Предельная теоретически возможная кодовая скорость называется пропускной способностью (capacity) канала связи.

Что значит "предельная" и "теоретически возможная". Для улучшения кодовой скорости лучше кодировать не отдельными битами, а блоками. Вот как код Хемминга берёт не отдельные биты, а блоки по 4 бита. Когда у нас блок, то у нас больше возможностей, мы можем осуществлять более "коллективные" операции. Так что беря блоки всё большей и большей длины, мы можем придумывать коды с более высокой кодовой скоростью.

А "теоретически возможная" - потому что кодовая скорость - не единственная характеристика кода с точки зрения практики. Например, код должен иметь быстрые алгоритмы кодирования и декодирования. Кодирование блоками слишком большой длины может быть и вычислительно сложным, и приводить к задержкам в линии связи: отправитель должен накопить весь блок, прежде чем начать его обрабатывать, а получатель всё это время ждёт. Но тем не менее теорема сообщает, какие у нас предельные теоретические возможности, когда мы абстрагируемся от этих подробностей. Для людей, разрабатывающих практические коды, она задаёт некий ориентир: что хотя бы теоретически возможно, а что принципиально невозможно. Как закон сохранения энергии в физике, например. Современные коды, исправляющие ошибки, достигают теоретического предела, являясь при этом вычислительно эффективными, практическими.