Наконец появилась задача, которую смогут решить только квантовые компьютеры

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

На ранних этапах изучения квантовых компьютеров специалисты по информатике задали вопрос, ответ на который, по их мнению, должен был открыть какую-то глубокую истину о возможностях этих футуристических машин. 25 лет спустя ответ на него был найден. В работе, опубликованной в мае 2018, специалисты по информатике Рэн Рэз и Авишай Тал предложили убедительное доказательство того, что вычислительные возможности квантовых компьютеров превосходят всё, чего в принципе могут достичь классические компьютеры. Рэз, профессор Принстонского университета и Вайзмановского научного института, а также Тал, постдок Стэнфордского университета, определили особый тип вычислительных задач. Они доказали, с одной оговоркой, что квантовые компьютеры могли бы эффективно решить задачу, а традиционные компьютеры завязли бы навечно, пытаясь это сделать. Специалисты по информатике искали такую задачу с 1993 года, когда впервые определили класс задач BQP, включающий в себя все задачи, которые способен решить квантовый компьютер. С тех пор они надеялись противопоставить BQP класс задач, известный как PH, включающий все задачи, выполнимые на любом классическом компьютере, даже невероятно продвинутом, разработанном какой-нибудь цивилизацией будущего. Возможность такого противопоставления зависела от отыскания задачи, которая принадлежала бы к классу BQP, но не к классу PH. И теперь Рэз и Тал сделали это.

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

Квантовые классы

Базовая задача теоретической информатики – разделить задачи на классы сложности. Класс сложности содержит все задачи, которые можно решить, располагая определённым ресурсом, таким, как время или память.

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

Два знаменитых класса сложности – это P и NP. P – это все задачи, которые способен быстро решить классический компьютер. (Задача «является ли число простым?» принадлежит к P). К NP принадлежат все задачи, которые классический компьютер не обязательно решает быстро, но правильность имеющегося решения любой из которых он может быстро проверить. («Каковы простые множители числа?» принадлежит к NP). Учёные считают, что классы P и NP различаются, но задача доказать это различие является сложнейшей и главнейшей из открытых задач в этой области.

PH содержит NP, который содержит P. Является ли BQP классом, отдельным от PH?

В 1993 году специалисты по информатике Итан Бернштейн и Умеш Вазирани определили новый класс сложности, который они назвали BQP, или «квантово-полиномиальное время с ограничением вероятности ошибок». Они определили класс как содержащий все задачи по принятию решений – задачи с ответом «да» или «нет» – которые квантовые компьютеры способны эффективно решать. Примерно в то же время они доказали, что квантовые компьютеры способны решить все задачи, на которые способны классические. То есть, BQP содержит все задачи, содержащиеся в P. Ещё один пример отдельных классов задач. Задача коммивояжёра спрашивает, существует ли путь, проходящий через определённые города, более короткий, чем заданное расстояние. Такая задача находится в NP. Более сложная задача спрашивает, является ли это расстояние наикратчайшим путём через эти города. Такая задача находится в PH.

Однако они не смогли определить, содержит ли BQP задачи, которых нет в другом важном классе задач, известном как PH или «полиномиальная иерархия». PH – это обобщение NP. Он содержит все задачи, которые можно получить, начав с задачи из NP, и усложняя её, добавляя уточняющие утверждения вроде «существует ли» и «для всех». Классические компьютеры пока не могут решить большую часть задач из PH, но этот класс можно считать классом задач, которые классические компьютеры могли бы решить, если бы оказалось, что P эквивалентно NP. Иначе говоря, чтобы сравнить BQP и PH, надо определить, есть ли у квантовых компьютеров преимущество перед классическими, которое останется, даже если классические компьютеры внезапно научатся решать гораздо больше задач, чем они могут решить сегодня.

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

Чтобы найти задачу, принадлежащую к BQP, но не к PH, нужно определить нечто, к чему «классический компьютер по определению не смог бы даже эффективно проверить ответ, не говоря уже о том, чтобы найти его, — сказал Ааронсон. – Это исключает множество задач, с которыми мы работаем в информатике».

Спросите оракула

Задача. Допустим, у нас есть два генератора случайных чисел, каждый из которых выдаёт последовательность цифр. Вопрос компьютеру: являются ли две этих последовательности полностью независимыми друг от друга, или они как-то незаметно связаны (например, получена ли одна последовательность преобразованием Фурье другой)? Ааронсон представил эту задачу «фурреляции» в 2009 и доказал, что она принадлежит к BQP. Остался второй, более сложный шаг – доказать, что фурреляция не входит в PH.

Рэн Рэз

В определённом смысле, именно это и удалось сделать Рэзу и Талу. Их работа разделяет BQP и PH при помощи т.н. "оракула" или «чёрного ящика». Это распространённый в информатике результат, к которому прибегают исследователи, когда то, что они хотят доказать, никак им не даётся. Самый лучший способ разделить классы сложности BQP и PH – измерить вычислительное время, требуемое на решение задач из каждого класса. Но в информатике нет «глубокого понимания реального вычислительного времени или возможности его измерить», — сказал Хенри Юн, специалист по информатике из Торонтского университета.

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

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

«В каком-то смысле мы понимаем такую модель гораздо лучше. Она больше говорит об информации, чем о вычислениях», — сказал Тал.

Авишай Тал

Новая работа Рэза и Тала доказывает, что для решения проблемы фурреляции квантовому компьютеру потребуется гораздо меньше подсказок, чем классическому. Более того, квантовому компьютеру нужна всего одна подсказка, при том, что в PH нет алгоритма решения такой задачи даже с неограниченным количеством подсказок. «Это значит, что существует крайне эффективный квантовый алгоритм, решающий такую задачу, — сказал Рэз. – Но если рассматривать только классические алгоритмы, то, даже если дойти до самых верхних классов классических алгоритмов, они с ней не справятся». Это доказывает, что с оракулом фурреляция относится к задачам, принадлежащим к BQP, но не к PH.

Рэз и Тал почти дошли до этого результата около четырёх лет назад, но не смогли сделать один шаг в будущем доказательстве. А потом, всего за месяц до публикации, Тал услышал о новой работе по генераторам псевдослучайных чисел, и понял, что технологии из той статьи как раз дают то, что им с Рэзом нужно было для того, чтобы закончить их собственную. «Это был недостающий фрагмент», — сказал Тал. Новости о разделении классов BQP и PH распространились быстро. «Мир квантовой сложности гудит», — писал Лэнс Фортнау, специалист по информатике из Технологического университета Джорджии на следующий день после публикации работы. Работа даёт железную уверенность в том, что квантовые компьютеры существуют в отдельном вычислительном мире от классических (по крайней мере, по определению с оракулом). Даже в мире, где P эквивалентно NP – там, где решить задачу коммивояжёра так же просто, как найти наиболее подходящую строчку в электронной таблице, – доказательство Рэза и Тала демонстрирует наличие задач, решить которые способен только квантовый компьютер.

«Даже если бы P был эквивалентен NP, даже с таким сильным предположением, — сказал Фортнау, — квантовые компьютеры всё равно будет не догнать».