В.И. Емельянов, Ю.В. Владимирова - Квантовая физика. Биты и кубиты (1161735), страница 29
Текст из файла (страница 29)
11 .2, а) Действуемоператором поворота Ry(n/2) на спин t, находящийся в состоянии 10).Затем под действием оператора Rzct( n /2) происходит поворот спинаt вокруг оси z по часовой стрелке на угол n /2. Затем действуютГл.16011.Кван.товые алгоритмы. Реализация кван.тового компьютераz;_.усtсРис.ttхt10)1°)IO)Rv(~)Rzct (~) Rz (-~))117~ II)Ry(~)IO)11.2.Реализация оператора77Rzct( -~)...ttCNOTRy( -~)tiO)я.( -ю / я.(-ю Jlll~ 11)с помощью однокубитовых операторовповорота Ry(a) и Rz(a) и двухкубитового оператора Rzct(a).
а) контрольныйкубит с исходно находится в состоянии IO); 6) контрольный кубит с исходнов состоянии ll)Rz (Ry (последовательно операторы-1r /2) и-1r /2) . В результате спиноказывается в конечном состоянии IO).Если контрольный кубит с изначально находится в состоянии 11)(спин вниз) (рис. 11.2, б), то последовательность операций такая же,tкак и в случае а, но поворот спинаRzct (-1r /2)1r /2.происходит вокруг осиВ результате целевой кубитt в результате действия оператораz против часовой стрелки на уголt оказывается в состоянии 11) соспином вниз. Таким образом, схема рис.операциюCNOT,11.2действительно реализуеткогда контрольный кубит находится в базисном состоянии IO) (верхняя последовательность операций на Рис. 11.3) или11) (нижняя последовательность операций).
Конечное двухкубитовоесостояние при этом оказывается сепарабельным (не перепутанным) :IOO) в первом случае и 111) во втором. Видно, что эти две . лоследовательности, если судить по действиям вычислителя, являются однойи той же:Rv(~)Rzct( ±~)Rz( -~)Rv( -~).( 11 .8)поскольку операция Rzct (+~) или Rzct ( -~) выполняется автоматически без его участия.Если же контрольный кубит с находится в суперпозиционном состоянии (10)+ 11) )/V2,то над целевым кубитомпоследовательность операций(11.8).t выполняется та жеПри этом одновременно и незави-11.5. Алгоритм Дойча при проиаеольном n181симо (параллельно) выполняются верхняя и нижняя nocлeдOIITioiiiiHO•сти операций, изоб~аженные на рис. 11.2. В частности, двухкубитовыеоперацииRzct ( ±~}этом виртуальновыполняются одновременно.
Целевой сnин t nрисовершает два вращения вокруг оси z одновременнопо часовой и против часовой стрелки. Результаты этих двух nараллель·ных виртуальных вычислений складываются и на выходе nолучаетсяперепутанное двухкубитовое состояние (100)+ 111)) / v'2 . Эта операциядает конкретный пример квантового параллельного вь1числения.Алгоритм Дойча при произвольном11.5.Обобщим квантовую схему рис.кубитовn11.1 на11.3.в регистре данных, рис.nслучай произвольнаго числаЭтот квантовый компьютерработает так.
Начальное состояние11/Jo)=IO) @n ® 11).После совершения n операций Адамара в регистре данных и однойоперации Адамара в нижнем регистре получается вектор состоянияvk L2n-111/JI) =lx) ® 10)~11).(11.9)х=ОIO)lx)11)IY)IYE11f(x)) 1-+---+----11/Jo)Рис.11.3.Квантовый алгоритм Дойча для произвольногаI1/JnВ состоянии1) в регистре данных в суперпозиционном видезаписано 2n п-разрядных чисел - аргументов функции f(x) . В соответствии с алr<;>ритмом (рис. 11.3) применяем оператор Uf к состояниюДля этого сначала действуем оператором Uf на каждый членв сумме (11.9). Имеем для произвольногах из (11.9):11/JJ)._1_1х)® [(IO)E!Эf(x))-(ll)E!Эf(x))] =V2nV2- 1- lx) ® I.O} -ll)_VF{-v/2'- -1-lx) ® IO) -ll)V2nесли f(x) =О.v/2'если f(x)= 1162Гл.11.Квантовые алгоритмы.
Реализация квантового компьютера= _1_1х} ® (-l)f(x) [10) -11)] =5nV2=_1_(-1)f(x)lx} ® [10) -11)).5nV2(11.10)Затем суммируем результаты и получаем2"-111/J} =2L_1_(- 1)f(x)lx} ® IO) -11).х=О 5nvf2В результате, за одну операцию квантового параллельного вычисленияполучена информация о2nзначениях функцииf(x).Hfi!JnДалее следует применить оператор Адамарак п-кубитовомурегистру данных, находящемуся в суперпозиционном состоянии. Базисными векторами в суперпозиции являются lx} = lxo, х1, ... , Xn-1}.Рассмотрим действие одного оператора Адамара на один из кубитовв базисном векторе~Hlxi} =L(-1)"';z;lzi}·(11.11)z;=0,1Тогда находимHfi!Jnlx}= Hfi!Jnlxo, · · ·, Xn-1} =vkL .
(-1)"'ozo+ ...+xn-1Zn-llzo, ... Zn-1}·(11.12)zo, ... ,z,.-1=0,1С учетом( 11.12)имеем""L...J- 2n(-1)f(x)+zoxo+ ...+zn-1Xn-11zQ, • • •'Z } кл IO) -11) =n-1 '01 vf2X,ZQ, ••• ,Zn-1Регистр данных в конечном состоянии 11/Jз}, находится в суперпозиционном состоянии 11/Joиt}. Выделим в этой суперпозиции состояние10 ... О}, которое получается, если все Zi = 0:111/Joиt}=Ao ... oiO ... О}+L Az~.z; .... ,z~_ 1 lzb, z~, ... , z~-1},где хотя бы одно из значенийzb, z~, ... , z~_ 1равно1.(11.14)J 1. б.Квантовые алгоритмыАмплитуда состояния16310 .
.. О)Ао ... о = 2~ z)-1)f(x).(11.15)хЕслиf(x)постоянна (либо О, либо1),то Ао ... о =±1.сбалансированная, то на половине значений суммируютсяЕсли+ 1,f(x)а надругой половине суммируются -1, в результате Ао ...о = О .Учтем теперь, что вектор !'Фоиt) нормирован на единицу, т.е.('Фоиt!'Фоиt) = 1, и, кроме этого, состояние 10 . . .
О) ортогонально любомуиз состояний !zb,z~,,z~_ 1 ) в (11 .14) и (0 . . . 0!0 . .. 0) = 1. Значит,...если Ао .. .о = ± 1, то в ( 11.14) ~' = О, то есть происходит взаимнаякомпенсация (деструктивная интерференция) членов в сумме ~'. Поэтому, если при измерении состояния регистра данных I'Фout) на всехкубитах получается !О), то f(x) - постоянна. Если же при такомизмерении получается хотя бы одно состояние 11), тох) - сбаланnf(сированная функция . Таким образом, благодаря выбору - задачи и построениюадекватногоквантовогоалгоритма,можнополучитьтакоевыходное состояние, что за одно измерение состояния регистра данныхможно получить решение задачи .
Из схемы на рис . 11 .3 видно, чтозадача Дойча при произвольнам n решается на квантовом компьютереза линейное по n число операций, то есть получается экспоненциальный выигрыш по сравнению с 2n /21 операциями, требуемыми для+решения этой задачи на классическом компьютере.11.6.Квантовые алгоритмыРассмотрение квантового алгоритма Дойча в п.11.5 показывает, чтопри измерении конечного суперпозиционного состояния происходит егоколлапс к одной из компонент суперпозиции, состоящей из последовательности нулей и единиц . Вся остальная информация, содержащаясяв суперпозиционном состоянии , необратимо теряется .
Эта трудностьявляется общей для всех квантовых алгоритмов иналагает серьезныеограничения на их возможные классы, требуя от алгоритма созданияв конце вычислений такой «умноЙ>> суперпозиции, которая при единственном измерении давала бы решение поставленной задачи . В алгоритме Дойча конечное состояние состоит либо из одного базисногосостояния с нулями на всех кубитах, либо представляет собой такуюсуперпозицию состояний кубитов, в котором каждое содержит хотябы одну единицу. Одно · измерение такого конечного состояния даетрешение задачи Дойча по распознаванию типа функции.Алгоритм Дойча демонстрирует то, что квантовые компьютеры могут решать некоторые вычислительные задачи более эффективно, чемклассические компьютеры .
Однако, задача Дойча является демонстрационной и не представляет практического интереса. В этом разделе164Гл.кратко11.Квантовые алгоритмы. Реализация квантового компьютерарассматриваютсяквантовыеалгоритмы,интересныесточкизрения практических приложений.На настоящий момент имеются три основных класса квантовых алгоритмов и целый ряд дополнительных квантовых алгоритмов. Первыйкласс основан на квантовой версии преобразования qрурье.
АлгоритмДойча и алгоритм Шора - факторизации больших чисел, принадлежатк этому классу. Эти два алгоритма и остальные «экспоненциальнобыстрые» алгоритмы являются частными случаями общего для этогокласса алгоритма Китаева.Второй класс алгоритмов - это алгоритмы поиска в неупорядоченной базе данных, в частности, алгоритм Гровера. Наконец, третийширокий класс квантовых алгоритмовмоделированиянаквантовых-это алгоритмы аналоговогокомпьютерахразличныхквантовыхсистем и процессов (атомов, молекул, твердых тел, химических реакцийи т.д.).
В последнее время предложены также эффективные квантовыеалгоритмы решения систем дифференциальных уравнений.11.6.1. Алгоритм факторизации больших чисел. Целый ряд современных схем кодирования, включая широко используемый RSA код(названный так по именам его создателей: Rivest, Shamir и Adelmaп),основаны на испоЛьзовании произведения двух достаточно большихпростых чисел. Это произведение используется в качестве открытогокода для передачи сообщения, а два простых числа, составляющих этопроизведение, используется в качестве секретного ключа для расшифровки сообщения.
Нахождение этих сомножителей необходимо длярасшифровки перехваченного кодированного сообщения. Наилучшийиз классических алгоритмов факторизации большого числа требуетвремени,котороерастетсверхполиномиальносувеличениемчислацифр в нем, и поэтому не может быть реализован на классическом компьютере при больших числах (содержащих многие сотни цифр).
Квантовый алгоритм Шора факторизации больших чисел N (1994 г.) факторизует заданное число за время, которое растет лишь как (log N) 3и может расшифровать сообщение достаточно быстро. Этот алгоритмвычисляет все значения определенной функции, используя квантовыйпараллелизм и перепутанность, и затем применяет квантовое преобразование Фурье. Измерение полученного состояния затем дает значение,из которого можно извлечь период этой функции и использовать егодля факторизации заданного числа.Квантовый алгоритм Шора для небольшого числа кубитов был реализован с использованием квантовых процессаров на основе ядерныхспинов и ионов в ловушках (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
