Показать меню

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

13.12.2020
20

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

Обзор

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

Еще по этой теме:
Евклидова квантовая гравитация
22:03, 12 декабрь
Евклидова квантовая гравитация
Евклидова квантовая гравитация — одна из попыток построить квантовую теорию гравитации. Формулировка Евклидова квантовая гравитация сформулирована на основе квантовой теории поля. Многообразия,
Квантовое превосходство
02:40, 12 декабрь
Квантовое превосходство
Квантовое превосходство — способность квантовых вычислительных устройств решать проблемы, которые классические компьютеры практически не могут решить. Квантовое преимущество — возможность решать
Класс PH
08:42, 11 декабрь
Класс PH
Класс сложности PH (от англ. polynomial hierarchy) — объединение всех классов сложности из полиномиальной иерархии: PH =
Эффект Парселла
14:14, 06 декабрь
Эффект Парселла
Эффект Парселла (Purcell effect, встречается также написание Эффект Пёрселла) — в квантовой электродинамике увеличение скорости испускания осциллятора в резонаторе по сравнению со скоростью
Класс (математика)
06:30, 06 декабрь
Класс (математика)
Класс — термин, употребляемый в теории множеств для обозначения произвольных совокупностей множеств, обладающих каким-либо определённым свойством или признаком. Более строгое определение класса
APX
08:20, 02 декабрь
APX
APX (от англ. «approximable») в теории вычислительной сложности — это класс NP-трудных задач, для которых существуют аппроксимационные алгоритмы полиномиальной сложности с постоянным коэффициентом
Комментарии:
Добавить комментарий
Ваше Имя:
Ваш 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