Квантовый алгоритм вычисления собственных значений и собственных векторов, обеспечивающий экспоненциальное увеличение скорости

Даниэль С. Абраме (Daniel S. Abrams) Сэт Ллойд (Seth Lloyd)

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

Задолго до основополагающего алгоритма Шора [1] и последующей волны интереса к квантовым вычислениям Фейнман предположил, что квантовый компьютер может быть полезен для моделирования других квантовых систем [7]. Это предположение базировалось на том наблюдении, что размерность гильбертова пространства, в котором описываются квантовые системы, экспоненциально растет с числом частиц.

Эта работа была выполнена при поддержке по гранту ф N00014-95-1-0975 от Office of Naval Research; ARO and DARPA no гранту # DAAH04-96-1-0386 to QUIC, the Quantum Information and Computation initiative; no DARPA гранту NMRQC, the Nuclear Magnetic Resonance Quantum Computing initiative; no программе ARO through an NDSEG.

Department of Physics, MIT 12-128b Cambridge, MA 02139 (abrams@mit.edu).

dArbeloff Laboratory for Information Sciences and Technology Department of Mechanical Engineering, MIT 3-160 Cambridge, MA 02139 (slloyd@mit.edu). Перевод M. B. Чичикиной.

аким образом, для полного описания состояния системы только 100 частиц со спином У2, каждая из которых, будучи изолированной, может

ыть определена всего лишь двумя комплексными амплитудами, тре-

уется 2 комплексных амплитуд. Этот экспоненциальный рост очень

граничивает возможность производить точные вычисления аЬ initio; поскольку невозможно даже описать начальное состояние (кроме случаев простейших квантовых систем), приходится прибегать к технике различных приближенных вычислений, чтобы выяснить характерные свойства квантовых систем.

В недавних работах в области квантовых вычислений были предло-

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

ыло сделано сравнительно мало работ по алгоритмам, которые вычисляют статические свойства физических систем [5]. В частности, из всех вопросов, которые можно задать о квантовой системе, есть один наиболее часто повторяющийся и для которого наиболее желательно получить эффективный алгоритм: каковы собственные значения и собственные векторы? В данной работе приводится квантовый алгоритм, который может находить собственные значения и собственные векторы

ператора Гамильтона в случаях, часто представляющих физический интерес. Более того, для выполнения алгоритма требуется промежуток времени, растущий как полиномиальная функция числа частиц и требу-

мой точности, тогда как во всех известных классических алгоритмах

то время растет экспоненциально.

Проблема может быть точно сформулирована следующим образом.

Рассмотрим оператор эволюции U = е , соответствующий гамильтониану Н, и аппроксимацию Va собственного вектора U (следовательно, и Н), который может быть построен за полиномиальное время, т. е. машина может быть приведена в состояние Va за полиномиальное чис-о квантовых логических операций. Обозначим истинный собственный вектор V и соответствующее собственное значение Л. Если состоя-ние Va таково, что (Va V) не является экспоненциально малой величи-

ной, то есть приближенный собственный вектор содержит компоненту истинного собственного вектора, которая ограничена полиномиальной функцией параметра задачи, тогда V и могут быть найдены за вре-мя, пропорциональное 1/ и 1/г, где е - требуемая точность.

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

Теперь опишем алгоритм, применимый к любому С/, который моет быть выполнен за квантовое полиномиальное время, независимо т того, представляет ли он оператор эволюции, соответствующий данному гамильтониану, или нет. (В [8] было показано, что оператор эво-юции, соответствующий любому локальному гамильтониану, может ыть построен на квантовом компьютере за полиномиальное время). Эта первая часть алгоритма была описана независимо в [12] применительно к вычислению собственных значений (но не собственных векторов) унитарных операторов, поскольку собственные значения опера-