Задача

Придумал сегодня красивую задачку:

Пусть $M$ — квадратная матрица $n\times n$, чьи элементы — рациональные числа. Если её характеристический полином \[\lambda^{n}+c_{n-1}\lambda^{n-1}+\ldots+c_{0}
\] имеет хотя бы один нецелый коэффициент $c_{k}$, то ясно, что никаким преобразованием подобия \[T: M\to T^{-1}MT\] матрицу не сделать целочисленной. Вопрос: верно ли обратное: пусть все $c_{k}$ — целые. Всегда ли существует преобразование подобия $T$, переводящее матрицу в целочисленную?

Две задачи по ТФКП

Задачи на одну тему, но забавные.

• Рассмотрим интеграл \[ I\left(n,m\right)=\oint_{C}\frac{dx}{2\pi i}\left(\frac{4x+9+5\sqrt{x^{2}+9}}{(x-4)^{2}}\right)^{n}P^{\left(m\right)}\left(x\right)\,, \] где $C$ --- маленький круг с центром в точке $x=4$, $P^{\left(m\right)}\left(x\right)=a_{m}x^{m}+a_{m-1}x^{m-1}+\ldots+a_{0}$ --- полином $m$-ого порядка, $n$ --- целое положительное число. Вычислить $I\left(n,m\right)$ для $m<n-1$.
• Вычислить для $n\in \mathbb{N}$ \[ \operatorname{Res}\limits_{x=2}\frac{1}{x\sqrt{x^{4}+9}}\left(\frac{25x^{2}+100x+44}{5\sqrt{x^{4}+9}-16x+7}\right)^{n}\,. \]

Клин 2

Как известно, терема Римана об отображении позволяет однозначно отобразить любую односвязную область комплексной плоскости на верхнюю полуплоскость с помощью голоморфной функции $f(z)=u(x,y)+i v(x,y)$.

Вчера впал в десятисекудный клин, пытаясь сопоставить такие утверждения:

1. $v$ равно нулю на границе области (в плоскости $z$).
2. $\Delta v =0$ внутри области.
3. $v$ не равно нулю внутри области.
4. Ну, и принцип максимума, конечно. 

Вот что значит не задумывался. Или задумывался, но забыл?

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

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

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

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

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

Когда говорят про алгоритм Шора, вспоминают принцип суперпозиции в квантовой механике, позволяющий якобы эффективно проводить вычисления параллельно сразу для всех возможных входных данных. Вот про этот параллелизм и пойдёт речь. Как я уже объяснял где-то в этом блоге, "память" квантового компьютера представляет из себя т.н. 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. Кстати, про "один вопрос" вспомнился такой заумный анекдот:

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

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

Квантовую механику я учил как раз четверть века назад. С тех пор и аж до 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$, поэтому интеграл от нее сходится, и мы получаем нормируемое решение. Физическая причина нерасплывания волновой функции состоит в том, что горбы потенциала эффективно отражают частицу так, что вероятность ее убегания на бесконечность равна нулю. Из картинки видно, что максимумы вероятности находятся слева от каждого горба.

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

Визуальное решение задач на построение

Для профилактики слабоумия начал опять решать задачи на Diofant.ru. Вчера вот такую задачу увидел

ЗАДАЧА 981 (Diofant.ru). Перпендикуляр к диаметру 'Дана окружность o и прямая линия l, которая проходит через ее центр. На окружности отмечена точка A, не лежащая на прямой. При помощи одной линейки без делений постройте перпендикуляр от точки к прямой.

Для решения таких задач я использую свой скрипт. Решить-то я решил, но поскольку задача проверяется в ручном режиме, надо было еще написать решение. Поэтому вчера я немного допилил скрипт (если кому-то интересно, смотреть как его подключить в коде) и теперь он худо-бедно документирует действия. Вот, можно попробовать решить вышеупомянутую задачу. Точки на пересечениях двух объектов ставятся их последовательным выделением (при включенном инструменте line).

---

Задание в методичку по квантовому программированию.

Есть квантовый компьютер с памятью 3 кубита. Определим однобитовые гейты\[\mathrm{H1}=\mathrm{Not}=\left(\begin{array}{cc}0&1\\1&0\end{array}\right)\,,\quad \mathrm{H2}=\mathrm{H}=\frac1{\sqrt{2}}\left(\begin{array}{cc}1&1\\1&-1\end{array}\right)\,,\quad \mathrm{H3}=\frac1{\sqrt{3}}\left(\begin{array}{cc}\sqrt{2}&1\\1&-\sqrt{2}\end{array}\right)\]
и их  управляемые варианты $\mathrm{cnH1}\,,\ \mathrm{cnH2}\,,\ \mathrm{cnH3}$, которые выполняют над битом соответствующее преобразование только если остальные два бита равны единице.
Система комманд нашего компьютера состоит из четырех комманд: $\mathrm{H1}\,,\ \mathrm{cnH1}\,,\ \mathrm{cnH2}\,,\ \mathrm{cnH3}$. Надо написать алгоритм, который при подаче на вход двоичного числа от 0 до 7 строит состояние (с определенным спином и проекцией) с соответствующим номером:

0. $\sqrt{1/2}(|001\rangle-|010\rangle)$
1. $\sqrt{1/2}(|101\rangle-|110\rangle)$
2. $\sqrt{1/6}(|001\rangle+|010\rangle-2|100\rangle)$
3. $\sqrt{1/6}(|101\rangle+|110\rangle-2|011\rangle)$
4. $|000\rangle$
5. $\sqrt{1/3}(|001\rangle+|010\rangle+|100\rangle)$
6. $\sqrt{1/3}(|101\rangle+|110\rangle+|011\rangle)$
7. $|111\rangle$

Здесь можно потренироваться:

---

Boilerplate

Your Program

Квантовые программисты

Все, наверное, слышали о квантовых компьютерах, которые, ну вот совсем скоро, будут созданы и будут решать все задачи, которые обычным, классическим компьютерам не по зубам. Я о них, видимо, в первый раз услышал где-то году в 97, сразу после прослушивания лекций по криптографии, в которых как раз объяснялась криптосистема с открытым ключом, основанная на сложности задачи факторизации. Поэтому важность алгоритма Шора я понял довольно быстро и при случае гордо объяснял всю историю.
Замечу, что никогда ни на одну секунду я не допускал, что реальный квантовый компьютер  будет создан в обозримом будущем (ну, скажем, лет за сто). Под "реальным квантовым компьютером" я понимаю, конечно, устройство, способное успешно конкурировать с обычными классическими компьютерами, а не просто раскладывать на множители число 15. Однако новости от компании D-wave, если им верить, показывают, что пора уже подумать о новой специальности в CS --- квантовый программист, а азы квантовой информатики нужно учить в школах и детских садах.

Ниже --- мой вклад в дело ликвидации квантовой компьютерной безграмотности. Это симулятор двухбитного квантового компьютера с набором комманд {Not,H,cNot,cH}, где две первые комманды --- однобитовые квантовые гейты, а две последние --- двухбитовые. Полноценную программу писать пока нельзя (возможно, в последующих постах это будет реализовано), так что работать можно в интерактивном режиме. Задача --- написать программу производящую определенное преобразование над входными данными. Сейчас объясню какое.

Кубит, как известно, --- двухуровневая квантовомеханическая система, и одной из ее естественных реализаций (хотя, возможно, не на практике) является спин 1/2. Нолик и единица представляются как \[|0\rangle=|\downarrow\rangle\,,\quad |1\rangle=|\uparrow\rangle\,.\] Квантовый регистр (так сказать, курегистр), соответственно, это набор кубитов, которые могут находится в запутанных состояниях. Квантовое вычисление состоит в выполнении некоторого преобразования над курегистром. Напомним, кстати, важное отличие квантового вычисления от классического. В классическом вычислении одной из самых популярных операций является операция присваивания. Можно присвоить любому биту заданное значение ноль или единица. В частности, можно очистить регистр, присвоив всем его битам значение ноль. В квантовом вычислении операция присваивания невозможна, поскольку она нарушает унитарность. То же самое можно сказать и про операцию копирования. А вот операция инверсии бита Not, которая меняет ноль на единицу, и наоборот --- возможна. В значительной степени последствия унитарности можно описать как обратимость любого вычисления: зная output и зная программу вычисления можно однозначно восстановить input (в частности, в процессе квантового вычисления ничего нельзя стереть бесследно). Нужно, правда, сказать, что унитарность, и, в частности, обратимость не сильно мешают для симуляции классических вычислений. Просто надо добавить дополнительные биты, заранее установленные в определенное состояние. Кстати, легко сообразить, что максимально необходимое число дополнительных битов равно числу основных.

 Итак, любое квантовое вычисление является унитарным преобразованием над курегистром.
Унитарное преобразование может затрагивать один или несколько битов. Важно, что любое унитарное преобразование может быть реализовано как суперпозиция одного типа двухбитного преобразования, cNot, и однобитных преобразований общего вида. С учетом линейности этих преобразований, их можно задать действием на базисные состояния: \[\mathtt{cNot}_{i,j}: |0_i,q_j\rangle\to |0_i,q_j\rangle\,,\quad |1_i,q_j\rangle\to |1,\bar{q}_j\rangle\,,\]
\[\left(\begin{array}{2}a&b\\c&d\end{array}\right)_{i}: |0_i\rangle\to a|0_i\rangle+b|1_i\rangle\,,\quad |1_i\rangle\to c|0_i\rangle+d|1_i\rangle\,.\] Здесь $\bar{0}=1\,,\ \bar{1}=0$, а во второй строчке $\left(\begin{array}{2}a&b\\c&d\end{array}\right)$ --- унитарная матрица. Операции $\mathtt{Not}$ и $\mathtt{H}$ являются частными случаями однобитовых операций: \[\mathtt{Not}_i=\mathtt{X}_i=\left(\begin{array}{2}0&1\\1&0\end{array}\right)_{i}\,,\quad \mathtt{H}_i=\left(\begin{array}{2}1/\sqrt{2}&1/\sqrt{2}\\1/\sqrt{2}&-1/\sqrt{2}\end{array}\right)_{i}\]
Операцию $\mathtt{cNot}$ удобно записать через проекторы: \[\mathtt{cNot}_{i,j}=\mathtt{P}^0_i\otimes \mathtt{I}_j+\mathtt{P}^1_i \otimes \mathtt{Not}_j\,,\] где $\mathtt{P}^0_i=\left(\begin{array}{2}0&0\\0&1\end{array}\right)_i\,,\,\,  \mathtt{P}^1_i=\left(\begin{array}{2}1&0\\0&0\end{array}\right)_i$. Используя свойства проекторов легко проверить, что  $\mathtt{cNot}$ -- действительно унитарная операция.  Для удобства наш квантовый процессор в числе комманд будет иметь еще одну двухбитовую унитарную операцию \[\mathtt{cH}_{i,j}=\mathtt{P}^0_i\otimes \mathtt{I}_j+\mathtt{P}^1_i \otimes \mathtt{H}_j\,,\]
Ну вот, теперь можно сформулировать и задачу. На вход программы подаются запутанные состояния двух кубитов, соответствующие определенным спинам и проекциям спина системы: \[|S=0,S_z=0\rangle=\frac1{\sqrt{2}}\left(|01\rangle-|10\rangle\right)\]
\[|S=1,S_z=-1\rangle=|00\rangle,\quad |S=1,S_z=0\rangle=\frac1{\sqrt{2}}\left(|01\rangle+|10\rangle\right), \quad |S=1,S_z=1\rangle=|11\rangle.\]
Наша задача --- придумать алгоритм, который переставляет по циклу проекции. То есть, программа, получив на вход состояние $|S,S_z\rangle$  с $S_z<S$ должна выдавать состояние $|S,S_z+1\rangle$, а состояние  $|S,S_z=S\rangle$ должна переводить в $|S,S_z=-S\rangle$.
Интерфейс такой: чтобы провести двухбитовую операцию (cNot или cH), нажимаем сначала на кнопку над первым битом, а затем над вторым. Однобитовые операции (Not или H) получаются двойным нажатием одной кнопки. Когда состояние уже такое, какое требуется, оно выделяется зеленым цветом. Например, $|S=0,S_z=0\rangle$ сразу зеленое, так как оно должно остаться на месте.

---

→

Desired result test1 1 |1⟩ |1⟩ test2 √1/2 |0⟩ |1⟩ √1/2 |1⟩ |0⟩ test3 1 |0⟩ |0⟩ test4 -√1/2 |0⟩ |1⟩ √1/2 |1⟩ |0⟩

Про числа и игры

Что-то стал за собою замечать, что совсем разучился в качестве отдыха и развлечения читать художественную литературу. Вместо этого читаю какие-нибудь книжки по математике, которые поинтереснее и, по возможности, попроще.

Вот, недавно стал читать книгу Конвея "О числах и играх". Много лет назад прочитал вот здесь про комбинаторную теорию в Го. В частности, прочитал про инфинитезимали, и это было круто. Сейчас решил перечитать, и нашел ссылку на Конвея. Вот цитата из первого параграфа:

 "Дедекинд (а до него автор — как считается, Евдокс — пятой книги Евклида) строил вещественные числа из рациональных. Его метод заключался в том, чтобы разделить рациональные числа на два множества L и R так, чтобы ни одно число из L не было больше никакого числа из R, и использовать это "сечение" для определения нового числа {L | R} в случае, если ни L и R не имеют экстремальной точки." 

Фактически, вот это самое дедекиндовское определение и берется далее за основу:

"Если L, R —  два множества чисел, и ни один элемент из L не  ⩾ любого элемента из R, то есть число {L | R}. Все числа строятся таким образом."

Отличие от дедекиндовского определения в том, что никаких чисел adhoc вводить не требуется. Конечно, еще нужно определить отношение ⩾ для таких чисел и операцию сложения (интересующимся смотреть книжку). Последняя позволяет отождествить определяемые числа с нормальными. Например, ноль выглядит как {∅ |∅}={|}. Вообще, одно и то же число можно представить разными способами, но это не страшно, с обыкновенными дробями тоже так.
Но, конечно, самое интересное начинается, если рассматривать пары {L|R}, в которых нет условий на элементы. Получаем определение комбинаторных игр на двоих:

"Если L, R —  два множества игр, то есть игра {L | R}. Все игры строятся таким образом."

Игры тоже можно складывать и вычитать. Числа в этом подходе — частный случай игр. А есть игры, числами не являющиеся, в частности, упомянутые инфинитезималы. Но про это как-нибудь в другой раз.

 Ну, и скрипт, конечно. Кстати, обнаружил, что поддерживается ползунок —   <input type="range" min="0" max="10"... />.

---

Двоичное число		результат
		-1.1

Эффект Ааронова-Бома и суперсимметрия (продолжение)

Это продолжение предыдущего поста. Вот его краткое содержание. Рассматривая гамильтониан частицы в поле соленоида \[ \mathrm{H}=\frac{\boldsymbol{\pi}^{2}}{2m}-\mu\sigma_{z}H_{z}, \] мы заметили, что при $g=4\mu m/e=2$ его можно записать в виде $\mathrm{H}=2Q_{1}^{2}=2Q_{2}^{2}$, где $Q_{1}=\boldsymbol{\sigma}\cdot\boldsymbol{\pi}/2\sqrt{m}$ и $Q_{2}=-i\sigma_{z}Q_{1}$ --- антикоммутирующие операторы.
Радиальное уравнение выглядит так \begin{equation} -P^{\prime\prime}\left(\rho\right)-\frac{1}{\rho}P^{\prime}\left(\rho\right)+\left(\frac{W\left(\rho\right)^{2}}{\rho^{2}}+\frac{\sigma}{\rho}W^{\prime}\left(\rho\right)\right)P\left(\rho\right)=k^{2}P\left(\rho\right)\label{eq:Pequation-2} \end{equation} Функция $W\left(\rho\right)$ зависит от распределения поля в соленоиде и обладает свойствами \[ W\left(0\right)=M,\quad W\left(\rho>R\right)=W=M-\Phi/\Phi_{0}\,. \] Благодаря суперсимметрии, нам удалось найти одно из решений этого уравнения в пренебрежении правой частью (т.е., при $\rho\ll1/k$): \begin{equation} P_{1}\left(\rho\right)=\exp\left[\sigma\int_{0}^{\rho}\frac{d\rho}{\rho}W\left(\rho\right)\right]\label{eq:sol} \end{equation} Тут следует заметить, что интеграл в экспоненте расходится на нижнем пределе если только $M\neq0$. Поэтому лучше писать, скажем, так \begin{equation} P_{1}\left(\rho\right)=\exp\left[\sigma\int_{R}^{\rho}\frac{d\rho}{\rho}W\left(\rho\right)\right]\label{eq:sol-2} \end{equation} Далее есть четыре различных случая \begin{align*} \mathrm{I}. & \sigma M\geq0\&\sigma W>0,\\ \mathrm{II}. & \sigma M\geq0\&\sigma W<0,\\ \mathrm{III}. & \sigma M<0\&\sigma W>0,\\ \mathrm{IV}. & \sigma M<0\&\sigma W<0. \end{align*} В случаях $\mathrm{I}$ и $\mathrm{II}$ функция $P_{1}\left(\rho\right)$ ведет себя при $\rho\to0$ как $\rho^{\left|M\right|}$, как и следует, конечно. При этом в случае $\mathrm{II}$ при $\rho>R$ мы получаем аномальное поведение $\rho^{-\left|W\right|}$, за которым мы, собственно, и охотились.
В случаях $\mathrm{III}$ и $\mathrm{IV}$ функция $P_{1}\left(\rho\right)$ ведет себя при $\rho\to0$ похабно --- как $\rho^{-\left|M\right|}$, что нас, конечно, не устраивает. Найдем второе решение, имеющее в нуле правильную асимптотику. Ищем его методом вариации постоянных \begin{equation} P_{2}\left(\rho\right)=C\left(\rho\right)P_{1}\left(\rho\right)\label{eq:sol-1} \end{equation}  Для функции $C\left(\rho\right)$ имеем уравнение \begin{equation} C^{\prime\prime}\left(\rho\right)+2C^{\prime}\left(\rho\right)\frac{\sigma}{\rho}W\left(\rho\right)+\frac{1}{\rho}C^{\prime}\left(\rho\right)=0\label{eq:Pequation-2-1} \end{equation} Считая выполненным условие $\sigma M<0$, получаем \begin{align*} C^{\prime}\left(\rho\right) & =\frac{1}{R}\exp\left[-\int_{R}^{\rho}\frac{d\rho}{\rho}\left(2\sigma W\left(\rho\right)+1\right)\right]=\frac{1}{\rho}\exp\left[-2\sigma\int_{R}^{\rho}\frac{d\rho}{\rho}W\left(\rho\right)\right]\\ C\left(\rho\right) & =\int_{0}^{\rho}\frac{d\rho}{\rho}\exp\left[-2\sigma\int_{R}^{\rho}\frac{d\rho}{\rho}W\left(\rho\right)\right] \end{align*} Легко определить зависимость коэффициента $C$ при $\rho\to0$: интеграл в показателе экспоненты равен $-2\sigma M\ln\rho+\mathrm{const}$, поэтому $C\left(\rho\right)\sim\rho^{-2\sigma M}=\rho^{2\left|M\right|}$. Соответственно, $P_{2}\left(\rho\right)\sim\rho^{\left|M\right|}$, как и следует.
Теперь определим поведение коэффициента $C$ при $\rho>R$: \begin{align*} C & =\int_{0}^{R}\frac{d\rho}{\rho}\exp\left[-2\sigma\int_{R}^{\rho}\frac{d\rho}{\rho}W\right]+\frac{1}{2\sigma W}\left(1-\left(\frac{\rho}{R}\right)^{-2\sigma W}\right)\\  & \sim\begin{cases} \rho^{0} & \text{при }R\ll\rho\ll1/k\text{ для случая }\mathrm{III}\\ \rho^{2\left|W\right|} & \text{при }R\ll\rho\ll1/k\text{ для случая }\mathrm{IV} \end{cases} \end{align*} Учитывая, что \[ P_{1}\left(\rho\right)\sim\rho^{\sigma W}=\begin{cases} \rho^{\left|W\right|} & \text{при }R\ll\rho\ll1/k\text{ для случая }\mathrm{III}\\ \rho^{-\left|W\right|} & \text{при }R\ll\rho\ll1/k\text{ для случая }\mathrm{IV} \end{cases}, \] получаем, что нужное нам решение $P_{2}\left(\rho\right)$ для обоих случаев $\mathrm{III}$ и $\mathrm{IV}$ при $R\ll\rho\ll1/k$ ведет себя как $\rho^{\left|W\right|}$.
Резюмируя, можно сказать, что аномальное поведение радиальной волновой функции в пределе $R\to0$ наблюдается только в случае $\mathrm{II}$, т.е., при $\sigma M\geq0\&\sigma W<0$. В случаях же $\mathrm{III}$ и $\mathrm{IV}$ состояние не зануляется действием операторов $Q_{1,2}$.

Эффект Ааронова-Бома и суперсимметрия

Рассмотрим нерелятивистскую частицу в поле соленоида. Гамильтониан Паули выглядит так:\[ \mathrm{H}=\frac{\boldsymbol{\pi}^{2}}{2m}-\mu\boldsymbol{\sigma}\cdot\mathbf{H}, \]Здесь $\boldsymbol{\pi}=\mathbf{p}-e\mathbf{A}$ --- удлиненный импульс. Поле точечного соленоида имеет вид\[ \mathbf{A}=\frac{\Phi}{2\pi}\frac{\mathbf{e}_{z}\times\mathbf{r}}{\rho^{2}}. \]Зависимость волновой функции от $z$ тривиальна и далее мы соответствующую часть гамильтониана не рассматриваем. В частности, мы считаем далее, что $\mathbf{p}=\left(p_{x},p_{y}\right)$. Переменные разделяются в координатах $\rho,\phi$ и, если искать решение в виде $\psi=e^{iM\phi}P\left(\rho\right)$, получим на функцию $P\left(\rho\right)$ уравнение\begin{equation} P^{\prime\prime}+\frac{1}{\rho}P^{\prime}+\left(k^{2}-\frac{\left(M-\Phi/\Phi_{0}\right)^{2}}{\rho^{2}}\right)P=0\label{eq:Pequation} \end{equation}Здесь $\Phi_{0}=\frac{2\pi\hbar c}{e}$ --- квант магнитного потока. Поскольку магнитное поле отсутствует во всей области $\rho>0$, это уравнение имеет одинаковый вид для частицы с любым спином. Будем считать, что $W=M-\Phi/\Phi_{0}$ не является целям числом. Решения уравнения (\ref{eq:Pequation}) очевидны --- функции Бесселя порядка $\pm\left|W\right|$. При $\rho\to0$ функция Бесселя с отрицательным индексом стремится к бесконечности, поэтому выбираем решение, имеющее приличную асимптотику в нуле: \[ P\left(\rho\right)\propto J_{\left|W\right|}\left(k\rho\right)\,. \]Здесь читателю предлагается подумать первый раз. Все правильно?

Разберемся. Понятно, что бесконечно тонкий соленоид означает предел соленоида конечного радиуса $R$ при $R\to0$. Или даже не предел, а просто ситуацию, когда $kR\ll1$. Рассмотрим эту ситуацию подробно. Для соленоида конечного радиуса имеем \[ \mathbf{A}=\frac{\Phi}{2\pi}\frac{\mathbf{e}_{z}\times\mathbf{r}}{\rho^{2}}f\left(\rho/R\right), \] где функция $f\left(x\right)$ стремится к нулю при $x\to0$ и равна единице при $x\geq 1$. Например, для случая однородного поля внутри соленоида эта функция равна $f\left(x\right)=\min\left(1,x^{2}\right)$. В общем случае магнитное поле внутри соленоида выражается через производную этой функции:\[ H\left(\rho\right)=\frac{\Phi f^{\prime}\left(\rho/R\right)}{2\pi\rho R} \] Соответственно, уравнение на $P\left(\rho\right)$ имеет вид\begin{equation} P^{\prime\prime}+\frac{1}{\rho}P^{\prime}+\left(k_{\perp}^{2}-\frac{\left(M-\frac{\Phi}{\Phi_{0}}f\left(\rho/R\right)\right)^{2}}{\rho^{2}}+\sigma\frac{g}{2}\frac{\Phi}{\Phi_{0}}\frac{f^{\prime}\left(\rho/R\right)}{\rho R}\right)P=0\label{eq:Pequation1} \end{equation}Здесь $\sigma=\pm1$ для спина вверх/вниз, $g=4m\mu/e$. Если частица бесспиновая, можно положить $g=0$. Поскольку $kR\ll1$, анализ проводится абсолютно аналогично анализу медленных частиц в § 132 3-его тома Ландау&Лифшица. На расстояниях больше радиуса соленоида, но много меньше $1/k$ уравнение имеет вид\begin{equation} P^{\prime\prime}+\frac{1}{\rho}P^{\prime}-\frac{W^{2}}{\rho^{2}}P=0\label{eq:Pequation2} \end{equation}Общее решение --- комбинация степеней, которую мы запишем для удобства как\begin{equation} c_{1}\left(\rho/R\right)^{\left|W\right|}+c_{2}\left(\rho/R\right)^{-\left|W\right|}\label{eq:rhollR} \end{equation}Коэффициенты $c_{1,2}$ не зависят от $k$ и определяются граничными условиями в нуле. Из соображений размерности сразу очевидно, что, с точностью до общей нормировки, они не зависят и от $R$. Волновая функция при произвольных $\rho>R$ является линейной комбинацией $J_{\pm\left|W\right|}$ с коэффициентами, которые, используя асимптотику функций Бесселя, легко выразить через $c_{1,2}$:\[ P\left(\rho\right)=c_{1}\Gamma\left(\left|W\right|+1\right)\left(kR/2\right)^{-\left|W\right|}J_{\left|W\right|}\left(k\rho\right)+c_{2}\Gamma\left(-\left|W\right|+1\right)\left(kR/2\right)^{\left|W\right|}J_{-\left|W\right|}\left(k\rho\right) \]Ну вот теперь в этой формуле мы можем перейти к пределу $R\to0$. В этом пределе первый член доминирует над вторым и, да, мы получаем\[ P\left(\rho\right)\propto J_{\left|W\right|}\left(k\rho\right)\,. \]Здесь читателю предлагается подумать второй раз. Все правильно?

Нет, не совсем. Это рассуждение годится, когда $c_{1}\neq0$. А вот если $g=2$ может получиться как раз $c_{1}=0$! Чтобы это доказать, обозначим $W\left(\rho\right)=M-\frac{\Phi}{\Phi_{0}}f\left(\rho/R\right)$. Тогда во всей области $\rho\ll 1/k$ мы имеем \begin{equation} P^{\prime\prime}+\frac{1}{\rho}P^{\prime}-\left(\frac{W^{2}}{\rho^{2}}+\frac{\sigma}{\rho}W^{\prime}\right)P=0\label{eq:Pequation3} \end{equation}Подстановкой легко проверить, что у этого уравнения есть решение\begin{equation} P\left(\rho\right)=\exp\left[\sigma\int_{0}^{\rho}\frac{d\rho}{\rho}W\left(\rho\right)\right]\label{eq:sol} \end{equation}Учитывая, что при $\rho>R$ величина $W\left(\rho\right)=W$ не меняется, получаем\[ P\left(\rho>R\right)=C\left(\frac{\rho}{R}\right)^{\sigma W}, \]где $C=\exp\left[\sigma\int_{0}^{R}\frac{d\rho}{\rho}W\left(\rho\right)\right]$. Таким образом, когда $\mathrm{sgn}W=-\sigma$, мы получаем чудо: для любой функции $f\left(x\right)$ коэффициент $c_{1}$ в (\ref{eq:rhollR}) строго зануляется. Конечно, хотелось бы понять, откуда такое чудо взялось. Вспоминаем, что при $g=2$ гамильтониан Паули можно записать в виде\[ \mathrm{H}=\frac{\left[\boldsymbol{\sigma}\cdot\boldsymbol{\pi}\right]^{2}}{2m}\,. \]Введем операторы \[ Q_{1}=\boldsymbol{\sigma}\cdot\boldsymbol{\pi}/2\sqrt{m},\quad Q_{2}=-i\sigma_{3}Q_{1}\,. \]Напомню, что жирные символами мы обозначаем двумерные вектора в плоскости $xy$. Легко сообразить, что\[ \left\{ Q_{i},Q_{j}\right\} =\delta_{ij}\mathrm{H}. \] А что это за соотношение? Правильно, это самый простейший пример суперсимметричной алгебры. Нам, правда, хотелось бы сразу увидеть суперсимметрию в радиальном гамильтониане. Но тут есть проблемы. Дело в том, что хотя сам гамильтониан коммутирует с $l_{z}=-i\partial_{\varphi}$, операторы $Q_{1,2}$ --- уже нет. Поэтому определить операторы сразу для радиального уравнения не удается. Тем не менее, выбрасывая $k^{2}$ из уравнения, мы, фактически, получаем уравнение на состояние с энергией, равной нулю. Поскольку гамильтониан выражается через квадрат эрмитова оператора, это состояние, если существует, является основным и может быть найдено из уравнения $Q_{1}\psi=0$ или $Q_{2}\psi=0$. Если мы будем искать решение в виде собственной функции операторов $l_{z}$ и $\sigma_{z}$, как $\psi=e^{iM\varphi}\phi_{\sigma}P\left(\rho\right)$, то как раз получим (\ref{eq:sol}). Итак, подытожим.
Почти для любого $\mu$ наша прескрипция выбирать в качестве решения радиального уравнения функцию $J_{\left|W\right|}\left(kr\right)$ является правильной. Исключение составляет случай, когда $\mu=\mu_{B}=e/2m$ (или $\mu=-\mu_{B}$). Причиной такого необычного исключения можно считать суперсимметрию гамильтониана для этого случая. Для этих случаев мы должны выбирать $J_{-\sigma\left|W\right|}\left(kr\right)$. Замечательно этот исключительный случай как раз соответствует нерелятивистскому электрону.

---

P.S. Ну и, да, здесь читателю тоже предлагается подумать, не обманул ли я где-нибудь его.
P.P.S. Исправил некоторые опечатки (ну и ошибки, чего уж там). Но это еще не конец истории, продолжение следует.

Про идеалы

Идеалов в реальном мире не бывает, но в математике они существуют еще как. Идеалы в  математике бывают разные, но здесь я расскажу про идеалы коммутативных колец.
Вообще, кольцо --- это множество, замкнутое относительно двух операций со свойствами сложения и умножения. Эти операции поэтому часто так и называют: сложение и умножение. Правда, коммутативность умножения не требуется, но нас интересует как раз кольцо с коммутативным умножением --- коммутативное кольцо. Ну еще хотят чтобы был нуль, и был противоположный элемент. Существование противоположного элемента позволяет определить в этом множестве и операцию вычитания по формуле $a-b\equiv a+(-b)$, где $-b$ --- элемент, противоположный $b$. Заметим, что существование единичного элемента и обратного элемента для ненулевого $a$ не требуется, и в этом принципиальное отличие кольца от поля.
Говоря неформально, в кольце деление даже на ненулевой элемент может быть невыполнимо. И, естественно, встает вопрос, а когда же деление все-таки выполнимо? Возьмем элемент кольца $a$ и спросим, какие элементы $b$ на него делятся, для каких $b$ разрешимо уравнение \begin{equation}b=ca.\label{eq1}\end{equation} Множество допустимых значений $b$ является примером идеала.

Возьмем самый простой пример коммутативного кольца — множество целых чисел $\mathbb{Z}$ с обычным сложением и умножением. Тогда, например, множество чисел, кратных числу $a$ является идеалом.

Можно расширить определение идеала так: пусть заданы несколько элементов кольца $a_1,\ldots,a_n$. Тогда идеал определим как множество значений $b$ (из кольца, конечно), для которых уравнение\begin{equation}b=c_1a_1+\ldots+c_na_n\label{eq2}\end{equation} разрешимо относительно $c_1,\ldots,c_n$ (в кольце, конечно). Про такие идеалы говорят, что они порождаются элементами $a_1,\ldots,a_n$. Для кольца целых чисел наше обобщение \eqref{eq2} не добавляет ничего нового. Чтобы это понять, заметим, что, во-первых, достаточно рассматривать идеалы, порожденные натуральными числами. Во-вторых, идеал, порожденный натуральными числами $a_1,\ldots,a_n$, совпадает с идеалом, порожденным  $\mathrm{GCD}(a_1,\ldots,a_n)$. Таким образом, в кольце целых чисел не только каждому натуральному числу соответствует идеал, но и наоборот, что открывает возможность переформулировать утверждения о натуральных числах в утверждения об идеалах. Вот, например, идеал, соответствующий простому числу (по понятным причинам называется простым идеалом), --- это собственный идеал (собственный $\equiv$ не совпадающий со всем кольцом), обладающий следующим свойством: для любого его элемента, имеющего вид произведения, по-крайней мере один из сомножителей также принадлежит идеалу. Теперь, когда у нас есть такое определение, мы можем его использовать для идеалов любых коммутативных колец, и, естественно, надеяться, что у этой и подобных конструкций есть простой смысл и большая польза.

Вот, например, рассмотрим полиномиальное кольцо ---  множество полиномов от $n$ переменных $x_1,\ldots,x_n$ с комплексными, скажем, коэффициентами. Полиномы, как и целые числа, можно складывать и умножать.  Обозначать это множество будем так: $\mathbb{C}[x_1,\ldots,x_n]$. В этом кольце наше обобщение \eqref{eq2} уже не сводится к \eqref{eq1}. Для кольца целых чисел каждый идеал у нас соответствовал натуральному числу, а для кольца полиномов идеалу можно придать гораздо более интересный смысл. А именно, идеалу, порожденному полиномами $p_1,\ldots,p_n$, сопоставим алгебраическое многообразие в $R^n$, заданное полиномиальными уравнениями \begin{align}p_1=0\nonumber\\\vdots\label{eq3}\\p_n=0\nonumber\end{align}Только вот это соответствие неоднозначное. В частности, если мы любой полином в системе \eqref{eq3} заменим на его степень, многообразие, очевидно не поменяется, а идеал, вообще говоря, поменяется. Чтобы соответствие было однозначным, нам нужно рассматривать не все идеалы, а то, что называется радикал-идеалы. Радикал-идеал $\mathcal{I}$ --- это идеал, для которого из условия $a^n\in \mathcal{I}$ следует $a\in \mathcal{I}$. Так вот соответствие между радикал-идеалами и алгебраическими многообразиями однозначно. Это означает, что, исследуя радикал-идеалы, можно исследовать алгебраические многообразия. Кстати, радикал-идеалы в кольце $\mathbb{Z}$ соответствуют натуральным числам, в разложении которых на простые нет степеней. Поэтому радикал-идеалы называются еще полупростыми. Очевидно, что простые идеалы являются также полупростыми, а обратное не всегда верно.

Пример приводимого многообразия,
заданного уравнением
$(x^2+y^2-4)(x^2-y)=0$

Чтобы понять, чему соответствуют простые идеалы, нам нужно ввести понятие неприводимых алгебраических многообразий. Неприводимые алгебраические многообразия ---  алгебраические многообразия, которые нельзя представить в виде объединения нескольких алгебраических многообразий. Так вот, неприводимые алгебраические многообразия играют роль простых чисел --- им соответствуют простые идеалы.

Красота идеальной математики на этом не кончается, но вот пост пора закруглять. Могу только порекомендовать для самообразования книжку Кокс, Литтл, О'Ши Идеалы, многообразия и алгоритмы. 

P.S. Все, можно статьи писать прямо в блоггере. Последний MathJax поддерживает нумерацию уравнений + ссылки через \ref и \eqref. Чтобы узнать как это включить, смотреть в коде поста скрипт с  src="...MathJax.js"

Клин

На прошлой неделе один обед протупил над следующим "парадоксом".

Рассмотрим матрицу \[
\Lambda_{\mathbf{p}}=\frac12\left(1+\frac{\varepsilon+\beta m}{p^2}\boldsymbol{\alpha}\mathbf{p}\right).
\] В голове не укладывались 4 утверждения, касающиеся этой матрицы:

1. $\Lambda_{\mathbf{p}}$ --- проектор, т.е. $\Lambda_{\mathbf{p}}^2=\Lambda_{\mathbf{p}}$. 
2.  $\Lambda_{\mathbf{p}}u_{\mathbf{p}}=u_{\mathbf{p}}$,  т.е., это проектор на пространство решений уравнения $[\varepsilon-\boldsymbol{\alpha}\mathbf{p}-\beta m]u_{\mathbf{p}}=0$.
3. $\Lambda_{\mathbf{p}}+\Lambda_{-\mathbf{p}}=1$, откуда следует, что $\Lambda_{\mathbf{p}}\Lambda_{-\mathbf{p}}=0$.
4. $u^{\dagger}_{\mathbf{p}}u_{\mathbf{-p}}\neq0$.

Только написав на доске понял в чем дело.

Еще идефикс

Все, конечно, знают, что риманова поверхность функции \[\sqrt{P_{2g+2}(z)},\] где $P_{2g+2}(z)$ --- полином $2g+2$ порядка, в общем случае гомеоморфна сфере с $g$ ручками. В частности, риманова поверхность функции $f(z)=\sqrt{z^4-1}$ должна быть гомеоморфна тору. Я вот тоже это недавно узнал. Ну, я когда-то знал это раньше, но забыл, да, да. Полезно потренировать воображение и сообразить, как непрерывной деформацией превратить тор в дважды накрытую сферу Римана с четырьмя точками ветвления. Я такими вещами обычно занимаюсь, когда не могу заснуть.
Проблема в том, что когда картинка понятна, очень хочется ее нарисовать, и сопротивляться этому желанию у меня пока не получается. Иначе картинка будет висеть в бэкграунде и тормозить весь мыслительный процесс. Вот только в данном случае нужно не нарисовать, а анимировать. К счастью, Wolfram Mathematica заботится о нас, толкает свой CDF формат (как альтернативу PDF-у, что-ли?). Ладно, попробуем. Ниже результат.
Когда ползунок в самой правой позиции, имеем дважды накрытую сферу Римана, на которой однозначно определена наша функция $f(z)$. Четыре конца красных линий соответствуют корням нашего полинома $\pm1,\pm i$. Сами линии обозначают один из возможных способов выбрать разрезы.

---

---

P.S. Главное страдание --- выдумать подходящую функцию, интерполирующую между двумя крайними положениями. Первоначальная простая, как три копейки, мысль --- интерполировать как $(1-t)*тор+t*сфера2$ --- дает убогий результат.

Теорема Левинсона

Сегодня, прибираясь в своей коллекции статей, обнаружил одну работу, которую я, очевидно, скачал, чтобы потом разобраться, и забыл. Про теорему Левинсона. Я, вообще, питаю слабость к строгим утверждениям в области физики, поэтому решил все-таки разобраться. Саму статью Левинсона [1] я добыть не смог, поскольку напечатана она в журнале с длинным малопонятным названием Kgl. Danske Videnskab. Selskab, Mat.-fys. Medd., но нашел зато совсем простую работу Веллнера [2] которую тут же и прочитал.
Так вот, теорема Левинсона --- это красивое утверждение о связи фазы рассеяния и количества связанных состояний в потенциале (в уравнении Шредингера). Фаза рассеяния, как известно, измеряется в экспериментах по рассеянию, поэтому извлечение из этой фазы информации о потенциале, безусловно, имеет важное значение. Если в обратной задаче рассеяния речь идет о том, чтобы полностью восстановить по данным рассеяния потенциал, то теорема Левинсона решает гораздо более скромную задачу, но не перестает от этого быть изящным и полезным фактом.
Итак, рассмотрим радиальное уравнение (р.у.) Шредингера
\[ -\chi_l^{\prime\prime} +\tilde{V}_l\chi_l=k^2\chi_l , \] где $\tilde{V}_l=V+l(l+1)/r^2$ --- эффективный потенциал с учетом центробежной части.
Фаза рассеяния $\delta_l(k)$ определяется асимптотикой волновой функции: \[ \chi_l(k,r)\to 2\sin(kr-\pi l/2+\delta_l(k)) \] Далее, для простоты изложения, кладем $l=0$. Решение при нулевом потенциале будем обозначать нижним индексом $F$: \[ \chi_F(k,r)=2\sin(kr) \] Умножим производную р.у. по $k$ на $\chi$ и вычтем р.у., умноженное на производную $\chi$ по тому же $k$: \[ (\dot\chi\chi^{\prime}-\chi\dot\chi^{\prime})^\prime=2k\chi^2, \] Точками здесь обозначены производные по $k$. Интегрируем по $r$ от нуля до достаточно большого $R$, такого, чтобы при $r=R$ уже можно было пользоваться асимптотикой. Получаем \[ \dot\delta=\frac12\int_0^R dr\chi^2-R+\frac{\sin(2kR+2\delta)}{2k}, \] Далее мы представляем \begin{gather} \frac{\sin(2kR+2\delta)}{2k} =-\lim_{\epsilon\to 0}\int_R^\infty dr \,e^{-\epsilon r}\cos(2kR+2\delta)\\ =\lim_{\epsilon\to 0}\int_R^\infty dr\, e^{-\epsilon r} [2\sin^2(kR+\delta)-1] =\lim_{\epsilon\to 0}\int_R^\infty dr \,e^{-\epsilon r} \left[\frac12\chi^2-1\right] \end{gather} и получаем симпатичную формулу \[ \dot\delta=\lim_{\epsilon\to 0}\int_0^\infty dr\,e^{-\epsilon r}\left[\frac12\chi^2-1\right] =\frac12\lim_{\epsilon\to 0}\int_0^\infty dr\,e^{-\epsilon r}\left[\chi^2-\chi_F^2\right]. \] Второй переход справедлив, вообще говоря, для $k\neq 0$, но это мелочь. Если мы проинтегрируем это равенство по $k$, то получим \[ \delta(\infty )-\delta(0)= \frac12\lim_{\epsilon\to 0}\int_0^\infty dr\,e^{-\epsilon r}\int_0^\infty dk\left[\chi^2-\chi_F^2\right]. \] Ну вот, теперь еще вспоминаем соотношение полноты для радиальных функций \[ \sum_{n=1}^{N} \chi_n(r)\chi_n(r^\prime)+\int_0^\infty\frac{dk}{2\pi}\chi(k,r)\chi(k,r^\prime)=\delta(r-r^\prime), \] где $N$ --- число связанных состояний. Это соотношение справедливо и для нулевого потенциала, когда $N=0$: \[ \int_0^\infty\frac{dk}{2\pi}\chi_F(k,r)\chi_F(k,r^\prime)=\delta(r-r^\prime), \] Разность двух последних соотношений и последующая замена $r^\prime \to r$ дает \[ \int_0^\infty dk\left[\chi^2-\chi_F^2\right]=-2\pi\sum_{n=1}^{N} \chi_n^2 \]

Окончательно, получаем теорему Левинсона: \[ \delta(\infty )-\delta(0)= -\pi\int_0^\infty dr\sum_{n=1}^{N} \chi_n^2 =-\pi N,. \] Изменение фазы рассеяния при изменении $k$ от нуля до бесконечности равно числу связанных состояний, умноженному на $-\pi$.

Выполнение теоремы Левинсона для потенциала $U(r)=-\frac{U_0}{\cosh^2 r}$. Зеленая кривая --- фаза рассеяния для $l=0$ как функция от энергии (правая шкала --- $E/U_0$). Уровни энергии в потенциале показаны пунктиром. Потенциал (показан синей кривой) постепенно углубляется и когда в нем появляется новый уровень, фаза рассеяния скачет на $\pi$.

Честно говоря, у меня такое жонглирование пределами всегда вызывает настороженность, но в данном случае результат достаточно красив, чтобы быть правильным, так что оставим строгий вывод математикам.
Да, забыл сказать, что неоднозначность определения фазы (к которой можно прибавить $\pi m$) не мешает этому соотношению. Нужно просто считать, что фаза определена как непрерывная функция $k$.
[1] N. Levinson, Kgl. Danske Videnskab. Selskab, Mat.-fys. Medd., 25(9) (1949)
[2] M. Wellner, Amer. J. Phys. 32 (1964) 787.

Матроиды для чайников

Пишу, в основном, чтобы самому не забыть.
Чтобы определить матроид, определим сначала бинарную группу цепей. Бинарную группу можно наглядно определить так

Бинарная группа цепей --- множество, состоящее из N-значных двоичных чисел (не обязательно всех) и замкнутое относительно групповой операции --- побитного исключающего или. Единицей группы является $\underbrace{0\ldots 0}_{N\text{ нулей}}$ и каждый элемент является себе обратным.

В теоретико-множественном определении нужно заменить N-значные двоичные числа на подмножества N-элементного множества, а исключающее или --- на исключающее объединение $(\#1\backslash\#2)\cup(\#2\backslash\#1)$. Почему интересна такая конструкция, потому что эта группа играет важную роль в теории графов.
Пусть у нас есть граф с N ребрами. Возьмем часть его вершин в левую руку (множество этих вершин назовем $A$), а остальные --- в правую ($B$), растянем и порежем все ребра, идущие из одной руки в другую. Множество ребер, которые оказались разрезанными назовем разрезом. Все разрезы данного графа, как нетрудно сообразить, образуют некоторую бинарную группу цепей, которую мы будем обозначать $C$. Действительно, разрез, соответствующий исключающему объединению двух разрезов получается разбиением множества вершин на \[A^{\prime\prime}=(A\cap A^{\prime})\cup (B\cap B^{\prime})\quad\text{ и }\quad B^{\prime\prime}=(A\cap B^{\prime})\cup (B\cap A^{\prime}).\] Кстати, множество ребер, имеющих общую вершину тоже, очевидно, является разрезом (защипнем эту общую вершину и отрежем все ребра, соединяющие ее с остальным графом).
Есть другая бинарная группа цепей, связанная с множеством ребер графа. Рассмотрим все подграфы графа, для которых в каждой вершине сходится четное число ребер. Ясно, что множества ребер таких подграфов (собственно, цепи) образуют бинарную группу цепей $L$.
Заметим, что задание бинарной группы цепей (и, в частности, групп $C$ и $L$) полным перечислением ее элементов представляется довольно избыточным. Вообще, наиболее экономичный способ описания --- это задать мультипликативный базис группы. Понятие матроида бинарной группы цепей лежит где-то на полдороги между полным множеством элементов группы и ее мультипликативным базисом.
Перед тем, как давать формальное определение, поясним суть дела на примере наших групп $C$ и $L$. Рассмотрим сначала некоторый разрез. Может так оказаться, что после разреза в одной или обоих руках окажется несвязный граф (см. картинку). Такой разрез может быть выполнен в два приема и поэтому уж точно бесполезен для построения базиса. Можно сказать, что такой разрез неэлементарный.
Аналогично, многие цепи являются неэлементарными. Это так, если подграф, им соответствующий, несвязен или содержит вершины со степенью 4 или выше (см. пример справа). Вот если мы исключим из $C$ и $L$ (как множеств) неэлементарные элементы, а заодно и единицу группы --- пустое множество, оставшаяся часть и будет называться матроидом. Итак, на теоретико-групповом языке матроид бинарной группы цепей--- подмножество всех элементарных элементов группового множества, т.е., всех непустых элементов, которые не включают в себя никакого другого элемента в качестве подмножества. Для нашего чайниковского определения бинарной группы

Матроид бинарной группы цепей --- подмножество всех таких ненулевых чисел из группового множества, которые обязательно меняются при побитном ИЛИ с любым элементом группы.

Все, хватит пока. Про алгоритм Татта напишу как-нибудь в другой раз.
P.S. Кстати, картинки рисованы в SVG-edit, не выходя из браузера, а затем скопипасчены прямо в пост.