Исследователи сформулировали первый пример задачи, которую даже в принципе не сможет решить никакой классический компьютер, но сможет квантовый. Специалисты искали ее 25 лет. Работа выложена на сервер Electronic Colloquium on Computational Complexity.

В разделе информатики под названием теория алгоритмов вычислительные задачи относят к разным классам сложности. Для унификации часто рассматриваются только задачи разрешимости, ответ на которые может быть только «да» или «нет». Широко известны классы сложности P и NP. Задачи из первого класса может решить классическая детерминированная машина Тьюринга (абстрактный, но универсальный вычислитель) за полиномиальное время. Это значит, что количество операций, которое машине необходимо совершить для получения ответа, можно представить как многочлен, зависящий от длины входного сообщения. Стандартная задача этого класса заключаетс в том, что вычислитель проверяет, является ли определенное число простым.

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

В новой работе ученые впервые представили задачу из класса BQP, куда входят проблемы, которые квантовый компьютер может решить за полиномиальное время. До этой работы не было понятно, существуют ли попадающие в BQP примеры, которые при этом не попадают в PH — обобщающий NP-класс, который включает в себя все потенциально решаемые на сколь угодно продвинутом классическом вычислителе задачи. Теперь доказано, что задача оракульного разделения (Oracle Separation) — это как раз такой случай. Она формулируется так: пусть есть два генератора случайных чисел, производящие последовательности цифр; надо решить, полностью ли независимы получающиеся последовательности (как должно быть в случае истинной случайности) или они связаны неким неочевидным образом?

E. Edwards/JQI

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