Квантовый компьютер для квантовых химиков
Dec. 7th, 2014 05:19 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
antihydrogenИзначально квантовый компьютер предлагался как средство для численного решения квантовомеханических задач. Хотя позже мейнстрим унесся в квантовую криптографию и прочие области, нужные человечеству исключительно для создания проблем для самого себя, кое кто не забыл, что техника вообще-то нужна для преодоления препятствий, которые поставила природа. Дальнейшее есть краткое изложение статьи 2008г., авторы которой попытались полностью расписать алгоритм решения временного уравнения Шредингера для системы частиц с помощью квантового компьютера.
Если говорить о чисто числомоделисткой стороне дела, используются самые простые методы. Для каждой пространственной размерности вводиться равномерная сетка с числом узлов, равным степени двойки. Набор значений волновой функции в этих узлах как бы записывается в виртуальный массив памяти квантового компьютера, про который я писал в предыдущем посте на эту тему. Соответственно, индексы массива (или попросту кубиты) разбиваются на группы по n штук, каждая из которых нумерует положение узла по одной из размерностей. Если число размерностей d, для запоминания волновой функции потребуется N=n*d кубитов.
Временная эволюция волновой функции рассчитывается помощью метода, аналогичному широко известному в узких кругах как метод расщепления с быстрым Фурье-преобразованием
Отличие квантовокомпьютерного метода от метода, широко известного в узких кругах, состоит в том, что вместо быстрого Фурье-преобразования используется квантовое Фурье-преобразование. Поскольку узкие круги разработчиков алгоритмов для квантового компьютера не пересекаются с первоначально упомянутыми узкими кругами обычных числомоделистов, метод расщепления с КФТ назвали алгоритмом 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, возможностью которого гордятся теоретические квантовокомпьтерщики, шаг по времени так же придеться уменьшать экспоненциально, с соответствующую экспоненциальным увеличением времени счета. А раз так, то на самом деле точность пространственной аппроксимации будет пропорциональна затраченным вычислительным ресурсам. Увеличение числа частиц без увеличения точности аппроксимации неизбежно приведет к катастрофе ортогональности. Положа руку на сердце, случаи, когда оная катастрофа действительно приводит к наблюдаемым расхождениям теории с экспериментов, не очень часты (обратный пример), но тем не менее эта проблема по неизбежности будет вызывать сомнения в результатах расчетов вышеописанным методом. Нужны другие, более продвинутые численные методы, хе хе…
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2014-12-07 04:30 pm (UTC)no subject
Date: 2014-12-07 10:10 pm (UTC)странно, откуда там квадрат? должно быть Δt<Δx, и смысл его в том, что чем меньше характеристический размер неоднородности, тем меньше должен быть временной шаг.
а при фиксированном рельефе уменьшение шага сетки только улучшит моделирование, даже без изменения временного шага.
no subject
Date: 2014-12-07 10:52 pm (UTC)no subject
Date: 2014-12-07 11:20 pm (UTC)сорри, я не согласен. если бы мы делали вычисления чаще, и прилагали потенциал во временных точках, кратных Δt, и нулевой потенциал в остальных точках, это ещё было бы правдоподобно, именно по причине периодического приложения потенциала, отличного от "дефолта" (нулевого потенциала).
а так - нет, периодической систематической погрешности взяться неоткуда, если соблюдается условие про рельеф (т.е. Δt * dU/dx << Δx).
no subject
Date: 2014-12-07 11:39 pm (UTC)no subject
Date: 2014-12-08 05:00 am (UTC)no subject
Date: 2014-12-08 05:24 pm (UTC)no subject
Date: 2014-12-08 03:12 pm (UTC)no subject
Date: 2014-12-08 08:23 am (UTC)no subject
Date: 2014-12-08 04:55 pm (UTC)Да и без принципа согласен тоже. Пусть погрешность аппроксимации такова, что проекция одночастичной приближенной функции на точную функцию равна 0.99. Тогда погрешность для системы 10 частиц будет порядка 1-0.99^10 = 10%, что для многих задач вполне терпимо. А вот для 100 частиц проекция 0.99^100=0.36, что уже есть признак наступающей "катастрофы ортогональности".
no subject
Date: 2014-12-09 02:08 pm (UTC)no subject
Date: 2014-12-26 08:08 am (UTC)no subject
Date: 2014-12-26 01:18 pm (UTC)no subject
Date: 2014-12-26 09:32 am (UTC)no subject
Date: 2014-12-26 01:17 pm (UTC)no subject
Date: 2014-12-26 12:47 pm (UTC)no subject
Date: 2014-12-26 01:19 pm (UTC)no subject
Date: 2014-12-27 12:07 pm (UTC)no subject
Date: 2014-12-28 07:33 pm (UTC)no subject
Date: 2015-01-18 12:49 am (UTC)http://huntingcoloradostyle.com/content/
Квантовый компьютер для квантовых химиков
Date: 2016-08-26 05:29 am (UTC)