Квантовый компьютер для квантовых химиков
Изначально квантовый компьютер предлагался как средство для численного решения квантовомеханических задач. Хотя позже мейнстрим унесся в квантовую криптографию и прочие области, нужные человечеству исключительно для создания проблем для самого себя, кое кто не забыл, что техника вообще-то нужна для преодоления препятствий, которые поставила природа. Дальнейшее есть краткое изложение статьи 2008г., авторы которой попытались полностью расписать алгоритм решения временного уравнения Шредингера для системы частиц с помощью квантового компьютера.
Если говорить о чисто числомоделисткой стороне дела, используются самые простые методы. Для каждой пространственной размерности вводиться равномерная сетка с числом узлов, равным степени двойки. Набор значений волновой функции в этих узлах как бы записывается в виртуальный массив памяти квантового компьютера, про который я писал в предыдущем посте на эту тему. Соответственно, индексы массива (или попросту кубиты) разбиваются на группы по n штук, каждая из которых нумерует положение узла по одной из размерностей. Если число размерностей d, для запоминания волновой функции потребуется N=n*d кубитов.
Временная эволюция волновой функции рассчитывается помощью метода, аналогичному широко известному в узких кругах как метод расщепления с быстрым Фурье-преобразованием
Ψ(t+Δt)= F-1 exp(-iTΔt) F exp(-iUΔt)Ψ(t)Гамильтониан системы расщепляется на кинетическую T=p2/2m и потенциальную U=U(x1,x2,…,xd) энергии, а пропагатор соответственно представляется в виде произведения пропагаторов. Между действием пропагаторов на каждом шаге по времени выполняются прямое F и обратное преобразование Фурье F-1, выполняющие переход соответственно к импульсному представлению, в котором диагонален оператор кинетической энергии, и обратно к координатному представлению, в котором диагонален оператор потенциальной энергии. Так что действие обоих пропагаторов сводится к умножению значений волновой функции в узлах на фазовые множители.
Отличие квантовокомпьютерного метода от метода, широко известного в узких кругах, состоит в том, что вместо быстрого Фурье-преобразования используется квантовое Фурье-преобразование. Поскольку узкие круги разработчиков алгоритмов для квантового компьютера не пересекаются с первоначально упомянутыми узкими кругами обычных числомоделистов, метод расщепления с КФТ назвали алгоритмом Zalka-Wiesner’а. Погрешность пространственной аппроксимации полиномиально зависит от шага сетки, а поскольку (при фиксированных границах пространственной области) шаг Δx обратно пропорционален числу узлов сетки, погрешность экспоненциально уменьшается с увеличением n. Погрешность метода расщепления в данной реализации получается первого порядка по временному шагу, но ее несложно повысить до второго порядка (все образованные люди, к которым я отношу прочитавших мою методичку для третьего курса, знают как …).
Перед умножением на фазовый множитель, нужно вычислить потенциал в каждом узле сетки. Тут следует еще раз напомнить, что набор n кубитов можно рассматривать как двоичное число, пропорциональное координате х. Потенциал представляется в форме степенного ряда, так что его вычисление сводиться к набору сложений и умножений х, то есть этого самого числа, представленного набором кубитов, с некоторыми коэффициентами. Сложение авторы обсуждаемой статьи предлагают выполнять с помощью алгоритма Draper’а, а умножение - столбиком (т.е. умножение сводиться к сложению), но вообще разных алгоритмов сложения и умножения для квантового компьютера придумали уйму. В любом случае, сложение производиться для двух чисел, записанных как двоичные разряды в двух кубитных регистрах, результат формируется в одном из регистров. Все, как в обычном компьютере, только эта операция одновременно выполняется для всех вероятных значений начальных значений регистров (вот тут популярная интерпретация квантового компьютера как компьютера, выполняющего сразу множество операций одновременно, оказывается удобной и уместной), то есть всех значений x. Окончательный результат вычисления U записывается в регистр из m кубитов, где m - число двоичных разрядов в fixed-point представлении значения U. Точнее, U туда бы записался, если бы этот регистр изначально был бы инициализован нулем.
Но нам то нужно не само значение U, а умножение волновой функции на exp(-iUΔt). Это делается с помощью трюка, называемого phase kickback. Он заключается в том, что регистр результата инициализируется не нулем, а специальным (не очень хитрым) образом. Инициализированный таким образом регистр, при записи в него результата вычисления U, меняет свое значение на отличающееся от начального только фазовым множителем exp(-iU(x1,x2,…,xd)Δt). Данный регистр и большой регистр из N кубитов, в котором записаны все вероятные значения координат х, образуют единую систему. Так как амплитуды вероятностей значений «большого регистра» - это значения волновой функции в точках, мы добились того, чего хотели - каждое из значений волновой функции умножилось на фазовый множитель, зависящий от координат точки. Аналогично выполняется и шаг расщепления с кинетической энергией.
Итого, для расчетов нужен квантовый компьютер с n*d+4m кубитов, где 4m уходит на служебные регистры для вычисления потенциала и выполнения phase kickback. Если по каждой координате положить по 1024 узлов, для расчетов эволюции квантовой системы из 10 частиц (например, точный расчет химической реакции двух атомов, имеющих суммарно 8 активных электронов) потребуется квантовый компьютер с 300 кубитами. Ну или классический компьютер с памятью в один наногуголбайт …
Еще надо было бы написать про проблемы введения в память начального состояния волновой функции и извлечения информации после окончания расчетов, но я уже устал.
Но усталость не помешает мне сделать наезд: все эти люди, начиная с пресловутых Залки и Визнера, разбираются в обычных численных методах явно хуже, чем в создании алгоритмов для квантовых компьютеров. В всяком случае, ни они, ни авторы пересказываемой статьи не вспомнили, что у численных схем кроме точности важна еще и устойчивость. Метод расщепления вообще то условно устойчив с условием Δt<Δx2. То есть при экспоненциальном уменьшении шага сетки Δx, возможностью которого гордятся теоретические квантовокомпьтерщики, шаг по времени так же придеться уменьшать экспоненциально, с соответствующую экспоненциальным увеличением времени счета. А раз так, то на самом деле точность пространственной аппроксимации будет пропорциональна затраченным вычислительным ресурсам. Увеличение числа частиц без увеличения точности аппроксимации неизбежно приведет к катастрофе ортогональности. Положа руку на сердце, случаи, когда оная катастрофа действительно приводит к наблюдаемым расхождениям теории с экспериментов, не очень часты (обратный пример), но тем не менее эта проблема по неизбежности будет вызывать сомнения в результатах расчетов вышеописанным методом. Нужны другие, более продвинутые численные методы, хе хе…
Если говорить о чисто числомоделисткой стороне дела, используются самые простые методы. Для каждой пространственной размерности вводиться равномерная сетка с числом узлов, равным степени двойки. Набор значений волновой функции в этих узлах как бы записывается в виртуальный массив памяти квантового компьютера, про который я писал в предыдущем посте на эту тему. Соответственно, индексы массива (или попросту кубиты) разбиваются на группы по n штук, каждая из которых нумерует положение узла по одной из размерностей. Если число размерностей d, для запоминания волновой функции потребуется N=n*d кубитов.
Временная эволюция волновой функции рассчитывается помощью метода, аналогичному широко известному в узких кругах как метод расщепления с быстрым Фурье-преобразованием
Ψ(t+Δt)= F-1 exp(-iTΔt) F exp(-iUΔt)Ψ(t)Гамильтониан системы расщепляется на кинетическую T=p2/2m и потенциальную U=U(x1,x2,…,xd) энергии, а пропагатор соответственно представляется в виде произведения пропагаторов. Между действием пропагаторов на каждом шаге по времени выполняются прямое F и обратное преобразование Фурье F-1, выполняющие переход соответственно к импульсному представлению, в котором диагонален оператор кинетической энергии, и обратно к координатному представлению, в котором диагонален оператор потенциальной энергии. Так что действие обоих пропагаторов сводится к умножению значений волновой функции в узлах на фазовые множители.
Отличие квантовокомпьютерного метода от метода, широко известного в узких кругах, состоит в том, что вместо быстрого Фурье-преобразования используется квантовое Фурье-преобразование. Поскольку узкие круги разработчиков алгоритмов для квантового компьютера не пересекаются с первоначально упомянутыми узкими кругами обычных числомоделистов, метод расщепления с КФТ назвали алгоритмом Zalka-Wiesner’а. Погрешность пространственной аппроксимации полиномиально зависит от шага сетки, а поскольку (при фиксированных границах пространственной области) шаг Δx обратно пропорционален числу узлов сетки, погрешность экспоненциально уменьшается с увеличением n. Погрешность метода расщепления в данной реализации получается первого порядка по временному шагу, но ее несложно повысить до второго порядка (все образованные люди, к которым я отношу прочитавших мою методичку для третьего курса, знают как …).
Перед умножением на фазовый множитель, нужно вычислить потенциал в каждом узле сетки. Тут следует еще раз напомнить, что набор n кубитов можно рассматривать как двоичное число, пропорциональное координате х. Потенциал представляется в форме степенного ряда, так что его вычисление сводиться к набору сложений и умножений х, то есть этого самого числа, представленного набором кубитов, с некоторыми коэффициентами. Сложение авторы обсуждаемой статьи предлагают выполнять с помощью алгоритма Draper’а, а умножение - столбиком (т.е. умножение сводиться к сложению), но вообще разных алгоритмов сложения и умножения для квантового компьютера придумали уйму. В любом случае, сложение производиться для двух чисел, записанных как двоичные разряды в двух кубитных регистрах, результат формируется в одном из регистров. Все, как в обычном компьютере, только эта операция одновременно выполняется для всех вероятных значений начальных значений регистров (вот тут популярная интерпретация квантового компьютера как компьютера, выполняющего сразу множество операций одновременно, оказывается удобной и уместной), то есть всех значений x. Окончательный результат вычисления U записывается в регистр из m кубитов, где m - число двоичных разрядов в fixed-point представлении значения U. Точнее, U туда бы записался, если бы этот регистр изначально был бы инициализован нулем.
Но нам то нужно не само значение U, а умножение волновой функции на exp(-iUΔt). Это делается с помощью трюка, называемого phase kickback. Он заключается в том, что регистр результата инициализируется не нулем, а специальным (не очень хитрым) образом. Инициализированный таким образом регистр, при записи в него результата вычисления U, меняет свое значение на отличающееся от начального только фазовым множителем exp(-iU(x1,x2,…,xd)Δt). Данный регистр и большой регистр из N кубитов, в котором записаны все вероятные значения координат х, образуют единую систему. Так как амплитуды вероятностей значений «большого регистра» - это значения волновой функции в точках, мы добились того, чего хотели - каждое из значений волновой функции умножилось на фазовый множитель, зависящий от координат точки. Аналогично выполняется и шаг расщепления с кинетической энергией.
Итого, для расчетов нужен квантовый компьютер с n*d+4m кубитов, где 4m уходит на служебные регистры для вычисления потенциала и выполнения phase kickback. Если по каждой координате положить по 1024 узлов, для расчетов эволюции квантовой системы из 10 частиц (например, точный расчет химической реакции двух атомов, имеющих суммарно 8 активных электронов) потребуется квантовый компьютер с 300 кубитами. Ну или классический компьютер с памятью в один наногуголбайт …
Еще надо было бы написать про проблемы введения в память начального состояния волновой функции и извлечения информации после окончания расчетов, но я уже устал.
Но усталость не помешает мне сделать наезд: все эти люди, начиная с пресловутых Залки и Визнера, разбираются в обычных численных методах явно хуже, чем в создании алгоритмов для квантовых компьютеров. В всяком случае, ни они, ни авторы пересказываемой статьи не вспомнили, что у численных схем кроме точности важна еще и устойчивость. Метод расщепления вообще то условно устойчив с условием Δt<Δx2. То есть при экспоненциальном уменьшении шага сетки Δx, возможностью которого гордятся теоретические квантовокомпьтерщики, шаг по времени так же придеться уменьшать экспоненциально, с соответствующую экспоненциальным увеличением времени счета. А раз так, то на самом деле точность пространственной аппроксимации будет пропорциональна затраченным вычислительным ресурсам. Увеличение числа частиц без увеличения точности аппроксимации неизбежно приведет к катастрофе ортогональности. Положа руку на сердце, случаи, когда оная катастрофа действительно приводит к наблюдаемым расхождениям теории с экспериментов, не очень часты (обратный пример), но тем не менее эта проблема по неизбежности будет вызывать сомнения в результатах расчетов вышеописанным методом. Нужны другие, более продвинутые численные методы, хе хе…