Алгори́тм — совокупность точно заданных правил решения некоторого класса задач или набор инструкций, описывающих порядок действий исполнителя для решения определённой задачи. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Независимые инструкции могут выполняться в произвольном порядке, параллельно, если это позволяют используемые исполнители.
Ква́нтовая (волнова́я) меха́ника — фундаментальная физическая теория, которая описывает природу в масштабе атомов и субатомных частиц. Она лежит в основании всей квантовой физики, включая квантовую химию, квантовую теорию поля, квантовую технологию и квантовую информатику.
А́лан Мэ́тисон Тью́ринг — британский математик, логик, криптограф, оказавший существенное влияние на развитие информатики. Офицер ордена Британской империи, член Лондонского королевского общества (1951).
Те́зис Чёрча — Тью́ринга — логико-математический принцип, устанавливающий эквивалентность между интуитивным понятием алгоритмической вычислимости и строго формализованными понятиями частично рекурсивной функции и функции, вычислимой на машине Тьюринга. В связи с интуитивностью исходного понятия алгоритмической вычислимости, данный тезис носит характер суждения об этом понятии и его невозможно строго доказать или опровергнуть. Перед точным определением вычислимой функции математики часто использовали неофициальный термин, «эффективно вычислимый» для описания функций, которые можно вычислить с помощью «бумажно-карандашных» методов.
Маши́на Тью́ринга (Шаблон:Сокр) — абстрактный исполнитель. Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Ква́нтовый компью́тер — вычислительное устройство, которое использует явления квантовой механики для передачи и обработки данных. Квантовый компьютер оперирует не битами, а кубитами, имеющими значения одновременно и 0, и 1. Теоретически это позволяет обрабатывать все возможные состояния одновременно, достигая существенного преимущества над обычными компьютерами в ряде алгоритмов.
Алонзо Чёрч — американский математик и логик, внесший значительный вклад в основы информатики.
Ква́нтовая запу́танность — квантовомеханическое явление, при котором квантовые состояния двух или большего числа объектов оказываются взаимозависимыми. Например, можно получить пару фотонов, находящихся в запутанном состоянии, и тогда если при измерении спина первой частицы её спиральность оказывается положительной, то спиральность второй всегда оказывается отрицательной, и наоборот.
Многомирова́я интерпрета́ция или интерпретация Эверетта — интерпретация квантовой механики, которая предполагает существование, в некотором смысле, «параллельных вселенных», в каждой из которых действуют одни и те же законы природы и которым свойственны одни и те же мировые постоянные, но которые находятся в различных состояниях. Исходная формулировка принадлежит Хью Эверетту.
Мультивселе́нная, или метавселенная, или гипервселенная , — гипотетическое множество всех возможных реально существующих параллельных вселенных. Представления о структуре Мультивселенной, природе каждой вселенной, входящей в её состав, и отношениях между этими вселенными зависят от выбранной гипотезы. Вселенные, входящие в Мультивселенную, называются альтернативными вселенными, альтернативными реальностями, параллельными вселенными или параллельными мирами.
Дэ́вид Элиезер Дойч — британский физик-теоретик израильского происхождения, работающий в Оксфордском университете; один из пионеров в области квантовых вычислений и пропагандист эвереттовской многомировой интерпретации квантовой механики. Член Лондонского королевского общества (2008).
«Вычислительные машины и разум» — основополагающая работа в области искусственного интеллекта, написанная английским учёным Аланом Тьюрингом и опубликованная в 1950 году в журнале «Mind», дающая широкой аудитории представление о том, что в настоящее время называется тестом Тьюринга.
Сверхтьюринговыми вычислениями называются такие вычисления, которые не могут быть проделаны на машине Тьюринга. Они включают в себя разнообразные гипотетические методы, основанные на суперрекурсивных алгоритмах, а также некоторые другие типы вычислений — например, интерактивные вычисления. Термин гипервычисления был впервые введён Джеком Коуплендом и Дианой Праудфут. Возможность физической реализации таких вычислений активно обсуждается.
Цифровая физика — совокупность теоретических взглядов, основанных на интерпретации, что Вселенная по сути является информацией и, следовательно, является вычислимой. Из данной идеи следует, что Вселенная может пониматься как результат работы некоторой компьютерной программы или как некий вид цифрового вычислительного устройства.
Квантовая машина Тьюринга — абстрактная машина, используемая для моделирования квантового компьютера; простая модель, которая, в то же время, может описать любые квантовые вычисления: любой квантовый алгоритм может быть формально описан как некоторая квантовая машина Тьюринга. Впервые построена в 1985 году Дэвидом Дойчем, обратившим внимание на аналогию между квантовыми вентилями и логическими вентилями в цифровых схемах.
За́мкнутая времениподо́бная ли́ния или за́мкнутая времениподо́бная крива́я в математической физике — времениподо́бная кривая на Лоренцевом многообразии, возвращающаяся в исходную пространственно-временную точку, то есть замкнутая мировая линия частицы в пространстве-времени. Существование таких линий в рамках общей теории относительности было впервые вынесено на широкое обсуждение Куртом Гёделем в 1949 году на основании полученного им точного решения уравнений Эйнштейна, известного как метрика Гёделя, хотя первое решение такого типа было получено ранее, в 1937 году Виллемом Ван Стокумом. Подобные кривые возникают и в других решениях, таких как «цилиндр Типлера» и «проходимая кротовая нора». Существование замкнутых времениподобных кривых позволяет путешествия во времени со всеми связанными с ними парадоксами.
Идея квантовых вычислений была независимо предложена Юрием Маниным и Ричардом Фейнманом в начале 1980-х. С тех пор была проделана колоссальная работа для построения работающего квантового компьютера.
Теоре́ма Чёрча — Тью́ринга — утверждение об отсутствии алгоритма, решающего проблему разрешения. Используется при доказательстве неразрешимости арифметики натуральных чисел. Впервые была сформулирована и доказана в 1936 году Алонзо Чёрчем ; в том же году, но несколько позже этот результат независимо получил Алан Тьюринг.
«Новый ум короля. О компьютерах, мышлении и законах физики» — научно-популярная книга британского физика Роджера Пенроуза, вышедшая в 1989 году.
Алгоритм Бернштейна — Вазирани — квантовый алгоритм, решающий задачу нахождения 
-битного числа, скрытого в черном ящике. Предложен Итаном Бернштейном и Умешем Вазирани в 1993 году. Данный алгоритм решает поставленную задачу значительно быстрее, чем это возможно в неквантовой постановке. Алгоритм может применяться в базах данных, атаках на блочные шифры, тестах производительности для квантовых компьютеров, был реализован на 5- и 16-кубитных квантовых компьютерах IBM.