Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2 (1156795), страница 58
Текст из файла (страница 58)
Классический обратимый вентиль(6.56)Го1АВА б304вьпю:rняющийперестановкуп-биrовыхстрок,может рассматриватьсякак унитарное преобразование, действующее на «вычислительный» базис {/х,)) как(6.57)Это действие унитарно, поскольку вес2nстрок /у,) взаимно ортогональны. КRантовое вычисление, построенное из таких к."тшссических вентилей,иреобразует/0 ... О)в одно из состояний вычислительного базиса, так чтоконечное измерение является детерминированным.Имеется три главные проб.'!Iемы, касающиеся нашей моде.ж, к которым мы хотели бы обратиться.
Первой из них является упиверсалыюсть.Са.:\-юе общее унитарное nреобразование, которое может быть выполненона n кубитах, является элементом U(2n). Паша модель могла бы оказатьсянеполной, если бы в U(2n) сущсстnоnа.Jш такие преобразования, которыемы не могли бы выполнитЕ>. На самом дспс мы увидим, что существует множество способов выбрать дискретный набор ун.иверсальиых квантовых венmwlей. Используя набор универса.ТhНЫХ вентилей, можно ностроить схемы,вычисляющие унитарное нреобразование, сколь yroJ~нo бШiзкое к любомуОЛСМСIПУ ff(2п).IJдаJол:аря универсалыюс1и, существует также анпаратно-независимо~";пон:ятие ква1-1mовой сложности.
Мы можем опредеJШть новый класс сложностиBQ Р- класс проблем принятия решения,которые с высокой вероятностью могут быть решсны с помощью квантовой схемы полиномиальногоразмера. Так как один универсальный квантовый компьютер может эффективно моделироваться другим. ·ю ~пот к.пасс не зависит от деталей аппаратного обесвечения (от выбранн01u нами набора универсальных вентилей).Заметим, чrо квантовый комп~ютер может ."Iепсо моделировать классическийвероятностныйкомпьютер:онможет приготовитьсостояние~ (IO) + /1) ), а затем спроецировать его на {/0), 11) }, генерируя случайныйбит. Следовательно, класс ВГJ' несомненно содержится вBQP.Однако, как обсуждалось в первой главе, представлЯется достаточно разумныможидать, что в действительностиBQP шире,чем ВРР, носко~1ьку классический вершпностный компьютер не может легко модетrровать квантовыйкомпьютер.
Фундамента.:1ЬIШЯ трудность состоит в том, что гильбертовопространствоnкубитов огромно. размерности2n,и, следовательно, математическое описание 1иnичного вектора в этом пространстве иск.1ючителъно С.'ЮЖНО.Вторая проблеманаИiJУЧШИм образом характеризовать ресурсы,необходимые для МОJ(слирования квантового компьютера классическим.6.2. КВАНТОВЫЕ СХЕМЫ305Мы увидим, что, несмотря па обширность гильбертова пространства, юrассический компьютер может моделировать п-кубитовый квантовый компьютер, дажеec.mего запас памятиЭто означает, чтоограничен,BQP содержи!сяron.PSPACE нроблеместь полиномиален пов классе сложностипринятия решения, которые могут быть rешены с исrюш.зованием пространства поmшомиалыюго рюмера, но могут потребовать для этого экспоненциального времени.
[Мы знаем, чтоNPтакже СО!\Сржится вPSPACE,так как проверка C(x<n), y(m)) = 1 для всех у( т) может быть вьшолненас испонь.зованием полиномиального nространства.] 1Третьей важной проблемой, :к которой следует обраnпься, являетсяточность. КлассBQPформально определен при идеализированном предположении, чrо квантовые вентили могут ныпоJШЯТься с идеальной rочностью. Ясно, чrо при любой реализации :квантового вычисления очень важноослабить это предположение. Семейство квантовых схем пшtиномиалъногорюмера, которое решает трудную проблему, не предстаnляло бы большопJинтереса, если бы от используемых в схемах вентилей требовалась экспопснциа.ньная точность.
Мы покажем, что на самом деле это не так. Идеализированная квантовая схема из Т вентилей с приемлемой точностью можетмоделироваться ве1rrилями с шумом ЩJИ ус.rюRии. цm Rероятпость ошиБкина Оi!ИН вентиль пропорциональна1/Т.Таким обра.·юм, квантовые компьютеры бросают серьезный вызовсильному тезису Черча- Тьюринrа, утверждаюшему, что любая физическиразумная модель вычисления может быть смоделиронана вероятностнымиклассическими схемами с полиномиальным заме,цлением в худшем С.'IJЧЗС.Но до сих пор нет строгого дока:зательстваBQI' ofroro,чmВРР,(6.58)и в бmrжайшем будущем оно не предвидится 2 . Действительно, следствиембыло быВРРoJ PSPACE,(6.59)что репш.-ю бы один из давно стоящих, кард,иналыrых открытых вопросовтеории сложности.Возможно,что ВР Рболееf BQ Рреа:""Iистичнонадеятьсянадоказательствотого,вытекает из другого стандартного предподоженил теории сложности, такого как Рof N 1'.Такое докюательство до сих пор1В действительносru в иерархии с;южносnr существует еще одна ступенька, которая может разделять BQJ> и PSPACE; можно показать, что RQP С р#Р С Р8РАСЕ,но нижемы не будем рассматривать р#Р_2То есть не следует ожидать юiерешнивизированнопl дока:~ателы:тню;.
Разделение междуВРР иBQP(<относительно оракулю; будет установлено ниже в )ТОЙ главе.306ГЛАВА 6не найдено. Но хотя мы все еще не в состоянии доказать, что квантовыекомпьютеры имеют возможности, выходящие да.;1еко за пределы возможностей обычных компьютеров, тем не менее можно привести свидетельства, указывающие наro,что ВРРf BQP.Мы увидим, чrо существуют проблемы, которые выглядят сложными ()J,ЛЯ классического вычисления), но тем не менее могут быть успешно решены с помощью квантовыхсхем.Таким образом, кажется верояmым то. что классификация сложностибудет зависеть от того, какой компьютер для решения задачи используется, классический или квантовый.
ЕсJШ такое разделение действительносуществует, то именно квантовая классификация должна рассматриватьсякак более фундаментальная. посwльку она в большей степени опираетсяна физические законы, управляющие Вселенной.6.2.1.ТочиостьОбсудим проблему точности. Представим. чrо мы хотим выполнип.вычисление, в котором квантовые вентилино врименяются к начальному состояниюU 1, U 2,... , Uт последовательl;p0 ).
Состояние. приготовленноеидеа.rJьной кнантооой схемой, имеет ви.а(6.60)Но н дсйстnительности наши вентили не явшrются идеально точными. Пытаясь нрименить унитарное иреобразованиеU t•мы вместо этого применяем искоrорос «близкое>> унитарное преобразовавиеU,.(Конечно, это несамый общий тип ошибки, который можно предншюжить,иреобразованисUtунитар1юеможет оказаться замененным супероператором. В ::>томслучае применямы рассуждения, пОдобные следующим ниже, но здесь мыограничим наmе внимание {<унитарными опшбками».)Ошибки нриводят :к тому. что действительное сосrояние компьютераудаляется от идеальноm. Как сюiьно оно удаляется? Пустьидеальное состояние после применсипяtl:,o,)обозначаетквантовых вентилей, так что(6.61)Но если мы применяем действительное преобразовавиеU,, ro(6.62)6.2.
КВАНТОJЗЬIЕ СХЕМЫ307где(6.63)- ненормироианный вскrор. Если IЧ\) обозначает действительное сосwя~ние послешагов,t.mI<P,) = 1'1'1) +\Е,),I<P,) = U,\<P,) = \'Р,) + IE,) + U,\E,}(6.64)и так да..1ее; в конечном счете мы попучимliт)=I'Рт)+ \Er) + Uт\Ет-1} + UтUт-1\Ет_,}+ ... 1 UтUт_ 1 ... U2 \E1 }.(6.65)Итак, мы вредставили разность между I<Рт) и I'Рт} в виде суммы Т оставпшхся слагаемых.
Наихудший случай, дающий наибольшее отклонениеi<P·,}от I'Рт), возникает, если все оставшиеся елагаемыс ориентированыв одном наnравлении, так ч10 ошибки интерферируют конструктивно. Сле~довательно,+ 11\Ет ,)\1 ++ ... + \\\Е,)\1 i\\\E1)\\,IIIEi)ll для люб01о унитарного U.III<Pт) -\р,.)\1 <;; 11\Г'-7·)11(6.66)rде учтено, что \\U\E,)\1 =Пусть \IAII обозначает норму оператора А, ··о есть максимум модуляeroсобственных значений. ТогдаIIIE,)II-11(0,- u,)\'P, ,}\1,;;; II(U,- u,)ll(6.67)(поскольку I'Pt _1 } нормиронан). Предположим теперь, что лри каждом значенииtошибка нашего кванrового вентиля ограничена неравенством11(0,- u,)l\<е.(6.68)Тогда после применения Т кванrоnых венmлей мы имеем1\I<Рт) -I'Рт)\1 <Те;(6.69)а этом смыспе накшL1ение ошибки в сосrоянии растет пропорционалънопродолжительности вычисления.\'ллвл3086Отк.,r:юнение, ограниченное неравснством (6.68), может бы1ъ нрс;~ставлено в эквивалентной форме IIW,- 111. где w, ~ u,u).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
