Сохраняя ранее введенные обозначения, предположим кроме того, что $N=2^{n} u$ что $F$ – биективное отображение (множество всех выходов – перестановка множества всех входов).
(i) Квантовое пространство входов и выходов – $2^{n}$-мерное комплексное гильбертово пространство $H_{n}$ с ортогональным базисом $|x\rangle$, $0 \leqslant x \leqslant N-1$. Вектора $|x\rangle$ называются классическими состояниями.
(ii) Квантовая версия $F$ – такой единственный унитарный опеpaтор $U_{F}: H_{n} \rightarrow H_{n}$, что $U_{F}|x\rangle=|F(x)\rangle$.

Квантовое параллельное вычисление $F$ – система (физическая реализация) с пространством состояний $H_{n}$ и оператором эволюции $U_{F}$.

Проще говоря, если мы применяем $U_{F}$ к начальному состоянию, которое является суперпозицией всех классических состояний с равными, например, амплитудами, то мы получаем одновременно все классические значения $F$ (т.е. их суперпозицию):
\[
U_{F}\left(\frac{1}{\sqrt{N}} \sum|x\rangle\right)=\frac{1}{\sqrt{N}} \sum|F(x)\rangle .
\]

Перед тем как перейти к более реалистической модификации этого определения, мы рассмотрим некоторые связанные с ним вопросы.
(А) Выше мы положили $N=2^{n}$, потому что мы представляем соответствующую классическую систему как $n$-битовый регистр (ср. обсуждение логических схем). Каждое число $0 \leqslant x \leqslant N-1$ записывается в двоичном виде как $x=\sum_{i} \epsilon_{i} 2^{i}$ и отождествляется с чистым (классическим) состоянием $\left|\epsilon_{n-1}, \ldots, \epsilon_{0}\right\rangle$, где $\epsilon_{i}=0$ или 1 – состояние $i$-го регистра. Квантовая система $H_{1}$ называется кубит. Мы имеем $H_{n}=H_{1}^{\otimes n},\left|\epsilon_{n-1}, \ldots, \epsilon_{0}\right\rangle=\left|\epsilon_{n-1}\right\rangle \otimes \ldots \otimes\left|\epsilon_{0}\right\rangle$.

Это согласуется с основными принципами квантовой механики. Гильбертово пространство объединения подсистем может быть отождествлено с тензорным произведением гильбертовых подпространств подсистем. Таким же образом раз.ожимые векторы соответствуют таким состояниям всей системы, при которых индивидуальные подсистемы находятся в определенных состояниях.
(В) Чистые квантовые состояния, строго говоря, – точки проективного пространства $P\left(H_{n}\right)$, то есть линии в $H_{n}$. Традиционно вместо них рассматриваются вектора единичной нормы. Это оставляет неопределенным общий фазовый множитель $\exp (i \varphi)$. Если у нас есть два вектора состояний, то индивидуальные фазовые множители не имеют объективного значения – значение имеет их частное, т. е. разность их фаз. Эта разность может быть измерена наблюдением эффектов интерференции. Эта возможность используется для создания эффективных квантовых алгоритмов.
(C) Если квантовая система $S$ изолирована, то ее динамическая эволюция описывается унитарным оператором $U(t)=\exp (i H t)$, где $H$ – гамильтониан, $t$ – время. Поэтому одна из возможностей выполнения $U_{F}$ – физически построить устройство, для которого $U_{F}$ был бы фиксированным оператором эволюции. Однако, это очевидным образом находится в противоречии со многими глубоко укоренившимися понятиями теории алгоритмов. Например, вычисление $F(x)$ для разных входов $x$ занимает разное время и было бы очень трудно уравнять их уже на стадии разработки.

Вместо этого можно попытаться выполнить $U_{F}$ как результат последовательности коротких взаимодействий системы $S$ с оборудованием, точно управляемых классическим компьютером (например, с использованием лазерных импульсов). Выражаясь математически, $U_{F}$ представляется как произведение некоторых стандартных унитарных операторов $U_{m} \ldots U_{1}$, каждый из которых действует только на небольшое подмножество (до трех) классических бит. Эти операторы называются квантовыми гейтами.

Сложность рассматриваемого квантового вычисления определена его длиной (числом гейтов $m$ ) и сложностью каждого из них. Последний пункт содержит тонкость: непрерывные параметры, например, фазовые сдвиги, от которых может зависеть $U_{i}$, делают объем информации каждого $U_{i}$ потенциально бесконечным и приводят к подозрению, что квантовый компьютер будет в действительности выполнять аналоговое вычисление, лишь реализованное иначе. Очень интересное обсуждение этого в [Ts] (лекция 9) убедительно отвергает эту точку зрения демонстрацией тех черт квантового вычисления, которые отличают его как от классической аналоговой, так и от классической цифровой обработки информации. Это обсуждение основано на технике вычислений, устойчивых к сбоям с использованием квантовых кодов для создания непрерывных переменных в высокой степени защищенных от внешнего шума.
(D) $\mathrm{C}$ классической точки зрения, требование о том, что $F$ должно быть перестановкой, выглядит очень жестким (например, в проблеме поиска $F$ принимает только два значения). Физическая причина этого требования то, что только такие $F$ продолжаются до унитарного оператора («квантовая обратимость»). Стандартный способ преодоления этого ограничения состоит во введении двух $n$-битовых регистров вместо одного для хранения как значения аргумента, так и значения функции. Более точно, если $F(|x\rangle)$ – произвольная функция, то мы можем заменить ее перестановкой $\widetilde{F}(|x, y\rangle):=|x, F(x) \oplus y\rangle$, где $\oplus$ – булева (побитовая) сумма. Это требует не более, чем полиномиального роста классической сложности, а ограничение $\widetilde{F}$ на $y=0$ порождает график функции $F$, который нам в любом случае нужен для того типа задач, которыми мы интересуемся.

Фактически для того, чтобы переработать классический алгоритм (последовательность булевых гейтов) для вычисления $F$ в квантовый, мы заменяем каждый классический гейт соответствующим обратимым квантовым гейтом, т. е. унитарным оператором, соответствующим ему в тензорной форме. Кроме двух регистров для хранения $|x\rangle$ и $F(|x\rangle)$ этот трюк также вводит дополнительные кубиты, в которых мы практически не заинтересованы. Соответствующее пространство и его содержимое иногда называется «свалка», «мусор» и т. п. Кроме обеспечения обратимости, добавочное пространство может быть введено также для работы с функциями $F:\{0, \ldots, N-1\} \rightarrow\{0, \ldots, M-1\}$, где $N, M$ – не степени двух (тогда мы увеличиваем их до ближайшей степени двух). Более детально этот вопрос рассмотрен в следующем разделе.

Заметим, что выбор последовательности гейтов (логической цепи) как классической модели вычисления существенен в следующем смысле: квантовая программа не может использовать условных команд. Действительно, для того, чтобы выполнить такую команду, нам надо наблюдать память в середине вычисления, но наблюдение в общем случае изменит текущее квантовое состояние.

По той же причине нам следует избегать команд копирования, поскольку классический оператор копирования $|x\rangle \rightarrow|x\rangle \otimes|x\rangle$ нелинеен. В частности, каждый выходной кубит квантового гейта может использоваться только в одном гейте на следующем шаге (если несколько гейтов используются параллельно): клонирование не разрешено.

Эти примеры показывают, что основы написания кода квантовой программы будут очень специфичны.
Теперь перейдем к проблемам, создаваемым программами вводавывода.

Ввод, или инициализация, в принципе, могут быть выполнены таким же способом, как и вычисление: мы задаем входное состояние, исходя, например, из классического состояния $|0\rangle$ и применяя последовательность основных унитарных операторов (см. следующий раздел). Вывод, однако, требует дополнительного квантовомеханического понятия наблюдения.
(E) Простейшая модель наблюдения квантовой системы с гильбертовым пространством $H$ требует выбора ортогонального базиса $H$. Только элементы этого базиса $\left|\chi_{i}\right\rangle$ могут появляться как результаты наблюдения. Если наша система находится в некотором состоянии $|\psi\rangle$ в момент наблюдения, она будет наблюдаться в состоянии $\left|\chi_{i}\right\rangle$ с вероятностью $\left|\left\langle\chi_{i} \mid \psi\right\rangle\right|^{2}$.

Это означает прежде всего то, что каждое квантовое вычисление существенно вероятностное. Наблюдение (части) квантовой памяти не то же самое, что «печать результата». Мы должны спланировать серию прогонов одной и той же квантовой программы и последующую классическую обработку наблюдаемых результатов, и мы можем только надеяться получить желаемый ответ с вероятностью близкой к единице.

Более того, это значит, что, выполняя квантовый параллелизм напрямую, как в (14), и затем наблюдая память так, как если бы она была классическим $n$-битовым регистром, мы просто получим некоторое значение $F(x)$ с вероятностью $1 / N$. Такое действие не использует потенциал квантового параллелизма. Поэтому мы сформулируем правильную версию этого понятия, оставляя больше гибкости и подчеркивая дополнительные задачи разработчика, каждая из которых может внести вклад в оценку сложности.