Алгоритм Залки

Алгоритм Залки — Визнера — предназначен для моделирования унитарной динамики квантовой системы $n$ частиц на квантовом компьютере. Унитарная динамика представляет собой решение уравнения Шредингера вида

$|\Psi(t)\rangle= exp(-iHt/h)|\Psi(0)\rangle$

где гамильтониан

$H=H_q+H_p$

есть сумма операторов кинетической

$H_p=p^2/2m$

и потенциальной

$H_q=V$

энергий. Алгоритм Залки — Визнера состоит в последовательном применении $t/\Delta t$ раз поочередно двух операторов, соответствующих этим энергиям:

$exp(-iH_p\Delta t/h)exp(-iH_q\Delta t/h)$,

что дает состояние $|\Psi (t)\rangle$ реальной системы в момент времени t, при условии $\Delta t=O(1/t)$.

Оператор, соответствующий потенциальной энергии $exp(-iH_q\Delta t/h)$ реализуется на квантовом компьютере непосредственно, так как он имеет диагональную форму. Оператор кинетической энергии должен быть предварительно диагонализирован с помощью квантового преобразования Фурье.

Усовершенствование алгоритма Залки — Визнера

Алгоритм Залки — Визнера использует для представления оператора эволюции формулу Троттера, получающуюся в результате разложения экспонент до второго члена. Это дает моделирование за время, квадратичное по сравнению с временем реального процесса: $O(t^2)$. Использование следующих членов разложения экспоненты дает более эффективный алгоритм моделирования, занимающий время $t^{1+\epsilon}$ где положительная константа $\epsilon$ может быть сделана сколь угодно малой. Тем самым, схема Залки — Визнера способна моделировать состояния квантовой системы $n$ частиц за почти линейное время, используя память $O(n)$.

Значение моделирования квантовых систем

Моделирование квантовых систем на классическом компьютере невозможно из-за того, что размерность пространства состояний реальной квантовой системы растет как экспонента от числа частиц в ней (см. Квантовый компьютер). Поэтому алгоритм Залки — Визнера реализует главную идею квантового компьютера — служить моделью любой многочастичной квантовой системы. Почти линейное время моделирования и линейная память означает, что квантовый компьютер, если он будет построен, сможет моделировать эволюции самых сложных систем (биомолекул, и, следовательно, жизни) из первых принципов.

Моделирование квантовой системы на квантовом компьютере имеет иной смысл, чем так называемые квантово-механические расчеты на обычных компьютерах, в которых мы явно получаем значения амплитуд $\lambda$ соответствующих состоянию $|\Psi\rangle=\lambda_0|0\rangle+\lambda_1|1\rangle+\ldots$. При моделировании на квантовом компьютере мы не получаем самих амплитуд, а только само состояние $|\Psi\rangle$ в его кубитовом дискретном приближении. Для получения же самих амплитуд надо многократно повторить алгоритм квантового моделирования и измерять полученное состояние, то есть реализовать квантовую томографию. Моделирование на квантовом компьютере дает меньше, чем дало бы моделирование на обычном компьютере, но последнее невозможно по причинам сложностного характера. Если бы мы могли моделировать с доступной сложностью динамику любой квантовой системы на обычном компьютере, то мы могли бы моделировать и процесс быстрого квантового вычисления что невозможно в силу известных нижних оценок квантовой сложности.

Моделирование сложных квантовых систем с необходимостью требует реализации квантового компьютера в той или иной форме.

Литература

• Кайе Ф., Лафламм Р., Моска М. Введение в квантовые вычисления. — Ижевск: РХД, 2009. — 360 с.
• Китаев А., Шень А., Вялый М. Классические и квантовые вычисления. — М.: МЦНМО, 1999. — 192 с.
• Нильсен М., Чанг И. Квантовые вычисления и квантовая информация. — М.: Мир, 2006. — 824 с.
• Прескилл Дж. Квантовая информация и квантовые вычисления (в 2-х томах). — Ижевск: РХД, 2008-2011. — 776 с.