Python conf in Kharkiv, Nov 16 with Intel, Elastic engineering leaders. Prices go up 21.10

Квантовая информатика для котов и людей: антропный принцип, эффект Зенона и фермент в роли машины Тьюринга

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 нельзя, я в особо сложных случаях буду применять систему записи математических символов и операций, принятую Кнутом в ТеХе.)

Для начала мы должны приготовить некоторое количество кубитов в начальном обнуленном состоянии. Протокол вычислений на квантовом компьютере (не путать с более частным понятием алгоритм вычислений на квантовом компьютере) представляет собой в данном случае совокупность следующих шагов:

  1. Некоторая линейная (более точно, унитарная) операция с конечным числом кубитов.
  2. Измерение состояния конечного числа кубитов.
  3. Двусторонняя вставка, то есть перенос состояния двух кубитов в S и О соответственно, ожидание в течение некоторого времени Т и обратное присвоение значений двум выбранным для этой цели кубитам.
После этого представим себе серию измерений на шаге 3, после каждого из которых переключатель может попасть в одно из двух возможных подпространств состояний: пространство, где он оказывается включен, и пространство, в котором он оказывается выключен. Мы получим в итоге два списка последовательных результатов, которые вместе с результатами измерений на шаге 2 образуют историю вычислений. Все возможные истории «склеиваются» в квантовое пространство состояний, объединяющее квантовое вычислительное устройство и систему, осуществляющую ввод данных и считывание результатов решения задачи с выбором из множества альтернатив.

Говорят, что последовательность исходов измерений регистра результатов т представляет невозможное вычисление, если мы можем по некоторым причинам быть твердо уверены как в том, что результат вычислений — это k и только k (на крайний случай, (фk) и только этот) даже невзирая на то, что ни на одном шаге протокола суперпозиция состояний S не коллапсировала в состояние|ВКЛ> (т. е.,|1>). В этом случае не имеет значения, что последовательность m может всецело относиться к истории типа «постоянно выключен» (all-off-inclusive history, мне очень нравится этот термин).

Это значит, иначе говоря, что:

  1. Нужный результат вычислений относился к истории, в которой компьютер был включен.
  2. Наделенная (естественным или искусственным) интеллектом система (программист или робот), измеряющая состояние регистра результатов и обнаружившая там свидетельства требуемого результата, относилась к истории, в которой компьютер был выключен.
Итак, компьютер работал и получил некоторый результат в одной параллельной вселенной, а программист существует в другой параллельной вселенной, связь между которыми ограничивается знанием результата вычислений. В той же вселенной, где существует программист, компьютер не работал. (Но это вовсе не значит, что программист не работал тоже, привет менеджерам по персоналу.)

Таким образом, понятно, что термины «бесплатные (или „ленивые“) вычисления» полностью образны: в каком-то из миров работа квантового компьютера несомненно имела место, но все, что до нас доходит из этого мира, это некоторый с необходимостью ограниченный поток информации о результатах вычислений.

Для самой «задачи сапера» этот вывод формулируется более прозрачно, в духе антропного принципа: всегда существует по крайней мере одна вселенная, в которой взрыв бомбы как следствие вычислительного процесса имеет место, но чтобы считывание результатов вычислений стало возможным, должна существовать по меньшей мере одна вселенная, в которой этого взрыва не случилось. В этой вселенной существует экспериментатор, которому теперь, однако, ясно, что бомба за время хранения ничуть не потеряла своих смертоносных свойств.

В такой трактовке ясна связь невозможных вычислений с задачей о коте Шрёдингера.

Если кот в какой-то из вселенных погиб, но мы в своей вселенной зафиксировали, что он выжил, то нам ни в коей мере не угрожают все неприятные эффекты паров цианида, вырвавшихся из камеры, — потому что в нашей текущей версии мира ампула с цианидом, убившая кота, никогда и не разбивалась. С другой стороны, если мы обнаружили, что кот издох, можно в определенной степени утешить себя тем, что в некоторых параллельных мирах он продолжает оставаться вершиной эволюции.

Говоря о невозможных вычислениях, можно, например, присвоить результату «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, будучи никем не наблюдаем, может продлиться до конца Вселенной...

Продолжение следует.

LinkedIn

12 комментариев

Подписаться на комментарииОтписаться от комментариев Комментарии могут оставлять только пользователи с подтвержденными аккаунтами.

Супер! Особливо дякую за посилання в статтях — буду потроху розбиратись, а то не все зрозумілоБлін, з інституту такої зацікавленості в темі не відчував

Да не за что: -) Тема эта при правильном подходе действительно взрывает мозг и формирует новый взгляд на жизнь. Когда поутихнет срач насчет налогового кодекса, сбацаю продолжение о поисковых агентах и семантике квантовых языков программирования. А то сейчас "обком закрыт, все ушли на фронт"©

Супер! Особливо дякую за посилання в статтях — буду потроху розбиратись, а то не все зрозуміло.Блін, з інституту такої зацікавленості в темі не відчував:) Дякую за статті!

@ Сашко

много букв и формул

как раз в моем изложении их самая малость: (Ты бы видел оригинальную работу того же Шора, там без хеннесси не разберешься:)

хотя вроде бы уже и не «школота, минусующая эту запись»

нет, ну к тебе это замечание не относится — да и средний балл подрос до приемлемых значений

кроме теории есть что в статьях?

Нет, я в научных изданиях по информатике не печатался. Как-то пропала охота связываться с яйцеголовыми scientific advisors, да и охват аудитории будет не тот, что нужен.

Просто знаю, что на Украине есть люди разрабатывающие квантовые компьютеры, с ними не связан?

Ну, если и есть, то я сам по себе.

hellip, извини, но статьи не осилил, много букв и формул (хотя вроде бы уже и не «школота, минусующая эту запись»)...но интересно стало, кроме теории есть что в статьях? Просто знаю, что на Украине есть люди разрабатывающие квантовые компьютеры, с ними не связан?

@clewer_one, +1@hellip, таки действительно слишком быстрый темп. хотя... Вы пишите, в любом случае можно по свободе перечитать. я пожалуй сначала начну еще раз. чтобы грокнуть, так сказать, во всей полноте

@ clewer_one Возможно, ты прав. Дело в том, что я сначала набросал объединенную статейку, потом увидел, что она получается слишком большой, и разбил на две части. Последнюю потом разбавил откликами на комменты. Собственно, поэтому во внутренней нумерации стоит 1а, а не 2. @ Аноним с удовольствием, сударь, но говорите ли вы от имени всех анонимусов? есть у меня на этот счет большое сомнение, потому как находится школота, минусующая эту запись: (

Ты молодец! Как на меня темп за быстрый, я вот ещё прошлую не освоил, а тут уже продолжение лежит.

hellip, я теперь тебя буду звать на Вы. (Прочту завтра, когда будет головая свежая)

Нет, не последний. Это зависит от того, взлетит ли самолет выживет ли сайт в его нынешнем виде -:) Я ведь и начал эту серию статей, глубоко тронутый призывом Макса «все на борьбу с флудерами».Также статью можно обсуждать здесь.

я плакал...зыэто последний очерк?

Подписаться на комментарии