antihydrogen: (spherical wave)
[personal profile] antihydrogen
Изначально квантовый компьютер предлагался как средство для численного решения квантовомеханических задач. Хотя позже мейнстрим унесся в квантовую криптографию и прочие области, нужные человечеству исключительно для создания проблем для самого себя, кое кто не забыл, что техника вообще-то нужна для преодоления препятствий, которые поставила природа. Дальнейшее есть краткое изложение статьи 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, возможностью которого гордятся теоретические квантовокомпьтерщики, шаг по времени так же придеться уменьшать экспоненциально, с соответствующую экспоненциальным увеличением времени счета. А раз так, то на самом деле точность пространственной аппроксимации будет пропорциональна затраченным вычислительным ресурсам. Увеличение числа частиц без увеличения точности аппроксимации неизбежно приведет к катастрофе ортогональности. Положа руку на сердце, случаи, когда оная катастрофа действительно приводит к наблюдаемым расхождениям теории с экспериментов, не очень часты (обратный пример), но тем не менее эта проблема по неизбежности будет вызывать сомнения в результатах расчетов вышеописанным методом. Нужны другие, более продвинутые численные методы, хе хе…

Date: 2014-12-07 04:30 pm (UTC)
From: [identity profile] livejournal.livejournal.com
Здравствуйте! Ваша запись попала в топ-25 популярных записей LiveJournal волжского региона. Подробнее о рейтинге читайте в Справке (http://www.dreamwidth.org/support/faqbrowse?faqid=303).

Date: 2014-12-07 10:10 pm (UTC)
From: [identity profile] 109.livejournal.com
Δt<Δx2

странно, откуда там квадрат? должно быть Δt<Δx, и смысл его в том, что чем меньше характеристический размер неоднородности, тем меньше должен быть временной шаг.

а при фиксированном рельефе уменьшение шага сетки только улучшит моделирование, даже без изменения временного шага.
Edited Date: 2014-12-07 10:11 pm (UTC)

Date: 2014-12-07 10:52 pm (UTC)
From: [identity profile] antihydrogen.livejournal.com
Это условие устойчивости, и рельеф тут не причем. Оно вытекает вот из чего: метод расщепления эквивалентен замене постоянного потенциала импульсным, с бесконечно короткими импульсами, следующими с периодом Δt. Такой потенциал неизбежно будет вызывать нефизический переход в возбужденное состояние с энергией 2π/Δt, и спустя какое то время это состояние станет доминирующим, то есть приближенное решение станет совершенно непохожим на точное. Единственный способ этого избежать - сделать так, чтобы состояний с энергией >= 2π/Δt в приближенном решении вообще не было. На сетке с шагом Δx минимально возможная длина волны 2Δx, соответственно максимальная возможная кинетическая энергия (π/Δx)2/2. Чтобы 2π/Δt было больше этой энергии, должно быть Δt<(4/π)Δx2, что и является точным условием устойчивости данной численной схемы.

Date: 2014-12-07 11:20 pm (UTC)
From: [identity profile] 109.livejournal.com
> метод расщепления эквивалентен замене постоянного потенциала импульсным, с бесконечно короткими импульсами, следующими с периодом Δt.

сорри, я не согласен. если бы мы делали вычисления чаще, и прилагали потенциал во временных точках, кратных Δt, и нулевой потенциал в остальных точках, это ещё было бы правдоподобно, именно по причине периодического приложения потенциала, отличного от "дефолта" (нулевого потенциала).

а так - нет, периодической систематической погрешности взяться неоткуда, если соблюдается условие про рельеф (т.е. Δt * dU/dx << Δx).

Date: 2014-12-07 11:39 pm (UTC)
From: [identity profile] antihydrogen.livejournal.com
Мы и прилагаем потенциал во временных точках, кратных Δt: формула exp(-iTΔt)exp(-iUΔt)exp(-iTΔt)exp(-iUΔt)...exp(-iTΔt)exp(-iUΔt)Ψ(0) есть решение временного уравнения Шредингера с потенциалом V(t)=UΔtδ(t-kΔt), где δ(t) - дельта-функция. А мы этой формулой аппроксимируем решение для постоянного потенциала, отчего и проблемы.
Edited Date: 2014-12-07 11:39 pm (UTC)

Date: 2014-12-08 05:00 am (UTC)
From: [identity profile] 109.livejournal.com
я не согласен. у нас нет никаких двух разных формул и двух разных потенциалов. мы берём формулу для непрерывного случая и численно аппроксимируем именно её (а не ту дискретную формулу, которую вы написали). появляющиеся при дискретизации ошибки обусловлены исключительно нелинейностью U. представьте себе случай (согласен, непрактичный, но тем не менее), когда U зависит от t и х линейно. Тогда ошибок аппроксимации вообще нет. и никаким синтетическим частотам, обратно пропорциональным Δt, взяться неоткуда.

Date: 2014-12-08 05:24 pm (UTC)
From: [identity profile] antihydrogen.livejournal.com
Ну я уже и не знаю, как еще вам объяснить. Но попробую еще раз - есть точная формула Ψ(t)=exp[-i(T+U)t]Ψ(0). Но мы не можем ее использовать, так как не умеем считать экспоненту от оператора T+U. Нам приходиться использовать вместо нее дискретную формулу, которую я написал, и "синтетические частоты" возникают именно из-за этой замены.

Date: 2014-12-08 03:12 pm (UTC)
From: [identity profile] 2born.livejournal.com
О, спасибо за ценное добавление!

Date: 2014-12-08 08:23 am (UTC)
From: [identity profile] korzhimanov.livejournal.com
Вопрос в том, а зачем сильно уменьшать пространственный шаг? Уже сама возможность посчитать УШ в 10 измерениях пусть и с посредственным пространственным шагом дорогого стоит.

Date: 2014-12-08 04:55 pm (UTC)
From: [identity profile] antihydrogen.livejournal.com
В принципе согласен.

Да и без принципа согласен тоже. Пусть погрешность аппроксимации такова, что проекция одночастичной приближенной функции на точную функцию равна 0.99. Тогда погрешность для системы 10 частиц будет порядка 1-0.99^10 = 10%, что для многих задач вполне терпимо. А вот для 100 частиц проекция 0.99^100=0.36, что уже есть признак наступающей "катастрофы ортогональности".

Date: 2014-12-09 02:08 pm (UTC)
From: [identity profile] korzhimanov.livejournal.com
Ах, вот в чём проблема. Тогда да, это принципиально.

Date: 2014-12-26 08:08 am (UTC)
From: [identity profile] ahiin.livejournal.com
Оффтопиком: с днем!

Date: 2014-12-26 01:18 pm (UTC)
From: [identity profile] antihydrogen.livejournal.com
Спасибо!

Date: 2014-12-26 09:32 am (UTC)
From: [identity profile] 2born.livejournal.com
C денем рождения, коллега! Всех вам благ!!!

Date: 2014-12-26 01:17 pm (UTC)
From: [identity profile] antihydrogen.livejournal.com
Спасибо!

Date: 2014-12-26 12:47 pm (UTC)
bisey: (Default)
From: [personal profile] bisey
С днем рождения!

Date: 2014-12-26 01:19 pm (UTC)
From: [identity profile] antihydrogen.livejournal.com
Спасибо!

Date: 2014-12-27 12:07 pm (UTC)
From: [identity profile] ratamaque.livejournal.com
С днём рождения!

Date: 2014-12-28 07:33 pm (UTC)
From: [identity profile] antihydrogen.livejournal.com
Спасибо!

Date: 2015-01-18 12:49 am (UTC)
From: [identity profile] beinikecy.livejournal.com
Another Code Pink group demonstrated without incident outside the home of CIA Director John Brennan, also in the Washington, DC suburb of McLean, as part of its Guantanamo Anniversary Weekend Torturers Tour Heritage Action for America, an offshoot of the more staid Heritage Foundation, came in for especial criticism, and when House Speaker John Boehner declared in December 2013 that the tea party-inspired groups had Бlost all credibility, Б it was clear whom he was talking about MEXICO CITY Reuters - The US Department of Transportation will soon be ready to consider lifting restrictions on Mexican trucking firms seeking to operate throughout the United States, Mexico s Communications and Transport Ministry said on Sunday Mexico and the United States have been lockedв Bubble Economy Part 1 of 5.
http://huntingcoloradostyle.com/content/imuran-order-cheap-usa-online-imuran-canadian-without-prescription
From: [identity profile] livejournal.livejournal.com
Пользователь [livejournal.com profile] kcp_frm сослался на вашу запись в своей записи «Квантовый компьютер для квантовых химиков (http://kcp-frm.livejournal.com/3612.html)» в контексте: [...] Оригинал взят у в Квантовый компьютер для квантовых химиков [...]
Page generated Jul. 27th, 2017 06:46 pm
Powered by Dreamwidth Studios