В начале прошлого года случилось поучаствовать в настоящей математической конференции по функциональным уравнениям. Я был приятно удивлен тем, что бо́льшая часть докладов оказалась вполне воспринимаема. Причина, конечно, не в том, что я такой умный — на физических конференциях очень часто из доклада я мало что могу понять — а в том, что математики больше стремятся сделать свой доклад понятным и меньше пускают пыль в глаза. Ну так мне показалось. И кроме меня был там еще один физик, который рассказывал про квантовый компьютер — а точнее, про запиленный им с соавторами эмулятор оного. На мой взгляд, доклад был совсем пустячный, но вот что интересно. В том месте где было гордо сказано, что после работы программы есть еще стадия считывания, на которой можно получить различные измеренные результаты с определенными вероятностями, я заметил среди слушателей искреннее недоумение. Подозреваю, что дело тут в неправильной подаче материала, призванной произвести эффект, а не сделать предмет понятным, но оставим это на совести докладчика.
В черновиках моего блога есть материал, который я давно уже начал, но никак не могу закончить. Про алгоритм Шора для факторизации чисел на квантовом компьютере. Фактически, с этого алгоритма начался — а злые языки говорят, что и закончится — квантовый компьютер. Оригинальная статья написана хорошо и понятно, но мне хотелось объяснить этот алгоритм ещё более просто — так чтобы могли прочитать и понять студенты (хотя бы те, которые раз прослушали его в моём исполнении). Поскольку пост завяз, я решил откусить часть изложения и поместить в отдельный пост, это и делаю.
Когда говорят про алгоритм Шора, вспоминают принцип суперпозиции в квантовой механике, позволяющий якобы эффективно проводить вычисления параллельно сразу для всех возможных входных данных. Вот про этот параллелизм и пойдёт речь. Как я уже объяснял где-то в этом блоге, "память" квантового компьютера представляет из себя т.н. 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. Кстати, про "один вопрос" вспомнился такой заумный анекдот:
В черновиках моего блога есть материал, который я давно уже начал, но никак не могу закончить. Про алгоритм Шора для факторизации чисел на квантовом компьютере. Фактически, с этого алгоритма начался — а злые языки говорят, что и закончится — квантовый компьютер. Оригинальная статья написана хорошо и понятно, но мне хотелось объяснить этот алгоритм ещё более просто — так чтобы могли прочитать и понять студенты (хотя бы те, которые раз прослушали его в моём исполнении). Поскольку пост завяз, я решил откусить часть изложения и поместить в отдельный пост, это и делаю.
Когда говорят про алгоритм Шора, вспоминают принцип суперпозиции в квантовой механике, позволяющий якобы эффективно проводить вычисления параллельно сразу для всех возможных входных данных. Вот про этот параллелизм и пойдёт речь. Как я уже объяснял где-то в этом блоге, "память" квантового компьютера представляет из себя т.н. 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. Кстати, про "один вопрос" вспомнился такой заумный анекдот:
На заседание философского общества спустился с неба ангел, и предложил философам ответить на любой их вопрос, но только на один. Философы начали спорить о том, какой вопрос задать. Ангел сказал: "ну вы тут решайте, я завтра вернусь и спросите". Некоторые философы предлагали связать несколько вопросов конъюнкцией, но другие возражали, что ангел не согласится считать это одним вопросом. Один философ предложил спросить ангела: "Какой вопрос самый лучший?", и потом, зная вопрос, подождать, пока не прилетит другой ангел в будущем. Но другие философы возражали, что не факт, что визит когда-либо повторится, и жалко тогда терять этот шанс. Наконец, философы договорились, и когда ангел вернулся на следующий день, задали ему следующий вопрос: "Какова упорядоченная пара, первый элемент который является лучшим вопросом, который можно задать ангелу, а второй элемент - ответом на этот вопрос?" Ангел тут же ответил: "Это упорядоченная пара, первым элементом которой является вопрос, который вы только что задали, а вторым - ответ, который я вам даю". И исчез.
Комментариев нет:
Отправить комментарий