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

Квантовая теория сложности — часть теории сложности вычислений в теоретической информатике. Изучает классы сложности, определённые с использованием квантовых компьютеров и квантовой информации, а также проблемы, связанные с этими классами сложности, и связи между классами квантовой сложности и классическими (неквантовыми) классами сложности.

Обзор

Класс сложности — это набор проблем, которые могут быть решены с помощью некоторой вычислительной модели в условиях ограниченных ресурсов. Например, класс сложности 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
• Полиномиальная иерархия
• Квантовая машина Тьюринга

Примечания

1. Иногда GSA неточно называют поиском в базе данных.

Литература

• John Watrous (2008). "Quantum Computational Complexity". arXiv:0804.3401v1 [quant-ph].
• Artem Kaznatcheev. Quantum query complexity (неопр.).