Квантовые алгоритмы могут находить выход из лабиринтов экспоненциально быстрее, чем классические, за счет забывания путей, по которым они шли. Новый результат предполагает, что компромисс может быть неизбежен.  

Представьте, что вы посещаете лабиринт с друзьями. Вы вышли из выхода вскоре после входа и ждёте несколько часов, прежде чем появятся ваши друзья. Естественно, они спрашивают о пути, по которому вы шли — вы ведь можете проследить свои шаги и показать им путь, верно?

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

Исследователи давно задавались вопросом, неизбежен ли этот компромисс. Неужели невозможно быстро найти выход, не забыв дорогу?

«Удивительно, что вам вообще нужно задавать этот вопрос», — сказал Мэтью Кудрон, учёный из Национального института стандартов и технологий в Гейтерсберге, штат Мэриленд.

В ноябре прошлого года Кудрон и двое его коллег сделали большой шаг к решению этой давней проблемы: они доказали, что ни один алгоритм из широкого и естественного класса быстрых квантовых алгоритмов не может найти путь через этот особый лабиринт, называемый сварным древовидным графом. Результаты показывают, что любой гипотетический алгоритм поиска пути, который не угадывает вслепую, должен временно потерять след входа, чтобы иметь хоть какие-то шансы на успех. Кажется, что забвение неизбежно.

«Я никак не мог предположить, что они действительно смогут это доказать», — сказал Саймон Аперс, исследователь квантовых вычислений из Национального центра научных исследований в области компьютерных наук в Париже, добавив, что результат «очень полезен для иллюстрации того, что квантовые алгоритмы могут и не могут делать».

Квантовое ускорение  

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

Поскольку интерференция должна работать правильно, не каждая вычислительная задача поддаётся квантовому ускорению, и действительно, исследователи всё ещё работают над тем, где могут помочь квантовые алгоритмы, спустя десятилетия после того, как впервые были предложены квантовые вычисления. Но они добились заметных успехов. В 1994 году Питер Шор разработал квантовый алгоритм для факторизации больших чисел — задача, очевидная сложность которой для классических компьютеров лежит в основе большей части современной криптографии. Алгоритм Шора мог быстро разложить на множители настолько большие числа, что все известные классические алгоритмы были бы практически бесполезны.

В 1996 году учёный Лов Гровер нашел второй потенциально практический пример: квантовый алгоритм для очень общей задачи поиска, похожей на поиск предмета, спрятанного внутри какой-либо из множества одинаковых коробок.

«В классическом варианте вы могли бы просто случайным образом попробовать некий вариант и посмотреть, нашли ли вы нужный, а затем попробовать ещё раз и вновь посмотреть, и вы продолжаете пробовать, пока не найдете нужный элемент», — сказал Аперс. Этот подход требует времени, пропорционального количеству ящиков. Умножьте это число на 100, и поиск будет в 100 раз медленнее.

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

Алгоритм Гровера был удивительно простой иллюстрацией ценности квантовой суперпозиции, но достигнутое им ускорение было относительно скромным — задачи, которые были далеко за пределами досягаемости лучших классических алгоритмов, также поставили бы алгоритм Гровера в тупик. Алгоритм факторинга Шора позволил увидеть огромную пропасть между возможностями квантовых и классических компьютеров. Был ли вариант задачи поиска Гровера, похожий на факторинг — практически неразрешимый для классических компьютеров, но лёгкий для квантовых компьютеров?

В конце 1990-х исследователи начали изучать этот вопрос, переформулировав его как вопрос о графах — сети точек или узлов, объединенных линиями, называемыми рёбрами. Любую задачу поиска можно сформулировать на языке теории графов, где один узел представляет собой начальную точку, другой — конечный пункт, а рёбра — возможные варианты выбора на каждом этапе пути.

Задача Гровера, например, соответствует поиску графа, в котором каждый узел связан с каждым другим узлом (потому что вы можете открывать ящики в любом порядке). Различные классические алгоритмы для данной задачи поиска сводятся к различным стратегиям исследования соответствующего графа по одному узлу за раз, в то время как квантовые алгоритмы могут перемещаться по нескольким рёбрам в суперпозиции.

Разветвление

В 2002 году группа учёных наконец нашла классически неразрешимую задачу поиска, которую можно было бы легко решить с помощью квантового алгоритма. Они начали с простого графа, называемого деревом, в котором каждый узел отрастает от двух рёбер, ведущих к ещё двум узлам, каждый из которых разделяется ещё на две ветви, и так далее. Начиная с одного «корневого» узла, древовидный граф многократно разветвляется, прежде чем закончиться последним слоем узлов, называемым «листьями». Команда представила, как взять два одинаковых дерева и «сварить» их вместе, расположив их листьями друг напротив друга, а затем используя случайный процесс, чтобы соединить каждый лист на одном дереве с двумя листьями на другом. Затем они задали следующий вопрос: Начав с одного корня сварного древовидного графа, сможете ли вы найти путь к другому?

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

Авторы статьи 2002 года показали, что простой квантовый алгоритм – «квантовое блуждание», которое равномерно распространяется по графу, используя множество путей в суперпозиции, – может найти путь к выходу намного быстрее. Это связано с тем, что симметричная компоновка объединённого древовидного графа приводит к интерференции между путями, и это концентрирует поток в прямом направлении. Выходной узел — это «точка фокусировки алгоритма», — сказал Александр Белов, учёный из Латвийского университета.

Есть большая вероятность, что этот алгоритм квантового блуждания сходится на выходе за время, пропорциональное количеству слоёв. Это делает его экспоненциально быстрее любого классического алгоритма — ускорение, сравнимое с алгоритмом факторинга Шора. Но интерференция, вызывающая квантовое ускорение, также стирает все записи о путях, которые алгоритм проходит на пути к выходу.

Учёные задались вопросом, есть ли способ получить лучшее из обоих миров — быстрый алгоритм, который идентифицирует путь от входа до выхода.

«Если это просто базовое квантовое блуждание, которое каким-то образом находит выход, это не сработает, — сказал Эндрю Чайлдс, учёный из Университета Мэриленда в Колледж-Парке, который был соавтором статьи 2002 года в качестве аспиранта и работал с Кудроном, публикуя новые результаты. — Но, может быть, вы могли бы как-нибудь его подправить.»

Улучшения

Одним из первых, кто подошёл к этой проблеме, был Ансис Росманис, учёный, ныне работающий в Высшей школе математики Университета Нагои. В статье 2010 года Росманис разработал класс алгоритмов, которые он назвал «квантовыми змеиными блужданиями», которые дополняют стандартный алгоритм квантовых блужданий памятью о том, где они были.

Поскольку стандартный алгоритм квантового блуждания проходит по графу, его следующий шаг зависит исключительно от того, где он находится в данный момент — как он туда попал, значения не имеет. В змеиных блужданиях Росманиса, напротив, вам нужно знать прошлое, чтобы предсказывать будущее. В частности, эволюция змеиного блуждания определяется «змеями», цепочками смежных узлов, через которые блуждание ранее проходило. Существует много разновидностей змеиных блужданий, различающихся, среди прочего, тем, как длина этих змей изменяется в ходе блуждания.

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

Затем в 2019 году Кудрон столкнулся со сварным древовидным графом в ином контексте: он и его коллега доказали, что все алгоритмы квантового блуждания, способные найти выход, не обладают свойством, универсальным среди алгоритмов, которые, как известно, дают экспоненциальное квантовое ускорение для иных задач. Результат не был напрямую связан с поиском пути, но Кудрон начал подозревать, что математические методы, которые позволили ему доказать это всеобъемлющее утверждение о свойствах всех алгоритмов сварных древовидных графов, могут также помочь решить вопрос о том, могут ли змеиные блуждания (или иные алгоритмы) найти путь. Переехав позже в том же году в Мэриленд, он начал сотрудничество с Чайлдсом, надеясь окончательно решить этот вопрос.

Чайлдс, Кудрон и их аспирант Амин Шираз Гилани начали с двух предположений, ограничивающих масштаб проблемы. Во-первых, они решили игнорировать необычные алгоритмы, пытающиеся телепортироваться в случайные точки графа в надежде наткнуться на выход. Эта стратегия похожа на попытку победить в видеоигре, выискивая хак, который можно использовать — возможно, технически это и жизнеспособно, но это было бы вопреки сути проблемы. Также сложно представить, что такое поведение может быть полезным, поскольку шансы попасть в нужное место становятся ничтожными на больших графах. Игнорирование алгоритмов, которые прыгают случайным образом, упростило анализ оставшихся алгоритмов, названных авторами «истинными» алгоритмами. В их число входили алгоритмы змеиного блуждания Росманиса и, возможно, иные, которые ещё никто не открыл.

Второе, более существенное предположение авторов заключалось в том, что алгоритм быстрого поиска пути останется «укоренённым», то есть он будет строить путь к выходному узлу, никогда не теряя из виду вход. Многие змеиные блуждания укоренены, но в принципе возможно, что змеиное блуждание без корней может найти путь к выходу — ему придётся отсоединиться от входного узла, а затем найти и вход, и выход позже.

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

Путь вперёд

Новый результат необязательно является концом истории. «Даже после изучения квантовых алгоритмов в течение достаточно долгого времени они продолжают меня удивлять», — написала в электронном письме Шелби Киммел, специалист по информатике из колледжа Миддлбери. Возможно, ещё существует гениальный алгоритм поиска пути за пределами рассматриваемого исследователями класса, который только и ждёт, чтобы его открыли.

В то время как алгоритмы, не являющиеся истинными, кажутся чрезвычайно маловероятными, неукоренённый алгоритм, возможно, мог бы построить путь от входа к выходу, начав где-то посередине. «Возможно, вы можете настроить его таким образом, чтобы змея вошла и оторвалась от корня, но затем каким-то образом решила вытянуться», — сказал Чайлдс, — «Это всё ещё не исключено».

Исследователям ещё предстоит найти практическое применение экспоненциальному квантовому ускорению, обнаруженному Чайлдсом и его коллегами 20 лет назад, отчасти потому, что оно зависит от особой симметрии сварного древовидного графа, который вряд ли существует в любой реальной сети. Но часто не менее важно понять, чего не могут сделать квантовые алгоритмы. Открытие Шором быстрого квантового алгоритма для факторизации больших чисел, который угрожает уничтожить нынешнюю криптографию, подчеркнуло важность решения проблем, как известно, трудных и для квантовых алгоритмов.

Один вид криптографии, неуязвимый для алгоритма Шора, основан на предположении, что найти пути между точками на определенных графах сложно. Доказательства того, что поиск пути через сварные деревья действительно сложен для квантовых алгоритмов, могут побудить исследователей разработать новые криптографические протоколы на основе графа сварных деревьев, хотя пока им не везло.

«Возможно, это означает, что такая структура в этой задаче просто не подходит для задач кодирования, которые нас волнуют», — сказал Чайлдс. «Или, может быть, вам просто нужно увидеть это правильно».

Автор перевода @arielf

НЛО прилетело и оставило здесь промокод для читателей нашего блога:
— 15% на заказ любого VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.