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

С помощью этой nроцедуры обратимаясхема осуществляется примерно дважды, до тех пор, пока не будет вы­полнена моделирусмая необратимая схема, а весь генерируемый при ~томмусор-· выброшен без какой-либо диссипации и, сле;~овате.:Jьно, энергети­ческих затрат.Эта проце11ура работает, но требует 01ромною nростраuства памятисе необходимый объем растет линейно с продюжитепьностью 'С модели­руемого необратимого вычиспения. ФакТWiески nространсnю можно ис­полиовать гора1до более эффективно (лишь с минимальным замедлением),так что его необходимый объем растет какlug Твместо Т.

(То ес1ъ су­щесiвует универсальная схема. требующая пространства схlogT;конечно,моделируя конкретное вычисление, можно добиться даже лучшего резуль­тата.)Чтобы зффективнее нслолъзовать нространство, раз11елнм вычислен11ена бюее мелкие шаги приб;шзительно одинакового размера и, когда этовозможно, будем обрашать их в нроцессе вычисления. Однако, подобно то­му как мы не в состоянии выполнить k-ый шаг вычисления до тех пор, nокане завершенk-1-ый шаr; мы не сможем обратить k-ый шаг, если пред­варительно был обращен k -1-ый шаг 1 .

Необходимый объем пространства(чrобы хранить наш мусор) будет расти как максимальное значение чис.:шшагов в пере;~ за вычетом количества выnолненных шагов назад.Проб.1ему, с которой мы столкнулись, можно сравнит•, с обратимой иг1Мы скромно предполаrс1ем, что не настолыrо прозорливы:, чтобы: nредвидеть, какая часп.выхода k~ 1-ro шага может потребоваться: позже. Слсдователыю, мы сохраняем полную записьоосrояния машины после k ~ 1-ro ma(·a, коrорая не должна удаляться до rex пор, пока не будетобнов.:1сна запись пос.1е завершения следующего шаrа.Г;IАВА3006рой ка.«ешкамu 1 .

Выполняемые ШЗJlf образуют одномерный ориентирОI\ВН­ный граф с уJлами~ пронумерованными как1, 2,3, ... , 1'.Выполнение k-гошаrа моделируется: помещением камешка в J>-ЫЙ узел графа, а выnо.ане­ннеизk-ro шага в обратном направлении моделируется удалением камешкаk-roузда. В начале игры нет узлов, занятых камеrпками, а с каждымходом мы их добав.тmем или удаляем. Однако мы не можем поместить ка­мешек в k-ый узел (за исключениемk = 1)до тех пор, пока не заполнен1-ый, а также мы не можем удалить камешек из k-го узла (за исключе­k-ниемk = 1),если свободен1-ый узел. Задача в том, чтобы запо,1Нитьk-узел Т (завершить вычисление), не используя большего, чем это необходи­мо, количества камешков (генерируя минимальный обьем мусора).Фактически с помощьюnка.'lешков мы можем .цостичi> узJ1а Т=2 11-1,но продвинуться дальше не сможем.Можно построить рекурсивную проце,~уру, позnоляюшую добратьсяzn- 1 -Io узла с помощью n камешков, оставляя в игре mлькодо Т =один камешек.

Пусть F 1 (k) обозначает помещение камешка в k-й узел, аF 1-1( k)- удаление камешка из k-ro узна. Тогла 2(6.47)остап. :1яст камешек в уз.1сиспользуя максимум два камешка на про­k = 2,межуточных этапа.х. Анало1·ично(6.48)достигает узнаk = 1, используямаксимум три камешка, а(6.49)достигает уззаk -· 8,используя. четыре камешка. Очевидно, можно по­строить процедуру Fn ( 1, 2" -I ), которая использует максимум n камешкови оставляет в игре один. [Программа(6.50)оставляетu игревсеnкамешков и гюзво.1яет зююлнить мак:сима.л.но уда­ленный узел k = 2"- 1.]Р.1Как бы ..10 отмечено Беннетом.

Относительно последнего обсуждеНИJI с.\!.: М. Li andVitanyi, Reversihility and Adiabatic CompuJation: 1Гading Лте and Space jOr Energy, Рте.R. Soc. London, А452, 769-789 (1996); quant-ph/9703022.2I!равые •ысти (6.47)- (6.50) следует читать с1ева Н<tПраво. Именно в чом nopЯ;lKe вы­полняются описываемые ими действия.-Прим. ред6.1. КЛАССИЧЕСКИЕ (ВЫtiИСЛИТЕЛЬНЫЕ) СХЕМЫПонимаемая как прш-ра1\1ма для выполнения Т:::: 2n · 1301шашв вычис­ления, ·па стратегия игрока в камешки предстаа;Iяст собой моделирование,требующее роста нространства как n ~ log 1'. Насколько щюдолжитсль­ным может быть это модеJШ.рование? На каждом этане описанной вышерекурсивной процедуры два шага вперед заменя.лись [I;Вумя шагами впереди ол:ним назад. Следовательно,Tirr=2п шагов необратимоrо вычисдениямоде.лируются 1~ev = зп шагами oбpanrмoro вычисления илиТre\•=(т )JogЗ/tog2 =(т)t,ss.1п1rr(6.51)'мы имеем ~еренный степенной закон замедления.В действительности мы можем уменьшип.

замедление до(6.52)при .iJЮбом Е>О. Вместо тоtо чтобы заменять два шага вперед двумя1! шагов вперед f шагами впередn этанов рекурсивная процедура до­n( f -1) + l камешкоn. Теперь мы име~шага\tи нперед и одним нюад, заменими€-1-им шаюм назад. Состоящая нзстигает узла f!1, используя максимумем Тiп -_ еп, а Trev ::::-:: (2f'- l)п, так что'1',....."(Тrev)log(2f-l)/Jogf.1rr(6.53)'nоказатель степени за~едления равенlog(2€- 1)log 2i + log ( 1 -ff)log еlogflog2o;1+-log<."'(6.54)а требуемое пространство растет какS о;logTnt о; t logf.Таким образом, для любого фиксированного Е(6.55)>О мы можем добюъся S,растущего как logT, и замед.ления, не большего чем (1iп) 1-+-с:.

U1дя игрыв камешки зто не оптимальный способ, если наша цель-продвинутьсякак можно дальше, используя минимально возможное коmrчество камеш­ков. Мы испо.-п.зуем больше камешков, чтобы добраться до Т ~го шага, заюделаем зто быстрее.)!'ЛАВА б302Итак, мы видим, что обратимая схема может уснешно моделироватьсхему, построенную из необратимых вентилей, не требуя персальных ре­сурсов памяти и не вызывая неразумно большого замед;Iсння.

Почему отоважно? Вас может беспокоить, что nоскольку обратимое вычисление <пруkнее» необратимоrо,roклассификация сложносrn зависит от 1ого, какимивычислениями мы пользуемся, обратимыми или необратимыми. Однако этоне так, поскольку необратимый компьютер легко моделируется обратимым.6.2.Квантовые схемыТеперь мы готовы сформулировюъ матема:111ческую модель квантово­го КОМIJьюrера. Мы обобщим мо~ель классической вычислительпой схемына модель квантовой вычисmrте.1ъной схемы.К:шссический компьютер оперирует битами. Он оснащен конечнымнабором вентилей, которые могут применяться к множеству битов. Кван­товый компьютер оперирует кубитами.

Будем предполагать, что он то­же оснащен дискретным набором фундаментальных компонентов, назы­ваемых кrюптовыми вентwmми. каждый квантовый вентиль представ.LЯ­ст собой унитарное преобразование, действующее на определеннос чис:юкубитов. В квантовых вычислениях конечное количество n кубитов пер­воначадьно полагаются имеющими значение/00 ... 0}.Выполняемая схе­ма nостроена из конечного чис;rа квантовых вентилей, действующих наэти кубиты.

Наконец, выполняется измерение фон Неймана всех кубитов(или некотороrо подмножества кубитов), проецирующее каЖдый из нихна базис{/0}, /1}}.Резулr,тат этого измерения является резушпатом вычис­ления.Некоторые особенности этой мрде;ш 1ребуют комментария.(1) Неявно нодразумевается, но очень важно, что гильбертоно простран­ство прибора имеет естественное разложение на тензорное произведе­ние пространс-тв б<JJiee низкой размерности, в данном случае-дву­мерных пространств кубитов. Конечно, вместо этого мы могли бы рас­смюрнвать тензорное произведение, донустим, кутритов. Но в любомслучае мы считаем, что существует естественное разложение на подси­стемы, которое соответствует квантовым вентилям, действующим од­новременно -rолько на несколько подсистем.

С математической точкизрения зто свойство вентилей ЯВJIЯется решающим дня формулиров­ки хорошо определенншu понятия квантовой сложности. С физиче­ской точки зрения фундаментальной причиной естественного разJiоже-6.2. KBAHTORЬIE СХЕМЫ303ния на подсистемы является локалыюсть; реа.ш,ные квантовые венти­ли должны дсйсmовать в Оl"Раниченной области пространства, то есть1<омньютер разбивается на nодсистемы, взаимодействующие только сосвоими ближайшими соседями.(2)Так как унитарные преобразовання образуют континуум, может пока­заться необязательным: посrулировать, чrо машина может выполнятьтолько выбранные нз дискретного множества квантовые операции.

Темне менее мы принимас:м это ограничение, поскольку не хотим, сталки­ваясь с выполнением нового вычисления, всякий ра3 изобретатьeroновую физическую реапизацию.(3)Мы могли бы допустить, чтобы наши квантовые вентили были суперо­ператорами, а конечным измерением-ПОЗМ. Но поскольку мы мо­жем просто моделировать суперопсратор, выполняя унитарное преоб­разование в расширенной системе, или-- ПОЭМ,вЫПОJШЯЯ измерениефон Неймана в расширенной снс-rеме, сформулированная модель об­ладает достаточной общностью.(4)Мы могли бы допустить, чтобы заключительное измерение бьuю кол­лективным измерением или проектором на друюй базис. Но mобоетакое и~мерение можно реализовать, вьтолняя nодходящее унитарноенреобразование после проепирования на стандартный базис{10/, 11) }n.Конечно, сложные коллективные измерения JШШЬ с некоторыми за­труднениями можно преобразовать в измерения в стандартном бази­се и при характеристике сложности алгоритма э111 трудности следуетиметь в виду.(5)Мы могли бы допустить наличие измерений на промежуючных этапахвычислений с последующим выбором квантовых вентидей.

обуслов­ленным резудьтатами этих измерений. Но фактически тот же результатвсегда может быть достигнут с nомощью квантовой схемы, в которойвсе измерения отложены вшrоть 110 ее окончания. (Хотя в принципсмы можем отложить измерения, на практике может оказаться полез­ным их выполнение на промежуточных этапах квантового алгоритма.)Будучи унитарным nреобразованием, кваитовый вентиль обратим. Факrи­чески классический обратимый компьютер представляет собой частныйслучай кванwвого компьютера.