Ква́нтовая (волнова́я) меха́ника — фундаментальная физическая теория, которая описывает природу в масштабе атомов и субатомных частиц. Она лежит в основании всей квантовой физики, включая квантовую химию, квантовую теорию поля, квантовую технологию и квантовую информатику.
Ква́нтовый компью́тер — вычислительное устройство, которое использует явления квантовой механики для передачи и обработки данных. Квантовый компьютер оперирует не битами, а кубитами, имеющими значения одновременно и 0, и 1. Теоретически это позволяет обрабатывать все возможные состояния одновременно, достигая существенного преимущества над обычными компьютерами в ряде алгоритмов.
Кле́точный автома́т — дискретная модель, изучаемая в математике, теории вычислимости, физике, теоретической биологии и микромеханике. Основой является пространство из прилегающих друг к другу клеток (ячеек), образующих решётку. Каждая клетка может находиться в одном из конечного множества состояний. Решётка может быть любой размерности, бесконечной или конечной, для решётки с конечными размерами часто предусматривается закольцованность при достижении предела (границы). Для каждой клетки определено множество клеток, называемых окрестностью. Например, окрестность фон Неймана ранга 2 включает все клетки на расстоянии не более 2 от текущей. Устанавливаются правила перехода клеток из одного состояния в другое. Обычно правила перехода одинаковы для всех клеток. Один шаг автомата подразумевает обход всех клеток и на основе данных о текущем состоянии клетки и её окрестности определение нового состояния клетки, которое будет у неё при следующем шаге. Перед стартом автомата оговаривается начальное состояние клеток, которое может устанавливаться целенаправленно или случайным образом.
Логи́ческий ве́нтиль — базовый элемент цифровой схемы, выполняющий элементарную логическую операцию, преобразуя таким образом множество входных логических сигналов в выходной логический сигнал. Логика работы вентиля основана на битовых операциях с входными цифровыми сигналами в качестве операндов. При создании цифровой схемы вентили соединяют между собой, при этом выход используемого вентиля должен быть подключён к одному или к нескольким входам других вентилей. В настоящее время в созданных человеком цифровых устройствах доминируют электронные логические вентили на базе полевых транзисторов, однако в прошлом для создания вентилей использовались и другие устройства, например, электромагнитные реле, гидравлические устройства, а также механические устройства. В поисках более совершенных логических вентилей исследуются квантовые устройства, биологические молекулы, фононные тепловые системы.
Квантовый вентиль — это базовый элемент квантового компьютера, преобразующий входные состояния кубитов на выходные по определённому закону. Отличается от обычных логических вентилей тем, что работает с кубитами. Квантовые вентили в отличие от многих классических всегда являются обратимыми.
Программируемая материя — это материя, которая может изменять свои физические свойства программируемым образом, посредством заданных пользователем или автономных восприятий. Программируемая материя, таким образом, связана с концепцией материала, который имеет внутренне присущую ему способность выполнять обработку информации. Состоит из молекулярных компьютеров.
Контролируемое отрицание — это обратимый логический вентиль, реализующий операцию, сходную с классическим XOR, частный случай класса вентилей C-U. Имеет 2 входа и 2 выхода. Первый вход — управляющий сигнал, второй вход — бит, который будет инвертирован в случае, если на управляющем входе подана единица. Классический логический вентиль NOT имеет 1 выход, но для сохранения обратимости в вентиле C-NOT требуется 2 выхода, на дополнительный выход подается неизменённый управляющий сигнал.
Вентиль Фредкина — универсальный трехвходовый логический вентиль класса C-U, достаточный для построения схем любой степени сложности. Обладает обратимостью — зная состояние выходов можно точно установить состояния входов элемента, таким образом на его базе можно строить обратимые вычисления и обратимые логические схемы. В частности, может использоваться как квантовый вентиль при реализации квантовых компьютеров. Назван в честь Эдварда Фредкина, предложившего этот вентиль.
Идея квантовых вычислений была независимо предложена Юрием Маниным и Ричардом Фейнманом в начале 1980-х. С тех пор была проделана колоссальная работа для построения работающего квантового компьютера.
Обратимые вычисления — модель вычислений, в которой процесс вычисления является в некоторой степени обратимым. Например, в вычислительной модели, использующей наборы состояний и переходов между ними, необходимым условием обратимости вычислений является возможность построения однозначного (инъективного) отображения каждого состояния в следующее за ним. На XX век и начало XXI века обратимые вычисления обычно относят к нетрадиционным моделям вычислений.
Обратимый клеточный автомат — клеточный автомат, в котором каждое состояние имеет единственного предшественника. Таким образом, это регулярная решётка из ячеек, состояние каждой из которых берётся из конечного множества состояний, и правило для одновременного обновления состояний ячеек, исходя из состояний её соседей. Условие обратимости заключается в том, что предыдущее состояние любой ячейки может быть определено, зная обновлённые состояния всех ячеек решётки. После обращения времени получается другой обратимый клеточный автомат, возможно — с намного большими окрестностями, но также с правилом для определения будущего состояния ячейки, исходя из текущих состояний ей соседей.
«Криттеры» — блочный клеточный автомат, проявляющий поведение, схожее с игрой «Жизнь» Конвея; в частности, полон по Тьюрингу. Впервые описан Томмазо Тоффоли и Норманом Марголусом в 1987 году, как и некоторые другие обратимые клеточные автоматы.
Бильярдный компьютер — логическая модель для проведения обратимых вычислений, механический компьютер, основанный на законах движения Ньютона и предложенный в 1982 году Эдвардом Фредкиным и Томмазо Тоффоли.
Гипотеза Аандераа — Карпа — Розенберга — это группа связанных гипотез о числе вопросов в форме «Имеется ли ребро между вершиной u и вершиной v?», на которые следует ответить, чтобы определить, обладает или нет неориентированный граф определённым свойством (инвариантом), таким как планарность или двудольность. Гипотеза названа именами норвежского математика Стола Аандераа и американских учёных Ричарда М. Карпа и Арнольда Л. Розенберга. Согласно гипотезе, для широкого класса инвариантов никакой алгоритм не может гарантировать, что алгоритм может опустить какой-либо запрос — любой алгоритм определения, обладает ли граф свойством, неважно, насколько умён этот алгоритм, он должен проверить каждую пару вершин, прежде чем дать ответ. Свойство, удовлетворяющее гипотезе, называется трудным.
Задача о гамильтоновом пути и задача о гамильтоновом цикле — это задачи определения, существует ли гамильтонов путь или гамильтонов цикл в заданном графе. Обе задачи NP-полны.
Ква́нтовое превосхо́дство — способность квантовых вычислительных устройств решать проблемы, которые классические компьютеры практически не могут решить. Квантовое преимущество — возможность решать проблемы быстрее. С точки зрения теории сложности вычислений под этим обычно подразумевается обеспечение суперполиномиального ускорения по сравнению с наиболее известным или возможным классическим алгоритмом. Термин был популяризирован Джоном Прескиллом, но концепция квантового вычислительного преимущества, особенно в моделировании квантовых систем, восходит к предложению квантовых вычислений, которое дали Юрий Манин (1980) и Ричард Фейнман (1981).
Анциллы — это дополнительные биты, используемые для достижения определённых целей при вычислениях. В классических вычислениях любой бит памяти может быть включен или выключен по желанию, не требуя для этого предварительного знания о состояниях или дополнительных ухищрений. Однако это не относится к квантовым вычислениям или классическим обратимым вычислениям. В этих моделях вычислений все операции с памятью компьютера должны быть обратимыми, а ведь включение или выключение бита приводит к потере информации о его начальном значении. По этой причине в квантовых алгоритмах невозможно детерминированно перевести биты в конкретное желаемое состояние, если только нет доступа к битам, исходное состояние которых известно заранее. Такие биты, значения которых известны априори, известны как биты анциллы в задачах квантового или обратимого вычисления.
Хеш-функции на основе клеточных автоматов — разновидность хеш-функций, использующая для вычисления клеточные автоматы. Использование клеточных автоматов обеспечивает высокий уровень параллелизма и, следовательно, позволяет достичь высоких скоростей, что необходимо в условиях ограниченных вычислительных мощностей и жестких требований к энергопотреблению. Хеш-функции на основе клеточных автоматов обладают хорошим лавинным эффектом. Использование клеточных автоматов позволяет добиться устойчивости к атакам временного анализа.
Квантовая схема — модель квантовых вычислений, аналогичная классическим схемам, в которых вычисление представляет собой последовательность квантовых вентилей, измерителей, инициализации кубитов известными значениями и, возможно, других действий. Минимальный набор действий, которые схема должна выполнять над кубитами, чтобы включить квантовые вычисления, известен как критерий Ди Винченцо.
Сверхпроводящие квантовые вычисления — раздел твердотельных квантовых вычислений, в котором сверхпроводящие электронные схемы реализуются с использованием сверхпроводящих кубитов в качестве искусственных атомов или квантовых точек. Для сверхпроводящих кубитов двумя логическими состояниями являются основное состояние и возбужденное состояние, обозначаемые 
соответственно. Исследования в области сверхпроводящих квантовых вычислений проводятся такими компаниями, как Google, IBM, IMEC, BBN Technologies, Rigetti и Intel. Многие недавно разработанные квантовые процессоры используют сверхпроводящую архитектуру.
