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

Измеряя корреляции, мы можем узнать намно1u больше;в принципс мы можем полностью реконструировать состояние.Любое удовлетнорительное описание состояния3JVкубитов должнохарактеризовать эти искшочительно С~1ожные нелокальные корреляции. Вотпочему классическое моделирование бодьшой квантовой системы требуетогромных ресурсов. (Когда подобные нелокальные корреляции существуютмежду частями системы, мы говорим, что части «запутаны», имея в внпуто, что мы не можем поmюстью расшифровать сосrояние системы путемсе деJiсн:ия и изучения отдельных частей).1_5_Квантовый параллелизмll 1985 году Дэвид Дойч придал идее Фейнмана более конкретнуюформу.

Дойч подчеркнул, что квантовый компьютер может лучше всего ре­ализовать свой вычислительный потенциал, осуществ.;-mя то, что он назван«квантовым паралледизмом» 1• Чтобы понять, что зrо означает, лучше всегорассмотреть пример.D. Deutsch, Quantнm Theory, the Church-Turing Ptinciple and the U a.iversal QuantumComputer, Proc. Roy. Soc., London, А400, 97 (l985); русский перевод в сборниш: статей Киан1ГЛАВА261Следуя Дойчу, представим черный ящик, вычисляющий функцию, ко­торая иреобразует один бит х в одии бит f (х). Мы не знаем, что проис­хо;:~;ит внутри ящика, но зто должно быть нечто сложное, нотому что вы­числение занимает24часа. Сущее11>ует четыре возможные функцииf(x)(ПОСКОЛЬКУ каждая ИЗ f (0) И f (1) МОЖеТ прЮ!ЯТЬ ОДНО ИЗ двух ВОЗМОЖНЫХзначений], и мы бы хоrели знать, что вычисляет ящик. ВычисJiсние обеихфункций /(0) и f(l) заня:ю бы 48 часов.Но мы не располагаем таким временем; нам нужен ответ через24 часа,а не через 48.

И пусть нас даже устроило бы знание того, является f (х)постоянной (f{O) ~ f(l)] или сбалансированной (f(O)f(1)] 1 • Но даже#в этом с;тучае получение ответа займет48часов.Теnерь nредставим квантовый черный ящик, вычисляющий f (х). Ко­нечно, f(x) может быть необратимой, в то время как действие квантовшакомш.ютера унитарно и .J.Шiжно быть обратимым, поэтому нам понадобитсяпрообразование и , трансформирующее два КУfiита в два:1U1 : !х)!у) ___, !х)/у е f(x)).(1.8)(Этот механизм инвертирует нrорой КУбит, если действиеfна первый КУ­бит дает 1, и ничего не делает, есJШ i\ействие f на первый кубит дает 0.)Мы можем опредеJШтъ, является ли f(x) постоянной шш сбалансирован­ной, испош~овав квантовый черный ящик дважды.

Но ПО..-:JУЧение одногорезультата 110-нрежнему занимает сутки, поэтому такой способ не годится.Може~ ли мы получить ответ (за24часа), воспользовавшись квантовымчерным ящиком лишь раз? (Это так называемая <<Задача Дойча» ).Так как черный ящик является квантовым компьютером, мы можем ны­брать в качестве нхоi\Ящеrо состояния суперпозицuю !О) и11).кубит приготовлен в начюыюм состоянии ~(IO) -11)), тоЕсли н1оройv2и1 : lx) ~(IO) -11)) ___, /.:r:) л(IJ(x)) -llEJJ/(x)))=то есrъ функцияf=lx){-l)f(x)_l (IO)- IJ))../2.(1.9)оказывается локализованной в зависящей от х фазе.товыU кmтьютер и квантовые вычиСllения под ред.

В.А. Садовничеrо, Ижевск, РХД (1999).llpu.:w.ред.!•)тот неско;Jько пеобычный термин обозначает, чтоI!ИИf(:X)два рmличных ·~начеиии: фунж­сбалансированы, то есть каждое из них соответсt"вует р01шо uо;юuине значенийаргумента х .. -- При.м. ред.1.5. КВАНТОВЫЙ ПАРАЛЛЕЛИЗМ27Теперь предположим, что первый кубит приготоRЛен в начальном состоя­нии - 1-(10) -t 11)). Тогда чериый ящик действует следующим образом:)2·И1 ~(IO) + 11)) ~(IO)-11))-_, _l [(-1)f(O)IO) -t (-1)!(1)11)] - 1 (10)-v'2.,f211)).(1.10)Наконец, мы можем выполнить измерение, проецирующее первый кубит набазис1±) =-1../2(IO) ±Очевидно, что мы всегда будем получатьрованная, и -1+), если она постоянна' .11)).1-), если(1.11)функuияf(x)сбаланси­Итак, мы решили задачу Дойча, а также нашли разницу между тем,что доступно классическому компьютеру, а что квантовому Классическомукомпьютеру прИJtется воспользоваться черным ящиком дважды, чтобы от­личить сбалансированную функцию от постоянной, а квантовый комnьютервыполняет это задание за один раз!Это возможно, потому ч·rо квантовый компьютер не ограничиваетсявычислением только f(O) или f(1).

Он может действовать на суперпозн­цию IO) и11),извлекая таким образом <<глобальную>> информацию о функ­ции, информацию, которая зависит и отf(O),и отf(l). Это и есть кванто­вый параллелизм.Теперь нредположим, что нас интересуют шобальные свойства функ­ции, которая действует на N битов, функции, зависящей от 2N возможныхаргументов. Чтобы вычислить по;тную таблицу значенийf(x ),нам при­IIШОСЬ бы считать f 2N раз, что совершенно невозможно при N > > 1(например, 1030 раз для N = 100).

Но с квантовым компьютером, действующим в соответствии си 1 : lx)IO) _,lx)lf(x)),(1.12)мы мог.'IИ бы выбрать следующее состояние входного регистра:[~ (10) + 11))]N =2;122~11х),(1.13)------1Впредыдущем описании квантовых вычислений мы говорили, что окончательное изме­рение проецирует каждый кубит иа базис {10),j1) },но здесь МЪ1 донусЮJем возможностьизме~ния в друrом базисе.

Чтобы описа'IЪ эту процедуру в старом базисе, необходимо передокоwнпельным измерением применить к каждому ку6И1у подходящее унитарное преобразо­вание.ГЛАВА 128и, вычисливf (х)только один раз, генерировать состояние:2N -1;/2 L2х=О(1.14)/x)/f(x)).В этом сосrоянии 'Закодированы глобальные свойстваf,и мы могли быизмечь некоторые из них, если бы только смогли придумать для этого эф­фективный способ.Это квантовое вычисление демонстрирует «массовый квантовый па­раллеJПIЗМ>); имитация подготовки такого состояния на к..гшссическом ком­пьютере потребовала бы от нас вычислятьчество ра1 (1\ЛЯN> > l). Тем не менееfневообразимо огромное коли­с помощью квантового компьютера:мы сде.1али это в один захо;~.

Это именно тот тип массовоrо нараллс.Jизма,который был осуществлен Шаром в его ашоритме факторизации.Как было отмечено ранее, характерной чертой квантовой информацииявляется то, что она может быть зако,r~ировапа в нелокальных корреляцияхмежду разными частями физической системы. Действительно, этот случайо·юбражен в уравнении(1.14); свойства функцииfхранятся в корреляцияхмсжлу «входным регистром» и «выходным регистром» квантовоrо комныо­тера.

Однако не так просто расшифровать э·tу нелока.Гiьну.ю информацию.Например, если бы я измерил вхо;\НОЙ регистр, то получил бы резую,­тат /х 0 ), где х 0 совершенно случайным образом выбрано из2Nвозможныхзначений. Такая процедура приготовила бы состояние(1.15)Мы могJШ бы перейти к измерению выходного регистра, чrобы получитьзначение f (х 0 ). Но у нас нет возможности определить f(y 0 ) !\ЛЯ любогоу0х 0 посредством дальнейших измерений, поско;тьку уравнение (1.14)fразрушено предьщушим измерением и сложные корреляции между реги­страми утеряны.

С.1едовательно, в этом случае квантовое вычисление недает преимущества перед классическим.Урок, полученный при решении задачи Дойча, состоит в том, что ис­пользование закодированных в уравнении( 1.14) корреляцийиногда ·~ребуетизобретательности. ИскусСТIЮ создания квантовых аJJгоритмов во многомзаключается в поиске способов эффективного использования нелокальныхкорреляций.1.6.Новая классификация сложностиКомпьютер на вашем рабочем столе не является квантовым, но все жеэто замечательное устройство: в припципе, он способен вьшо:шить любоемыслимое вычисление.

По в ;tсйствительности существуют нычисдения,1.6. НОВАЯ КЛАl:СИФИКАЦИЯ СЛОЖНОСТИ29которые вы не можете выполнить: вам не хватает либо времени, либо па­мяти. Но если объем вашей памяти неограничен и вы согласны жд;ать столь­ко, сколько потребуется, тогда все, ч1u достойно называться вычислением,может быть выполнено вашим маленьким ПК. Поэтому мы называем его«универсальным компьютером».Кпассическав теория сдоЖJюсти изучаео; какие задачи являются слож­ными, а какие простым и. Обычно понятия «сложная» и «простая» опреде­ляются rоличеством необходимых вре].!ени и/или паМЯ111. Но как придатьсмысл разJШЧию между простым и сложным, не описав аппаратные сред­ства, которые мы будем использовать? Задача может быть сложной для ПК,но, наверное, я смог бы разработать устройство специального назначения,которое смошо бы решить ее гора.mа быстрее.

А может быть в будущем по­явится более совершеm1ый утпrверсальный компьютер, сnособный решитьэту задачу гораздо эффективнее. Действительно имеющие смысл различиямежду с~ожным и простым должны быть универсальными ~ они не долж­ны занисе1ъ от того, какое устройство мы используем.Теория сложности главным образом обрашаст внимание на различиемежду алгоритмами, выполняемыми за <шолиномиальное время» н за «экс­поненциальное времю>. С любым алгоритмом А, действующим на вход не­ременной длины, можно сопостааить фунщию сложиости ТА (N), где N ~длина входа в битах. ТА ( N) представляет собой максимальное «время>>(то ес-.;ь количество элементарных операций), необходимое дли полного вы­полнения алгоритма для любого входа изалгоритм факторизации, то ТА ( N)цииN -битового·-Nбитов.

[Например, если А ~время, необходимое для факториза­числа 1! худшем случае.] Мы говорим, что А выполняетсяза полиномиальное время, еслиTA(N).:; Poly(N),гдеPoly( N)обозначает полином от переменной(1.16)N.СЛедовательно, nоли­номиальное время означает, что необходимое дли решения задачи времярастет ие быстрее степени ю:тичества входящих биrов.Если задача выnолняется не за пошrnомиалъное время, то мы гово­рим, что ее решение требует экспоненциального времени (хотя на самомделе терминолегически зто не совсем верно, посК'ОЛьку, конечно~ существу­ют су перполиномиальные функции тиnа N 10• N, которые на самом делевозрастают гораздо медленнее экспоненциальных).

Это рациональный кри­терий определения грани между простым и сложным. Но действительнорешающим доводом в пользу этого различия служит его незааисимость оттого, какой rомпъютер мы используем. Универсальность различия междуполиномиальным и экспоненциальным следует из одного из главных ре­зультатов теории вычислительных систем: универсальный (юiассическнй)ГЛАВА 130I<Омпыотер может моделировать другой в худшем случае с <<nолиномиаль­ным превышением>> (времени). Это злачит, что если на вашем I<Омпьютереа.,rтгоритм выполняется за полиномиальное время:,wя всегда могу выпод­ни1Ъ его на своем компьютере за поJIИномиалыюе время.