четверг, 5 апреля 2018 г.

Минимальность или экстремальность классического действия?

На днях неожиданно возник вопрос про минимальность классического действия \[ S\left[x\left(t\right)\right]=\intop_{0}^{T}dt\left[\frac{\dot{\boldsymbol{x}}^{2}}{2}-U\left(\boldsymbol{x}\right)\right] \] на классических траекториях $\boldsymbol{x}=\boldsymbol{x}_{0}\left(t\right)$. Как понимать сноску 2 на стр. 10 в первом томе ЛЛ " Следует, однако, указать, что в такой формулировке принцип наименьшего действия не всегда справедлив для всей траектории движения в целом, а лишь для каждого из достаточно малых её участков..." . Что понимается под "достаточно малыми" участками? Инфинитезимальные или конечные? Покажем, что второе. Точнее мы докажем, что при достаточно малых, но конечных $T$, действие является локальным минимумом в пространстве траекторий с фиксированными концами, т.е., строго увеличивается при малых вариациях $\boldsymbol{x}$, сохраняющих значения $\boldsymbol{x}\left(0\right)$ и $\boldsymbol{x}\left(T\right)$.

Пусть $\boldsymbol{x}=\boldsymbol{x}_{0}+\delta\boldsymbol{x}$, причем $\delta\boldsymbol{x}\left(0\right)=\delta\boldsymbol{x}\left(T\right)=0$, тогда имеем \[ S\left[\boldsymbol{x}\right]=S\left[\boldsymbol{x}_{0}\right]+\delta S=S\left[\boldsymbol{x}_{0}\right]+\intop_{0}^{T}dt\left[\frac{\left(\delta\dot{\boldsymbol{x}}\right)^{2}}{2}-\frac{1}{2}\partial_{i}\partial_{j}U\left(x_{0}\right)\delta x_{i}\delta x_{j}\right]\,, \] где мы опустили члены порядка $O\left(\delta x^{3}\right)$. Второй член может быть отрицательным, поэтому нам нужно доказать, что вклад первого члена больше для любых вариаций при достаточно малом $T$.

Пусть $\delta x_{max}=\left|\delta\boldsymbol{x}\left(t_{0}\right)\right|$ --- максимальное значение отклонения. Оцениваем: \[ \frac{1}{T}\intop_{0}^{T}dt\left(\delta\dot{\boldsymbol{x}}\right)^{2}\geqslant\left(\frac{1}{T}\intop_{0}^{T}dt\left|\delta\dot{\boldsymbol{x}}\right|\right)^{2}\geqslant\left(\frac{1}{T}\intop_{0}^{t_{0}}dt\delta\dot{\boldsymbol{x}}\right)^{2}=\left(\frac{\delta x_{\mathrm{max}}}{T}\right)^{2} \] Первое неравенство стандартно доказывается из $\frac{1}{T}\intop_{0}^{T}dt\left(\left|\delta\dot{\boldsymbol{x}}\right|-\frac{1}{T}\intop_{0}^{T}dt\left|\delta\dot{\boldsymbol{x}}\right|\right)^{2}\geqslant0$ раскрытием скобок. Таким образом, если мы возьмём \begin{equation}\label{Tcond} T<\frac{1}{\max\sqrt{\left|\partial_{i}\partial_{j}U\left(\boldsymbol{x}_{0}\right)\right|}}\,, \end{equation} то, очевидно, $\delta S>0$. Здесь \[ \left|\partial_{i}\partial_{j}U\left(\boldsymbol{x}_{0}\right)\right|=\max_{\boldsymbol{n},\boldsymbol{n}^{2}=1}\left|\left(\boldsymbol{n}\boldsymbol{\nabla}\right)^{2}U\left(x_{0}\right)\right|\,. \] Действительно, имеем \begin{align*} \delta S & =\intop_{0}^{T}dt\left[\frac{\left(\delta\dot{\boldsymbol{x}}\right)^{2}}{2}-\frac{1}{2}\partial_{i}\partial_{j}U\left(x_{0}\right)\delta x_{i}\delta x_{j}\right]\geqslant\frac{\left(\delta x_{\mathrm{max}}\right)^{2}}{2T}-\intop_{0}^{T}dt\frac{1}{2}\left|\partial_{i}\partial_{j}U\left(x_{0}\right)\delta x_{i}\delta x_{j}\right|\\ & \geqslant\frac{\left(\delta x_{\mathrm{max}}\right)^{2}}{2T}-\intop_{0}^{T}dt\frac{1}{2}\left|\partial_{i}\partial_{j}U\left(x_{0}\right)\right|\left(\delta\boldsymbol{x}\right)^{2}\geqslant\frac{\left(\delta x_{\mathrm{max}}\right)^{2}}{2T}\left(1-T^{2}\max\left|\partial_{i}\partial_{j}U\left(x_{0}\right)\right|\right)>0\,. \end{align*} Тут, конечно, есть формально вопрос, по какому множеству надо брать максимум  в уравнении \eqref{Tcond}. Если существует глобальный максимум, то можно взять его. Если же нет, то нужно учесть, что, когда мы будем уменьшать $T$, классическая траектория тоже будет меняться. Но она постепенно будет приближаться к прямой, соединяющей начальную и конечную точки, поэтому достаточно рассмотреть максимум по узкому цилиндру вблизи прямолинейной траектории.

Ещё удобнее при фиксированной траектории рассматривать действие на её кусках, как и предлагает ЛЛ. Ясно, что при делении траектории на всё меньшие и меньшие части $\max \left|\partial_{i}\partial_{j}U\left(\boldsymbol{x}_{0}\right)\right|$ для каждой части может только уменьшаться, а интервал времени обязательно уменьшается, поэтому легко найти требуемое разбиение.


 Конечно, как всегда, возможны патологические случаи, например, когда потенциал имеет излом на траектории. Однако, приведённые аргументы вполне дают представление о справедливости утверждения о минимальности классического действия и, в частности, о естественности названия "принцип наименьшего действия" в противоположность названию "принцип экстремального действия".

P.S. Кстати, если взять осциллятор, то мы увидим, что наша оценка довольно грубая --- в $\pi$ раз отличается от точной оценки. Ну, то есть уже при $T<\frac{\pi}{\omega}$ минимальность является обязательной, а у нас получилось $T<\frac1{\omega}$.

понедельник, 2 октября 2017 г.

Задача про неравенства Белла

Недавно придумал вот такую задачу:

Есть черная комната, из которой выносится пара пеналов, один синий, другой --- красный (для определённости). В каждом пенале есть по три отделения. Разрешается открыть по одному отделению в каждом пенале. После этого выносится следующая пара пеналов. Экспериментально установлено, что когда открываются одинаковые отделения в обоих пеналах (например, в обоих третье отделение), в одном обязательно находится один черный шар, а в другом --- белый. При этом в каждом пенале черный и белый шар выпадают с одинаковой частотой (вероятностью). Если же открываются разные отделения (например, отделение №1 в синем пенале и №2 в красном, но всё сказанное далее относится к любой паре отделений с несовпадающими номерами), то в них возможны все комбинации: чёрный-чёрный, чёрный-белый, белый-чёрный и белый-белый. Причём комбинации чёрный-чёрный и белый-белый выпадают с одинаковой вероятностью $p_1$, а комбинации чёрный-белый и белый-чёрный также равновероятны и имеют, соответственно, вероятность $p_2=\frac12-p_1$. Есть очевидные ограничения на $p_1$: $0<p_1<1/2$. Вопрос: можно ли получить более сильные ограничения на возможные $p_1$?

P.S. Эти ограничения как раз и являются неравенствами Белла для данного сетапа.

P.P.S. Надо бы картинки нарисовать поясняющие, но пока времени нету.

четверг, 10 августа 2017 г.

Гёмбёц

Недавно пытался придумать несколько задач для курса мат. анализа, которые не выглядели бы надуманными. То есть, я искал задачу, которая возникает время от времени в реальной жизни, но её решение требует знаний мат. анализа. Оказалось, что это совсем непросто. Либо задачи выглядят надуманными, либо не требуют для решения неэлементарных методов. Так что, должен признаться, ничего у меня толком не получилось. Но в процессе размышления придумал такую задачу
Доказать, что любая плоская выпуклая фигура с постоянной плотностью массы и гладкой границей имеет как минимум два устойчивых положения равновесия.
Сделаем два замечания: Во-первых, если отбросить требование постоянной плотности,
очевидно, легко любую выпуклую фигуру сделать неваляшкой с одним устойчивым равновесием и одним неустойчивым. Второе замечание --- обобщение утверждения на трёхмерье оказывается неверным (гуглить по слову в заголовке поста).

P.S. Пост был написан, наверное, с год. А с тех пор я пробовал дать эту задачу одному сильному фмшатнику. Он почти решил.

P.P.S. По воспоминаниям похожим образом решается ещё такая задача
Доказать, что фигура с минимальным периметром при фиксированной площади --- круг.
 И вот ещё

Доказать, что не существует устойчивых мыльных пузырей с топологией поверхности тора (т.е. в виде бублика).
Эту последнюю задачу я, впрочем, только в предположении цилиндрической симметрии умею решать.

понедельник, 24 апреля 2017 г.

Euclidea

Недавно поставил себе на телефон  Euclidea. Это игра, состоящая из задач на построение циркулем и линейкой. Когда-то я подумывал о том, что было бы неплохо сделать такую игру и подсадить на неё нынешнее поколение геймеров с тем, чтобы из них получились крутые геометры. Теперь, когда игра появилась, я её поставил с наивной уверенностью, что ни одна задача на построение циркулем и линейкой в тупик меня поставить не сможет. Ага, как же. Один маленький нюанс, оказалось, полностью меняет дело. Этот нюанс --- ограничение числа ходов. Под ходом понимается построение окружности циркулем или прямой линии линейкой. С учётом этого ограничения некоторые задачи казались мне просто неразрешимыми. Вот несколько примеров. В каждом случае заданное отмечено черным цветом, а построить требуется красное.
  1. (квадрат с заданной вершиной, вписанный в окружность с отмеченным центром за 7 ходов)
  2. (касательная к окружности с отмеченным центром в заданной точке за 3 хода)
  3. (равностороний треугольник с заданной вершиной, вписанный в окружность (центр не отмечен!) за 6 ходов)

пятница, 2 декабря 2016 г.

Формула суммирования Пуассона

Давным давно, когда был я чуть ли ещё не школьником, была у меня глупая привычка покупать научные книжки, даже если я и не очень понимал что в них написано. Одной из таких книжек (точнее, два тома) была монография “Упаковки шаров, решетки и группы” Конвея и Слоэна. Очень мне понравилась тогда бумага, на которой она напечатана — с одной стороны листа гладкая, а с другой — шершавая. И содержание тоже ничего было, хоть я тогда и много не понимал. И вот что меня поразило: оказывается, ко времени написания книжки не была доказана оптимальность даже гранецентрированной кубической упаковки в трёхмерье. Там, если я помню правильно, про эту оптимальность было написано как-то так: "все математики верят, а физики знают". Ещё я из этой книжки вынес, что размерности 8 и 24 --- какие-то особенные.

Так вот, оказывается, с тех пор многое изменилось. Оптимальность гранецентрированной кубической упаковки доказана в 1998 г. Томасом Халесом (Thomas Hales). А в начале этого года совсем молодая девушка-математик Марина Вязовска доказала оптимальность упаковки $\Lambda_8$ в восьмимерье (arXiv:1603.04246). И буквально через неделю вышла работа arXiv:1603.06518 с доказательством оптимальности упаковки для решётки Лича в 24-мерье, основанная на доказательстве в восьмимерье.

Работа Марины Вязовской концептуально очень ясная и опирается на ограничение на плотность упаковки сверху, полученному в работе arXiv:math/0110009. Это простое и, как оказывается, очень мощное ограничение доказывается с помощью формулы суммирования Пуассона. Если Фурье-преобразование функции $f(\boldsymbol{x})$ определить формулой \[\hat{f}\left(\boldsymbol{t}\right)=\int f\left(\boldsymbol{x}\right)e^{2\pi i\boldsymbol{x}\boldsymbol{t}}d\boldsymbol{x}\,,\]то справедлива следующая формула:\[\sum_{\boldsymbol{x}\in\Lambda}f\left(\boldsymbol{x}\right)=\frac{1}{\left|\Lambda\right|}\sum_{\boldsymbol{t}\in\Lambda^{*}}\hat{f}\left(\boldsymbol{t}\right)\,.\]Здесь $\Lambda$ — любая решётка в $\mathbb{R}^{n}$, $\left|\Lambda\right|$— объём её элементарной ячейки, $\Lambda^{*}$ — двойственная к $\Lambda$ решётка. Если не гнаться за строгостью, эту формулу можно доказать так: \[ \frac{1}{\left|\Lambda\right|}\sum_{\boldsymbol{t}\in\Lambda^{*}}\hat{f}\left(\boldsymbol{t}\right)=\frac{1}{\left|\Lambda\right|}\sum_{\boldsymbol{t}\in\Lambda^{*}}\int f\left(\boldsymbol{x}\right)e^{2\pi i\boldsymbol{x}\boldsymbol{t}}d\boldsymbol{x}=\int f\left(\boldsymbol{x}\right)\frac{1}{\left|\Lambda\right|}\sum_{\boldsymbol{t}\in\Lambda^{*}}e^{2\pi i\boldsymbol{x}\boldsymbol{t}}d\boldsymbol{x}=\int f\left(\boldsymbol{x}\right)\sum_{\boldsymbol{y}\in\Lambda}\delta\left(\boldsymbol{y}-\boldsymbol{x}\right)d\boldsymbol{x}=\sum_{\boldsymbol{x}\in\Lambda}f\left(\boldsymbol{x}\right)\,. \] Ну, естественно, чтобы формула имела смысл, нужно чтобы функция и её Фурье-образ достаточно быстро спадали на бесконечности. Если сдвинуть аргумент в правой части на $\boldsymbol{v}$, то из свойств Фурье-преобразования имеем \[ \sum_{\boldsymbol{x}\in\Lambda}f\left(\boldsymbol{x}+\boldsymbol{v}\right)=\frac{1}{\left|\Lambda\right|}\sum_{\boldsymbol{t}\in\Lambda^{*}}e^{-2\pi i\boldsymbol{v}\boldsymbol{t}}\hat{f}\left(\boldsymbol{t}\right)\,. \] Это как раз формула (2.1) из math/0110009. Далее доказывается следующая теорема. Допустим, что мы нашли функцию $f$ со следующими свойствами \begin{align*} 1. & f\left(\boldsymbol{x}\right)\leqslant0\text{ для }\left|\boldsymbol{x}\right|\geqslant1\\ 2. & \hat{f}\left(\boldsymbol{t}\right)\geqslant0\text{ для любого }\boldsymbol{t} \end{align*} Тогда центральная плотность (=число центров единичных шаров на единичный объём) периодических упаковок ограничена сверху величиной $\frac{f\left(0\right)}{2^{n}\hat{f}\left(0\right)}$. Вот такое неожиданное утверждение --- где функция, а где упаковка.
Доказательство совсем не сложное: пусть периодичность упаковки определяется решёткой $\Lambda$, причём в элементарной ячейке находится $N$ шаров. Для дальнейшего удобно считать, что радиус шаров равен $1/2$, так что расстояния между центрами любых двух не меньше единицы. Пусть расположение центров в элементарной ячейке задаётся векторами $\boldsymbol{v}_{1},\ldots,\boldsymbol{v}_{N}$. Запишем формулу суммирования Пуассона в таком виде \begin{equation} \sum_{j,k=1}^{N}\sum_{\boldsymbol{x}\in\Lambda}f\left(\boldsymbol{x}+\boldsymbol{v}_{j}-\boldsymbol{v}_{k}\right)=\sum_{j,k=1}^{N}\frac{1}{\left|\Lambda\right|}\sum_{\boldsymbol{t}\in\Lambda^{*}}e^{-2\pi i\left(\boldsymbol{v}_{j}-\boldsymbol{v}_{k}\right)\boldsymbol{t}}\hat{f}\left(\boldsymbol{t}\right)=\frac{1}{\left|\Lambda\right|}\sum_{\boldsymbol{t}\in\Lambda^{*}}\left|\sum_{k=1}^{N}e^{2\pi i\boldsymbol{v}_{k}\boldsymbol{t}}\right|^{2}\hat{f}\left(\boldsymbol{t}\right)\,.\label{eq:Poisson1} \end{equation} Аргумент $\boldsymbol{x}+\boldsymbol{v}_{j}-\boldsymbol{v}_{k}$ в левой части можно рассматривать как вектор, соединяющий центры шаров в точках $\boldsymbol{x}+\boldsymbol{v}_{j}$ и $\boldsymbol{v}_{k}$. Поэтому он может быть по модулю меньше единицы только если это один и тот же шар, т.е. $\boldsymbol{x}=0$, $j=k$. А значит, левая часть не больше $Nf\left(0\right)$. В правой части все слагаемые неотрицательны, поэтому она не меньше одного члена суммы с $\boldsymbol{t}=0$, т.е. $N^{2}\hat{f}\left(0\right)/\left|\Lambda\right|$. Поэтому получаем \[ Nf\left(0\right)\geqslant N^{2}\hat{f}\left(0\right)/\left|\Lambda\right| \] Поскольку наши шары имеют радиус $r=1/2$, центральная плотность равна $\delta=\frac{Nr^{n}}{\left|\Lambda\right|}=\frac{N}{\left|\Lambda\right|2^{n}}$ и мы имеем желаемое утверждение \[ \delta\leqslant\frac{f\left(0\right)}{2^{n}\hat{f}\left(0\right)}\,. \] А что же сделала Марина Вязовска? Она построила  для $\mathbb{R}^{8}$ такую функцию $f$, что выведенная оценка сверху оказывается совпадающей с плотностью решётки $\Lambda_8$, которая определяется как \begin{equation}\Lambda_8 = \left\{(x_i) ∈ \mathbb{Z}^8 \cup (\mathbb{Z}+1/2)^8 \bigg|\sum x_i = 0 (\mathrm{mod} 2)\right\}.\end{equation} Ясно, что это сделать ну очень непросто: те члены сумм в обеих частях равенства \eqref{eq:Poisson1}, которыми мы пренебрегали для получения неравенства, должны быть равны нулю чтобы позволить точное равенство. Кстати, уже из определения решётки $\Lambda_8$ видно, чем замечательно 8-мерное пространство. Расстояние между точками решетки $(0,0,0,0,0,0,0,0)$ и $(\frac12,\frac12,\frac12,\frac12,\frac12,\frac12,\frac12,\frac12)$ равно $\sqrt{2}$, как и расстояние между $(0,0,0,0,0,0,0,0)$ и $(1,1,0,0,0,0,0,0)$. Можно посчитать контактное число: \[240=4{8 \choose 2}+2+2{8 \choose 2}+{8\choose 4}\] Как построена требуемая функция напишу как-нибудь в другой раз.

среда, 18 мая 2016 г.

Квантовый параллелизм.

В начале прошлого года случилось поучаствовать в настоящей математической конференции по функциональным уравнениям. Я был приятно удивлен тем, что бо́льшая часть докладов оказалась вполне воспринимаема. Причина, конечно, не в том, что я такой умный — на физических конференциях очень часто из доклада я мало что могу понять — а в том, что математики больше стремятся сделать свой доклад понятным и меньше пускают пыль в глаза. Ну так мне показалось. И кроме меня был там еще один физик, который рассказывал про квантовый компьютер — а точнее, про запиленный им с соавторами эмулятор оного. На мой взгляд, доклад был совсем пустячный, но вот что интересно. В том месте где было гордо сказано, что после работы программы есть еще стадия считывания, на которой можно получить различные измеренные результаты с определенными вероятностями, я заметил среди слушателей искреннее недоумение. Подозреваю, что дело тут в неправильной подаче материала, призванной произвести эффект, а не сделать предмет понятным, но оставим это на совести докладчика.

 В черновиках моего блога есть материал, который я давно уже начал, но никак не могу закончить. Про алгоритм Шора для факторизации чисел на квантовом компьютере. Фактически, с этого алгоритма начался — а злые языки говорят, что и закончится — квантовый компьютер. Оригинальная статья написана хорошо и понятно, но мне хотелось объяснить этот алгоритм ещё более просто — так чтобы могли прочитать и понять студенты (хотя бы те, которые раз прослушали его в моём исполнении). Поскольку пост завяз, я решил откусить часть изложения и поместить в отдельный пост, это и делаю.

Когда говорят про алгоритм Шора, вспоминают принцип суперпозиции в квантовой механике, позволяющий якобы эффективно проводить вычисления параллельно сразу для всех возможных входных данных. Вот про этот параллелизм и пойдёт речь. Как я уже объяснял где-то в этом блоге, "память" квантового компьютера представляет из себя т.н. q-регистр, состоящий из нескольких q-бит. Каждый q-бит — двухуровневая система, состояние которой описывается спинором — вектором в пространстве $\mathbb{C}^2$, а еще лучше сказать  в $\mathbb{CP}^1$. q-бит может находиться не только в состояниях $\mathbf{1}={1 \choose 0} $ и $\mathbf{0}={0 \choose 1} $, но и в произвольной их суперпозиции с комплексными коэффициентами.

Важно, что когда q-биты сгруппированы в q-регистр, состояние последнего уже описывается вектором в тензорном произведении пространств, соответствующих отдельным q-битам. Если наш q-регистр состоит из $n$ q-битов, то его состояние есть суперпозиция $2^n$ базисных состояний, каждое из которых естественно нумеровать $n$-значным двоичным числом, то есть базисные векторы будем обозначать как\[|\underbrace{01011\ldots}_{n \text{ разрядов}}\rangle\] Система команд квантового компьютера обычно включает однобитные и двухбитные унитарные преобразования — гейты (в русской литературе вентили). Вычисление состоит из применения заданной последовательности гейтов (задание этой последовательности и является "программой"), и его удобно изображать диаграммой, в которой каждому q-биту соответствует горизонтальная линия, однобитовым гейтам — блобы на ней, а двухбитовым — блобы с коннекторами. Не буду загромождать эту заметку описанием стандартных гейтов и диаграммной техники, так как это нормально написано и в английской Википедии. Замечу мимоходом, что использование диаграмм для наглядного представления "частичных" преобразований в тензорных произведениях пространств является очень стандартным приёмом, который, к тому же, может найти и совершенно неожиданные применения (ну, для меня неожиданные, а кто-то с ними ест и спит).

Нам для рассуждений понадобится только преобразования — NOT, CNOT и CCNOT (т.н. Toffoli gate). Первое является однобитовым отрицанием, второе — двухбитным преобразованием, которое инвертирует или не инвертирует второй бит в зависимости от того установлен или нет первый. Третье преобразование является трёхбитным и сводится к инверсии третьего бита в случае, если оба первых установлены. Его можно реализовать как последовательность бвухбитных, но сейчас не о том речь. Достаточно определить эти преобразования для базисных состояний одного, двух или трёх q-битов, а для произвольных состояний, конечно, всё будет определено по линейности.

Напомню, что важным свойством квантовых вычислений является их обратимость. То есть, зная программу и результат всегда можно восстановить входные данные. Это свойство (очевидное из определения вычисления, как унитарного преобразования) очень сильно отличает квантовый компьютер от классического, поскольку одной из основных операций классического вычисления является присваивание, теряющее информацию о состоянии переменной (бита) до присваивания.

Другое отличие состоит в том, что считывание информации из q-регистра, или из отдельных его битов, абсолютно непохоже на классическое. Если в классическом регистре можно всегда безнаказанно считать любой бит, не изменив его состояние, то в q-регистре так, хотя бы в принципе, можно сделать для q-битов, находящихся строго в одном из базисных состояний $0$ или $1$ (тут педанты могут меня поправить, что достаточно знать, что кубит находится в одном из двух ортогональных состояний). В остальных случаях: а) результат считывания не определён (например, для одного бита можно получить с определенными вероятностями и $0$ и $1$) и б) после считывания состояние q-регистра меняется. Поэтому обычно считывание происходит только один раз — в конце вычисления. Отсюда, скажем, следует, что инструкция ветвления if (x==1) then do something не может быть буквально перенесена в квантовую программу, поскольку, по-крайней мере в классическом вычислении, предполагает считывание значения x. Но тем не менее, есть утверждение о том, что все логические операции можно реализовать с помощью одной — например, с помощью NAND(A,B)=NOT(AND(A,B)). Доказательство этого утверждения сводится к набору упражнений на построение остальных операций из NAND. Вот, например,отрицание NOT(A) строится как NAND(A,A). На всякий случай, напомню, что арифметические операции можно легко построить из логических. Конечно, вопрос про копирование в классических вычислениях не задаётся — считается, что это и не операция вовсе.

Значит, чтобы научиться выполнять классические программы на квантовом компьютере, мы должны понять как выглядят аналоги копирования и операции NAND. Оба эти вопроса решаются использованием дополнительных предустановленных битов (или предсброшенных). Вот скажем, если есть предусмотрительно запасённый бит C в состоянии $0$, мы в него можем скопировать другой бит A, просто выполнив преобразование CNOT(A,C). Также в этот бит можно поместить NAND(A,B). Просто нужно выполнить программу NOT(C);CCNOT(A,B,C). Первая инструкция инвертирует бит C,  а вторая выполняет Toffoli gate, "помещая" в C результат вычисления XOR(C,AND(A,B))=XOR(1,AND(A,B))=NAND(A,B).

Таким образом, если у нас есть некоторый классический алгоритм вычисления функции $f(x)$ для любого заданного двоичного $n$-значного числа $x$, мы можем написать P программу для квантового компьютера, которая вектор состояния $|x,0,\ldots\rangle$ переводит в $|x,f(x),g(x)\rangle$ где $g(x)$ обозначает испорченные в процессе вычисления вспомогательные q-биты. Отметим, что эта испорченность зависит от $x$.

Наконец мы готовы обсудить квантовый параллелизм. Итак, пусть у нас есть q-регистр, находящийсяв состоянии \[\frac1{2^{n/2}}\sum_x|x,0,\ldots\rangle\] Благодаря линейности квантовых преобразований, ранее упомянутая программа P переведёт этот вектор в \[\frac1{2^{n/2}}\sum_x|x,f(x),g(x)\rangle\,,\] где $f(x)$ — полезная функция, а $g(x)$ — мусор.

Так вот, одно из объяснений в статье Шора, которое я при поверхностном прочтении статьи и не понял, и ради которого, собственно, и писал эту заметку, касается того, как этот мусор убрать, не нарушая квантовую когерентность. Идея простая до безобразия (и оттого особенно красивая) состоит в том, чтобы после получения результата "скопировать" его в чистую область памяти, а затем произвести "undo" всей программы P. То есть, если программа P осуществляет унитарное преобразование $U$, то мы делаем такую последовательность действий: \begin{multline}\frac1{2^{n/2}}\sum_x|x,0,\ldots\rangle\stackrel{U}{\longrightarrow} \frac1{2^{n/2}}\sum_x|x,f(x),g(x),0,\ldots\rangle \\ \stackrel{\text{copy}}{\longrightarrow}\frac1{2^{n/2}}\sum_x|x,f(x),g(x),f(x)\rangle \stackrel{U^{-1}}{\longrightarrow}\frac1{2^{n/2}}\sum_x|x,0,\ldots,0,f(x)\rangle \end{multline} При беглом прочтении я никак не мог взять в толк, зачем нужно заботиться об обнулении вспомогательных битов.

Кажется, что мы наконец-то получили параллельное вычисление сразу для всех возможных входных данных, и если бы у нас был механизм определения вектора состояния, то это, конечно, так и было бы. Но тут в игру вступает квантовая механика, которая как-бы говорит "Хоть я и знаю всё, отвечу я только на один твой вопрос — задавай". То есть, попытка измерения разрушит когерентность и даст $f(x)$ только для одного значения $x$, причём, выбрать, для какого конкретно, не удастся. Так что, как использовать такой параллелизм — это ещё надо подумать. Но об этом напишу отдельно.

P.S. Кстати, про "один вопрос" вспомнился такой заумный анекдот:
На заседание философского общества спустился с неба ангел, и предложил философам ответить на любой их вопрос, но только на один. Философы начали спорить о том, какой вопрос задать. Ангел сказал: "ну вы тут решайте, я завтра вернусь и спросите". Некоторые философы предлагали связать несколько вопросов конъюнкцией, но другие возражали, что ангел не согласится считать это одним вопросом. Один философ предложил спросить ангела: "Какой вопрос самый лучший?", и потом, зная вопрос, подождать, пока не прилетит другой ангел в будущем. Но другие философы возражали, что не факт, что визит когда-либо повторится, и жалко тогда терять этот шанс. Наконец, философы договорились, и когда ангел вернулся на следующий день, задали ему следующий вопрос: "Какова упорядоченная пара, первый элемент который является лучшим вопросом, который можно задать ангелу, а второй элемент - ответом на этот вопрос?" Ангел тут же ответил: "Это упорядоченная пара, первым элементом которой является вопрос, который вы только что задали, а вторым - ответ, который я вам даю". И исчез.

вторник, 26 апреля 2016 г.

Состояния фон Неймана-Вигнера


Квантовую механику я учил как раз четверть века назад. С тех пор и аж до 2011 года пребывал в наивной уверенности в том, что состояния непрерывного спектра обязательно ненормируемы. Но когда занимался задачей про квазилокализованные состояния, про которую я когда-то писал, обнаружил, что это не так. Еще на заре квантовой механики Вигнер и фон Нейман придумали пример нормируемых состояний непрерывного спектра.


Рассмотрим, например, такой потенциал\begin{equation*} V(x)=\left\{\begin{array}{rl}-\frac{\sin x (8 x \cos x-5 \sin x+\sin 3 x)}{x^2}& x>0&\\ \infty & x\leq 0\end{array}\right.\end{equation*}
Потенциал (заштрихован), энергия и волновая функция.
Потенциал на бесконечности стремится к нулю, поэтому при $E>0$ естественно ожидать непрерывный спектр. Подстановкой можно проверить, что у уравнения Шредингера\begin{equation*}
k^2\psi=-\frac{d^2\psi}{dx^2}+V(x)\psi
\end{equation*} при $k=1$ есть точное решение \begin{equation*}
\psi=\frac{e^{\text{Ci}(2 x)} \sin (x)}{x},
\end{equation*}где $\text{Ci}(x)$ --- интегральный косинус. Соответствующая этому решению плотность при больших $x$ убывает как $1/x^2$, поэтому интеграл от нее сходится, и мы получаем нормируемое решение. Физическая причина нерасплывания волновой функции состоит в том, что горбы потенциала эффективно отражают частицу так, что вероятность ее убегания на бесконечность равна нулю. Из картинки видно, что максимумы вероятности находятся слева от каждого горба.

В моём примере энергия нормируемого состояния меньше, чем высота первого горба, но если я правильно помню, то можно подобрать и потенциал, в котором нормируемое состояние имеет энергию выше любого его горба.