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

Это унuтарная 2k х 2",.,-матрица U с собственными значениямиez·в t ~ cz·в 2, •.• е iB2 "'·. Д."IЯ всех, кроме множества меры нуль, таких :\1атрип каждое (} i представляет собой иррационалыrос число, кратное п,и все Bi песоизмеримы (каждое Bi/0 тоже иррационально). Положи­1тельная целая степень U.,. матрицы U имеет собственные :щаченияКаждый такой енисок собственных значений определяет точку на2k-мерном торе (произведении 2• окру-жностей). Так как n принима­ет целые положительные значения, зти точки шютно заво;,шяют весьтор, ССJ1И U является типичной. !:ели U = eiA, то для любого веще­ственною Л положительные целые степениUсколь угодно близки кU(Л) = е<>А Мы утверждаем, что любое U(Л) достигается положи­тельными целыми степеня~и(2)U.Переключеное входов и выходов.

Имеется несколько (массических)преобразований, коrорые можно выпоmшть, всего лишЕ. переставивметкиk куби1ов ИJllf, другими словами, применяя вентиль U к ку­битам в друl()м поряпке. Из (2k)! перестановак Сiрок длипой k путемобмена кубитами можно реализоватькkk!НсШI вентилем, применяемымкубитам в стандарrном порядке являетсяU,а Р-перестанов­ка, осуществ.:mемая путем обмена кубитами, то мы мОжем построитьвентильU'~PUP 1(6.83)ТОЛЬКО С ПО\10ЩЫО персЮIЮЧСНИЯ ВХОДОВ И ИЫХОДОВ ИСХОДНОГО IJCIITИJIЯ.Например, обмен двумя кубюами осуществляет псрсстановкуР~:·101)llO)(6.84)илир= (ь ~] ~ ~ ·) ,оооооо1действующую в базисе {IOO), IOI), IIO),и выХОJ\Ы, мы получаем венти..11ь=111)}.(6.85)!lерек:почая входы6.2. КRАНТОВЫЕ СХЕМЫ313Мы можем также ностроить любую целую положительную степеньU':(PUP- 1)" ~ PV"P- 1(3) Замкнутая алгебра Ли. Мы уже замечаJШ, ч·rо если венпшь U =eiAявляется типичным, то его степени rшотны на rope {еiЛА}.

Мы можемда.1ее ;rока._iать, что ecJJи U = eiA и U' = eiB тип»чные венти;ш, то длялюбых вещественных а,/3, 1'из них можно составить вентиль, скольугодно близкий кИЛИei(n:A+t'3B)е ---y[A,BJ_(6.86)Таким образом, <<1\Остижимые» преобразования образуют замкнуtуюалгебру Ли. Мы говорим, что U = eiA генерируется nреобра.>Jовани­ем А; тогда если А и В являются типичными генераторами ДОС'fижи­мых преобра.1ований, 10 .этим же свойством об.ilадают их вещественные.:l:Инейные комбинации и (умноженный наi)коммутатор.Снача.·:ш заметим, чтоСледоватеЛI.IIО, :Iюбос прсобразование ci(cxA+J3B) достижимо, сели та­ковыми являются ei.aAfn и ei.ВB/n.

Более того.lirп (f~iB/ Vne-iAf-.Jii,e -i-B/ y'ii.eiAj ..j"il) nn-><:ю=lim [1-l(ABnn-->oo-ВА)]п = е-[А,в',(6.88)так что е- [A,Bj также достижимо.Применяя результаты(1), (2)и(3),можно наказать, что типичныйдвухкубитовый вентиль является универсальным.1.Вентидь Дойча.Первым, обраnшmим внимание на существова­nие уииверсальноrо квантового вентиля, был Дэвид Доifч (1989г.). Трехку­биrовый универсальный вентиль Дойча является квантовым кузеном вен­тиля Тоффоли. Это дважды кошршшруемое R-прсобразованиеГЛАВА 6314которое применяетRк третье~ кубиту. если два первых имеют значение,равное единице; в противном случае-- действует тривиально. Здесь(6.89)представляет, с точностыо до фазы, поворот на е вокруг оси х, г~с(}неi<О­торый песоизмеримый с п угод.п-ая степень вентиля Дойча представляет собой Дllажды I<Онтро;:шруе­моеRn.

В частности, R 4 = R.(48), так что вес однокубитовыс преобра­зования, генерируемые и х• достигаются целыми степенями R. Более того,его(4n + 1 )-ойстепенью является преобразование.[-z cos(4n+1)82.. (4n+1)(}]+zихsш2,(6.90)сколь угодно б.:1изкое к их· С~1едовательно, венmль Тоффо;rи достигаетсяцелыУи степенями вентиля Дойча, то есть вентидь Дойча является универ­сальным для классических вычислений.Действуя на трехкубитоRый вычислиrелъиый базис{ IOOO), IOOJ), 1010), IOJI), 1100), 1101). 1110), IШ) },(6.91)1·енсратор венти.;IЯ Дойча переставляст два его носледних злемента:1110) .....Изобразим эту8IШ).(6.92)х 8-матрицу как(о-х)в7= (01 О)(6.93)~·С помощью вентиля Тоффоли можно выполнить перестаковку JJюбых этихвосьми элементов.

в частности, д..т1я любых т иР=n(6m)(7n).(6.94)Следовательно, нам доступно любое преобразо11анис, 1·снерирусмоеP(o-x)67p-l ~ (tтxJmn·(6.95)6.2. КВАIIТОВЫЕ СХЕМЫ315Более того,[(ux)sc.(tт,)s1] [(~ ~ g), (g g1 ~)] ~ ( -1g g~) =i(uy)57·=о о оооп о(6.96)Аналогично мы можем реализовать любое унитарное нрсобразование. ге-нерируемое (и уJmn. Наi<Dнец,(6.97)Следовательно, нам достунно любое преобразование, п~нсрируемое линей­ной комбинацией матриц (и,,у,,)тп· Они образуют линейную оболочку ал­гебры Ли SU (8), следовательно, мы можем генерировать любое трех куби­товое унитарное ареобразование (за искточением несупJ,ествснной общейфа-1ы).Вспомним теперь, ч1u мы уже обнаружили, что, комбинируя трехби­твые вентили Тоффоли, можно построить п-битовый вентиль Тоффоли.-----.------Схема--t------+---/0) -!!t-г4-----dl---ис1Ю~rь..1ует один вспомогательный бит, чтобы построить четырехбитовыйвентиль Дойча (трижды контролируемоеR) из одного трехбитового венти­JIЯ Дойча и двух трехбиrовых вентилей Тоффоли.

Аналогичная схема ре­ализует п-битовый вентиль Дойча из одного трехбитового вентиля Дойчаи двухn-1-битовых вентилей Тоффоли. Кщь скоро мы имеем п-биrовыйвентиль Дойча, а также универсальное классическое вычисление, точно теже аргументы, что и выше.

показывают. что можно реалнзовагъ любое пре­обраювание из2.SU(2n).Универсальные двухкубп"Говые вентили.Мы нщ~ели, что дляуниверсальности Юiассических обратимых вычислений необходимы трех­битовые универсальные вентили. Однако в кванrовых вычислениях ока­зываются адекватными двухкубитовые вентили. Поскольку мы уже знаем.что вентиль Дойча универса.тен, мы можем установить это. показав, что онможет быть образован комбинацией двухкубитовых вентилей.316Гллвл6Фактически, еслиобозначает вентилъ контролируемоеU (унитарное 2 х 2-nреобразование Uприменяется ко второму кубиту, если первый имеет значение, равное едини­це; в противном случае вентиль действует тривиально), то RCJП1f.JIЬ дваждыконтролируемоеUполучается с помощью схемыхуСтепеньюU, примснсшюй к третьему кубшу, являетсяу- (х EIJ у)+ :с- х +у- (х +у- 2ху) = 2ху.(6.98)Следовательно, вентиль Дойча можно построить из вентилей контралируе­мот U, контролирусмОIОи контро;шруемоrо 'NOT, гдеu-J.,u~ ~.(8 ) :->.Rx(6.99)мы можем Rыбрать(6.100)Так как положительные степенииu- 1,Uсколь уmдно б,;шзко приближакrrся к С1' хто вентиль Дойча можно сконструировать и:1 одного ~wшь кон­тролироуемогоU.

Следовательно, при иррациона.ньном 8j1r контролиру-емое(~) само по себе является универсальным вентилем.e-i1ri 4 Rx(Заметим, что приведеиная выше конструкция показывает, что, несмот­ря на то, что мы не можем ностроить вентиль Тоффо.1и из К.'lассичсскихднухбитовых обратимых вентилей, его можно сконструировать из коюро­лируемого «квадратного корня израт котороrо U 2 ~а,.)NOT», roесть контролируемопJU,квад­§.2. КВАНТОНЫЕ CXl:::\fblТиnичные двухбитовые вентили.3.317Итак, мы нашли :конкретныедвухбитовые вентшш (контролируемые повороты), являющиеся уиивер­са.1Ьными.

Следовательно, д.1я универсальности вполне достаточно, селимы можем строить ruютные в И (4) нреобрюования, ,тействующие на парыкубитов.Однако на самом деле достаточно JIIOбoro тиничного двухкубитовоговенти;rя, чтобы генерировать все прсобрюования из И(4). Как мы видели,если е'А - типичный злемент И ( 4 ), то можно реализовать любое нреоб­ра.~ование, r·енерирусмое А. Более·roro,можно реализовать любые преоб­рюования, rенерируемые элементом минимальной ат-ебры Ли, содержа­щей А игде1' -перестановкаD=PAP- 1 ,(\01) +-> \10) ), получаемая(6.101)переключениемвходови выходов.Рассмотрим теперь общее преобрюование А [рюложенное в ба.1исе ал­гебры Ли U(,l)], а также рассмотрим конкретную схему построения 16-ти::шементов а.ш"Сбры Ли путем посдсдопательных коммутаций исходя из Аи В.

Конструируемые таким образом .элементы .-:rинсйно независимы [а от­сю;\а с01едует, что любое преобрюование в;-штель конкретной16 хU(4)достижимо], если опреде­16-матрицы не равен нуmо. ЕсJШ этот определительне обращается в нуль тождественно, то его нули появляются rолъко на под~многообразии меры нуль. Фактически мы можем выбрать, допустим,А=(аl+fо-х+"У<Ту)2з(rтри нссоизмсримых о:)(6.102),6, r) и с помощью явных вычислений показать. чтодействитет>нО, начиная с А и В, последовательными коммутациями мож­но генерировать всю 16-мериую алгебру Ли.

Следовательно, мы приходвмк заключению, что неуспех генерирования всей алгебры И(4) нетипичен,и обнаруживаем, что почти вес днухкубиrовые вентюш универсальны.4.Другие достаточные наборы вентилей,Очевидно также, чтоуниверсальные квантовые вычисления можно реализоваu. с nомощью на~бора вентилей, состоящих из классических мноrокубиwвых и квантовыходнокубитuвых вентилей.

Наnример, можно увидеn~, что универса,;Тhныйнабор образуется венте;IемXOR,комбинируемым с однокубитовымн вен­тилями. Рассмотрим схемухГЛАВА б318применяющую ко второму кубпту прсобра.1ование АВСи Аи хВО' хС, если х, если х = О,= 1.

Если мы можем nодобрать такие А, В, С, чтоАВС= 1,(6.103)AuxBuxC = U,тогда эта схема функционирует как вен111ЛЪ контро,тируемоечески ддя любого унитарногоют унитарные2UU.Факти­с единичным Определитедем существу­х 2-прсобразовання А, В, С с такими свойствами (каквы покажете в упражнении). 0Iсдоватсльно,XORв совокупности с про­извольными однокубитовыми преобразованиями образуют универсапьныйнабор. Конечно, двух типичных (некоммутирующих) однокубитовых ире­образований достаточно, чтобы добиться чего угодно. В действительностис помощьюXOR-aи единственNого типичноrо однокубитового поворотамы можем построить второй однокубитовый поворо1; не коммутирующийс первым.

Таким образом, XOR вместе со всего лишь одним однокубито­вым вентилем образует увиверсальный набор вентилей.Если мы сJюсобны реализовать вентиль Тоффоли, тоrда д;Jя универ­сальных вычислений достаточно даже некоторых нетипичпых одпокубито­вых преобразований. Например (еще одно упражнение), вентиль Тоффолисовместно с поворотами на"/2вокруг осей х иzпредставляет собой уни­версальный набор.5.Точность.Наше обсуждение универсальности сфокусирова.~осьна достижимости. оставив без внимания сложность. Мы всего лишь уста­новили, что можем пос·1роить квантовую схему, сколь утодно близкую ктребуемому элементу из И ( 2n), и о не рассмотрели размер необходимой намсхемы. Однако с 1uчки зрения теории квантовой сложности универса..'!Ь­ность очень важна, поскольку она означает, что с нриемлемой точностьюи разумным замедпением одm1 квантоный компьютер может модеШiроватьдрутой.В действительности до сих пор мы были не очень точны: в вонросео том, что означает для одного унитарного преобразования быть «бнизким»к другому; для этого следует определить топологию.