Квантовый алгоритм — алгоритм, предназначенный для выполнения на квантовом компьютере.
В теории алгоритмов классом P называют множество задач, для которых существуют «быстрые» алгоритмы решения. Класс P включён в более широкие классы сложности алгоритмов.
В теории алгоритмов классом NP называют множество задач разрешимости, решение которых возможно проверить на машине Тьюринга за время, не превосходящее значения некоторого многочлена от размера входных данных, при наличии некоторых дополнительных сведений.
В теории алгоритмов классом сложности BPP называется класс предикатов, быстро вычислимых и дающих ответ с высокой вероятностью. Задачи, решаемые вероятностными методами и лежащие в BPP, возникают на практике очень часто.
Дискре́тное логарифми́рование (DLOG) — задача обращения функции 
в некоторой конечной мультипликативной группе 
.
Класс сложности PSPACE — набор всех проблем разрешимости в теории сложности вычислений, которые могут быть разрешены машиной Тьюринга с полиномиальным ограничением пространства.
В теории сложности, PP является классом проблем, решаемых вероятностными машинами Тьюринга за полиномиальное время, с вероятностью ошибки менее 1/2. Аббревиатура PP обозначает «вероятностный полиномиальный по времени».
В теории сложности полиномиальная иерархия — это иерархия классов сложности, которая обобщает классы P, NP, co-NP до вычислений с оракулом.
В информатике временна́я сложность алгоритма определяется как функция от длины строки, представляющей входные данные, равная времени работы алгоритма на данном входе. Временная сложность алгоритма обычно выражается с использованием нотации «O» большое, которая учитывает только слагаемое самого высокого порядка, а также не учитывает константные множители, то есть коэффициенты. Если сложность выражена таким способом, говорят об асимптотическом описании временной сложности, то есть при стремлении размера входа к бесконечности. Например, если существует число 
, такое, что время работы алгоритма для всех входов длины 
не превосходит 
, то временную сложность данного алгоритма можно асимптотически оценить как 
.
Класс сложности EXPTIME (иногда называемый просто EXP) — это множество задач, в теории сложности вычислений, решаемых с помощью детерминированной машины Тьюринга за время O(2p(n)), где p(n) это полиномиальная функция от n.
Питер Шор — американский учёный. Автор работ в области геометрии, теории вероятностей, комбинаторики, теории алгоритмов и квантовой информатики. Наиболее известен своими основополагающими результатами в теории квантовых вычислений.
Теория сложности вычислений — подраздел теоретической информатики, занимающейся исследованием сложности алгоритмов для решения задач на основе формально определённых моделей вычислительных устройств. Сложность алгоритмов измеряется необходимыми ресурсами, в основном это продолжительность вычислений или необходимый объём памяти. В отдельных случаях исследуются другие степени сложности, такие как размер микросхем, или количество процессоров, необходимая для работы параллельных алгоритмов.
В теории сложности, QMA — это квантовый аналог NP в классической теории сложности и аналог MA в вероятностной. Он связан с BQP также, как NP связан с P, или MA связан с BPP.
В математике, приближенная схема полиномиального времени или polynomial-time approximation scheme (PTAS) обозначает класс приближенных полиномиальных по времени выполнения алгоритмов для решения, как правило, NP-трудных оптимизационных задач. Если P = NP, то введение этого понятия теряет смысл. Поэтому далее будем предполагать, что Р не совпадает с NР. И без ограничения общности определим понятие для задачи минимизации.
Постквантовая криптография — часть криптографии, которая остаётся актуальной и при появлении квантовых компьютеров и квантовых атак. Так как по скорости вычисления традиционных криптографических алгоритмов квантовые компьютеры значительно превосходят классические компьютерные архитектуры, современные криптографические системы становятся потенциально уязвимыми для криптографических атак. Большинство традиционных криптосистем опирается на проблемы факторизации целых чисел или задачи дискретного логарифмирования, которые будут легко разрешимы на достаточно больших квантовых компьютерах, использующих алгоритм Шора. Многие криптографы в настоящее время ведут разработку алгоритмов, независимых от квантовых вычислений, то есть устойчивых к квантовым атакам.
Квантовая теория сложности — часть теории сложности вычислений в теоретической информатике. Изучает классы сложности, определённые с использованием квантовых компьютеров и квантовой информации, а также проблемы, связанные с этими классами сложности, и связи между классами квантовой сложности и классическими (неквантовыми) классами сложности.
В теории сложности вычислений EQP — класс задач разрешимости, решаемых квантовым компьютером, который выводит правильный ответ с вероятностью 1 и выполняется за полиномиальное время. Это — квантовый аналог класса сложности P.
Ква́нтовое превосхо́дство — способность квантовых вычислительных устройств решать проблемы, которые классические компьютеры практически не могут решить. Квантовое преимущество — возможность решать проблемы быстрее. С точки зрения теории сложности вычислений под этим обычно подразумевается обеспечение суперполиномиального ускорения по сравнению с наиболее известным или возможным классическим алгоритмом. Термин был популяризирован Джоном Прескиллом, но концепция квантового вычислительного преимущества, особенно в моделировании квантовых систем, восходит к предложению квантовых вычислений, которое дали Юрий Манин (1980) и Ричард Фейнман (1981).
Криптографическая гибкость («крипто-гибкость») позволяет системе информационной безопасности переключаться на альтернативные криптографические примитивы и алгоритмы, не внося существенных изменений в инфраструктуру системы. Крипто-гибкость заключается в способности предвидеть развитие угроз и переходить на новые алгоритмы по мере их появления. Криптографическая гибкость облегчает модернизацию и развитие системы, может выступать в качестве меры безопасности или механизма реагирования на атаки, когда обнаруживается уязвимость алгоритмов шифрования системы. Система безопасности считается крипто-гибкой, если её алгоритмы шифрования могут быть легко заменены и, по крайней мере, частично автоматизированы.
