Квантовая информатика с человеческим лицом
1. Внимательно вглядись, или Квантовые вычисления для ленивого программиста
Когда я слышу про кота Шрёдингера, мне хочется достать ружье.
Стивен Хокинг
В университете все «юные химики», а не только программисты, могут узнать (но не обязательно понять), что квантовый способ описания окружающего мира является чуть ли не единственно возможным средством сохранить прогностическую ценность теоретической химии. Еще Дойч и Фейнман указали, что моделирование квантовохимических процессов, лежащих в основе мироздания, на классических компьютерах, даже полных по Тьюрингу, с вычислительной точки зрения — почти безнадежное занятие (см., например, [Fe1982, Deu1985]. Объем пространства состояний системы с ростом числа вовлеченных в расчет атомов растет так, что потребление памяти становится экспоненциальным. Вычислительная химия, в частности, и развивалась так, чтобы как-то преодолевать возникающие в связи с этим трудности.
В 1982 г. Бенёв показал [Ben1982], что вычислительная мощность компьютеров, использующих манипулирование квантовомеханическими объектами — атомами и молекулами, — может превосходить возможности классических компьютеров, и ввел аналогичное классическому понятие квантовой машины Тьюринга.
В 1992 г. появился первый алгоритм, существенным образом использующий явление квантового параллелизма (об этом подробнее здесь), то есть тот факт, что вычислительные элементы квантового компьютера (кубиты, от qu(antum) bits) могут находиться, по существу, одновременно в нескольких состояниях, а не в одном четко определенном, как элементы компьютера классического. Иначе говоря, применяя некоторую программу эволюции (нас сейчас не интересует точная ее природа) к начальному состоянию регистров такой машины, мы получаем одновременно все возможные результаты ее выполнения. То есть мы можем вместо того, чтобы вовлекать в процесс N классических регистров, каждый из которых находится в определенном начальном состоянии |x>, применить квантовую суперпозицию классических состояний |x>. О системе, принятой для записи состояний отдельных кубитов |x> , можно подробнее почитать здесь.
В 1994 г. Шор заметил, что в рамках классической теории чисел задачу о взломе алгоритма RSA можно свести к вычислению периода некоторой функции. Этот процесс удается экспоненциально ускорить, переписав классический алгоритм с учетом ограничений, налагаемых квантовомеханической природой «железа», и применив квантовый аналог преобразования Фурье. В результате, мы будем наблюдать Фурье-интерференцию образов периодической функции, все значения которых вычисляются одновременно и независимо друг от друга. Надо особо отметить, что Шор не пользовался приемами избыточности и не прибегал к кодам с коррекцией ошибок, поскольку в квантовой информатике оператор простого копирования запрещен (почему это так, отдельный вопрос, можно пока сказать, что в квантовой механике допустимы только линейные преобразования, а клонирование состояния кубита нелинейно по своей природе). В итоге ему удалось разработать метод взлома системы RSA для квантового компьютера, требующий полиномиального времени работы. Таким образом, было получено прямое доказательство того, что внедрение квантовых алгоритмов может иметь революционные последствия для современной криптографии. Это достижение привлекло значительный интерес к квантовой информатике, и работы по созданию действительно дееспособных квантовомеханических вычислительных устройств резко интенсифицировались. Вся эта область сейчас уже совершенно необъятна, и я не буду ее детально касаться в первом очерке. Нужно подчеркнуть, что создание такой машины — задача технически чрезвычайно сложная. Вот один из наиболее продуманных вариантов: такой квантовый компьютер уже знает, что 3×5 = 15, но это только начало!
Но, во-первых, технология не стоит на месте, и следует ожидать такого же прорыва, как в свое время при переходе от электронных ламп к полупроводникам, а во-вторых, ничто не препятствует создать симуляторы квантовых компьютеров «внутри» классических устройств.
В частности, Эмер разработал императивный язык квантового программирования QCL (лично я предпочитаю использовать реализацию для AMD64), а Альтенкирх и Виццотто применили для моделирования квантовых эффектов на классических компьютерах библиотеки Haskell. Ван Тондер, вдохновленный LINQ, разработал квантовый аналог ламбда-выражений и позаботился об их реализации средствами Scheme; квантовый симулятор недавно интегрировали также в Common Lisp. Наконец, Сэлингер предложил функциональный язык квантового программирования QPL, в котором допускается сочетать классические и квантовые инструкции, а также раздельно обрабатывать классические коды управления и квантовые данные.
Теперь, когда некоторое общее представление о квантовой информатике, надеюсь, получил даже тот читатель, который ленился кликать по ссылкам, я хочу проиллюстрировать некоторые неочевидные свойства квантовых алгоритмов, рассказав об интересном и малоизвестном эффекте, как нельзя лучше соответствующей старой заповеди советского инженера: «Работает? Не трогай!»
Вкратце, мы сейчас убедимся, что ничегонеделание в квантовом программировании представляет собой весьма нетривиальную операцию, и при определенных условиях можно узнать результат выполнения программы, даже не включая компьютер.
Я буду в дальнейшем следовать терминологии, принятой у Джозсы, первооткрывателя этого эффекта.
* * *
Представим себе квантовый компьютер, снабженный переключателем по принципу «мертвой руки», изначально установленным в положении «ВЫКЛ». Пусть изначальное состояние квантовых регистров — |QC>, а регистр, предназначенный для вывода результатов, может содержать два значения — 0 и 1, или, с квантовомеханической точки зрения, пребывать в состояниях |0> и |1>. Заставим квантовый компьютер выполнить алгоритм решения некоторой задачи, предусматривающий выбор из многих альтернатив, среди которых правильна только единственная. И пусть регистр результатов, изначально пребывающий в состоянии |0>, примет значение k = 0 или 1 в зависимости от неуспеха или успеха нашего эксперимента. Вычисления проводятся только в том случае, если переключатель переводится в положение «ВКЛ». По окончании эксперимента компьютер возвращают в первоначальное состояние.
С квантовомеханической точки зрения, любое вмешательство в работу переключателя приводит его сперва в некоторое промежуточное состояние, образованное суперпозицией возможных исходов этого вмешательства. Ситуация аналогична эксперименту с котом Шрёдингера. Итак, даже если компьютер не включен, предварительное заполнение квантовых регистров данными уже перевело всю систему (переключатель, регистры данных и регистр результатов) в суперпозицию состояний
(|ВЫКЛ> + |ВКЛ>)/sqrt(2) * |QC> * |0>.
Теперь просто подождем время, отведенное на прогон алгоритма. Система переходит в состояние
1/sqrt(2) * (|ВЫКЛ> * |QC> * |0> + |ВКЛ>*|QC> *|k>)
После этого переключатель оказывается, в зависимости от того, что с ним было до запуска алгоритма, в одном из двух новых состояний:
|ВЫКЛ> → 1/sqrt(2) * (|ВЫКЛ> + |ВКЛ>); |ВКЛ> → 1/sqrt(2) * (|ВЫКЛ> — |ВКЛ>)
Результирующее конечное состояние системы будет таким:
1/sqrt(2) * ((1/sqrt(2) * (|ВЫКЛ> + |ВКЛ>)) * |QC> * |0> + (1/sqrt(2) * (|ВЫКЛ> — |ВКЛ>)) *|QC> *|k>) =
= 1/sqrt(2) * ((1/sqrt(2) * (|0> + |k>)*|ВЫКЛ> + (1/sqrt(2) * (|0> — |k>)*|ВКЛ>)) * |QC>
Теперь мы измеряем состояние переключателя, а следом заглядываем в регистр результатов. Пусть мы видим, что переключатель ВКЛЮЧЕН. Тогда в регистре должно быть значение 1.
Но с вероятностью 50% проверка состояния регистра даст значение 0. И если это происходит, то мы должны заключить, что вычисления по алгоритму не осуществлялись, потому что в противном случае в регистре результатов содержалось бы значение 1.
Заметьте, что если k = 0, то мы никогда не увидим положение ВКЛ. Если же k = 1, то у нас 50%-е шансы наблюдать положение ВКЛ. Итак, если мы обнаружили, что k = 1, то с вероятностью 25% мы можем получить решение задачи (и при этом верное), не включая компьютер.
Откуда же в таком случае появляется результат? Мы что, получаем его просто так, не расходуя никаких вычислительных ресурсов? Существует любопытное объяснение этого эффекта: с точки зрения многомировой интерпретации квантовой механики, если даже измерение состояния регистра результатов показало, что вычисление не имело места, то в некоторой параллельной вселенной, где переключатель все-таки оказался в положении ВКЛ, компьютер продолжал работать. Именно там этот ответ и был вычислен.
Элицур и Вайдман отметили, что компьютер потенциально может быть сконструирован таким образом, чтобы после получения верного ответа он самоуничтожался (например, это касается сверхтьюринговых машин). Если вышеописанный эксперимент проводится именно с таким «компьютером для шахидов», то с вероятностью 25% мы обнаружим, что k = 1, и, тем не менее, компьютер продолжает работать. По очевидным причинам описанную модификацию эксперимента называют «задачей сапера». Немало у нее общего и с квантовым бессмертием. О том, как все это может выглядеть на практике, можно почитать в отличном романе Нила Стивенсона.
Говорят, что все беды от лени, но мы только что убедились, что лень может быть и очень полезна для постижения природы окружающей Вселенной!
Продолжение: Квантовая информатика для котов и людей: антропный принцип, эффект Зенона и фермент в роли машины Тьюринга
Все про українське ІТ в телеграмі — підписуйтеся на канал DOU
23 коментарі
Підписатись на коментаріВідписатись від коментарів Коментарі можуть залишати тільки користувачі з підтвердженими акаунтами.