Все, наверное, слышали о квантовых компьютерах, которые, ну вот
совсем скоро, будут созданы и будут решать все задачи, которые обычным,
классическим компьютерам не по зубам. Я о них, видимо, в первый раз
услышал где-то году в 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$ сразу зеленое, так как оно должно остаться на месте.
Замечу, что никогда ни на одну секунду я не допускал, что реальный квантовый компьютер будет создан в обозримом будущем (ну, скажем, лет за сто). Под "реальным квантовым компьютером" я понимаю, конечно, устройство, способное успешно конкурировать с обычными классическими компьютерами, а не просто раскладывать на множители число 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$ сразу зеленое, так как оно должно остаться на месте.
| → |
| |||||||||||||||||||||||||||||||||
Комментариев нет:
Отправить комментарий