Войти  |  Регистрация
Авторизация

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



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

Обзор

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

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

Квантовая сложность запроса

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

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

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

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

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


Добавить комментарий
Ваше Имя:
Ваш E-Mail:
  • bowtiesmilelaughingblushsmileyrelaxedsmirk
    heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
    winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
    worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
    expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
    disappointedconfoundedfearfulcold_sweatperseverecrysob
    joyastonishedscreamtired_faceangryragetriumph
    sleepyyummasksunglassesdizzy_faceimpsmiling_imp
    neutral_faceno_mouthinnocent