Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2 (1156795), страница 56
Текст из файла (страница 56)
Например, мы конструируем О( 4 ) из венпыей g(з) с помощьюсхемыXJ.r,_J_о--4--~j,_-хзу~+------XJх,охзуljJ х, ·Х2·Хз.I'ель пocлeдtiCIU О(З) ·веr-пиля- верпуть вспомогательному бmу его начальное значение, равное пулю. В действительности, добавив еще один а( 3 J-вен-294ГЛАВА бтиль, можно реализовать 8(4 ), коmрый работает независимо от наqальногозначения вспомогательного бита:х,Х2wхз.-'Х1rХ2тIw--хзСнова мы можем искточить последний нептиль,ccJwнас не беспокоитизменение значения вспомогательного бита1 .Мы можем убедиться в rом, что вспомогате.;IЬНЫЙ биr действительно необходим.
Поскодьку О( 4 ) предстамяет собой нечетную перестановку (фактически подстановку) 16-ти четырехбитоных строк, он переставляет 1111 и 111 О. Однако вез), действуя на любые чш бита из четырех,осуществляет четную перестановку; например, действуя на последние трибита, он переставс-mет О 111 с 011 О или 1111 с 11102 Поско;1ьку нроизведение четных перестановак также является четным, мы не можем получить48( )как нроизведенне ВСНТИЛСЙ О(З), действующее ТОЛЬКО на lJCTЫpeбита.Конструкцию О( 4 ) из четырех еСЗ) можно непосредственно обобщитьна конструкцию оСп) из двух eCn-l) и двух ()(з) (только расширив х 1 в приведеиной выше диаграмме до нескольких битов).
Итерируя эту конструкцшо, МЫ ПОдучИМ О(п)_СХему, СОСТОЯщуЮ ИЗ 2n~ 2 -t- 2n-З- 2 веНТИЛеЙ (J(З).Более того, ;J)IЯ этого достаrочно rо:1ько одноrо вспомогательного бита?>.(Если нам пеобХО){ИМО построить (J(n). то для .эmго по;щйдет любой доС1)'ПНЫЙ вспомоrательный бm; так как схема возвращает ему с го начальное значение.) Следующим шагом заметим, что. соединяя &(n) с вентилямиNOT,мы можем в действительности менять значение контрольной строки,1На самом деле Восстановл~ние uачадьноrо значения вспомогательного бита ш, осуществ!Diе~юе в ~той схеме вторым верхним ()( 3 )-вентилсм, .118J1Иется необходш.юй ооерацисй. Именноблагодаря этому на выходе второго нижнего о(з)_вентиля нолучается Jy 9 (wхз ЕВ х 1 x 2 x 3 )j Ef!щх 3 =-у ffi х х 2 х 3 .
Носледнее равенство легко проверяется с учетом коммутоnивности и ас1социативнос"I"И сложения по моду;Iю 2. - Прwи. ред2По-видимому aii'Юp имеет ввиду, чrо в< 4 >-венПUiь осущестRJ1&ет нечепюе количествоuетривиат.нuх пол:становок (одну), а ()( 3 )-вентиль- четное (две). -llpuм. ред.3С больцшм нспомоштельным пространством можно значительно эффективнее построilтъ o(n) из (JCJ) вентилей (см. упражнения).6.1. КЛАССИЧЕСКИЕ (ВЫЧИСЛИТЕЛЬНЫЕ) СХНМЫ295<<упранляющей» вентилем. Например, схемаХ2----+-----х,_._-···$--у--4-----1инвертирует значение у, если х 1 х 2 х 3 =010,и действует тривиально в nротивном случае. Таким образом, эта схема пероставляет две строки:и0101.Подобным образом, с ншющью венТИJiей еСп) иNOT0100можно придумать схему, которая переставляст ,1юбыс дне п-бИ'Iuвые С'IJ)ОКИ, отличающисся только одним битом.
(Расположение бита, которым они отличаются,выбирается R качсстне цели вентиля &(1 •) .)Но фактически подстаиовка, обменивающая любые две п-битовыестроки, может быть представлена как произведение по,пстановок, коrорыеобменивают строки, отшrчающиеся только ощmм битом. Если а 0 и а 8две строки, расстояние Хемминга между которыми равноs(отличаются-sпозициями), то существуст цепь(6.41)такая, что каждая строкаu тrойпоследовательности удалена от ближайшихсоседей на равное единице расстояние Хемминга.
Следовательно, каждаяиз подстановак(6.42)может быть реализована как венти.1ь е<п), соепиненный вентилями 1\ОТ.Комбинируя Iщцстановки, находим(а 0 ,а,) = (а,_ 1 ,а.,)(а,2 ,а,_ 1 ) ...... (а 2 ,а3 )(а 1 ,а 2 )(а 0 ,а 1 )(а 1 ,а 2 )(а2 ,а 3 ).(6.43)мы можем сконструироваtь подс·1·аиовку с равнымизsрасстоянием Хеммиш·а2s-1 подстановкис едшшчным расстоянием Хсмминга.что мы можем построить (а 01 а 5 ) из вентилей оСп) и NОТ.Отсюда СJтедует,ГЛАВА 6296Наконец, посколысу каждая нсрестановка я:впяется произведением подстановок, мы показали, что шобая обратимая функция ·n-биrов (каждаяпсрестаноi\Ка п.-биншых строк) представ.пяст собой произведение Rснти.1ей О(З) и вентилей NOT, использующее то;н.ко оцин бит вспомогатс. "'ьпого.пространства.КонечноJ операцияNOTможет быть выполнена с помощью JJСнтиля е('), если мы фиксируем два входящих бита равными единицам.
Такимобразом, вентиль Тоффоли &(з) является универсальным дия обратимых вычислений, если мы можем фиксировать входящие биты и отбрасывать выходящие.6.1.4.Компьютер бильярдных шаровДвухбитовых вспти.:Iей достаточно для увиверсальных необратимыхвычис,1еннй, но для универсальных обратимых вычислений необходимытрехбитовые нентили. Возникает соблазн сказать, что д..-ur их реализациинеобходимы <прехчастичные в:Jаимодействию>, так что СОЗJщние обратимого аппаратнот обеснсчения яшшется бо.-тее сложной проб.псмой, чем создание необратимого.
Однако это угверждение в какой-m мере может бытьобманчивым.Фредкии описал, как можно построить универсальный обратимый компьютер, в котором фундаментальным взаимодействием является упругоесшлкновение "ежду двумя бильярдными шарами. Шары радиуса 1//2нвижутся по квадратной решетке, nерщщ которой равен единице. В каждый целочисленный момент времени центр каждого шара находится в ушерешетки; наличие или отсутствие шара в данном узле (в ::пот момент времени) кодирует бит информации. В течение каждого единичного интервалавремени каждый (подвижный) шар проходит единичное расстояние вдольодного из направлений решетки. Иногда, в целочисленные моменты времени, проИСХОДИТ уnругое рассеяние на 90° N~YX шар011, занимающих уз..~ы~удаленные друт <П лрута на рассшяние /2 (соединенные диагональю ячейки решетки).Прибор nр01раммируется закреrшением части шар<Jв в некошрых узлах, I<оторые действуют как идеальные отражатеШI.
После за,;хания начальных положений и направлений движения подвижных шаров система выполняет программу, эволюционируя в течение конечного илтерваJJа временив соответстнии с механикой Ньютона. Резу;1ы·ат считывается 11утем наблюдения конечных пшюжений t!О)l.Rижных шаров. Столкновения недиссипатшшы, так что после обращения всех скоростей вычис;tснис может бытьпройдено н обратном порядке.6.1. КЛАССИЧRСВ:ИЕ (ВЫЧИСЛИТЕЛЬНЫЕ) СХЕМЫ297Чтобы показать, что ::на машина является универсальным обратимымкомпьютером, мы должны объяснить, как в ней реализовать универсальныйвенти.1ь. Удобно рассмотреть трехбиrовый вентиль Фредкина(x,y,z) ~ (x,xz+xz,xz+xy),{6.44)который меняет местами у иz, ecJiи х = О {мы ввели обозначение х == -..т).
Rы можете убедиться в том, что венти.-:ть Фредюша может моде.-пrроnать венти:rьNAND/NOT,если мы фиксируем входы и игнорируемВЫХ0,11Ы.Мы можем посчюить вентиль Фредкина из более примитивного обьекта, венти.ля-переключателя. Переключатень преобра.зует два бита в три,1\Сйствуя по правилу(о:,у) ~(6.45)(x,x·v,x·y).хХ·ух·уЭтот венти.1ь «обратим» в том смысле, что его можно пройти в обратномнаправлении, действуя на ограниченный трехбитвый вход, принимтощийодно из четырех значений:(6.46)Более топ), 11ереключатель сам по себе универсален; фиксируя входы и игнорируя ныходы, он может выполнить операциюход),AND{второй выход) н СОРУ {у=1,NOT(у =1,третий выпервый и второй выходы). Тогдане УiЩВительно, что, комбинируя перскшочатсли, можно построить универсальный3--+zх3вентиль.
Действительно, схемаГЛАВА 6298образует венти;JЬ Фредкипа из четырех иереюпочателей (два из них проходятся в примом напра:вденни, два других--в обращом). Время за,держки,необхО/\И:мос ддя синхронизации, явно не показано.В комньютере билЬ>!рдных шаров лере"'~юча:rе;rь строится из такихдвух 01ражатслсй, чтобы (в случае х =у=1) два движуrnихсяшара стопкну;шсь дважды. В этом случае траектории шаров имеют видухШар, помеченный как х, вылетает из вентиля вдопь rой же траектории(и в то же самое 11ремя) независимо от надичия ипи отсуrстния другогошара. Однако при х =1nоложение друrого шара (есди он имеется) смещается вниз по сравнению сeruконечным положением при х=О-этои есть переЮJючателъ.
Коль скоро мы можем ностроить нерек.11Ючатель, тоиожем 11остроиТI. и НСПТ11ЛЬ Фредкнна и, таким образом, рсали:ювать универсальную обратимую до111ку на комньюrсре билъяр!1НЫХ шаров.Очевидной слабостью схемы бильярдных шаров является то, что нача.:tьные ошибки положений и скоростей шаров будут быстро накапливаться и в К'Онце концов ко~пыотср о.кажстся нссос·юятельны:!l.t:. Как отмеча.lОСh11 первойглаве (а Ландаузр нас·юятелыю подчеркивал это).
подобнымнедостатком бу11,ет страдать любая пре;щагаемая схема нсниссипативныхнычислений. Чтобы контролировать ошибки, :мы должны быть в сос"Iоянии сжимать фазовое пространство прибора, '!ТО с необхщимостью будетдиссипативным нроцессом.6.1.5.Экономия пространстваНо KJIOMC проблемы контроля ошибок, есть еще один к.юочевой вопрос,касающийся обратимых вычислений. Как распорядип~ся всномоrатедьным11ространством, необходимым длямым?roro,чтобы сделать вычисление обрати6.1. КЛАССИЧЕСКИЕ (DЫЧИСJШТЬЛЬНЫЕ) СХF.МЫ299Обсуждая универса.1ьность вентиля Тоффоли, мы видели, что в лрипципе можно выпо;rnить любое обратимое вычисление, используя очень малое вспомогательное nространство.
Но на практике может оказаты:я неRероятно сложно nонять, как выполвиТI. конкретное вычисJ[ение, используяминимальное яространство, и во всяком случае экономия пространства может обернуться непомерным расходом времени.Существует общая стратегия моделирования необратимого вычисления на обратимом компьютере. Каждый необратимый вентиль,NOTЮIИСОРУ, можно моделnровать вентЮiем Тоффоли, фиксируя входы и игнорируя выходы. Мы накапливаем и сохрааяем весь «мусор» выходящих битов, которые необходимы, чтобы обратить этапы вычисления. Вычисление выполняется вплоть до завершения, нос:1е чего делается копия ВЬIХо;-щ.(Эта СОРУ-операпия логWiески обратима.) Затем вычисление nроизводится в обратном порядке, чтобы избави гься от «мусора>> и вернуп, все регистры в их начальные состояния.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
