Квантовая теория – теория параллельных взаимодействующих миров. Есть обстоятельства, при которых вычисления, выполненные в разных мирах, могут быть скомбинированы с помощью $\mathcal{Q}$, давая возможность параллельной обработки. Рассмотрим квантовую программу
\[
N^{-\frac{1}{2}} \sum_{i=1}^{N}|\pi(f, 2,3), i, 0\rangle,
\]

которая предписывает во всех $N$ мирах вычислять $f(i)$ для $i$ от 1 до $N$. Из линейности и из (2.11) следует, что после выполнения (3.16) $\mathcal{Q}$ останавливается в состоянии
\[
N^{-\frac{1}{2}} \sum_{i=1}^{N}|\pi(f, 2,3), i, f(i)\rangle .
\]
Хотя это вычисление требует в точности того же времени, объема памяти и оборудования, что и (2.11), состояние (3.17) содержит результаты произвольно большого числа отдельных вычислений. $К$ сожалению, в каждом мире доступен не более, чем один из этих результатов. Если (3.16) выполняется много раз, среднее время, требуемое для того, чтобы вычислить все $N$ значений $f(i)$, которые я буду означать вместе как $f$ – по крайней мере не меньше того, какое требуется в $(2.11)$ для вычисления всех их последовательно. Теперь я покажу, что математическое ожидание времени вычисления любой нетривиальной $N$ кратно распараллеливаемой функции $G(\boldsymbol{f})$ от всех $N$ значений $f$ с помощью квантового параллелизма, такого, как (3.16), не может быть меньше, чем время, требуемое для вычисления его последовательно с помощью (2.11).

Для простоты предположим, что $\tau$, время выполнения (2.11), не зависит от $i$ и что время, необходимое для того, чтобы скомбинировать все $\boldsymbol{f}$ для формирования $G(\boldsymbol{f})$, пренебрежимо мало в сравнении с $\tau$. Теперь предположим, что существует программа $\zeta$, которая для каждой функции $f$ извлекает значение $G(f)$ из (3.17) в пренебрежимо малое время и с вероятностью $|\beta|^{2}$. То есть $\zeta$ действует так:
\[
N^{-\frac{1}{2}} \sum_{i=1}^{N}|i, f(i)\rangle \rightarrow \beta|0, G(f)\rangle+\left(1-|\beta|^{2}\right)^{\frac{1}{2}}|1\rangle|\lambda(f)\rangle,
\]

где состояния $|\lambda(\boldsymbol{f})\rangle$ не содержат информацию о $G(\boldsymbol{f})$. Тогда можно измерить содержимое первой ячейки. Если она содержит нуль, то вторая ячейка должна содержать $G(\boldsymbol{f})$. Иначе информация в (3.17) потеряна и ее придется перевычислять. Унитарность влечет равенство
\[
\frac{1}{N} \sum_{i=1}^{N} \delta(f(i), g(i))=|\beta|^{2} \delta(G(f), G(g))+\left(1-|\beta|^{2}\right)\langle\lambda(f) \mid \lambda(g)\rangle
\]

для любых функций $g(i)$ и $f(i)$.
Если $G(\boldsymbol{f})$ не является константой, когда для любой функции $f(i)$ существует другая функция $g(i)$ такая, что $G(g)
eq G(f)$, но $g(i)=f(i)$ для всех, кроме одного значения $i$ между 1 и $N$. Для этого выбора
\[
1-N^{-1}=\left(1-|\beta|^{2}\right)\langle\lambda(f) \mid \lambda(g)\rangle,
\]
что влечет $|\beta|^{2}<N^{-1}$. Таким образом, среднее время для вычисления $G(f)$ должно быть по крайней мере $\tau /|\beta|^{2}=N_{\tau}$. Отсюда следует, что квантовый параллелизм не может использоваться для сокращения среднего времени распараллеливаемых алгоритмов.
В качестве примера квантового параллелизма для $N=2$ положим
\[
G(\boldsymbol{f}) \equiv f(0) \oplus f(1) .
\]
(см. уравнение (2.12)). Тогда состояние (3.17), следующее квантовому параллельному вычислению, имеет вид
\[
2^{-\frac{1}{2}}(|0, f(0)\rangle+|1, f(1)\rangle) .
\]

Программа $\zeta$, пригодная для «декодирования» этого состояния, производит измерение любой невырожденной наблюдаемой с собственными состояниями
\[
\left.\begin{array}{rl}
\mid \text { zero }\rangle & \equiv \frac{1}{2}(|0,0\rangle-|0,1\rangle+|1,0\rangle-|1,1\rangle), \\
\mid \text { one }\rangle & \equiv \frac{1}{2}(|0,0\rangle-|0,1\rangle-|1,0\rangle+|1,1\rangle), \\
\mid \text { fail }\rangle & \equiv \frac{1}{2}(|0,0\rangle+|0,1\rangle+|1,0\rangle+|1,1\rangle), \\
\mid \text { error }\rangle & \equiv \frac{1}{2}(|0,0\rangle+|0,1\rangle-|1,0\rangle-|1,1\rangle) .
\end{array}\right\}
\]

Такая наблюдаемая существует, поскольку состояния (3.23) образуют ортонормированное множество. Более того, измерения могут быть сделаны за фиксированное время, не зависящее от времени выполнения алгоритма, вычисляющего $f$. Если результат измерения – «zero» (т.е. собственное значение, соответствующее состоянию |zero ) ) или «оnе», то можно заключить, что $f(0) \oplus f(1)$ равно нулю или единице соответственно. Какова бы ни была функция $f$, с вероятностью $\frac{1}{2}$ выход будет «fail», в случае которого о значении $f(0) \oplus f(1)$ нельзя сделать никакого вывода. Вероятность выхода «error» при попытке вычисления может быть сделана сколь угодно малой, вне зависимости от природы $f$.

В этом примере достигается граница $N \tau$ для времени вычисления. Однако, для $N>2$ я не могу построить примеров, в которых среднее
время работы меньше чем $\left(N^{2}-2 N+2\right) \tau$, и я предполагаю, что это оптимальная нижняя оценка. Кроме того, хотя и существуют нетривиальные примеры квантово распараллеливаемых алгоритмов для всех $N$, в тех случаях когда $N>0$, ни для одного из них область определения функции $G(\boldsymbol{f})$ не является множеством всех $2^{N}$ возможных графиков функции $f$.

В практических вычислительных задачах, особенно в приложениях реального времени, не всегда нужно минимизировать именно среднее время выполнения программы: часто требуется минимизировать минимальное или максимальное время или какую-либо более сложную меру. В таких случаях квантовый параллелизм может вступить в свои права. Я приведу два примера этого.
(1) Предположим, что (3.17) – программа оценки завтрашних изменений на фондовой бирже по сегодняшнему ее состоянию, а $G(\boldsymbol{f})$ определяет наилучшую стратегию инвестиций. Если $\tau$ – один день, $N=2$, то классическая версия этой программы работает два дня и поэтому бесполезна. Если квантовая версия исполняется каждый день, то в среднем в один день из двух ячеек одна содержит результат измерения «1», соответствующее fail (неудаче). В такие дни инвестиций делать не следует. Но с той же средней частотой будет появляться нуль, показывая, что ячейка два содержит корректное значение стратегии инвестиций $G(\boldsymbol{f})$. Функция $G(\boldsymbol{f})$, которая соединяет результаты двух классических «процессоро-дней» вычисления, в этих случаях вычислялась бы одним процессором за один день. Один из физических путей описания этого эффекта состоит в том, что когда подзадачи $N$-кратной параллельной задачи распределяются между $N^{2}-2 N+2$ мирами, по крайней мере в одном из них может быть получен окончательный результат.
(2) Теперь рассмотрим проблему разработки параллельных систем обработки информации, подверженных воздействию шума. Например, предположим, что требуется в пределах фиксированного времени $\tau$ вычислить некоторую $N$-кратно распараллеливаемую функцию $G(\boldsymbol{f})$. Доступно $N R$ процессоров, каждый из которых может давать сбой по причине теплового шума и т.п. с вероятностью $p$. Для простоты предположим, что такая ошибка оборудования может быть надежно обнаружена. Задача состоит в том, чтобы минимизировать общую частоту сбоев $q$. «Классически» (т.е. без использования квантового параллелизма) можно минимизировать $q$ посредством $R$-кратной избыточности: $R$ процессоров программируются для выполнения каждой из $N$ параллельных подзадач. Машина в целом при этом будет давать сбой только если терпят неудачу все $R$ процессоров, выполняющие какую-нибудь подзадачу. Это происходит с вероятностью
\[
q_{\text {classical }}=1-\left(1-p^{R}\right)^{N} .
\]

Однако при использовании квантового параллелизма каждому из $N R$ процессоров можно дать все $N$ задач. Каждый из них может сбиться по двум независимым причинам: $(i)$ с вероятностью $p$ произойдет аппаратный сбой, (ii) с вероятностью, которую я определил для определенных $G(\boldsymbol{f})$ как $1-\left(N^{2}-2 N+2\right)^{-1}$, процесс закончится в том мире, в котором не получается ответ. Требуется, чтобы добился успеха лишь один из $N R$ процессоров, поэтому частота отказов имеет значение
\[
q_{\text {quantum }}=\left[1-\left(N^{2}-2 N+2\right)^{-1}(1-p)\right]^{N R},
\]

которое для подходящих значений $p, N$ и $R$ может быть меньше, чем (3.24).