Дж. Прескилл - Квантовая информация и квантовые вычисления. Тома 1-2 (1156795), страница 59
Текст из файла (страница 59)
TaR как оператор Wt унитарен, каждое ero собственное число имеет вид фазы ei8 •а соответствующее собственное значение оператора W t - 1 имеет .модульle'8 - 11 =так что(6.68)(2- 2eos8) 112 ,(6.70)требует, чтобы каждое собственное значение удоюстворялонеравенствуf:2cos8>1 - 2,(и.1и(6.71)181;S е для малых е). Природа неравенства (6.69) понятна. В каждыймомент времени I<P) поворачивается относитеJII.но I'P) на угол порядка ,;(в худшем случае), а расстояние между векторами возрастает максимумна величину порядка е.Какая точность является достаточно хорошей? На последнем этапе вычисления мы кы1ю,;шяем ортогоналыюе измерение, а вероятность ре3у;н.тата а в идса.;Iьном снучас равнаР(а) = l\ai'Pт}l 2(6.72)Вследствие ошибок t'\Сйствите~тьной верояпюстью будетF(a) ~ l(al?т}i2(6.73)Если действительный вектор бли:юк к идеальному, то и распределения вероятностей тоже б.IИЗКи.
ЕсJШ мы просуммируем по ортонормированномубюису{la} }, то ПОii)'ЧИМL IP(a)- P(a)l (2III<Pт} -I'Pт}ll.(6.74)акак ны накажете в ;J.Омашнем упражнении. Следовательно, ecJJИ при боJtЬших Т мы сохраняем неизменным (и малым) ТЕ,roошибка в распредс.1ении вероятностей также остается фиксированной. В частности. ес.!И мыра.1работали квюповый алгоритм, который с верояnюстью выше ~ + Ь пранильно решает проблему принятия решения (в идеальном случае). rогдас вероятностью, превышающей ~, мы можем добиться успеха и с помощью наших шумящих вентилей, если действие этих вентилей может бытьвыподнено с точностью Т.с; < О( J).
Семейство квантовых схем может реально решать сложные проблемы в юшссе BQ Г до тех пор, пока мы в сосmянии улучшать точность выполнения венпшей пропорнион3.;1ЫЮ обьемувычислений.6.2. КRАIПОВЫЕ СХЕМЫ6.2.2. BQPs;;309PSPACEКонечно, ютассический компьютер может моделировать mобую квантовую схему. Но какой объем памяти ему для этого потребуется? Поскодькумоделирование п~кубитовой схемы включает в себя маниаудирование матрицами размера2n,то с наивной -ruчки зрения может покаэаться, что дляэтого необходим экспоненциальный поnзапас памяти. Однако тенерь мынакажем, что с приемлемой точностью (хотя и очень :медленно!) моделирование может быть выполнено в пространстве полиномиального размера.Это о:шачаст, что :к.1асс квантовой сложностиBQPсодержится в :к.аассеР S РАС Е задач, которые могут быть решены с исполr,зованием пространства полиномиального ра.змера.Обьекюм классическото моделирования является вычисление нероятности каждого возможного резу~11~тата а заключительного измерения(6.75)где(6.76)произведение Т квантовых вентилей.
Каждыйкубитов, может быть прсдстав..т1сн унитарной2nUРдействующий наnх 2n-матрицей, характеризуемой комплексными ма1ричными э."Iементами(6.77)(y!U,Ix),где х, у Е{0, l, ... , 2n -1}.Явно выписывая пршrJведение матриц, мы имеем(6.78)Уравнение(6.78)нредставляет собой вариант предстаюения квантового вычис.:rения «интегралом по траекторИЯМ}}-амrшиту.л:а вероятности конечного результата а выражается в виде когерентной суммы амrшитуд каж~1огоиз огромного количества 2n(T-l) возможных вычисmпельных нутей, начинающихся в rочке О и после Т шагов заканчивающихся в а.Чтобы вычислить (aiU(T)IO), наш классический сииулятор долженсложить 2n(T- l) ко:мшrексных чисел в уравнении (6.78).
Первая нроблема,с ю:пuрой мы встречаемся, состоит R том, что :к.-шссические схемы конечного размера реализуют целочисленную арифметику, тогда как матричные310элементы(yiU,Ix)не обязаны быть рациональными чисдами. Следовательно, классический симуляrор лолжен выпошшть приближеннт. .Iе вычисJJСния с ра_1умFюй точностъю. Каждое из 2n(1'-t) слагаемых суммы представляет собой произведение Т комплексных сомножителей. Накапливаемыеошибки непременно должны быть МЗJ[ЫМИ, если мы пыражасм матричные элементы с помощью т точных биrов, где т ве~'ШI<О по сравнсни10сn(T- 1).Следовательно, мы можем заменить каждый комплексный матричный элемент nарой це.зы:х чисед определенного знака, принимающихзначения {0, 1, 2, ...• 2m- 1 }.
Этн цеш,rе числа дают двоичное рюложениевещественной и мнимой частей матричного элемента, выраженного с rочностью2-m.Нашему симулятору потребуется вычислип, каждое слагаемое в(6.78)и накопить их полную сумму. Но каждое добамение требует только умеренного объема пространства памяти, и, более того, поскольку длЯ следующего сложения необхо;J;имо сохранять только накоШlенную частичнуюсумму, не очень большое пространство требуется для суммирования всехслагаемых, даже есди их экспоненциально много.Итак, остается лишь рассмотреть вычисление тиnичного слагаемогосуммы, произведения Т матричных элеменwв. Нам потребуется классическая схема.
вычис.1яющая(yiU,Iт);эта схема принимает2nвходящих битов(6.79)(х, у)и выдаст на выходе 2m-битовое (комплексное) значение матричншu элемента. Имея схему, выnопняющую эту функцию, легко построить схему, которая перемножает комIt'Iексные числа, не используя большого пространства.Наконец, обратимся к свойстl}ам, котuрые мы потребовали от наборакванwвых вентилей,-зто дискретное множестио вентилей, кажд.ый из которых действует на ограниченное количество кубитов. Jlоскош,ку имеетсяфиксированное (и конечное) mличество вентилей, то существует лишь конечное количество вентилей-nодпрограмм.
с которым нашему симу:mторунеобходимо уметь обращаться. А поскольку вентИJШ действуют только нанеско:n.ко кубитов, почти все их матричные элементы исчезают (ес.1илико), а значение(yiUix)nвеможет быть определено (с требуемой точностью)с помощью простой схемы, требующей незначительной памяти.Например, в случае однокубитового вентиля, действующего на первыйкубит,(y 1y2 ... yn1Пix 1 x 2...xn)=O,ес;IИx 2x 3... xnofY2 Yз···Yn·(6.80)Простая схема может еравпить х 2 с у 2 , х 3 с у3 и так л.aJJec и дать на выходе6.2.
КВАНТОВЫЕ СХЕМЫ311нуль, есJШ равенство не выполняется. В случае равенства она выдает одноиз четырех комnJiексных чисел(6.81)с т точными битами. Простая схема может закодироватькомплекснозначиой2х8mбитов этой2-ма-rрицы. Подобным образом простая схема, требующая пространство лишь полиномиа.:Iьного поnиmразмера, можетвычислить матричные элементы любого венпшя фиксированного ра:~мера.Таким образом, IШассический компьютер с пространством, оrраниченным сверху размеромpoly(n),может моделировать п-кубнтовый универсальный квантовый компьютер и, следовательно,BQP <;; PSPACE.Конечно,также очевидно, что онисанное нами моделирование требует экспоненциального времени, так как нам необходимо вычислить сумму 2n(T-l) коммексных чисел.
(В действительности большинство слагаемых исчезает, ноколичество неисчезающих слагаемых остается экспоненциально большим.)6.2.3.Увнверса.:tьвые квантовые вентилиМы должны обратиться к еще одному фундаментальному вопросу, касающемуся кван·ювых вычислений, как построить адекRатный набор квантопых венти.:Iей? ДрУJ·и~и с:.ювами, что образуст универсальный кванrовыйкомпьютер?Ответ вам понравится.
Для реализации универСЗJIЬных квантовых вычислений достаточно любоru типичноrо двухкубитового венти.:п. То есть,если мы можем применять эти вентили к любой варе кубитов, то любогоиз них, кроме множества меры нуль унитарных4х 4-матриц, достаточно,чтобы построить п-кубитовую схему, вычисляющую преобразование, скольугодно близкое к любому элементуU(2n).Математически это не особенно гJIУбокий резудьтат, но с физическойточки зрения он очень интересен. Э1о означает, что в квантовом мире, покамы можем нрщ~умыватъ типичные ;щухкубитовые взаимодействия и осуществлять их точно между любыми двумя кубитами.
мы в состоянии вычислять чrо угодно, независк..\ю от сложности. Нетривиапьные J\ычисленияв квантовой теории встречаются повсюду.Кроме этого общего результата, интересно продемонстрировать и конкре11IЫС наборы универсальных венти.i'IСЙ, коrорые очень :Jегко могут бытьреализованы физическп. Обсудим несколько примеров.L"уществует несколько основных элемеmов, входящих в состав люботонабора универсальных квантовых вентилей.ГЛАВА 6312{1) Степени типичного вентиля. Рассмотрим «типичный» k-битовый венТШIЪ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
