Айзек Л. Чуанг
(Isaac L. Chuang) ${ }^{1}$
Ливен М.К.Вандерсипен, Ксинлан Жу
(Lieven M. K. Vandersypen, Xinlan Zhou) ${ }^{2}$
Дебби В. Леюнг
(Debbie W.Leung) ${ }^{3}$
Сет Ллойд
(Seth Lloyd) ${ }^{4}$
Квантовый компьютер — это устройство, обрабатывающее информацию квантово-механическим когерентным способом $[1-5]$. В принципе, можно использовать когерентную квантовую интерференцию, чтобы осуществлять такие вычисления, как разложение больших чисел на множители или поиск в несортированной базе данных, более быстро, нежели классические компьютеры $[1,2,6-8]$. Шумы, некогерентность и технические трудности делают сложным построение крупномасштабных квантовых компьютеров [9-13]. Ионные ловушки и оптическое резонаторы являются многообещающими с точки зрения экспериментальных подходов $[14,15]$, но еще ни один квантовый алгоритм не был реализован на таких системах.

С другой стороны, из-за естественной изоляции от окружающей среды, ядерные спины являются особенно хорошими «квантовыми битами» [16], и их использование для квантовых вычислений возможно посредством ядерного магнитного резонанса (ЯMP) [17-19]. В настоящей статье мы описываем экспериментальную реализацию квантового алгоритма с использованием ЯМР для решения чисто математической задачи за меньшее количество шагов, чем это возможно классически.
${ }^{1}$ IBM Almaden Research Center K10/D1, San Jose, CA 95120.
${ }^{2}$ Solid State Electronics Laboratory, Stanford University, Stanford, CA 94305.
${ }^{3}$ Edward L. Ginzton Laboratory, Stanford, CA 94305.
${ }^{4}$ MIT Dept. of Mechanical Engineering, Cambridge, Mass. 02139.
(C) Nature, №393, pp. 143-146 (1998).
Перевод А. И. Дубиковского.
В частности, наш простой квантовый компьютер может определить общие свойства неизвестной функции, используя меньшее количество вызовов функции, нежели при использовании классического компьютера.

Мы осуществили самую простую возможную версию квантового алгоритма Дойча-Джозса (Deutsch-Jozsa, D-J) [6], который определяет, является ли неизвестная функция постоянной или сбалансированной. Постоянная функция $f(x)$ от $N$ битов до одного либо $f(x)=0$ для всех $x$, либо $f(x)=1$ для всех $x$. Сбалансированная функция $f(x)=0$ для точно половины ее аргументов, и $f(x)=1$ для оставшихся. Чтобы с уверенностью определить, является ли функция постоянной или сбалансированной, на детерминированном классическом компьютере требуется до $2^{N-1}+1$ вызовов функции: даже если взять половину аргументов и найти $f(x)=0$ для каждого, все еще нельзя с уверенностью заключить, что функция постоянна. Напротив, D-J алгоритм, усовершенствованный Р. Кливом и др. [20] и Аланом Таппом, позволяет квантовому компьютеру определнть, нвлнется ли $f(x)$ постоннной или сбалансированной, используя только один вызов функции.

D-J алгоритм хорошо иллюстрируется его самым простым возможным случаем, когда $f$ преобразует один бит в другой; это тот случай, который мы реализовали (это также самый простой случай алгоритма Саймона [7]). Имеется четыре возможных значения $f$, два из которых постоянны, $f_{1}(x)=0, f_{2}(x)=1$ а оставшиеся два имеют равное число 0 и 1 значений: $f_{3}(x)=x, f_{4}(x)=\mathrm{NOT} x$. Выяснение, является ли такая функция постоянной или сбалансированной, аналогично задаче, является ли монета настоящей — с орлом на одной стороне и решкой на другой, или фальшивой — с орлом на двух сторонах. В классическом случае нужно смотреть на монету дважды: сначала на одну сторону, затем на другую, чтобы определить — настоящая это монета или фальшивая. $\mathrm{D}-\mathrm{J}$ алгоритм использует квантовую когерентность, чтобы определить, является ли квантовая «монета» настоящей или фальшивой, посмотрев на нее только один раз. Алгоритм требует одного «входящего» спина и одного «рабочего» спина, и схематично представлен на рис. 1.

Экспериментально этот квантовый алгоритм был осуществлен с использованием ядерных спинов атомов ${ }^{1} \mathrm{H}$ и ${ }^{13} \mathrm{C}$ в помеченных углеродом-13 молекулах хлороформа $\left(\mathrm{CHCl}_{3}\right.$ ) как входящий и рабочий квантовый бит («кубит»). $|0\rangle$ ( $|1\rangle$ ) описывает состояние спина, направленного по (против) внешнему сильному статическому магнитному полю $\mathbf{B}_{0}$ в $+\widehat{z}$ направлении. Упрощенный гамильтониан для такой А. Л. Чуанг, Л. М. К. Вандерсипен, К. Жу, Д. В. Леюнг, С. Ллойд
2 -спиновой системы в хорошем приближении ( $\hbar=1$ ) равен [21]
\[
\widehat{\mathscr{H}}=-\omega_{A} \widehat{I}_{z A}-\omega_{B} \widehat{I}_{z B}+2 \pi J \widehat{I}_{z A} \widehat{I}_{z B}+\widehat{\mathscr{H}}_{e n v} .
\]

Первые два члена описывают свободную прецессию спина $A\left({ }^{1} \mathrm{H}\right)$ и $B\left({ }^{13} \mathrm{C}\right)$ относительно $-\mathbf{B}_{0}$ с частотами $\omega_{A} / 2 \pi \approx 500$ МГц и $\omega_{B} / 2 \pi \approx$ $\approx 125$ МГц. $\widehat{I}_{z A}$ — оператор углового момента в $+\widehat{z}$ направлении для $A$. Третий член описывает скалярное спин-спиновое взаимодействие $J \approx$ $\approx 215$ Гц. $\widehat{\mathscr{H}}_{\text {env }}$ описывает взаимодействие с окружающей средой, включая взаимодействие с ядрами хлора, и также члены более высокого порядка в спин-спиновом взаимодействии, и этим членом, как будет описано ниже, можно пренебречь.

Рис. 1. Квантовая схема реализации D-J алгоритма. (T0) Начинаем с обоих «входящего» и «рабочего» кубитов (А и В) в состоянии $|0\rangle$. (T1) Выполняем преобразование $Y:|0\rangle \rightarrow(|0\rangle+|1\rangle) / 2^{1 / 2},|1\rangle \rightarrow(-|0\rangle+|1\rangle) / 2^{1 / 2}$, $|0\rangle \rightarrow(|0\rangle+|1\rangle) / \sqrt{2},|1\rangle \rightarrow(-|0\rangle+|1\rangle) / \sqrt{2}$, к А, и обратное преобразование $\bar{Y}$ к В, в итоге получаем состояние $\frac{1}{2} \sum_{x=0}^{1}|x\rangle(|0\rangle-|1\rangle)$. Входящий кубит в некотором квантовом смысле регистрирует и 0 и 1 одновременно. (T2) Вызываем функцию: применяем $f$ к А, и прибавляем результат к В по модулю 2. До тех пор, пока квантовые логические операции, необходимые для вычисления $f$, выполняются когерентно, рабочий кубит в некотором квантовом смысле теперь содержит значения $f$ при всех возможных аргументах; это результат, названный Дойчем «квантовым параллелизмом» [1]. Два кубита находятся теперь в состоянии $\frac{1}{2} \sum_{x=0}^{1}|x\rangle(|0+f(x)\rangle-|1+f(x)\rangle)=$ $=\frac{1}{2} \sum_{x=0}^{1}(-1)^{f(x)}|x\rangle(|0\rangle-|1\rangle)$. (Т3) Выполняем инверсию преобразования (T1), вследствие чего получаем кубиты в суперпозиции состояний. Если $f$ постоянна, то множители $(-1)^{f(x)}$ есть либо все +1 , либо все -1 , и результат преобразования в этом шаге — состояние $\pm|00\rangle$. Если $f$ является сбалансированной, то ровно половина множителей $(-1)^{f(x)}$ есть +1 , и половина -1 , и результат преобразования — состояние $\pm|10\rangle$. (Т1) Читаем А. Если это 0 , то $f$ постоянная; если 1 , то $f$ сбалансированная.
Пять теоретических шагов квантового алгоритма, (T0)-(Т4), были экспериментально осуществлены следующим образом:
(E0) Начальное состояние подготавливалось в 200 мМ, 0.5 мл хлороформа, растворенного в d6-ацетоне при комнатной температуре и стандартном давлении. $\mathcal{O}\left(10^{18}\right)$ молекул в этом растворе, как можно думать, были независимыми простыми квантовыми компьютерами, работающими одновременно.

Теоретически, идеальный результат получается, когда спины во всех молекулах приготовлены в 00 состоянии. Поскольку эксперимент выполнялся при комнатной температуре, начальная матрица плотности $\rho$ для системы в тепловом равновесии имеет заселенности $\operatorname{diag}(\rho)=$ $=\left[n_{00}, n_{01}, n_{10}, n_{11}\right]$ в $00,01,10$ и 11 состояниях соответственно, где $\rho-$ матрица плотности, $n_{i}$ пропорционально $e^{-E_{i} / k T} / 2^{N} \approx\left(1-E_{i} / k T\right) / 2^{N}$ с энергией $E_{i}$ состояния $i$, а $N=2$ является числом кубитов, используемых в нашем эксперименте. Существует несколько методов для извлечения из такого состояния теплового равновесия только сигнала от 00 состояния $[17,18]$; мы использовали метод «временного усреднения» $[22]$, который использует суммирование трех экспериментов, в которых заселенность из 01,10 и 11 состояний циклически переставляется перед выполнением вычислений. Существенное наблюдение суть $\left[n_{00}, n_{01}, n_{10}, n_{11}\right]+\left[n_{00}, n_{11}, n_{01}, n_{10}\right]+\left[n_{00}, n_{10}, n_{11}, n_{01}\right]=$ $=\alpha[1,1,1,1]+\delta[1,0,0,0]$, где $\alpha=n_{01}+n_{10}+n_{11}$ — фоновый сигнал, который не детектируется, а $\delta=3 n_{00}-\alpha$ — отклонение от однородного фона, чей сигнал эффективно ведет себя подобно желаемому чистому квантовому состоянию $|00\rangle$. Перестановки выполнены с использованием метода, используемого для вычислений, описанных ниже. Этот метод избегает технических трудностей обнаружения сигнала от единственного ядерного спина и позволяет системе, дающей легко обнаружимый сигнал, используемый для квантового вычисления, оставаться при комнатной температуре.

Заметим, что в то время как этот метод требует вычисления $f(x)$ 3 раза, фактически это не является необходимым. Хотя шаг (T0) обусловлен исходным чистым состоянием $|00\rangle$, алгоритм работает также хорошо, если начальный входящий кубит $|1\rangle$; однако, когда рабочий кубит первоначально $|1\rangle$, это не очень хорошо, поскольку невозможно отличить константу от сбалансированной функции, но это не влияет на другие работающие компьютеры. Таким образом, тепловое состояние — хорошее начальное состояние для этого алгоритма, и нам необходимо выполнить только один экеперимент. Результаты с использованием теплового и чистого начальных состояний описаны ниже.
(E1) Импульсные радиочастотные электромагнитные поля (РЧ) используются для того, чтобы преобразовать кубиты, как это требуется в (T1). Эти поля, ориентированные в $\widehat{x}-\widehat{y}$ плоскости перпендикулярно $\mathbf{B}_{0}$, выборочно адресуются или $A$, или $B$, осциллируя с частотой $\omega_{A}$ или $\omega_{B}$. Классически, РЧ импульс, направленный, к примеру, по $\widehat{y}$, вращает спин относительно этой оси на угол, пропорциональный $\approx t P$, т. е. произведению длительности $t$ и мощности $P$ импульса. В примитивной картине простых магнитов $\pi / 2$ импульс вдоль $\widehat{y}$ (мы будем называть его $Y$ ) поворачивает $\widehat{z}$ ориентированный спин на $90^{\circ}$, к $\widehat{x}$ (аналогично, пусть $\bar{Y}$ вращает спин на $\pi / 2$ относительно $-\widehat{y}$, и $X$ — на $\pi / 2$ относительно $\widehat{x}$, и т. д; нижние индексы будут, описывать над какими спинами эта операция производится). Это описание состояния является классическим в том смысле, что обыкновенный магнит всегда имеет определенное направление. Однако, в реальности спин ядра — квантовый объект, и вместо поворота в направлении $\widehat{x}$ он, фактически, является суперпозицией состояний вверх и вниз, $(|0\rangle+|1\rangle) / \sqrt{2}$. Аналогично, спин, классически описываемый как находящийся по направлению $-\widehat{x}$, фактически находится в состоянии $(|0\rangle-|1\rangle) / \sqrt{2}$. (E1) таким образом состоит из двух импульсов РЧ $Y_{A} \bar{Y}_{B}$.
(E2) Функция $y \rightarrow y \oplus f(x)$ осуществляется посредством использования РЧ-импульсов и спин-спинового взаимодействия. Напомним, что спин $A$ представляет входящий кубит $x$, и $B$ — рабочий кубит $y$, а $f$ хранит свое значение. $f_{1}$ реализована как $\tau / 2-X_{B} X_{B}-\tau / 2-X_{B} X_{B}$ (читается слева направо), где $\tau / 2$ представляет временной интервал $1 / 4 J \approx 1.163$ мс, в течение которого происходит взаимодействие связанных спинов. Типичные длины импульсов были $10-15$ мкс. Это известная рефокусировка [23] импульсных последовательностей, которая реализует нужное действие. $f_{2}$ реализована как $\tau / 2-X_{B} X_{B}-\tau / 2$, подобно $f_{1}$, но без последних импульсов, так что $B$ инвертирован. $f_{3}$ есть $Y_{B}-\tau-\bar{Y}_{B} X_{B}-\bar{Y}_{A} \bar{X}_{A} Y_{A}$, что осуществляет «контролируемое HE» действие, в котором $B$ инвертирован тогда и только тогда, когда $A$ находится в $|1\rangle$ состоянии. Для понимания можно использовать примитивную картину классических магнитов для случая начальных состояний 00 или 10 и последовательности импульсов $Y_{B}-\tau-X_{B}$ (заметим, что после (E1) оба спина не просто $|0\rangle$ или $|1\rangle$, но находятся в суперпозиции обоих состояний, и в этом случае необходимы дополнительные импульсы $f_{3}[17]$ ). Сперва $Y_{B}$ поворачивает $B$ по $+\widehat{x}$. Затем $B$ прецессирует в $\widehat{x}-\widehat{y}$ плоскости относительно — $\widehat{z}$. Из-за спин-спинового взаимодействия $B$ прецессирует чуть медленнее (быстрее), если $A=0$ $(A=1)$. После $\tau$ секунд $B$ достигает $+\widehat{y}(-\widehat{y})$ во вращающейся системе координат. $X_{B}$ затем поворачивает $B$ к $+\widehat{z}(-\widehat{z})$, то есть к 0 или 1 , где конечное состояние $B$ зависит от начального $A$. Точное квантовое описание легко получается посредством перемножения унитарных матриц вращения. Наконец, $f_{4}$ осуществляется как $Y_{B}-\tau-\bar{Y}_{B} \bar{X}_{B}-\bar{Y}_{A} \bar{X}_{A} Y_{A}$, что похоже на $f_{3}$, но с инвертированным $B$.
(E3) Инверсия (E1) осуществляется посредством РЧ-импульсов $\bar{Y}_{A} Y_{B}$ для возвращения спинов к $\pm \widehat{z}$. Спин $A$, который был сначала $|0\rangle$, тем самым преобразуется в $|0\rangle$ или $|1\rangle$ соответственно для постоянной или сбалансированной функции.
(E4) Результат считывается посредством импульса $X_{A}$, возвращая спин $A$ обратно в $\widehat{x}-\widehat{y}$ плоскость. Время изменения напряжения $V(t)$, вызванное прецессией спина $A$ вокруг $-\mathbf{B}_{0}$, регистрируется фазочувствительной катушкой. Исследование спектра $V(t)$, после проведения одного эксперимента и соответствующего считывающего импульса немедленно показывает, является ли $f(x)$ постоянной или сбалансированной, как показано на рис. 2.

Мы также нашли всю матрицу плотности отклонений $\rho_{\Delta} \equiv \rho-$ $-\operatorname{Tr}(\rho) I / 4$ (рис. 3 ), описывая конечное 2-кубитное состояние. Эти результаты однозначно доказывают полное правильное функционирование квантового алгоритма и дают анализ погрешностей, описываемый ниже.

Квантовое вычисление требует, чтобы когерентная суперпозиция сохранялась на продолжении всего вычисления. Для этого требуется хорошо изолированная квантовая система (с малым $\widehat{\mathscr{H}}_{\text {env }}$ ), и, к счастью, ядерные спины являются естественно хорошо изолированными от окружающей среды. Непостоянство фазы из-за неоднородности $\mathbf{B}_{0}$ было минимизировано посредством использования около 30 электромагнитов, чтобы статическое поле было постоянным примерно в одной из $10^{9}$ частей всего объема используемого образца. Константы продольной и поперечной временной релаксации $T_{1}$ и $T_{2}$ были измерены с использованием стандартного обратного восстановления и последовательности импульсов Карра-Парселла-Мейбума-Гилла [23], что дало $T_{1} \approx 19$ и 25 секунд и $T_{2} \approx 7$ и 0.3 секунды, соответственно для протона и угле-
А. Л. Чуанг, Л. М. К. Вандерсипен, К. Жу, Д. В. Леюнг, С. Ллойд
рода; они были намного длиннее, чем требовалось для нашего эксперимента, который был завершен приблизительно за 7 миллисекунд.

Единственными наиболее существенными источниками погрешностей в эксперименте были неоднородность РЧ и несовершенство настройки длины импульса. Непосредственный критерий неоднородности — время экспоненциального убывания порядка $\approx 200$ мкс одного импульса. С учетом смешения заселенностей, на каждое ядро действовало порядка 7 импульсов с кумулятивной продолжительностью $\approx 70 \div 100$ мкс.

Второй наиболее важный вклад в погрешность — низкое отношение «сигнал-шум» для углерода, отношение пик сигнала/RMS шум $\approx 35$, тогда как для протона $\approx 4300$. Сигнал от углерода был намного более слабым, поскольку для него гиромагнитное отношение в 4 раза меньше, и приемная катушка для углерода была установлена более далеко от рабочего образца. Меньшие вклады в погрешность давали неполное затухание между последовательными экспериментами, отклонения несущей частоты и численные погрешности при расчетах.

Недостатки такого маленького квантового компьютера были скорее во власти технологии, нежели чем в фундаментальных принципах. Однако, квантовые компьютеры на основе ЯМР более чем с 10 кубитами будут требовать новых подходов, поскольку с увеличением числа кубитов сила сигнала экспоненциально убывает в используемой схеме $[24,25]$ : для $N$ спинов сигнал от начального состояния $00 \ldots 0$ пропорционален $n_{00 \ldots 0} \propto N Z^{-N}$, где при больших температурах функция $Z \approx 2$. Кроме того, временная когерентность естественно уменьшается для больших молекул, в то время как продолжительность работы логической схемы увеличивается. Однако, существует некоторый оптимизм; например, из-за коллективного характера ЯМР-технологий можно получать результат при достижении различимой большей части молекул правильного конечного состояния. Тем самым, создание эффективно чистого состояния не является необходимым. Оптическая накачка и различные методы охлаждения также могут использоваться для начальной поляризации рабочего образца, для увеличения амплитуды сигнала, поскольку при низких температурах $Z \approx 1$. Квантовые вычисления явно обрисовывают интересные и нужные сложные экспериментальные задачи будущего.
Рис. 2. Спектр протона после исполнения $\mathrm{D}-\mathrm{J}$ алгоритма и единственного считывающего импульса $X_{A}$ с эффективно чистым начальным состоянием $|00\rangle$ и с тепловым начальным состоянием [на вставке]. Низкие (высокие) частотные линии соответствуют переходам $|00\rangle \leftrightarrow|10\rangle \quad(|01\rangle \leftrightarrow|11\rangle)$. Частота -499755169 Гц, а амплитуда дана в произвольных единицах. Спектр есть фурье-образ времени изменения напряжения $V(t)$, индуцируемого в катушке из-за прецессии спина $A$ вокруг $-\mathbf{B}_{0}$ с частотой $\omega_{A}$ после считывающего импульса $X_{A} \cdot V(t)$ есть $V(t) \approx V_{0} \operatorname{Tr}\left[e^{-i \widehat{\mathscr{H}} t} e^{-i \frac{\pi}{2} \widehat{I}_{x}} \rho(0) e^{i \frac{\pi}{2} \hat{I}_{x}} e^{i \widehat{\mathscr{H}} t} \times\left(-i \widehat{\sigma}_{x A} \widehat{\sigma}_{y A}\right)\right]$, где $\widehat{\sigma}_{\{x, y\}}$ — матрицы Паули, а $\rho(0)$ — матрица плотности состояния непосредственно перед считывающим импульсом. В соответствии с этим, спектральная линия для спина $A$ действительна и положительна (отрицательна), когда спин $A-|0\rangle(|1\rangle)$ непосредственно перед считывающим импульсом $X_{A}$. Эксперимент был выполнен в Станфордском университете с использованием магнита 11.7 Tesla Oxford Instruments и спектром типа Varian UNITY Inova с тройной резонансной проверкой. ${ }^{13} \mathrm{C}$-меченый $\mathrm{CHCl}_{3}$ был получен в Кембриджской изотопной лаборатории (Cambridge Isotope Laboratories, Inc.) [CLM-262].

Заметим, что в при подготовке этой статьи мы узнали о похожем эксперименте Дж.А.Джонса и М. Моски в Оксфордском университете $[26]$.
Рис. 3. Экспериментально измеренная и теоретически ожидаемая матрица плотности отклонений после выполнения $\mathrm{D}-\mathrm{J}$ алгоритма. Диагональные элементы представляют собой нормированную заселенность состояний $|00\rangle,|01\rangle,|10\rangle$ и $|11\rangle$ (слева направо). Недиагональные элементы представляют взаимосвязь между разными состояния. Амплитуды показаны с реальными знаками компонент; все мнимые компоненты были малы. Матрица плотности отклонений была получена интегрально от спектральных линий протона и углерода, полученных в 9 экспериментах с различным считывающими импульсами для каждого спина (томография квантового состояния [24]). Наблюдаемые экспериментальные недостатки могут быть оценены следующим образом. В экспериментах нормированная заселенность чистых состояний (в идеальном случае равная 1) варьировалась от 0.998 до 1.019 . Другие элементы матрицы плотности отклонений (в идеальном случае 0 ) были по величине меньше 0.075 . Относительная ошибка $\varepsilon$ для экспериментальной матрицы плотности $\rho_{\exp }$ для чистых конечных состояний, определенная как $\varepsilon=\left\|\rho_{\text {exp }}-\rho_{\text {theory }}\right\| /\left\|\rho_{\text {theory }}\right\|$, варьировалась между 8 и $12 \%$.