Что писать в труды конференции --- всегда для меня проблема. С одной
стороны доклад обычно уже делается по опубликованной работе, а с другой
--- терпеть не могу писать уже написанное. Поэтому пытаюсь всунуть в
свой вклад хоть что-то новое. Вот, в последний такой опус,
вышедший сегодня, написал свои не до конца продуманные идеи про
редукцию в параметрическом представлении. Среди прочего, использовал
свойства следующего интегрального (точнее, наполовину интегрального,
наполовину дифференциального) преобразования.
Рассмотрим линейное
пространство гладких функций $\phi(x)$ на $[0,\infty)$, спадающих
быстрее любого полинома на бесконечности и разложимых в ряд Тейлора в
окрестности нуля. Определим в этом пространстве преобразование
\[\phi(x)\to \tilde{\phi}_m=I^m[\phi],\,m\in\mathbb{Z}\,,\] где
$I^m[\phi]$ --- такой функционал
\[I^m[\phi]=\left\{\begin{array}{cc}\frac{1}{\Gamma(m)}\int_0^\infty dx
x^{m-1}\phi(x)\,,& m>0\\ (-1)^m\phi^{(-m)}(0)\,,&m\leqslant
0\end{array}\right.\]
Красота этого определения --- в том, что
справедливы следующие формулы \[I^m[-d\phi/dx]=I^{m-1}[\phi]\,,\quad
I^m[x\phi]=m I^{m+1}[\phi]\] Вот интересно, как написать обратное
преобразование (если оно существует, конечно)?
Для профилактики слабоумия начал опять решать задачи на 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 строит состояние (с определенным спином и проекцией) с соответствующим номером:
Все, наверное, слышали о квантовых компьютерах, которые, ну вот
совсем скоро, будут созданы и будут решать все задачи, которые обычным,
классическим компьютерам не по зубам. Я о них, видимо, в первый раз
услышал где-то году в 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$ сразу зеленое, так как оно должно остаться на месте.
Что-то стал за собою замечать, что совсем разучился в качестве отдыха и развлечения читать художественную литературу. Вместо этого читаю какие-нибудь книжки по математике, которые поинтереснее и, по возможности, попроще.
Вот, недавно стал читать книгу Конвея "О числах и играх". Много лет назад прочитал вот здесь про комбинаторную теорию в Го. В частности, прочитал про инфинитезимали, и это было круто. Сейчас решил перечитать, и нашел ссылку на Конвея. Вот цитата из первого параграфа:
"Дедекинд (а до него автор — как считается, Евдокс — пятой книги Евклида) строил вещественные числа из рациональных. Его метод заключался в том, чтобы разделить рациональные числа на два множества 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"... />.
