В 1994 году один математик придумал, как заставить квантовый компьютер делать то, на что не способен обычный классический компьютер. Работа показала, что, в принципе, машина, основанная на правилах квантовой механики, может эффективно разбить большое число на его простые множители — задача настолько сложная для классического компьютера, что она составляет основу большей части сегодняшней интернет-безопасности.
Последовал всплеск оптимизма. Возможно, думали исследователи, мы сможем изобрести квантовые алгоритмы, способные решать огромное количество самых разных задач.
Но прогресс застопорился. «Это была немного обломочная траектория», — сказал Райан О'Доннелл Университета Карнеги-Меллона. «Люди говорили: «Это потрясающе, я уверен, что мы получим множество других замечательных алгоритмов». Неа." Ученые обнаружили резкое ускорение только для одного узкого класса задач из стандартного набора. называется НП, а это означает, что у них были эффективные проверяемые решения, такие как факторинг.
Так было почти три десятилетия. Затем в апреле исследователи изобретенный принципиально новый вид задач, которые квантовый компьютер должен решать экспоненциально быстрее, чем классический. Он включает в себя вычисление входных данных для сложного математического процесса, основанного исключительно на его беспорядочных выходных данных. Еще предстоит определить, стоит ли эта проблема особняком или она является первой на новом рубеже многих других.
«Чувство возбуждения есть, — сказал Винод Вайкунтанатан, ученый-компьютерщик из Массачусетского технологического института. «Многие люди думают о том, что еще есть».
Ученые-компьютерщики пытаются понять, что квантовые компьютеры делают лучше, изучая математические модели, которые их представляют. Часто они представляют себе модель квантового или классического компьютера в паре с идеализированной вычислительной машиной, называемой оракулом. Оракулы подобны простым математическим функциям или компьютерным программам, принимающим входные данные и выдающим заранее определенный результат. Они могут иметь случайное поведение, выводя «да», если входные данные попадают в определенный случайный диапазон (скажем, от 12 до 67), и «нет», если это не так. Или они могут быть периодическими, так что вход от 1 до 10 возвращает «да», от 11 до 20 дает «нет», от 21 до 30 снова дает «да» и так далее.
Допустим, у вас есть один из этих периодических оракулов, и вы не знаете период. Все, что вы можете сделать, это передать ему числа и посмотреть, что он выводит. С такими ограничениями, как быстро компьютер сможет найти период? В 1993 году Дэниел Саймон из Монреальского университета обнаружил, что квантовый алгоритм может вычислить ответ на тесно связанную проблему экспоненциально быстрее, чем любой классический алгоритм.
Результат позволил Саймону определить один из первых намеков на то, где можно ожидать значительного превосходства квантовых компьютеров. Но когда он представил свою статью на ведущей конференции, она была отклонена. Однако статья заинтересовала младшего члена программного комитета конференции — Питер Шор, который в то время работал в Bell Laboratories в Нью-Джерси. Далее Шор обнаружил, что может адаптировать алгоритм Саймона для расчета периода оракула, если он у него есть. Затем он понял, что может еще раз адаптировать алгоритм, чтобы решить уравнение, которое ведет себя подобно периодическому оракулу: уравнение, описывающее факторинг, который является периодическим.
Результат Шора стал историческим. Квантовый алгоритм, который он открыл, мог быстро сводить гигантские числа к составляющим их простым множителям, чего не может сделать ни один известный классический алгоритм. В последующие годы исследователи открыли другие эффективные квантовые алгоритмы. Некоторые из них, такие как алгоритм Шора, даже давали экспоненциальное преимущество, но никто не мог доказать резкое квантовое преимущество в любой задаче NP, которая не была периодической.
Этот недостаток прогресса привел двух ученых-компьютерщиков, Скотт Аронсон Техасского университета в Остине и Андрис Амбаинис Латвийского университета, сделать замечание. Доказательства квантового преимущества всегда казались зависимыми от оракулов, обладающих какой-то неслучайной структурой, например периодичностью. В 2009 году они высказал предположение что не может быть резкого ускорения в задачах NP, которые были случайными или неструктурированными. Никто не мог найти исключения.
Их гипотеза ограничивала возможности квантовых компьютеров. Но в нем говорилось только, что не было резкого ускорения для определенного типа неструктурированной задачи NP — с ответами «да» или «нет». Если проблема заключалась в выяснении более конкретных, количественных ответов, что известно как проблема поиска, гипотеза не применялась.
Имея это в виду, исследователи Такаси Ямакава Лабораторий социальной информатики NTT и Марк Жандри из NTT Research и Принстонского университета решили поэкспериментировать со специальной задачей поиска, предложенной в 2005 г. Одед Регев.
Представьте себе набор флюгеров, направленных в одном направлении. Дайте каждому из них размеренный толчок, затем пусть порывистый ветер повлияет на их направление. Регев хотел определить, основываясь на их окончательных направлениях, куда они все указывали изначально. Подобные проблемы стали называть «обучением с ошибками», потому что толчок и ветер действуют как источник случайной ошибки в исходном направлении. Есть свидетельства того, что это трудно решить как для классических, так и для квантовых алгоритмов.
Ямакава и Жандри подправили установку. Они изменили силу стартовых толчков, сделав их более предсказуемыми. Они также заставили ветер определяться случайным оракулом, так что в одних случаях он был еще более случайным, а в других - полностью бездействующим.
С помощью этих модификаций исследователи обнаружили, что квантовый алгоритм может эффективно находить начальное направление. Они также доказали, что любой классический алгоритм должен быть медленнее в экспоненциальный множитель. Как и Шор, они затем адаптировали свой алгоритм для решения реальной версии проблемы, которая заменяет оракула реальным математическим уравнением.
Ученые-компьютерщики все еще работают над тем, чтобы понять и решить эту проблему. Вайкунтанатан сравнивает это с другим, возникающим при сжатии данных: когда информация сжимается, два бита могут быть случайно сжаты в одно и то же место, перезаписывая их. Проблема предсказания этих столкновений заранее, чтобы их можно было избежать, имеет некоторое сходство. «Это класс проблем, которые в основном выглядят вот так, — сказал он. «Возможно, эти проблемы можно решить квантово».
Были надежды, что неструктурированная проблема, подобная новой, может быть решена даже на сегодняшних неоперившихся версиях квантовых компьютеров, что даст возможность их протестировать. Мысль заключалась в том, что неструктурированные задачи могут потребовать меньше ресурсов для программирования или быть менее чувствительными к шуму, поскольку они уже случайны. Но пока новая проблема кажется слишком сложной для решения существующими квантовыми компьютерами. «Это странная проблема. Я не думал дать ему определение, — сказал Ааронсон. «Но, оглядываясь назад, у него есть несколько очень приятных особенностей».
Результат представляет собой первый пример резкого квантового преимущества в неструктурированной проблеме NP. Может ли быть много других проблем, которые квантовый мир превращает из практически неразрешимых в решаемые? Теперь есть больше оснований так думать.
«Это несколько перевернуло наши представления о том, в каких задачах могут быть хороши квантовые компьютеры», — сказал О'Доннелл.
