Квантовый компьютер для классических программистов
Про квантовый компьютер все слышали. Кто-то боится, что он лишит работы всех современных программистов (особенно этого почему-то бояться php-программисты), кто-то отрицает, что он когда-нибудь будет создан. Чтобы развеять опасения и подготовить широкие программистские массы к новому стилю программирования я пишу этот пост.
Собственно, дальнейшее есть изложение модели квантового компьютера на классическом. Оперативная память квантового компьютера - массив из 2N комплексных чисел (N - число кубитов). Набор кубитов - набор индексов массива (или же набор цифр в двоичном представлении сквозного индекса массива, если желаете). Операции с массивом не произвольны, а ограничены следующими правилами:
I. Возможны только операции по маске, над целыми блоками массива. Однокубитные операции - это на самом деле операции над половинками массива, двухкубитные - над четвертушками, трехкубитные - ну вы поняли. Например, операция «квантовое NOT» - это просто обмен двумя половинками массива:
Anew(****0***) = A(****1***)
Anew(****1***) = A(****0***)Здесь Anew - новое состояние массива, звездочка - произвольное состояние индекса, запятые между индексами опущены, операция выполняется над четвертым кубитом справа.
Двухкубитная операция «контролируемое NOT» - обмен двух четвертушек с оставлением остальной части неизменной:
Anew(*1**0***) = A(*1**1***)
Anew(*1**1***) = A(*1**0***)В примере седьмой кубит справа - контролирующий.
II. Что бы вы не делали, сумма квадратов модулей элементов массива должна равняться единице. Из-за этого, простое сложение и вычитание не относяться к базовыми операциям, вместо них есть т.н. преобразование Адамара, сложение и вычитание двух половинок массива с делением на корень из двух:
Anew(****0***) = ( A(****0***) + A(****1***) ) / √2
Anew(****1***) = ( A(****0***) - A(****1***) ) / √2А вместо умножения на число - умножение половинки массива на фазовый множитель:
Anew(****1***) = exp(iδ) A(****1***)
III. Инициализируется массив присвоением единицы одному из элементов, и нуля всем остальным.
IV. Из массива можно извлечь только квадраты модулей элементов, для извлечения элемента требуется многократные перезапуски программы, число перезапусков обратно пропорциональна величине элемента. Поэтому программа должна выдавать ответ в форме как можно меньшего количества ненулевых элементов, в идеале - выставлять в единицу единственный элемент массива, индекс которого и будет ответом.
Для выполнения любого алгоритма достаточно перечисленных выше однокубитных и одной двухкубитной команды - контролируемого NOT. Мудреность низкоуровневого программирования компенсируется потенциальной огромностью доступной оперативной памяти (при 270 кубитах число элементов массива превышает число атомов в видимой части Вселенной) и тем, что операции над массивом выполняются за один такт.
Существует куча библиотек для разных языков для эмуляции квантового компьютера, где вышеописанные операции уже реализованы. Есть и специализированные языки для управления квантовыми компьютерами, за неимением последнего управляющие его моделью, реализованной с помощью одной из помянутых библиотек. Достоинства квантового компьютера являются проблемами при его эмуляции: при числе кубитов N > 30 (для мощного домашнего компьютера) или N > 50 (если у вас есть суперкомпьютер) массив не поместиться в оперативной памяти.
Что касается советов соискателям грядущих рабочих мест в сфере квантового компьютинга: к собеседованию надо будет выучить, что такое квантовое преобразование Фурье - оно понадобится как в криптографии, так и в индустрии легкого молекулостроения (про квантовое моделирование квантовых систем я планирую написать отдельный пост). 1С-программистам, лишившимся работы из-за грядущей квантовой революции в бухучете (вероятностный бюджет, мнимые активы… ну собственно ничего существенно не изменится), можно посоветовать учить алгоритм Гровера. А вот что делать php-программистам, не знаю - даже в шутку не могу представить применения квантового компьютера в веб-дизайне.
Собственно, дальнейшее есть изложение модели квантового компьютера на классическом. Оперативная память квантового компьютера - массив из 2N комплексных чисел (N - число кубитов). Набор кубитов - набор индексов массива (или же набор цифр в двоичном представлении сквозного индекса массива, если желаете). Операции с массивом не произвольны, а ограничены следующими правилами:
I. Возможны только операции по маске, над целыми блоками массива. Однокубитные операции - это на самом деле операции над половинками массива, двухкубитные - над четвертушками, трехкубитные - ну вы поняли. Например, операция «квантовое NOT» - это просто обмен двумя половинками массива:
Anew(****0***) = A(****1***)
Anew(****1***) = A(****0***)Здесь Anew - новое состояние массива, звездочка - произвольное состояние индекса, запятые между индексами опущены, операция выполняется над четвертым кубитом справа.
Двухкубитная операция «контролируемое NOT» - обмен двух четвертушек с оставлением остальной части неизменной:
Anew(*1**0***) = A(*1**1***)
Anew(*1**1***) = A(*1**0***)В примере седьмой кубит справа - контролирующий.
II. Что бы вы не делали, сумма квадратов модулей элементов массива должна равняться единице. Из-за этого, простое сложение и вычитание не относяться к базовыми операциям, вместо них есть т.н. преобразование Адамара, сложение и вычитание двух половинок массива с делением на корень из двух:
Anew(****0***) = ( A(****0***) + A(****1***) ) / √2
Anew(****1***) = ( A(****0***) - A(****1***) ) / √2А вместо умножения на число - умножение половинки массива на фазовый множитель:
Anew(****1***) = exp(iδ) A(****1***)
III. Инициализируется массив присвоением единицы одному из элементов, и нуля всем остальным.
IV. Из массива можно извлечь только квадраты модулей элементов, для извлечения элемента требуется многократные перезапуски программы, число перезапусков обратно пропорциональна величине элемента. Поэтому программа должна выдавать ответ в форме как можно меньшего количества ненулевых элементов, в идеале - выставлять в единицу единственный элемент массива, индекс которого и будет ответом.
Для выполнения любого алгоритма достаточно перечисленных выше однокубитных и одной двухкубитной команды - контролируемого NOT. Мудреность низкоуровневого программирования компенсируется потенциальной огромностью доступной оперативной памяти (при 270 кубитах число элементов массива превышает число атомов в видимой части Вселенной) и тем, что операции над массивом выполняются за один такт.
Существует куча библиотек для разных языков для эмуляции квантового компьютера, где вышеописанные операции уже реализованы. Есть и специализированные языки для управления квантовыми компьютерами, за неимением последнего управляющие его моделью, реализованной с помощью одной из помянутых библиотек. Достоинства квантового компьютера являются проблемами при его эмуляции: при числе кубитов N > 30 (для мощного домашнего компьютера) или N > 50 (если у вас есть суперкомпьютер) массив не поместиться в оперативной памяти.
Что касается советов соискателям грядущих рабочих мест в сфере квантового компьютинга: к собеседованию надо будет выучить, что такое квантовое преобразование Фурье - оно понадобится как в криптографии, так и в индустрии легкого молекулостроения (про квантовое моделирование квантовых систем я планирую написать отдельный пост). 1С-программистам, лишившимся работы из-за грядущей квантовой революции в бухучете (вероятностный бюджет, мнимые активы… ну собственно ничего существенно не изменится), можно посоветовать учить алгоритм Гровера. А вот что делать php-программистам, не знаю - даже в шутку не могу представить применения квантового компьютера в веб-дизайне.