В этом разделе мы даем краткое введение в проблему квантовых вычислений, акцентируя внимание на свойствах, которые мы в дальнейшем используем. Мы опишем только массивы квантовых гейтов, или квантовые ациклические схемы, которые являются аналогом ациклических схем в теории классических компьютеров. Другие модели квантового компьютера рассмотрены в следующих работах: квантовые машины Тьюринга в [Deutsch, 1989, Bernstein and Vazirani, 1993, Yao, 1993], квантовые клеточные автоматы в [Feynman, 1986, Margolus, 1986, 1990, Lloyd, 1993, Biafore, 1994]. Если они допускают малую вероятность ошибки, то квантовые машины Тьюринга и массивы квантовых гейтов могут вычислить одну и ту же функцию за полиномиальное время [Yaо, 1993]. Возможно то же самое будет справедливо и для различных моделей квантовых клеточных автоматов, но это пока не доказано. Это вселяет уверенность в том, что принадлежность к классу функций, вычислимых квантовым способом за полиномиальное время с малой вероятностью ошибки, не зависит от конкретной структуры квантового компьютера. По аналогии с классическим классом проблем BPP назовем этот класс BQP.

Рассмотрим систему из $n$ объектов, каждый из которых может находиться в двух состояниях. В отличие от классической физики, в которой для полного описания состояния этой системы потребовалось бы $n$ битов, в квантовом случае для полного описания состояния системы необходимо $2^{n}-1$ комплексных чисел. Если быть более точным, состоянием такой квантовой системы является точка в $2^{n}$-мерном векторном пространстве. Каждому из $2^{n}$ возможных классических состояний объектов сопоставим базисный вектор этого векторного пространства и обозначим его, например, следующим образом – $|011 \ldots 0\rangle$,
предполагая, что первый бит содержит 0 , второй содержит 1 , и так далее. Здесь под обозначением кет-вектора $|x\rangle$ понимается, что $x$ есть (чистое) квантовое состояние. (Смешанные состояния в данной статье не обсуждаются, поэтому мы их и не определяем; для этого смотрите литературу по квантовой теории, например Peres [1993].) Гильбертово пространство, ассоциируемое с нашей квантовой системой, является комплексным векторным пространством с базисом из $2^{n}$ векторов, и состояние нашей системы в любой момент времени представлено вектором единичной длины этого гильбертова пространства. Поскольку умножение этого вектора-состояния на фазовый множитель единичной длины не изменяет состояние системы, нам достаточно только $2^{n}-1$ комплексных чисел для полного описания этого состояния. Мы представим эту суперпозицию состояний как
\[
\sum_{i=0}^{2^{n}-1} a_{i}\left|S_{i}\right\rangle,
\]

где амплитуды $a_{i}$ являются комплексными числами, причем $\sum_{i}\left|a_{i}\right|^{2}=1$, а $\left|S_{i}\right\rangle$ – базисные векторы этого гильбертова пространства. Если измерить состояние машины (по отношению к данному базису) на любом конкретном шаге вычислений, то вероятность обнаружить систему в базисном состоянии $\left|S_{i}\right\rangle$ будет $\left|a_{i}\right|^{2}$; однако измерение состояния машины спроектирует ее в наблюдаемый базисный вектор $\left|S_{i}\right\rangle$. Поэтому наблюдать состояние машины можно только в конце вычислений. Общие квантомеханические измерения могут оказаться значительно более сложными,чем в случае проекции их на канонический базис. Мы ограничимся рассмотрением этого случая. Это не очень сильно ограничит нашу модель вычислений, так как измерения в других разумных базисах, как и другие локальные измерения, могут быть смоделированы при помощи квантового вычисления для изменения базиса и последующем преобразовании к каноническому базису.

Для того, чтобы использовать физическую систему для вычислительных целей, необходимо иметь возможность изменять состояние этой системы. Законы квантовой механики разрешают только унитарные преобразования над векторами состояния. Унитарными матрицами называются такие, у которых комплексно сопряженная транспонированная матрица совпадает с обратной. Требование того, чтобы преобразования векторов состояния соответствовали унитарным матрицам, гарантирует, что сумма вероятностей всех возможных исходов даст единицу. Определение квантовых схем (и квантовой машины Тьюринга) разрешает только локальные унитарные преобразования; другими словами, унитарные преобразования только над фиксированным числом битов. Физически это вполне объяснимо. Абсолютно не ясно, как физически реализовать унитарное преобразование над $n$ битами, тогда как двубитные преобразования теоретически могут быть реализованы на относительно простых системах [Cirac and Zoller, 1995, DiVincenzo, 1996, Sleator and Weinfurter, 1995, Chuang and Yamomoto, 1995]. Тогда как общие $n$-битные преобразования всегда могут быть построены из двубитных [DiVincenzo, 1995, Sleator и Weinfurter, 1995, Lloyd, 1995, Deutsch et al., 1995], необходимое число таких преобразований зачастую будет экспоненциально по $n$ [Barenco et al., 1995a]. Таким образом, системы двубитных преобразований формируют конструктивные блоки квантовых схем аналогично тому, как универсальные системы классических гейтов (таких как AND, OR и NOT гейты) формируют конструктивные блоки классических схем. В действительности, в качестве универсальной системы квантовых гейтов достаточно иметь только однобитные гейты и очень простую разновидность двубитного гейта, контролируемого NOT (также называемого XOR гейтом), который изменяет значение второго бита тогда и только тогда, когда значение первого равно единице.

Возможно, полезным окажется следующий пример. Квантовый гейт может быть задан таблицей истинности: для каждого базисного вектора на входе нам надо задать конечное значение. Например, один такой гейт
\[
\begin{array}{l}
|00\rangle \rightarrow|00\rangle \\
|01\rangle \rightarrow|01\rangle \\
|10\rangle \rightarrow \frac{1}{\sqrt{2}}(|10\rangle+|11\rangle) \\
|11\rangle \rightarrow \frac{1}{\sqrt{2}}(|10\rangle-|11\rangle) .
\end{array}
\]
Не для любой таблицы истинности можно подобрать физически осуществимый квантовый гейт, многие таблицы истинности вообще не соответствуют унитарным преобразованиям.

Вышеприведенный гейт может быть представлен также и в виде матрицы. Ряды соответствуют базисным векторам на входе. Столбцы соответствуют базисным векторам на выходе. Индексы $(i, j)$ соответствуют $i$-му базисному вектору на входе и $j$-му базисному вектору на выходе гейта. Указанная выше таблица истинности соответствует следующей матрице:

Квантовый гейт осуществим, если и только если соответствующая матрица унитарна, другими словами, если обратная есть сопряженная и транспонированная.

Предположим, что наша машина находится в суперпозиции состояний
\[
\frac{1}{\sqrt{2}}|10\rangle-\frac{1}{\sqrt{2}}|11\rangle
\]

и мы применим унитарное преобразование, соответствующее (2.2) и (2.3). Окончательные выходные данные будут результатом умножения матрицы (2.3) на вектор (2.4). Таким образом, машина перейдет в суперпозицию состояний
\[
\frac{1}{2}(|10\rangle+|11\rangle)-\frac{1}{2}(|10\rangle-|11\rangle)=|11\rangle .
\]

Этим примером показана потенциальная эффективность интерференции в квантовых вычислениях. Если бы мы начали вычисления с состояния $|10\rangle$, либо с состояния $|11\rangle$, то существовует вероятность обнаружения состояния $|10\rangle$ после действия гейта (2.3). Однако, когда мы начинаем вычисления с суперпозиции этих двух состояний, амплитуда вероятности наблюдения $|10\rangle$ пропадает, другими словами, у нас нет вероятности обнаружить это состояние после действия гейта. Заметим, что если бы мы начинали вычисления с суперпозиции состояний
\[
\frac{1}{\sqrt{2}}|10\rangle+\frac{1}{\sqrt{2}}|11\rangle,
\]

в конце мы имели бы вместо состояния $|11\rangle$ состояние $|10\rangle$, хотя начальное состояние (2.6) задает те же вероятности появления любой частной конфигурации, что и суперпозиция (2.4).

Если мы применяем гейт только к двум битам большого вектора (теперь наша цепь должна состоять более чем из двух проводов), то для каждого базисного вектора мы используем преобразование, меняющее состояние этих двух битов согласно таблице истинности, и не затрагивающее остальных битов. Это соответствует умножению полного вектора состояния на тензорное произведение матрицы гейта, действующего на эти два бита, и единичных матриц для оставшихся битов. Например, применение преобразования, представленного в (2.2) и (2.3) к первым двум битам базисного вектора $|110\rangle$ дает вектор $\frac{1}{\sqrt{2}}(|100\rangle-|110\rangle)$.

Массив квантовых гейтов представляет собой систему квантовых гейтов и логических «проводов», соединяющих их входы и выходы. Входные данные для массива гейтов, возможно вместе с дополнительными рабочими гейтами, которые первоначально полагаются 0 , прогоняются через последовательность квантовых гейтов. Значения битов определяются после действия последнего гейта, и полученные значения будут выходными данными. Эта модель аналогична классической ациклической схеме в теории вычислений. Она была изучена Үао [1993]. Сравнивая массивы гейтов с квантовой машиной Тьюринга, нам надо ввести условия, которые выделяют массивы гейтов в универсальные классы сложности. Другими словами, так как массивы гейтов для разных размеров начальных данных различны, необходимо предотвратить устройство создающее массивы гейтов от укрывания невычислимой (или сложно вычислимой) информации по упорядочиванию гейтов. Для того, чтобы сделать массивы квантовых гейтов универсальными, к определению массива гейтов нам необходимо добавить два требования. Первое является стандартным условием того, чтобы создание массива квантовых гейтов требовало полиномиального числа (классических) шагов. Вторым может стать стандартная часть определения аналоговых классов сложности, хотя в силу того, что аналоговые классы сложности не так хорошо изучены, это требование не так широко известно. Это требование заключается в том, чтобы на вход гейтов, описываемых унитарными матрицами, подавались вычисляемые числа. В особенности, первые $\log n$ битов должны быть классически вычисляемы за полиномиальное по $n$ время [Solovay, 1995]. Это предохраняет невычислимую (или трудно вычислимую) информацию от потери ее битов, описываемых амплитудами квантовых гейтов.