- Квантовая информатика для котов и людей: антропный принцип, эффект Зенона и фермент в роли машины Тьюринга
1а. Цветы пастушьей сумки, или Не так все это было, совсем не так…
Всесокрушающий меч и непробиваемый щит нельзя применить одновременно.
Хань Фэй-цзы
В первом своем очерке я попытался дать популярное введение в квантовую информатику. Я особо коснулся проблемы невозможных вычислений, описав алгоритм, позволяющий, с некоторой долей вероятности, найти решение «задачи сапера» без каких бы то ни было вычислительных операций, кроме простого ожидания.
Почитав комментарии на ДОУ и Хабрахабре, я понял, что неплохо бы рассмотреть этот результат с более общей точки зрения. Сейчас мы:
1) попробуем понять, вправду ли невозможные вычисления обходятся программисту задаром,
2) узнаем, что случилось с котом Шредингера,
3) выясним, можно ли сделать результат невозможного вычисления единственным материальным следствием прогона квантовой программы,
4) заглянем внутрь квантового кулера.
Джозса определяет невозможные вычисления так: это существенным образом использующие квантовую природу регистров оперативной и постоянной памяти вычисления, при которых оказывается возможным получить интересующие нас результаты даже в том случае, когда компьютер находился в формально неактивном состоянии.
Следует сразу уточнить, что квантовый компьютер, владелец которого отправился с визитом вежливости в любимую кафешку или на башорг, на самом деле обычно не находится во включенном или выключенном состоянии, но в их суперпозиции. Это понятие мы и будем существенно использовать, исследуя дальнейшие возможности невозможных вычислений. Введем обозначения:
S – для регистра, отвечающего за переключатель питания квантового компьютера и потенциально способного пребывать в состоянии |ВЫКЛ> (т.е., |0>), |ВКЛ> (т.е., |1>), а также в их суперпозиции с определенными весовыми коэффициентами (обычно 1/sqrt(2), но не всегда).
O – для регистра вывода результатов вычислений, первоначально содержащего некоторое значение ф.
R – для пространства состояний внешних регистров, содержащих определенные данные и/или предназначенных для резервного копирования промежуточных результатов (в последнем случае они называются кучей или свалкой). В случае, если в ходе прогона алгоритма в течение некоторого времени Т получен определенный результат k, он записывается в О в бинарном виде с применением сложения по модулю 2.
Тогда с формально-математической точки зрения Манин [Ma1999] и Джозса определяют блок-схему вычислений с использованием квантового компьютера так:
ВЫКЛЮЧЕН: |0>|ф>|R> |0>|ф>|R> и ВКЛЮЧЕН: |0>|ф>|R> |0>|ф k>|R>
(Замечание. Поскольку адекватно отразить некоторые спецсимволы средствами html нельзя, я в особо сложных случаях буду применять систему записи математических символов и операций, принятую Кнутом в ТеХе.)
Для начала мы должны приготовить некоторое количество кубитов в начальном обнуленном состоянии. Протокол вычислений на квантовом компьютере (не путать с более частным понятием алгоритм вычислений на квантовом компьютере) представляет собой в данном случае совокупность следующих шагов:
- Некоторая линейная (более точно, унитарная) операция с конечным числом кубитов.
- Измерение состояния конечного числа кубитов.
- Двусторонняя вставка, то есть перенос состояния двух кубитов в S и О соответственно, ожидание в течение некоторого времени Т и обратное присвоение значений двум выбранным для этой цели кубитам.
После этого представим себе серию измерений на шаге 3, после каждого из которых переключатель может попасть в одно из двух возможных подпространств состояний: пространство, где он оказывается включен, и пространство, в котором он оказывается выключен. Мы получим в итоге два списка последовательных результатов, которые вместе с результатами измерений на шаге 2 образуют историю вычислений. Все возможные истории «склеиваются» в квантовое пространство состояний, объединяющее квантовое вычислительное устройство и систему, осуществляющую ввод данных и считывание результатов решения задачи с выбором из множества альтернатив.
Говорят, что последовательность исходов измерений регистра результатов т представляет невозможное вычисление, если мы можем по некоторым причинам быть твердо уверены как в том, что результат вычислений – это k и только k (на крайний случай, (ф k) и только этот) даже невзирая на то, что ни на одном шаге протокола суперпозиция состояний S не коллапсировала в состояние |ВКЛ> (т.е., |1>). В этом случае не имеет значения, что последовательность m может всецело относиться к истории типа «постоянно выключен» (all-off-inclusive history, мне очень нравится этот термин).
Это значит, иначе говоря, что:
- Нужный результат вычислений относился к истории, в которой компьютер был включен.
- Наделенная (естественным или искусственным) интеллектом система (программист или робот), измеряющая состояние регистра результатов и обнаружившая там свидетельства требуемого результата, относилась к истории, в которой компьютер был выключен.
Итак, компьютер работал и получил некоторый результат в одной параллельной вселенной, а программист существует в другой параллельной вселенной, связь между которыми ограничивается знанием результата вычислений. В той же вселенной, где существует программист, компьютер не работал. (Но это вовсе не значит, что программист не работал тоже, привет менеджерам по персоналу.)
Таким образом, понятно, что термины «бесплатные (или «ленивые») вычисления» полностью образны: в каком-то из миров работа квантового компьютера несомненно имела место, но все, что до нас доходит из этого мира, это некоторый с необходимостью ограниченный поток информации о результатах вычислений.
Для самой «задачи сапера» этот вывод формулируется более прозрачно, в духе антропного принципа: всегда существует по крайней мере одна вселенная, в которой взрыв бомбы как следствие вычислительного процесса имеет место, но чтобы считывание результатов вычислений стало возможным, должна существовать по меньшей мере одна вселенная, в которой этого взрыва не случилось. В этой вселенной существует экспериментатор, которому теперь, однако, ясно, что бомба за время хранения ничуть не потеряла своих смертоносных свойств.
В такой трактовке ясна связь невозможных вычислений с задачей о коте Шрёдингера.
Если кот в какой-то из вселенных погиб, но мы в своей вселенной зафиксировали, что он выжил, то нам ни в коей мере не угрожают все неприятные эффекты паров цианида, вырвавшихся из камеры, – потому что в нашей текущей версии мира ампула с цианидом, убившая кота, никогда и не разбивалась. С другой стороны, если мы обнаружили, что кот издох, можно в определенной степени утешить себя тем, что в некоторых параллельных мирах он продолжает оставаться вершиной эволюции.
Говоря о невозможных вычислениях, можно, например, присвоить результату «0» в соответствующем регистре ярлычок ЖИЗНЬ, а противоположному варианту «1» – ярлык СМЕРТЬ. (Есть мнение, что здесь уместнее слова «присутствие» и «отсутствие».) Невозможное вычисление дает результат «0», если в ходе коллапса мы оказались в той подсистеме пространства состояний, где переключатель по завершении работы оказался выключен, а иная подсистема для нас просто перестала быть. В противном случае мы вынуждены заключить, что прихоть судьбы забросила нас в ту вселенную, где компьютер не работал вообще ни мгновения, но это, впрочем, не помешало нам узнать все, что мы хотели. Образно говоря, частое наблюдение за состоянием регистра результатов «замораживает» квантовомеханически связанный с ним переключатель квантового компьютера в положении ВЫКЛ; более тщательный анализ, исключающий из рассмотрения «свалку», показал, что с увеличением числа прогонов Q квантового алгоритма вероятность обнаружить в регистре результатов верный ответ при выключенном компьютере растет как {cos[/(2Q)]}2Q. Это явление называется квантовым эффектом Зенона и встречается еще в алгоритме Дойча-Джозсы, который достаточно прост и известен, чтобы не упоминать о нем здесь отдельно.
Дальнейшая модификация «задачи сапера» связана с привлечением третьего вспомогательного кубита, – при этом формируется состояние, называемое «кот-зомби», чтобы отличить его от классического «кота Шрёдингера».
Что же это за хитрая животина такая? Рассмотрим начальное трехкубитное состояние |000>, эволюционирующее затем в суперпозицию
cos ф |000> + sin ф |100>,
где ф – фазовый угол вектора состояния системы в квантовом пространстве, ф = [/(2Q)]. В этом случае пространство возможных исходов измерений натянуто на восемь (23) векторов, два из которых представляют невозможное вычисление:
|k1> = () * (sin ф|000> – cos ф|100> + sin ф |001>), |k2> = () * (sin ф|000> – cos ф|110> – sin ф |001>),
причем = 1/sqrt(1+(sin ф)2). Исход |k> = |1> соответствует |k1>, а исход |k> = |0> соответствует |k2>. Совокупная вероятность обнаружить последствия невозможного вычисления по сравнению с простейшим случаем возрастает и составляет теперь 0.344. Конъектура Джозсы гласит, что такая вероятность достигнет 1 только при бесконечном числе прогонов алгоритма, а это опять, как и в первой заметке, отсылает нас в область сверхтьюринговых вычислений и машин Зенона-Томпсона.
Утверждение, что невозможные вычисления никогда не станут единственно возможными, сохраняет силу и для многокубитовых переключателей, хотя в этом случае оказывается, что вероятность хотя бы одного такого события в принципе можно довести до 1.
Теперь подумаем, что можно сделать для минимизации тепловых потерь квантового компьютера. Вопрос этот куда более заковырист, чем может показаться. Как справедливо заметили на Хабрахабре, кулер на кубит не поставишь и змеевики охлаждения к нему не прикрутишь…
Беннетт [Be1973], вероятно, первым обратил внимание на аналогию между схемой работы квантового вычислительного устройства и внутриклеточными химическими системами, ответственными за перенос генетической информации. Каждый из процессов биосинтеза включает длинную детерминированную последовательность манипуляций с генетическим кодом, где фермент действует как копирующая ленту машина Тьюринга. Надо заметить, что ферменты не просто записывают информацию на «ленту», но скорее производят ее. Копирование такой «ленты» – логически и химически обратимая операция. Именно это нам и нужно, чтобы минимизировать рассеяние энергии на вычислительных регистрах компьютера, работающего в молекулярном или атомарном масштабе.
Обратимый квантовый компьютер должен работать вблизи положения термодинамического равновесия.
Очевидно, впрочем, что у квантового компьютера, как и у биохимической внутриклеточной системы, имеется значительное число вероятностно распределенных состояний, из которых только одно представляет интерес, а остальные паразитны. Чтобы обеспечить приемлемую скорость вычислений, надо сделать так, чтобы движения в попятном направлении по ленте истории системы блокировались настолько эффективно, насколько это возможно. Образно говоря, квантовый компьютер, как и классический, характеризуется определенной «тактовой частотой», и для программиста первоочередной задачей будет подавить отклонение от этой «частоты» – декогерентизацию кубитов.
Если на одну логическую операцию квантовый компьютер создает один бит информационной (= тепловой) энтропии, то нижняя граница потерь энергии для такого устройства при комнатной температуре составляет примерно 3 ⋅ 10-21 Дж (= k ln 2, это значение называется пределом фон Неймана – Ландауэра). Это довольно впечатляющее значение, но надо сказать, что достичь его не менее сложно, чем приблизиться к абсолютному нулю шкалы температур.
Даже в ДНК-копировальных машинах, что работают внутри наших тел, энергетические потери на каждом «шаге вычислений» на порядок выше: биохимическим системам не только не нужно, но и опасно работать на скоростях быстродействия, близких к теоретическому максимуму.
Тем не менее, собственно тепловые потери квантового компьютера не идут ни в какое сравнение с таковыми для классического устройства. Более важная часть энергетических затрат связана прежде всего с тем, что каждое квантовое вычисление – существенно вероятностное. Если попытаться наблюдать квантовую память так, как если бы она была классическим регистром, мы просто получим некоторое значение целевой функции с вероятностью 1/N, где N – число кубитов в регистре.
На самом деле мы должны (как это, собственно, и делается в «задаче сапера») превратить один из кубитов l в индикатор состояния квантового устройства. Кубит l можно периодически наблюдать из внешнего мира, не рискуя внести непоправимую сумятицу в работу самого ядра квантового компьютера. Каждая правильная программа установит его в 1, если она остановилась и получила результат, и не будет взаимодействовать с ним в ином случае. Собственно, Дойч и определяет правильность квантовой программы (Q-программы) так: Q-программа правильна, если время ее работы конечно. Определение это подчеркивает важную роль наблюдателя-программиста в квантовых вычислениях: квантовый BSOD, будучи никем не наблюдаем, может продлиться до конца Вселенной…
Продолжение следует.
Оценить статью на сайте | 5 комментариев
Переслать
- Менеджмент highload проектов
Highload?
Что вообще такое highload (или высоконагруженные) проекты? Нет какого-то определенного порога, переходя через который проект становится высоконагруженным. Это скорее составное свойство, в которое входят несколько типичных характеристик:
- Много функционала. Это может быть большой набор модулей, как на порталах или соц. сетях. Это также может быть одно специфической направление, но очень глубокое (например, youtube.com или twitter). Второе встречается чаще.
- Постоянный рост. Неуспешные проекты не бывают высоконагруженными. Для того, чтобы стать highload нужен рост, постоянный и уверенный.
- У Вас есть потребность масштабироваться. Это самый важный момент. И это не означает, что у Вас должны быть десятки миллионов просмотров страниц каждый день. Все дело в аппаратном обеспечении и необходимости масштабироваться. Если у Вас стоит один сервер за миллион долларов, который сможет обеспечить Вам десятикратный рост, то до этого момента Ваш проект не высоконагруженный. И наоборот.
Управление высоконагруженным проектом очень не похоже на управление обычным проектом. Почему?
- Вам нужны специалисты экстра класса (как минимум очень хорошие специалисты). Таких найти трудно, даже за хорошие деньги. Рынок повернут так, что обычно именно они выбирают на какой проект пойти, а не наоборот.
- Сравнительно большие бюджеты на аппаратное обеспечение и его администрирование
- Стоимость ошибки очень большая. Как технической, так и стратегической
- Пройдя порог высокой нагрузки, каждая новая функция проходит жесткую модерацию на предмет потенциальной угрозы производительности продукта
- Постоянная работа над оптимизацией, вынимание подводных камней и избавление от бутылочных горлышек
Команда
Как и в любом проекте любой области, Ваша команда – это Ваше все. Умение принимать правильные решения, вовремя реагировать на проблемы, разумно подходить к решению задач – это важнейшие свойства ее членов. Не ищите идеал, но стремитесь к нему. Не торопитесь с выбором команды, выбирайте каждого участника тщательно и обдумано.
С технической стороны в проектах с высокой нагрузкой нет ничего заумного. Любой технический специалист может научиться этому. Но в команде обязательно должен присутствовать человек с опытом. Именно он будет ускорителем в решении постоянных проблем с нагрузкой. Кроме того, желательно такого человека поставить на позицию лидера команды, т.к. его опыт будет очень важен при обсуждении и внедрении новшеств.
Глава разработки
Лидер Вашей команды должен не просто управлять процессом разработки. Это человек, который должен понимать проект изнутри. Он будет помогать Вам принимать решения по поводу внедрения определенных изменений, нового функционала и дальнесрочного планирования.
Почему это важно. Представим себе работу над проектом в самом разгаре. Перед очередной итерацией управляющие проекта продумывают новую порцию функционала. На подходе две новые “фичи”: личные сообщения и фотоальбомы. Вы уточняете сроки у разработчиков и получаете одинаковые оценки – по две недели на каждую задачу. Вы решаете, что они равноценные и ставите их в план одну за другой. Проходит две недели, и Вы с удивлением узнаете, что для запуска фотоальбомов Вам понадобиться докупить два сервера и перейти на новый тарифный план в датацентре. Не запланировав заранее этих расходов, Вы вынуждены отложить запуск. В результате потеряны две недели. Хотя это и не такая далекая от практики проблема, в реальности все гораздо сложнее.
Каждую Вашу идею обсуждайте и взвешивайте не только с точки зрения бизнеса, а и с технической стороны. Это не значит, что нужно просто отказываться от каждой более-менее тяжелой функции. Нет, наоборот, техническая команда поможет выработать оптимальное решение и правильно построить план.
Тратьте много времени на то, чтобы глава технической команды (а желательно и каждый ее учасник) понимал Ваши приоритеты, знал проект изнутри – какие функции первостепенны, какие второстепенны, какая стратегия у проекта и т.п. Это сэкономит кучу времени при принятии локальных решений. Например, Ваш системный администратор при аварийных ситуациях сможет сам принять решение – отключить на время определенную функцию или позвонить разработчикам и попросить срочно исправить.
Минимизируйте и приоритезируйте
Одно из важных умений при работе с крупным проектом – это умение минимизировать, отбрасывать лишнее, отделять действительно важное от того, что можно отложить. Не менее важно доносить это до исполнителей. Разработчик должен понимать, какая часть его задачи несет в себе существенное влияние на бизнес, а какая малое или вообще ничего не значит. Одна из Ваших основных задач, чтобы это понимание обязательно было у всех членов команды. Следует периодически проводить небольшие встречи, на которых рассказывать о ближайших планах, приоритетах и стратегии.
Типичная работа над новой задачей на highload проекте выглядит так:
- У нас появляется новая крупная задача
- Мы детально обсуждаем ее, расставляем приоритеты. Делаем взвешенную оценку важности каждого компонента новой функции для бизнеса и для продукта
- После этого думаем, что можно выкинуть из задачи – без чего можно начать, попробовать, протестировать эту функцию. При правильном подходе этот процесс позволяет сократить первоначальный объем работ в 2…3 раза.
- Приступаем к работе над задачей
Такой подход к реализации имеет также большое значение для бизнеса. Никто никогда не знает, станет ли какая-то функция популярна или нет. Зачастую приходится отказываться от какой-то функции через месяц или два после ее релиза, т.к. ей никто не пользуется. Минимизация задач на предварительной стадии очень сильно экономит время и делает работу в разы эффективнее.
Рефакторинг
В одно суровое утро к Вам приходит глава разработки и говорит: “привет, нам нужен рефакторинг такого-то модуля или мы не справимся с нагрузкой”… Не нужно паниковать. Рефакторинг – это нормально, но не тогда, когда на него бросают все технические ресурсы. Рефакторингом нужно заниматься постоянно, но малыми порциями. В любом случае, если так говорит глава разработки, Вам нужно ему доверять. Иначе он Вам не подходит. Если Вы считаете, что этот раздел переделывать не нужно – вина Ваша, Вы плохо донесли приоритеты до команды.
Важно полагаться на мнение технической команды не только поэтому. Очень часто существуют определенные скрытые, не понятные для Вас зависимости внутри системы. Такие вещи трудно объяснить и попытки донести это до нетехнических людей обычно напоминают неубедительный бред. Но ведь они не записывались в преподаватели. Просто убедитесь, что это решение принято с учетом Вашей стратегии и приоритетов и были рассмотрены все альтернативы. Обсудите это, часто в результате вырабатывается новое и более оптимальное решение (например, Вы решаете на время отключить несколько незначительных функций, которые создают много проблем).
Настройтесь на динамику
Будьте готовы к неожиданностям. В highload проектах их очень много. Это могут быть как технические трудности, возникающие в условиях роста нагрузки, так и стратегические повороты из стороны в сторону. Приготовьтесь к этому сами и приготовьте свою команду. Важно понимать, что Вы не “строите 10 месяцев большой проект”, а на протяжении 10 месяцев развиваете проект. Отличие в том, что во втором случае дальнесрочная стратегия имеет только обзорный/поверхностный характер, а детали поведения вырабатываются исходя их показателей в моменте.
И не менее важное замечание – держите баланс между анализом и разработкой. Не поддавайтесь на уловки некоторых программистов часами болтать об осмысленности и философии того или иного подхода. Концентрируйтесь именно на движении к результату, а не на планировании этого движения. Все равно все пойдет не по плану 
Оценить статью на сайте | 8 комментариев
Переслать
- Квантовая информатика с человеческим лицом
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, и, тем не менее, компьютер продолжает работать. По очевидным причинам описанную модификацию эксперимента называют «задачей сапера». Немало у нее общего и с квантовым бессмертием. О том, как все это может выглядеть на практике, можно почитать в отличном романе Нила Стивенсона.
Говорят, что все беды от лени, но мы только что убедились, что лень может быть и очень полезна для постижения природы окружающей Вселенной!
Продолжение: Квантовая информатика для котов и людей: антропный принцип, эффект Зенона и фермент в роли машины Тьюринга
Оценить статью на сайте | 16 комментариев
<a href="mailto:?subject=%3F>%3F%3F%3F%3F%3F%3F%3F%3F%20%3F%3F%3F%3F%3F%3F%3F%3>F%3F%3F%3F%20%3F%20%3F%3F%3F%3>F%3F%3F%3F%3F%3F%3F%3F%3F%20%3F%3F%3F%3F%3F&body=h>ttp%3A%2F%2Ffeedproxy%2Egoogle>%2Ecom%2F%7Er%2FDevelopersOrgUa%2F%7E3%2FwkIc0uRBS>Tk%2F%0d%0a%0d%0a%2D%2D%0d%0ah>ttp%3A%2F%2Fwww%2Erss2email%2Eru%20%2D%20%3F%3F%3F>%3F%3F%3F%3F%3F
developers.org.ua
