Програ́ммное обеспе́чение (ПО) — программа или множество программ, используемых для управления компьютером.
А́лан Мэ́тисон Тью́ринг — английский математик, логик, криптограф, оказавший существенное влияние на развитие информатики. Офицер ордена Британской империи, член Лондонского королевского общества (1951).
Те́зис Чёрча — Тью́ринга — логико-математический принцип, устанавливающий эквивалентность между интуитивным понятием алгоритмической вычислимости и строго формализованными понятиями частично рекурсивной функции и функции, вычислимой на машине Тьюринга. В связи с интуитивностью исходного понятия алгоритмической вычислимости, данный тезис носит характер суждения об этом понятии и его невозможно строго доказать или опровергнуть. Перед точным определением вычислимой функции математики часто использовали неофициальный термин, «эффективно вычислимый» для описания функций, которые можно вычислить с помощью «бумажно-карандашных» методов.
Ква́нтовый компью́тер — вычислительное устройство, которое использует явления квантовой механики для передачи и обработки данных. Квантовый компьютер оперирует не битами, а кубитами, имеющими значения одновременно и 0, и 1. Теоретически это позволяет обрабатывать все возможные состояния одновременно, достигая существенного преимущества над обычными компьютерами в ряде алгоритмов.
Квантовый алгоритм — алгоритм, предназначенный для выполнения на квантовом компьютере.
Дэ́вид Элиезер Дойч — британский физик-теоретик израильского происхождения, работающий в Оксфордском университете; один из пионеров в области квантовых вычислений и пропагандист эвереттовской многомировой интерпретации квантовой механики. Член Лондонского королевского общества (2008).
Сверхтьюринговыми вычислениями называются такие вычисления, которые не могут быть проделаны на машине Тьюринга. Они включают в себя разнообразные гипотетические методы, основанные на суперрекурсивных алгоритмах, а также некоторые другие типы вычислений — например, интерактивные вычисления. Термин гипервычисления был впервые введён Джеком Коуплендом и Дианой Праудфут. Возможность физической реализации таких вычислений активно обсуждается.
Языки квантового программирования — языки программирования, позволяющие выражать квантовые алгоритмы с использованием высокоуровневых конструкций. Их цель не столько создание инструмента для программистов, сколько предоставление средств для исследователей для облегчения понимания работы квантовых вычислений.
Цифровая физика — совокупность теоретических взглядов, основанных на интерпретации, что Вселенная по сути является информацией и, следовательно, является вычислимой. Из данной идеи следует, что Вселенная может пониматься как результат работы некоторой компьютерной программы или как некий вид цифрового вычислительного устройства.
Квантовый робот — гипотетическое квантовое устройство, представляющее собой подвижную квантовую наносистему со встроенным квантовым компьютером и системами взаимодействия с окружающей средой. Первую модель квантового робота предложил Поль Бенёв в 1998 году.
Тезис Чёрча — Тьюринга — Дойча — более строгая в физическом смысле формулировка эвристического вычислительного тезиса Чёрча — Тьюринга, предложенная Дэвидом Дойчем в 1985 году.
Компью́терная му́зыка — термин, который первоначально использовался в кругу специалистов-профессионалов для обозначения области инженерных разработок, связанных с цифровым синтезом музыкальных звуков, цифровой обработкой звуковых сигналов, цифровой записью различных сонорных структур и так далее.
Ве́нтиль То́ффоли (CCNOT) — универсальный контролируемый обратимый вентиль с тремя входами и выходами, предложенный Томасом Тоффоли в 1980 году.
Вентиль Фредкина — универсальный трехвходовый логический вентиль класса C-U, достаточный для построения схем любой степени сложности. Обладает обратимостью — зная состояние выходов можно точно установить состояния входов элемента, таким образом на его базе можно строить обратимые вычисления и обратимые логические схемы. В частности, может использоваться как квантовый вентиль при реализации квантовых компьютеров. Назван в честь Эдварда Фредкина, предложившего этот вентиль.
Идея квантовых вычислений была независимо предложена Юрием Маниным и Ричардом Фейнманом в начале 1980-х. С тех пор была проделана колоссальная работа для построения работающего квантового компьютера.
Обратимые вычисления — модель вычислений, в которой процесс вычисления является в некоторой степени обратимым. Например, в вычислительной модели, использующей наборы состояний и переходов между ними, необходимым условием обратимости вычислений является возможность построения однозначного (инъективного) отображения каждого состояния в следующее за ним. На XX век и начало XXI века обратимые вычисления обычно относят к нетрадиционным моделям вычислений.
Алгоритм Бернштейна — Вазирани — квантовый алгоритм, решающий задачу нахождения 
-битного числа, скрытого в черном ящике. Предложен Итаном Бернштейном и Умешем Вазирани в 1993 году. Данный алгоритм решает поставленную задачу значительно быстрее, чем это возможно в неквантовой постановке. Алгоритм может применяться в базах данных, атаках на блочные шифры, тестах производительности для квантовых компьютеров, был реализован на 5- и 16-кубитных квантовых компьютерах IBM.
Анциллы — это дополнительные биты, используемые для достижения определённых целей при вычислениях. В классических вычислениях любой бит памяти может быть включен или выключен по желанию, не требуя для этого предварительного знания о состояниях или дополнительных ухищрений. Однако это не относится к квантовым вычислениям или классическим обратимым вычислениям. В этих моделях вычислений все операции с памятью компьютера должны быть обратимыми, а ведь включение или выключение бита приводит к потере информации о его начальном значении. По этой причине в квантовых алгоритмах невозможно детерминированно перевести биты в конкретное желаемое состояние, если только нет доступа к битам, исходное состояние которых известно заранее. Такие биты, значения которых известны априори, известны как биты анциллы в задачах квантового или обратимого вычисления.
Turochamp — шахматная программа, разработанная Аланом Тьюрингом и Дэвидом Чемперноуном в 1948 году в рамках исследования по информатике и машинному обучению. Перед тем, как сделать ход, Turochamp рассматривает все возможные ходы и просчитывает каждый возможный ответ оппонента, после чего дополнительно анализирует удачные ходы. Всем полученным в результате анализа позициям присваивается метрика, по которой программа выбирает наиболее удачный ход. Следуя этому алгоритму, программа способна разыграть полноценную партию от начала до конца против живого соперника на уровне начинающего игрока в шахматы.
Квантовая схема — модель квантовых вычислений, аналогичная классическим схемам, в которых вычисление представляет собой последовательность квантовых вентилей, измерителей, инициализации кубитов известными значениями и, возможно, других действий. Минимальный набор действий, которые схема должна выполнять над кубитами, чтобы включить квантовые вычисления, известен как критерий Ди Винченцо.
