Предложен новый полиномиальный по времени квантовый алгоритм, использующий квантовое преобразование Фурье, определяющий собственные значения и собственные функции оператора Гамильтона. Алгоритм может быть применен в тех случаях (обычно имеющих место в физических и химических задачах ab initio), для которых все известные классические алгоритмы требуют экспоненциального времени вычисления. Рассмотрено применение алгоритма к конкретным задачам, и сделан вывод, что интересные задачи атомной физики, которые трудно решить классическими методами, могут быть разрешены с использованием от 50 до 100 квантовых битов.

Задолго до основополагающего алгоритма Шора [1] и последующей волны интереса к квантовым вычислениям Фейнман предположил, что квантовый компьютер может быть полезен для моделирования других квантовых систем [7]. Это предположение базировалось на том наблюдении, что размерность гильбертова пространства, в котором описываются квантовые системы, экспоненциально растет с числом частиц.
${ }^{1}$ Эта работа была выполнена при поддержке по гранту \# N00014-95-1-0975 от Office of Naval Research; ARO and DARPA по гранту \# DAAH04-96-1-0386 to QUIC, the Quantum Information and Computation initiative; по DARPA гранту NMRQC, the Nuclear Magnetic Resonance Quantum Computing initiative; по программе ARO through an NDSEG.
${ }^{2}$ Department of Physics, MIT 12-128b Cambridge, MA 02139 (abrams@mit.edu).
${ }^{3}$ d’Arbeloff Laboratory for Information Sciences and Technology Department of Mechanical Engineering, MIT 3-160 Cambridge, MA 02139 (slloyd@mit.edu).
Перевод М.В.Чичикиной.
Таким образом, для полного описания состояния системы только 100 частиц со спином $\frac{1}{2}$, каждая из которых, будучи изолированной, может быть определена всего лишь двумя комплексными амплитудами, требуется $2^{100}$ комплексных амплитуд. Этот экспоненциальный рост очень ограничивает возможность производить точные вычисления ab initio; поскольку невозможно даже описать начальное состояние (кроме случаев простейших квантовых систем), приходится прибегать к технике различных приближенных вычислений, чтобы выяснить характерные свойства квантовых систем.

В недавних работах в области квантовых вычислений были предложены различные методы моделирования физики на квантовых компьютерах $[8,11,2,4,3,5]$, и было показано, что они действительно эффективны, как и предполагал Фейнман. Однако, в то время как предыдущие работы описывали разнообразные алгоритмы для приведения квантового компьютера в состояние, соответствующее состоянию физической системы, для эволюции со временем этого состояния в компьютере и для измерения свойств эволюционирующего состояния $[8,11,2,4,3]$, было сделано сравнительно мало работ по алгоритмам, которые вычисляют статические свойства физических систем [5]. В частности, из всех вопросов, которые можно задать о квантовой системе, есть один наиболее часто повторяющийся и для которого наиболее желательно получить эффективный алгоритм: каковы собственные значения и собственные векторы? В данной работе приводится квантовый алгоритм, который может находить собственные значения и собственные векторы оператора Гамильтона в случаях, часто представляющих физический интерес. Более того, для выполнения алгоритма требуется промежуток времени, растущий как полиномиальная функция числа частиц и требуемой точности, тогда как во всех известных классических алгоритмах это время растет экспоненциально.

Проблема может быть точно сформулирована следующим образом. Рассмотрим оператор эволюции $\widehat{U}=e^{-\frac{i}{\hbar} \widehat{H} t}$, соответствующий гамильтониану $\widehat{H}$, и аппроксимацию $V_{a}$ собственного вектора $\widehat{U}$ (следовательно, и $\widehat{H}$ ), который может быть построен за полиномиальное время, т. е. машина может быть приведена в состояние $V_{a}$ за полиномиальное число квантовых логических операций. Обозначим истинный собственный вектор $V$ и соответствующее собственное значение $\lambda_{v}$. Если состояние $V_{a}$ таково, что $\left|\left\langle V_{a} \mid V\right\rangle\right|^{2}$ не является экспоненциально малой величиной, то есть приближенный собственный вектор содержит компоненту истинного собственного вектора, которая ограничена полиномиальной функцией параметра задачи, тогда $V$ и $\lambda_{v}$ могут быть найдены за время, пропорциональное $1 /\left|\left\langle V_{a} \mid V\right\rangle\right|^{2}$ и $1 / \varepsilon$, где $\varepsilon$ – требуемая точность.

Интуитивно ясно, что алгоритм разлагает пробное начальное приближение на компоненты, не являющиеся пренебрежимо малыми, и определяет соответствующие собственные значения. Если оператор $\widehat{U}$ (и, следовательно, его собственные векторы) экспоненциально большой размерности, что типично, то неизвестны классические алгоритмы, которые могут найти хотя бы собственные значения за полиномиальное время. Хотя требование существования начального вектора состояния $V_{a}$ с определенными свойствами может показаться слишком ограничивающим, часто (если не сказать обычно) возможно получить такое предположение для «реальных» проблем, используя существующие классические приемы. Например, в любой физической системе с дискретными энергетическими уровнями, которые не расположены экспоненциально близко к основному состоянию (как в атоме), если возможно получить классически любой вектор состояния с предполагаемой энергией просто меньшей, чем первое возбужденное состояние (на неэкспоненцально малую величину), тогда этот вектор состояния должен содержать компоненты основного состояния, не являющиеся пренебрежимо малыми, и – хотя это может даже отдаленно не походить на основное состояние – этот вектор может быть использован как приближенное состояние $V_{a}$ для определения истинного основного состояния и энергии основного состояния за полиномиальное время. Наконец, если из-за каких-то проблем невозможно получить классически приблизительный подсчет с требуемой точностью, часто бывают случаи, когда вектор состояния $V_{a}$ может быть получен с использованием квантового алгоритма, как квантово смоделированный отжиг.

Теперь опишем алгоритм, применимый к любому $\widehat{U}$, который может быть выполнен за квантовое полиномиальное время, независимо от того, представляет ли он оператор эволюции, соответствующий данному гамильтониану, или нет. (В [8] было показано, что оператор эволюции, соответствующий любому локальному гамильтониану, может быть построен на квантовом компьютере за полиномиальное время). Эта первая часть алгоритма была описана независимо в [12] применительно к вычислению собственных значений (но не собственных векторов) унитарных операторов, поскольку собственные значения операторов можно использовать для решения задачи об абелевом стабилизаторе. Рассмотрим квантовый компьютер, состоящий из $m+l+w$ кубитов, где совокупность $m$ кубитов (назовем их индексными битами) используется для быстрого преобразования Фурье, множество $l$ кубитов описывает гильбертово пространство, в котором действует оператор $\widehat{U}$, и $w$ дополнительных кубитов требуются для временной памяти. Пусть $M=2^{m}$. Точность результата будет расти как $1 / M$. Предположим, что $m$ индексных кубитов первоначально находятся в состоянии $|0\rangle$ и $l$ кубитов находятся первоначально в состоянии $V_{a}$ (следовательно, нужно, чтобы $V_{a}$ было построено за квантовое полиномиальное время). В этом случае начальное состояние есть
\[
|\Psi\rangle=|0\rangle\left|V_{a}\right\rangle,
\]

где предполагается (если заранее не оговорено противное), что $w$ рабочих кубитов находятся в состоянии $|0\rangle$. Мы производим поворот на $\pi / 2$ в каждом из $m$ индексных кубитов, чтобы получить состояние
\[
|\Psi\rangle=\frac{1}{\sqrt{M}} \sum_{j=0}^{M-1}|j\rangle\left|V_{a}\right\rangle .
\]

Затем проводится ряд квантовых логических операций, которые переводят компьютер в состояние
\[
|\Psi\rangle=\frac{1}{\sqrt{M}} \sum_{j=0}^{M-1}|j\rangle(\widehat{U})^{j}\left|V_{a}\right\rangle .
\]

Это преобразование завершается применением операции $\widehat{U}$ ко второму набору $l$ кубитов (которые первоначально были в состоянии $\left|V_{a}\right\rangle$ ) $j$ раз. Это можно легко выполнить, проводя цикл (обозначенный $i$ ) от 1 до $M$. Используя стандартные операции квантовой логики, установим флаговый кубит на величину $|1\rangle$, если только $i<j$, и произведем операцию $\widehat{U}$, управляемую значением этого флага. Таким образом, получены только те компоненты приведенной выше суперпозиции, для которых $i<j$. Наконец, изменим значение флаговых кубитов и продолжим вычисления со следующей итерацией. После $M$ итераций получим приведенное выше состояние.

Здесь полезно переписать состояние немного в другом виде. Пронумеруем собственные вектора $\widehat{U}$ как состояния $\left|\phi_{k}\right\rangle$ и соответствующие
собственные значения как $\lambda_{k}$. После этого можно написать
\[
\left|V_{a}\right\rangle=\sum_{k} c_{k}\left|\phi_{k}\right\rangle
\]

описанное выше состояние (3) может быть переписано в форме
\[
\begin{aligned}
|\Psi\rangle & =\frac{1}{\sqrt{M}} \sum_{j=0}^{M-1}|j\rangle(\widehat{U})^{j} \sum_{k} c_{k}\left|\phi_{k}\right\rangle= \\
& =\frac{1}{\sqrt{M}} \sum_{k} c_{k} \sum_{j=0}^{M-1}|j\rangle\left(\lambda_{k}\right)^{j}\left|\phi_{k}\right\rangle .
\end{aligned}
\]

Если записать $\lambda_{k}$ как $e^{i \omega_{k}}$ и поменять порядок кубитов так, чтобы номера $\left|\phi_{k}\right\rangle$ оказались первыми, результат будет более наглядным:
\[
|\Psi\rangle=\frac{1}{\sqrt{M}} \sum_{k} c_{k}\left|\phi_{k}\right\rangle \sum_{j=0}^{M-1} e^{i \omega_{k} j}|j\rangle .
\]

Теперь очевидно, что квантовое преобразование Фурье, произведенное на $m$ индексных кубитах: вычислит фазы $\omega_{k}$ и, следовательно, собственные значения $\lambda_{k}$. Квантовое преобразование Фурье требует только poly $(m)$ операций, в то время как точность результата растет линейно с $M$ или как $2^{m}$. Каждая частота появляется с амплитудой $c_{k}=\left\langle V_{a} \mid \phi_{k}\right\rangle$. Производя измерение на $m$ индексных кубитах, можно получить каждое собственное значение с вероятностью $\left|c_{k}\right|^{2}$. Следовательно, нужно только полиномиальное число шагов, чтобы получить любое собственное значение, для которого $c_{k}$ не будет экспоненциально малым. Если начальное пробное значение $\left|V_{a}\right\rangle$ близко к нужному состоянию, (т. е., $\left|\left\langle V_{a} \mid V\right\rangle\right|^{2}$ близко к 1), то может понадобиться только несколько попыток.

Более того, так же можно получить и собственные векторы: если измерения уже сделаны, и собственные значения $\lambda_{k}$ определены, оставшиеся $l$ кубитов «коллапсируют» в состояние соответствующего собственного вектора. Конечно, состояние $\left|\phi_{k}\right\rangle$ в некотором смысле «заперто в ловушке» внутри компьютера. Но, поскольку невозможно хранить $2^{l}$ фаз, связанных с состоянием, как классическую информацию,
Д. С. Абрамс, С. Ллойд
нельзя надеяться на лучшее. Однако, если представляют интерес различные свойства собственных векторов, то их можно определить с помощью различных измерений этого состояния. Для квантовых вычислений ab initio среди легко получаемых свойств наибольший интерес представляют следующие: плотность распределения заряда, корреляционная функция, распределение импульсов и т. д. Обсуждение вопроса, каким образом нужная физическая информация может быть извлечена из квантового компьютера, приведено в [11].

Обсудим теперь точнее вопрос получения собственных векторов и собственных значений «реального» гамильтониана. Обычно требуется найти собственные состояния гамильтониана в форме
\[
H=\sum_{i=1}^{n}\left(T_{i}+V_{i}\right)+\sum_{i>j}^{n} V_{i j},
\]

где $n$ – число частиц, $T_{i}$ – кинетическая энергия, $V_{i}$ – внешний потенциал и $V_{i j}$ – взаимодействие между частицами. Однако нет причин, почему эти методы нельзя было бы применять к другим гамильтонианам или к гамильтонианам, содержащим дополнительные слагаемые, если гамильтониан может быть представлен в виде суммы локальных взаимодействий (то есть суммы слагаемых, которые действуют только на $k$ кубитов, где $k$ не зависит от числа частиц $n$ ). (В атомных задачах, например, можно включить эффективное взаимодействие как спин-орбитальную связь или как ядерные эффекты конечных областей действия). Поскольку гамильтониан эрмитов, мы применяем описанные выше шаги для оператора эволюции $\widehat{U}(t)=e^{-i H t}$, который унитарен и имеет те же собственные векторы и собственные значения. Этот оператор эволюции можно получить с помощью методов, описанных в [8]. Основная идея состоит в представлении
\[
\begin{array}{c}
H=\sum H_{i}, \\
\widehat{U}(t)=e^{-i H t}=\left(e^{-i H_{1} \frac{t}{m}} e^{-i H_{2} \frac{t}{m}} \ldots e^{-i H_{k} \frac{t}{m}}\right)^{m}+\sum_{i>j}\left[H_{i}, H_{j}\right] \frac{t^{2}}{2 m}+\ldots,
\end{array}
\]

где каждый $H_{i}$ действует только на $k$ кубитов одновременно. (В описанном выше гамильтониане каждый $H_{i}$ представляет одно из слагаемых $T_{i}, V_{i}$ или $\left.V_{i j}\right)$. Пусть $U_{i}=e^{-i H_{i} \frac{t}{m}}$. Каждое слагаемое $U_{i}$ может быть быстро посчитано, поскольку оно действует в пространстве только $k$ квантовых битов, где $k$ мало. Для достаточно больших $m$ второе слагаемое в правой части (и слагаемые высших порядков) стремятся к нулю. Следовательно, возможно получить $\widehat{U}(t)$ путем действия на состояние каждым $U_{i}$ последовательно всего $m$ раз. Тщательный анализ [8] показывает, что для того, чтобы смоделировать $\widehat{U}(t)$ с точностью $\varepsilon$, необходимо проделать $O\left(t^{2} / \varepsilon\right)$ квантовых логических операций ${ }^{1}$.

Для конкретных задач форма матриц $U_{i}$ в большой степени зависит от базиса, выбранного для описания гильбертова пространства. Более того, выбор может сильно влиять на число элементов базиса, требуемого для точного описания системы. В обычном представлении первичного квантования каждая частица описывается рядом из $l$ кубитов, представляющим волновую функцию отдельной частицы. Система как целое, таким образом, представлена $n \cdot l$ кубитами. (Возможно также представление вторичного квантования, которое может быть более эффективным для определенных задач; см. [11].) Для описанного выше гамильтониана матрицы $U_{i}$ могут быть получены очень эффективным способом с использованием либо координатного, либо импульсного пространства для одночастичного базиса и переходом между пространствами с помощью квантового преобразования Фурье. Однако для большинства проблем не существует проблемы выбора самого эффективного представления собственных состояний с определенным значением энергии. Один из наборов базисных состояний обычно более эффективен и чаще используется при соответствующих классических вычислениях: примером могут служить вейвлеты; другим стандартным представлением может быть одноэлектронное решение для эффективного потенциала. Поскольку размерность одночастичного базиса фиксирована (и мы выбираем более сложный базис с очевидной целью – сохранить его
${ }^{1}$ Тот факт, что $U(t)$ имеет одни и те же собственные значения и векторы для всех $t$, может привести к ошибочному заключению, что число операций, необходимое для нахождения собственных состояний с данной точностью, может быть сокращено путем выбора более коротких промежутков времени $t$ для оператоpa $U(t)$. Однако для выполнения алгоритма требуется вычислить $U^{M}$, и, поскольку $U(t)^{M}=U(M t)$, очевидно, что $U=U(t)$ может быть вычислено с большей точностью, если $U^{M}$ будет вычислено с фиксированной точностью. Действительно, поскольку собственные векторы определены с точностью, пропорциональной $M$, число квантовых логических операций, необходимых для вычисления собственных состояний с заданной энергией с точностью $\varepsilon$, очевидно, порядка $\varepsilon^{-2}$.
малым), тогда операторы $U_{i}$ всегда могут быть вычислены в выбранном базисе и построены с использованием операторов $O\left(d^{4}\right)$, где $d$ – размерность одночастичного базиса [6]. Таким образом, можно применять квантовые алгоритмы, используя наиболее тщательно подобранный базис, который, как правило, используется при стандартных вычислениях ab initio. (Поскольку существует быстрое квантовое вейвлетное преобразование [9], возможно, что вейвлетный базис окажется особенно полезным).

С другой стороны, существует взаимозависимость между памятью и скоростью. При использовании координатного или импульсного представления нужно только $O(\operatorname{poly}(k))=O(\operatorname{poly}(\log d))$ операций, чтобы получить каждое из $U_{i}$; однако требуется большое количество кубитов, чтобы описать точно собственное состояние. Используя наиболее тщательно подобранный базис, можно значительно сократить требуемое количество кубитов, однако может оказаться, что требуется гораздо большее количество квантовых логических операций $O\left(k^{4}\right)$, чтобы построить каждое $U_{i}$. То есть, как и при обычных вычислениях, оказывается, что выбор базиса в квантовых вычислениях будет зависеть от специфики решаемой проблемы и возможностей данного вычислительного устройства.

Обычно начальное состояние $V_{a}$ является результатом классических вычислений, например, метода Хартри-Фока или вычисления конфигурационного взаимодействия. Можно использовать любой ab initio метод, приводящий к известной волновой функции. (Заметим, что это понятие не включает в себя методы, использующие теорию функционала плотности, поскольку нужна волновая функция, а не просто распределение плотности заряда). Если мы вводим еще не симметризованную или антисимметризованную волновую функцию, мы можем использовать алгоритмы, описанные в [11], чтобы сделать это эффективно.

Наконец, обсудим работающие ab initio вычисления энергетических уровней атома, чтобы сравнить описанный выше квантовый алгоритм с известными классическими методами. Задачи атомной физики служат особенно удачным исходным пунктом, поскольку хорошо известны очень точные экспериментальные данные. Квантовые алгоритмы наиболее близки методам, известным как «полное активное конфигурационное взаимодействие» или «полное конфигурационное взаимодействие», поскольку многочастичный базис включает все возможные произведения векторов одночастичного базиса. Этот подход наиболее
эффективен в ситуациях, где энергия корреляции велика и где много «конфигураций» обладают близкими энергиями (это обычно бывает, когда много электронов находятся на незаполненной оболочке). К сожалению, трудно точно оценить минимальный размер системы, для которой квантовые вычисления превосходят лучшие классические, поскольку во избежание экспоненциального увеличения вычислений при оценки основного состояния используются разнообразные изощренные методы. Наиболее точные классические вычисления не используют прямо метод «полного конфигурационного взаимодействия». Однако, ссылаясь на [10], можно оценить, что вычисление уровней энергии В (5 электронов) с использованием примерно 20 угловых волновых функций и 40 радиальных волновых функций для каждой частицы – всего 800 волновых функций для отдельной частицы и, следовательно, $800^{5} \approx 10^{15}$ полных многочастичных базисных состояний – может дать более точный результат, гем любое современнейшее класситеское вычисление. По крайней мере, такие вычисления могли привести к представляющим научный интерес результатам (которые невозможно получить классически), касающихся корреляционной энергии электронов в В и относительной важности различных возбужденных состояний.

Квантовое вычисление основного состояния В с использованием описанного выше базиса может быть выполнено с 60 кубитами: 10 для частицы, чтобы представить состояние атома (всего 50 кубитов), 6 или 7 кубитов для квантового преобразования Фурье и несколько дополнительных «черновых» ${ }^{1}$. К сожалению, двухчастичные операторы (порождаемые кулоновским взаимодействием между электронами) действуют в подпространстве размерности $\left(2^{10}\right)^{2}$; они, таким образом, представлены матрицами с $2^{40}$ элементами. Вводить такие операторы грубой силой – значит оставлять их без описания в обозримом будущем. Однако, возможно, удастся провести необходимые преобразования, используя квантовый алгоритм. Один из возможных методов –
1 Число кубитов, необходимых для квантового преобразования Фурье, не так велико, как можно было бы предположить сначала, основываясь на сделанном ранее предположении, что точность линейно пропорциональна размеру преобразования Фурье. Это утверждение верно для фиксированного $U$. Изменяя $U$ – в частности, увеличивая длину временного интервала $t$ в $U(t)$, – можно получить собственные значения с любой точностью, используя фиксированное число операций в Фурье-преобразовании. Однако размер этого преобразования должен быть достаточно большим, чтобы выделить частоты, соответствующие отдельным собственным векторам. Именно исходя из этих соображений была получена оценка в 6 или 7 кубитов (64- или 128-мерное Фурье-преобразование).
замена базиса: после представления взаимодействия частиц в координатном пространстве вместо орбитального базиса посчитать кулоновские термы будет просто. Таким образом, можно отдельно перевести каждую частицу в координатное пространство (для этого требуется небольшое число квантовых логических операций), получить эволюцию, определяемую кулоновским взаимодействием, и произвести обратное преобразование. $К$ сожалению, представление в координатном пространстве требует больше кубитов. По нашим оценкам, 30 кубитов на частицу (10 на каждое измерение, для реальной пространственной решетки $1024 \times 1024 \times 1024$ на частицу) будет более чем достаточно. Поскольку эти 30 кубитов только временно нужны для двух частиц, взаимодействие которых мы рассматриваем для какого-нибудь состояния в алгоритме, то для нового эффективного алгоритма нужно всего $2 \times 30$ кубитов (для взаимодействующих частиц), дополнительные $3 \times 10$ кубитов (для оставшихся частиц) и те же 10 кубитов для преобразования Фурье и рабочего пространства. Таким образом, оказывается, что для того, чтобы на самом деле провести «интересные» вычисления с использованием описанных выше алгоритмов, нужен квантовый компьютер примерно с 100 кубитами. Конечно, остается вероятность, что может быть изобретен эффективный алгоритм для описания кулоновского взаимодействия, не требующий дополнительного рабочего пространства.

Подведем итог: предложен новый квантовый алгоритм, который может быть использован для нахождения собственных векторов и собственных значений оператора Гамильтона. Алгоритм обеспечивает экспоненциальное увеличение скорости по сравнению с лучшими классическими методами. Первые реальные вычисления лучше всего проводить для задач атомной физики по двум причинам: и потому, что имеются точные экспериментальные данные для проверки результатов вычислений, и потому, что используемые параметры укладываются в ожидаемые рамки малых квантовых компьютеров. По нашим оценкам, $50-100$ кубитов достаточно для проведения «интересных» вычислений, которые трудно сделать классически. Наконец, мы предлагаем пару интересных вопросов, которые остались открытыми. Первый: хотя мы сделали оценки относительно числа требуемых кубитов, было бы интересно точно подсчитать число квантовых гейтов, нужных, чтобы выполнить «интересную» задачу. Второй: стоило бы сделать детальный анализ влияния ошибок, как и анализ исправляющих ошибки кодов в данном контексте.

D.S. А. выражает признательность за поддержку NDSEG fellowship и благодарит D. Lidar, C. Froese Fisher, и особенно W. R. Johnson за полезные дискуссии. Часть данного исследования была выполнена при поддержке гранта \# N00014-95-1-0975 от Office of Naval Research, также ARO и DARPA от гранта \# DAAH04-96-1-0386 to QUIC, Quantum Information and Computation initiative, и DARPA гранта от NMRQC, Nuclear Magnetic Resonance Quantum Computing initiative.