Теория квантовой сложности

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

Двумя важными классами квантовой сложности являются BQP и QMA, которые являются квантовыми аналогами классов сложности P и NP с ограниченной ошибкой. Одна из основных целей квантовой теории сложности состоит в том, чтобы выяснить, где находятся эти классы по отношению к классическим классам сложности, таким как P, NP, PP, PSPACE и другим.

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

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

Примером, иллюстрирующим возможности квантовых вычислений, является алгоритм Гровера (также GSA от англ. Grover search algorithm) для решения задачи перебора, то есть нахождения решения уравнения

${\displaystyle (1)\qquad f(x)=1,}$

где ${\displaystyle f}$ есть булева функция от n переменных[1]. Квантовая сложность запроса алгоритма ${\textstyle O{\left({\sqrt {N}}\right)}}$ — квадратичное улучшение по сравнению с наилучшей возможной классической сложностью запроса (то есть линейного поиска).

• Квантовые вычисления
• Класс BQP
• Полиномиальная иерархия
• Квантовая машина Тьюринга

• John Watrous (2008), Quantum Computational Complexity, arΧiv:0804.3401v1 [quant-ph]

• Artem Kaznatcheev. Quantum query complexity (неопр.).