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

Выполняя~(1 + sin 21Гф), что доста­контролируемое iU, мы можем также измеритьточно для оnределения ф но модулю целое число.Однако в алгоритме факгоризации нам необходимо измерять фазуe 2 1Гik/r с экспоненциальной rочносrъю, чrо, похоже, требует экспоненци­ального количества испытаний. Донустям все же, что мы можем эффектив­но вычислять высокие степениU(какn случаесU а)~такие как(6.258)С помощью описанной выше процедуры измерения U 2J мы определяемехр ( 21Гi2 1 ф),(6.259)где e 2 1riф- собственное значение оператора U.

Следовательно, измере­ние U 2' с точностью до одного бита зквивалентно измерению j-10 битасобственного значения U.\1ы можем использовать эту процедуру определения фазы для отыска­ния порядка и, следовательно, факторизации. Обратим уравнение (6.253),чтобы получить(6.260)6.11. 0ПРF.ДЕЛЕНИЕ ФАЗЫ371каждое состояние вычислительного базиса (при х 0 :::/ О) является равно­взвешенной сунерпозициейrU а.собственных состоянийИзмеряя собственное значение, мы получаем Лk ....:.: e 21rik/r с k, рав­новероятно выбирающи:мся и.1 {0, 1~2, . .. ,r -1}.

Если т< 2п, то, чтобыопределить kfr. мы измеряем с точностью до 2n битов. В прииципе мыможем выnолнять Э1)' процедуру на компьютере, который хранит меньшекубитов, чем это необходимо для вычисленияQtT,потому что всякий размы можем присrупать к определению только одного бита изНо поучительно представить, что мы включаемk/r.QFT в процедуру опре­деления фазы.

Предположим, чtо схемаIO)--0--------.---__l_(/0) +Л 4 1J))IO)-lн'--•----т------1--~(/О)+ Л 2 /1)):::+1 J}=~J,~J2__l_(/0)J2+ Л/1))действует на собственное состояние /Л) унитарного иреобразованияУс:ювный ОТIСратор U rотовит состояние - 1-(/0)у'2+ Л/1)),условный опе-ратор U 2 готовит ~(/О)+ Л2/1)), а условный оператор U 4+ Л /1))4U.-__l_IO) +v2J2и так дапее. Мы могли бы вьnюлнить иреобразование Адамараи измерить каждый из этих кубитов, чтобы получить распределение ве­роятностей, управляющее j-м битом ф, где Л = е 2 п'Ф. Но целесообразнеезаметить, что приготовленное схемой состояние равно2rn.-1_1_Lу'2"' у~ое'•'Ф"/у).(6.261)Лучший способ узнать значение ф- выполнить перед измерением QFT(m),а не иреобразование Адамара Н (т)Рассмотрим для ясности случай т = З.

Схема, которая готовит состо­яние(6.262)Гллвл б372а затем выполняет его Фурье-анализ, имеет видЭта схема почти петюстыо выполняет описанную выше стратегию опреll.е­ления фазы, по со значительной модификющей. Прежде чем мы выполняемзавершающее преобра..·юванис Адамара и измеряем У 1 иfj 2 ,выполняютсянекоторые условные фа:юные повороты. Это те фазовые повороты, кото­рые опичают QI<'T(З) от иреобразования Адамара Н(з) и резко повышаютэффективность, с которой мы можем извлечь значение ф.Мы можем лучше понять, что делают ус:1овньJе повороты, есJШ пред­положим, что ф =k/8приkЕ{0, 1, 2, ... , 7};в это>~ случае нам известно,что прсобразовапис Фурье будет с вероятностью единица 1·енерировать на1\ЫХОде У -=k.Мы можем представитьkв виде д.воичнон) раз;rожсния(6.263)Фактически схема для самого младшего значащего бита у 0 иреобразованияФурье явщrется в точности измерительной схемой Китаева, применяемойк унитарному преобразованию U 4 , собстnенньrе значения котороП) равны(е 2 ~'Ф) 4= ei~k = ei~ko= ±1.(6.264)Измерительная цень И/(еально ра:.шичает собственные значениячтоfio~± 1,такk0.Схема !I)JЯ с;rедующего бита У 1 начти такая же, как и измеритс.IЬнаяcxe:wa ;~;ая U 7 с собственным значением(e21riФ)2 = ei-тrk/2 = ei1r(k 1.k 0 ) ~(6.265)за исключением того, что добав.1ен условный фа.·ювый nоворот~ которыйумножает фазу на exp[-i1Г(.k 0 )], давая в результате е'~•,.

Вновь, применяявслед за измерением иреобразование Адамара, мы с онределенностью но~лучасм результатii 1 = k1. Аналогичносхема дляjj 2измеряет собственносзначение(6.266)за искшочением юrn, что условный поворот уда..1яст ci1r(.k1 k()), так что ре­зу:u,татом с определенностью являетсяfj 2 = k2 .6.12. РЕЗЮМЕТаким образом,QFT373наилучшим образом осуществляет программуоnре;(еления фазы. Сначала мы измеряем значащие биты младших рюря­дов фазы ф и ИС!юлr,зуем приобретенную в измереникх информацию, чтобыу.rучruить достоверность определения значащих битов следующих разря­дов.

Имея в виду эту интернретацию, вы сможете просто запомнить схемуцляQFT(")!6.12.РезюмеКлассические схемы. Сложность задачи можно характеризован. раз­мером однородного семейства логических схем, рещающих зту задачу. За­дача трудная, ес;1и ра'Змер схемы является суnерполиномиальной функци­ей от размера входа.

Один классический универсальный компьютер :можетэффективно мол;елировать другой, так что классификация сложности ап­паратно-не1ависима. Трехбитовый венТШiь Тоффо;m является универса.гп.­ным для кJшссических обрати:мых вычислений. Обратимый компьютер мо­жет мо;~слировать необратимый без значительного замед.Jения и неприем­.:Jемых затрат памяти.Кваштuиые схемы. Хотя этu не доказано, но выглядит праnдопО)~об­ным, что квантовые схемы полинамиалыюга размера не мо1ут моделиро­ваться классическими вероятностными схемами полиномиального размера(BQPfВРР); O!IНaJ<O ;щя зтогодостаточно попиномиальноrо простран­ства (ПQР<;;: PSPACE). Квантовая схема с шумом может с нриемлемойточностью моделировать идеальную квантовую схемуразмера Т.

если каж­дый квантовый вентиль имеет точность порядка1/Т.Один универсаль­ный кванrовый компьютер может эффективно моделировать другой, такчто класс сложностиBQPаппаратно независим. Типичный двухкубнто­вый квантовый вентиль, если он может действовать на любую пару куби­тов в нриборе, адекватен д.~я универальных кванiовых вычис.Jений.

Так­же адекватны вентШiь контролируемое ~·от плюс типичный однокубитовйвентиль.Бьrс·rрый квантовый поиск. Исчерпывающий поиск маркированно­го э;~смента в неструктурированной базе данных из1Vзлементов можетбыть выпо;rnен с номощью квантово1о компьютера за время порядка vГfli,но не быстрее. Квадратичное квантовое ускорение также может быть до­стигнуто для некоторых проблем структурированного поиска, но некото­рые проб:1емы оракула не допускают существенного кванrовшо ускорения.Два участника, каждый из которых имеет о распоряжении таб:шцу изN374ГЛАВА6заnисей, могут лока.rшзовать совпадающие строки в их таблицах, обменяв­шись О( VNlog N) кубнтами, явно вступая в конф.тшп с духом (но не бук­вой) границы Холепо.О1ыскание периода ..

Используя квантовый nаралле:m:зм, можно вы­числить квантоное иреобразование Фурье в N -мерном прос1ранстве за вре­мя норядка (log N) 2 (по сравнению со временем N log N д.сrя классическо­го быс1рого иреобразования Фурье); если нам нужно сразу после зюговыполняп. измерение, то для вычисленияQPTдостаточно однокубитовыхнентилей.

Таким образом, квантовые компьютеры моrут зффсК1ивпо ре­шать некоторые задачи с периодической струюурой, такие как факториза­ция и задача о дискретном логарифме.6.13.Упражнения6.1. Линейвоемоделирование вентили Тоффолв. На пекции мы постро­или п-битовый вентиль Тоффшш e<n) из трехбитоных вентилей Тоф­фоли &( 3 ). Схема требовала только оююго бита вспомогательного про­странства, но количество венпшей было экспоненциально велико по n.Исполь3уя более широкое вспомогательное пространство, можно су­щественно сократить ко;rm:чество вентилей.а) Найдите вычисляюшее e(n) семейстпо схем из 2п- 5 вентилей е(з).(Здесь используетсяце вычисленияn- 3 вспомоt'ательныхбитов, которые в кон­возвращаются к своим исходным, равным нушо,значениям.)Ь) Найдите вычисдяющее e(n) семейство схем из 4n-12 вентилей g(з),которое работает независимо от начальных значений вспомога­тельных битов.

(Вновьn·- 3 вспомогательныхбитов в конце вы­числения возвращаются к своим начальным. не обя:.ште.1ьно рав­ным нущо, значениям.)6.2.Универсальный набор квантовых венти!'ей. Цельзтогоунражне­ния --завершить дем-он~tрациrо тшtJ, что контролируемое КОТ и про~изпольньtе однокубиtовьtе йентилИ образуют универсальный набор.а) ПустьU -произвольная унитарная2х 2-матрица с единичнымонределитедем. Найдите унитарные иреобразования А, В и Стакие, чтоАВС~1,(6.267)(6.268)6.13. УПРАЖНЕНИЯ375(Указание. Из конструкции уг;:юв Эйлера мы знаем, чтоU = R,('Ф)R"(B)RztФ),где, напри>~ер,R, (Ф)(6.269)обозначает поворот вокруг оси z на угол ф.Нам также известно, чrо, например,uxRzlф)ux = Rzt-ф).J(6.270)Ь) Расс!Wотритс двухкуби-швый веитиль контролируе"'ой фаsы: онприменяет U '-'- ею:l ко вrорому кубиту, есни первый кубит имеетзначение 11), и 11ействует тривиально в противном случае.

Пока­жите, чrо фактически он является однокубитовым вентилем.с) Используя вентили контролируемоеNOTи однокубитовые венти­ли, изобразите схему, реа.1ИЗующую контролируемоенроизно:IЬнос унитарное6.3.2хU,гдеU-2-nреобра1ованис.Точностh. Целr:. Э1Utu упражненияустановить связь между rочно­-стью квантового сос1ояния и ·шчностыо соответствующего распреде­ления вероятностей.а) ПустьIIAIIобозначает норму оператора А, аIIAII,, = tr [(AAI) 112 ]обозначает следовуюnop;wy.(6 271)Покажите, чтоIJABII., '( IIBII · IIAIJ,,и1tr(6.272)Al '( IIAII"Ь) Преююложим, что р ир-две матрицы ппотности, а{la)}-пол­ный ортанормированный базис. Так чтоРа =Р.

=(alpla),(aliJia)(6273)соответствующие расnределения вероятностей. Исnользуя (а),покажите, что(6.274)ас) Предположим, что р=I'Ф)(ФI и р ~ I.P)(,PJ -чистые состояния.Исnользуя (Ь ), покажите, чтоL:IP.- f>.J•( 2IJIФ) -IФJII-(6.275)376Г.1АВА 66.4. Поискв базе да11ных с непрерывным временем. Квантовая системас п-кубитовым rШIЬбертовым нространством имеет гамШiьтониапН~=rдеl'-"') -(6276)Elw}(wl,неизвсстное состояние вычислительного бюиса. Вам нужнонайти значениеr.vс помощью следующей щюцедуры. Включите не :за­висящее от времени возмущение Н', так что полным гамильтонианомбудетН=+Н'.Hw(6.277)Пригоrовьrе начальное состояние 1'1'> 0 } и позвольте ему ово,поциониро­вать в течение времени Т под управлением Н. Затем измерьте состо­яние. По резуJJr.тату измерения вы должны сделать вывод относитель­ноw.а) Допустим, что в качестве начального состояния выбрано2n-11ls) = - -"2n/2 Цs-lx},(6.278)-оа в качестве возмущенияН'Els)(sl.(6.279)Решите зависящее от времени уравнение Illредию'Сра(6.280)чтобы найти состояние в "Мометп времени Т.

Каким следует вы­брать'1'.чтобы оптимизщювать вероятность успешного опреде­ления vЛЬ) Теперь нредноложlfм, чтоI'<Po}и Н' можно выбрать какими угод­но, но мы требуем~ чтобы спустя время Т состоянием системыбьтоlw), так чтобы измерение онредС.1 1ЯЛО&Jс единичной ве­роятностью успеха. Выведите нижнюю. границу, которой должноудовлетворять Т, и сравните с вашим результатом в (а). [Ука­зание. Как и в нашем апа."Iизс на леiЩии, сравните эволюцию,управ:JЯемую Н, с эволюцией, управляемой Н' (случай «пусто­го opaкymD> ), и используйте уравнение Шредингера, чrобы найти,как быстро состояние, эоошоционирующее в соответствии с Н,отклоняется от состояния, эволюционируюп.:~;его в соответствиис Н'.]Часть11Решение упражнений 11Решения унрежнений ныполнены Эндрю Лэндалом и Джимом Харрннrтоном (упр.