Книга Эта странная математика. На краю бесконечности и за ним - Дэвид Дарлинг

Большинство ученых, занимающихся вычислительными системами, полагают, что P ≠ NP. Это мнение подкреплено десятилетиями исследований, в результате которых ни для одной из более чем 3000 известных NP-полных задач не было найдено ни единого алгоритма, позволяющего решить ее за полиномиальное время. И все же аргумент, основанный на отрицательном опыте, не слишком убедителен, особенно в свете неожиданного доказательства Великой теоремы Ферма – очень просто сформулированной задачи, для решения которой потребовались огромные усилия и самые передовые методы. Чисто философские аргументы в пользу того, что P ≠ NP, также не очень убедительны. Скотт Ааронсон, математик, специалист в области теории вычислительных систем, преподающий в Массачусетском технологическом институте, заявил: “Если окажется, что P = NP, то мир станет совершенно не таким, каким мы его обычно считаем. Не будет больше никакой особой ценности в «творческих скачках», исчезнет принципиальная разница между решением задачи и признанием правильности найденного решения”. Тем не менее и в математике, и в других науках с завидной частотой происходят события, полностью переворачивающие наши представления об окружающем мире. Если действительно окажется, что P = NP, то, прежде всего, вряд ли это открытие будет иметь большое практическое значение – ведь доказательство, скорее всего, будет неконструктивным. Другими словами, даже если будет доказано, что для решения NP-полных задач существуют полиномиальные алгоритмы, ни одного конкретного алгоритма в доказательстве приведено не будет. Так что по крайней мере в ближайшем будущем нашим защищенным данным ничто не угрожает – хотя не совсем ясно, как долго это продлится, ведь математики уже всерьез занялись поиском такого алгоритма.

В любом случае, прежде чем существенные сдвиги в решении проблемы равенства P и NP или в разработке более эффективных алгоритмов поставят под угрозу безопасность наших данных, на помощь нам, вероятно, подоспеет квантовая механика. Разработки в области квантовой криптографии могут привести к созданию абсолютно стойкого шифра, не поддающегося дешифровке никакими методами. Один из действительно нераскрываемых шифров был изобретен еще в 1886 году и получил название “одноразовый блокнот”. Ключ представляет собой случайную последовательность букв той же длины, что и сообщение. Сообщение объединяется с ключом путем присвоения каждой букве числового значения (A = 1, B = 2 и так далее), сложения числовых значений букв сообщения и соответствующих им букв ключа, вычитания из получившихся сумм 26, в случае если сумма превышает 26, и последующего обратного превращения чисел в буквы[24]. Доказано, что этот метод является абсолютно криптостойким. Даже если у кого-то найдется достаточно времени, чтобы перебрать все возможные комбинации, будет совершенно невозможно отличить правильную расшифровку от множества неправильных вариантов. Важное условие: чтобы шифр невозможно было взломать, ключ должен после использования уничтожаться. Если его использовать повторно, то любой человек, имеющий в своем распоряжении оба зашифрованных сообщения и знающий, что ключ один и тот же, сможет их расшифровать. Кроме того, ключи должны передаваться секретно, поскольку доступ к ключу грозит мгновенной расшифровкой. Одноразовые шифры в свое время использовались советскими шпионами. Они сшивались в крошечные блокноты и пропитывались специальным горючим составом, чтобы при уничтожении от них не оставалось и следа. Такие шифры и сейчас используются для защиты данных, передаваемых по линии прямой связи между президентами США и России. Но необходимость секретно обмениваться ключами – серьезный недостаток метода, делающий его непригодным для большинства практических целей, например для передачи данных онлайн.

С приходом квантовых технологий все может измениться. В их основе лежит тот факт, что измерение определенной характеристики световых частиц (фотонов), называемой поляризацией, влияет на саму поляризацию. (Поляризация – это свойство волн, соответствующих фотонам, которое описывает поведение колеблющейся величины в плоскости, перпендикулярной направлению их движения.) Определяющим обстоятельством является то, что, если поляризацию измерить дважды в одном направлении, результат будет один и тот же. В одном из методов измерения используется фильтр, называемый ортогональным. Если свет поляризован вертикально или горизонтально, он проходит через ортогональный фильтр, сохраняя исходную поляризацию. Свет, поляризованный иным образом, также пройдет через фильтр, но изменит поляризацию либо на вертикальную, либо на горизонтальную. Еще один метод измерения поляризации использует диагональный фильтр, работающий так же, как и ортогональный, только колебания происходят под углом и к вертикали, и к горизонтали. И завершают устройство криптографической системы еще два фильтра. Один из них определяет, как поляризован свет, прошедший через ортогональный фильтр; второй делает то же по отношению к свету, прошедшему через диагональный фильтр.

Предположим, нам нужно передать случайный бит для использования в “одноразовом блокноте”. Мы пропускаем фотон через ортогональный или диагональный фильтр (выбор произволен), а затем записываем, как он был поляризован – вертикально или горизонтально. То же просим сделать и получателя. Получатель сообщает нам, какой фильтр использовал он, а мы уточняем, какой использовали сами. Если они совпадают, то переданный бит можно в дальнейшем использовать в “одноразовом блокноте”. Если нет, бит удаляется, а процесс повторяется. Злоумышленник не сумеет узнать, какой из фильтров был использован, пока фотон не пройдет через всю систему и его уже нельзя будет измерить. Более того, поскольку измерение поляризации способно ее изменить, мы можем, собрав достаточно битов, сравнить небольшую их часть, а после этого удалить. Если совпадение полное, канал связи считается защищенным, а значит, остальные биты можно безопасно использовать в “одноразовом блокноте”. Если же нет, мы поймем, что нас пытаются подслушать, и в этом случае все переданные биты отбраковываются. Таким образом, квантовая криптография не только защищает “одноразовый блокнот” от злоумышленников, но и делает то, что не под силу традиционной криптографии, – выявляет саму попытку перехвата данных.

Область квантовых вычислений развивается очень динамично. В 2017 году физики из Университета Сассекса обнародовали проект создания крупномасштабных квантовых компьютеров, сделав его доступным для всех. В этом проекте разъясняется, как избежать декогеренции – проблемы, которая до тех пор мешала ученым создать в лабораторных условиях устройство более чем на 10–15 кубитов. Также там приводится описание конкретных технологий, которые позволят сделать реальностью мощные квантовые компьютеры с гораздо большим числом кубитов. Среди таких технологий: использование в качестве кубитов ионов (заряженных атомов), захваченных в специальные ловушки, при комнатной температуре; передача ионов из одного модуля системы в другой при помощи электрических полей; а также применение логических вентилей, контролируемых микроволнами и изменением напряжения. Для начала ученые из Университета Сассекса собираются построить небольшой прототип квантового компьютера. Тем временем Google, Microsoft и множество различных стартапов, таких как IonQ, разрабатывают собственные схемы, основанные на захвате ионов в ловушки, использовании явления сверхпроводимости и (в случае с Microsoft) на концепции топологических квантовых вычислений. Компания IBM объявила о своих планах “через несколько лет” вывести на рынок квантовый компьютер на 50 кубитов, а ученые уже заглядывают дальше, предвидя то время, когда реальностью станут машины на миллионы, а то и на миллиарды кубитов[25].