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

На ранних этапах изучения квантовых компьютеров специалисты по информатике задали вопрос, ответ на который, по их мнению, должен был открыть какую-то глубокую истину о возможностях этих футуристических машин. 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 при помощи т.н. ""оракула«:[https://ru.wikipedia.org/…%D0%BE%D0%BC]» или «чёрного ящика». Это распространённый в информатике результат, к которому прибегают исследователи, когда то, что они хотят доказать, никак им не даётся.

Самый лучший способ разделить классы сложности BQP и ЗР – измерить вычислительное время, требуемое на решение задач из каждого класса. Но в информатике нет «глубокого понимания реального вычислительного времени или возможности его измерить», — сказал Хенри Юн, специалист по информатике из Торонтского университета.

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

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

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

Авишай Тал

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

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

Новости о разделении классов BQP и PH распространились быстро. «Мир квантовой сложности гудит», — писал Лэнс Фортнау, специалист по информатике из Технологического университета Джорджии на следующий день после публикации работы.

Работа даёт железную уверенность в том, что квантовые компьютеры существуют в отдельном вычислительном мире от классических (по крайней мере, по определению с оракулом). Даже в мире, где P эквивалентно NP – там, где решить задачу коммивояжёра так же просто, как найти наиболее подходящую строчку в электронной таблице – доказательство Рэза и Тала демонстрирует наличие задач, решить которые способен только квантовый компьютер.

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