Главная » Все файлы » Просмотр файлов из архивов » PDF-файлы » Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2

Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2, страница 56

Описание файла

PDF-файл из архива "Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2", который расположен в категории "книги и методические указания". Всё это находится в предмете "квантовые вычисления" из седьмого семестра, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст 56 страницы из PDF

Например, мы конструируем О( 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роизводит­ся в обратном порядке, чтобы избави гься от «мусора>> и вернуп, все ре­гистры в их начальные состояния.

Свежие статьи
Популярно сейчас