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

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

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

Но прогресс застопорился. «Это был довольно неудачный путь, – сказал Райан О’Доннелл из Университета Карнеги-Меллона. – Люди говорили: “Это потрясающе, я уверен, что мы получим множество других удивительных алгоритмов”. Нет». Ученые обнаружили резкое ускорение только для одного узкого класса задач из стандартного набора, называемого NP, что означает, что у них были эффективно проверяемые решения, такие как факторизация.

Так продолжалось почти три десятилетия. Затем в апреле 2022-го года учёные изобрели принципиально новый вид задач, которые квантовый компьютер должен решать экспоненциально быстрее, чем классический. Он включает в себя вычисление входных данных для сложного математического процесса, основанного исключительно на его беспорядочных выходных данных. Еще предстоит определить, стоит ли эта проблема особняком или она является первой на новом рубеже многих иных.

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

Учёные пытаются понять, что квантовые компьютеры делают лучше, изучая математические модели, которые их представляют. Часто они представляют себе модель квантового или классического компьютера в паре с идеализированной вычислительной машиной, называемой оракулом. Оракулы подобны простым математическим функциям или компьютерным программам, принимающим входные данные и выдающим заранее определенный результат. Они могут иметь случайное поведение, выводя «да», если входные данные попадают в определенный случайный диапазон (скажем, от 12 до 67), и «нет», если это не так. Или они могут быть периодическими, так что вход от 1 до 10 возвращает «да», от 11 до 20 дает «нет», от 21 до 30 снова дает «да» и так далее.

Допустим, у вас есть один из этих периодических оракулов, и вы не знаете период. Всё, что вы можете сделать, это передать ему числа и посмотреть, что он выводит. С такими ограничениями, как быстро компьютер сможет найти период? В 1993 году Дэниел Саймон из Монреальского университета обнаружил, что квантовый алгоритм может вычислить ответ на похожую проблему экспоненциально быстрее, чем любой классический алгоритм.

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

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

Этот недостаток прогресса побудил двух учёных, Скотта Ааронсона из Техасского университета в Остине и Андриса Амбайниса из Латвийского университета, провести наблюдение. Доказательства квантового преимущества всегда казались зависимыми от оракулов, обладающих какой-то неслучайной структурой, например периодичностью. В 2009 году они предположили, что не может быть резкого ускорения в задачах NP, которые были случайными или неструктурированными. Никто не мог найти исключения.

Их гипотеза ограничивала возможности квантовых компьютеров. Но в ней говорилось только, что не было резкого ускорения для определенного типа неструктурированной задачи NP – с ответами «да» или «нет». Если проблема заключалась в выяснении более конкретных, количественных ответов, что известно как проблема поиска, гипотеза не применялась.

Имея это в виду, исследователи Такаши Ямакава из NTT Social Informatics Laboratories и Марк Жандри из NTT Research и Принстонского университета решили поэкспериментировать с конкретной задачей поиска, предложенной в 2005 году Одедом Регевом.

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

Ямакава и Жандри подправили установку. Они изменили силу стартовых толчков, сделав их более предсказуемыми. Они также заставляли ветер определяться случайным оракулом, так что в одних случаях он был еще более случайным, а в других – полностью бездействующим.

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

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

Были надежды, что неструктурированная проблема, подобная новой, может быть решена даже на сегодняшних неоперившихся версиях квантовых компьютеров, что даст возможность их протестировать. Мысль заключалась в том, что неструктурированные задачи могут потребовать меньше ресурсов для программирования или быть менее чувствительными к шуму, поскольку они уже случайны. Но пока новая проблема кажется слишком сложной для решения существующими квантовыми компьютерами. «Это странная проблема. Я не думал дать ей определение, – сказал Ааронсон. – Но, оглядываясь назад, у неё есть несколько очень приятных особенностей».

Результат представляет собой первый пример квантового преимущества в неструктурированной проблеме NP. Может ли быть много иных проблем, которые квантовый мир превращает из практически неразрешимых в решаемые? Теперь есть больше оснований так думать.

«Это несколько перевернуло наши представления о том, в каких задачах могут быть хороши квантовые компьютеры», – сказал О’Доннелл.

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

НЛО прилетело и оставило здесь промокод для читателей нашего блога:

— 15% на все тарифы VDS (кроме тарифа Прогрев) — HABRFIRSTVDS.

Квантовые алгоритмы побеждают новый вид проблем