ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 11.12.2020
Просмотров: 55
Скачиваний: 1
Семинар 8. Квантовые алгоритмы.
8.1 Алгоритм Дойча (Deutsch).
Алгоритм Дойча сочетает квантовый параллелизм с квантовомеханической интерференцией. Рассмотрим цепь приведенную на рис. 8.1.
Пусть гейт Адамара приводит первый кубит в суперпозицию вида (|0� + |1�)/√2,авторойкубитвсостояниесуперпозициивида(|0�−|1�)/√2.Этоозначает,чтогейтАдамарадействуетнапервыйкубитвсостоянии|1�, а на второй кубит в состоянии |1�.
рис. 8.1. Входное состояние такой цепи, есть двухкубитовое состояние вида: |ψ0� = |01� . (8.1) После действий оператора Адамара данное двухкубитовое состояние будет иметь вид:
|0� + |1�|0�− |1�. (8.2)
|ψ1� = √2 ·√2
Рассмотрим действие оператора Uˆна |x� (|0�− |1�)/√2,где|x� может принимать одно из двух значений: |x� = |0� или |x� = |1�
Uˆ�� = |0, 0 ⊕ f(0)�− |0, 1 ⊕ f(0)� , для |x� =0 (8.3)|x� (|0�− |1�) |1, 0 ⊕ f(1)�− |1, 1 ⊕ f(1)� , для |x� =1.
Функцияf(x)принимаетзначения0или1,приx=0,1.Рассмотримпоследовательнослучай|x� = |0�
Uˆ=0, 1� ,f(0)=0=(−1)f(0)(8.4)
|0� (|0�− |1�) |0, 0�− |0, 0� ,f(0)=1|0� (|0�− |1�).
|0, 1�−|Аналогичнодляслучая|x� = |1�
Uˆ1� (1�)= |1, 0�− |1, 1� ,f(1)=0=(−1)f(1)1� (1�). (8.5)
||0�− ||1, 1�− |1, 0� ,f(1)=1||0�− |
Объединяя равенства (8.4) и (8.5) получим
ˆ
U � |x� (|0�− |1�) � =(−1)f(x)|x� (|0�− |1�)/√2. (8.6)
Таким образом после действия цепи U на двухкубитовое состояние |ψ1� получим
U : |ψ1�→ |ψ2� = ±|0�√+2|1�|0�√+2|1�,еслиf(0)=f(1). (8.7)
·
±|0�−|1�|0�−|1�,еслиf(0)=f(1)
√2 · √2 �
Действуя в соответствии с цепью приведенной на рис. 8.1. на первый кубит гейтом Адамара, находим:
0� |0�−|1�еслиf(0)=f(1)
√2
H1 : |ψ2�⇒ |ψ2� = ±|1� |0�−|1�еслиf(0)=f(1). (8.8)
±|√2 �
Учитывая,чтоf(0)⊕ f(1)=0еслиf(0)=f(1),иf(0)⊕ f(1)=1,еслиf(0)=�f(1)можнопереписать выражение (8.8) в виде
|ψ3� = ±|f(0)⊕ f(1)�|0�− |1�. (8.9)
√2
Такимобразомизмеряясостояниепервогокубитаможноопределитьзначениеf(0)⊕ f(1),т.е.квантоваяцепьдаетвозможностьопределитьглобальноесвойствофункцииf(x),используятолькоодновычислениеf(x).Этобыстрее,чемсиспользованиемклассическоговычислительногоустройства,котороепотребуеткакминимумдвухвычислений.
В простейшем варианте задача Дойча состоит в следующем 1 Пустьимеютсячетыребинарныефункцииfi(x)отдвоичнойпеременнойx=0,1приэтомфункцииf1иf2–постоянныипринимаютзначенияf1(x)=0,f2(x)=1,афункцииf3иf4–принимаютследующиезначения:f3(x)=x,f4(x)=x.Приэтомговорят,чтофункцииf3иf4–
¬
сбалансированы. В задаче Дойча требуется определить к какой группе (постоянные или сбалансированные) относится функция fi
Классическоерешениетакойзадачипредполагаетпроведениекакминимумдвухопераций
– вычислениеfi(0)иfi(1).Квантовыйалгоритмпозволяетрешитьзадачузаоднуоперацию.Квантовыйкомпьютерработаеткакчерныйящик(вквантовыхвычисленияхегопринятоназыватьОракул),выполняяунитарнуюоперацию
Uˆ|x�⊗ |y� ⇒|x�⊗ |y ⊕ f(x)� . (8.10)
Оператор Uˆпредставляется четырьмя матрицами размерности 4 × 4, определяющими четыре
1 DeutschD.QuantumTheorytheChurch-TuringPrincipleandtheUniversalQuantumComputer.Proc.Roy.Soc.London,1985,VA400,№1818,p.57.Переводсанглийскогоподред.В.А.Садовничего:Сборн"Квантовыйкомпьютериквантовыевычисления".Ижевск.Ред.журн."Регулярнаяихаотическаядинамика",1999,с.157.
возможныефункцииfi(x)Uˆf1 ≡ 00
⎟⎟⎠
⎜⎜⎝ ⎞
⎛
⎞
⎛
10000100
010
001
≡ ˆUˆf2
I;
≡
1000
0001
≡
Iˆ⊗
NOT
;
00010010
⎞
⎛
⎞
⎛
10000100
Uˆf3 ≡ 01
00100001
Как следует из изложенного выше алгоритма для решения задачи Дойча достаточно только одной операции (квантовая цепь 8.1). Если состояние первого кубита на выходе цепи (8.9) |0�,тоf1,2(x)–постоянныефункции.Еслисостояниепервогокубитанавыходецепи|1�,тоf3,4(x)–сбалансированныефункции.Существенно,чтоприэтомневычисляютсязначениясамихфункций.Квантовыйкомпьютервыделяет"глобальную"информациюиз
Экспериментально данный алгоритм был реализован на простейших ЯМР– квантовых компьютерах 2
8.2 Алгоритм Дойча – Джозса (Deutsch-Jozsa).
Данный алгоритм был сформулирован для общего случая, когда |x� и |y� являются векторами в 2n-мерном гильбертовом пространстве x� =x0,x1,...xn−1�, y� =
ˆ|||3
⎟⎟⎠суперпозициисостояний. аквантовыйОракул действуетнамногомерныйвекторсостояния U|�y,y,...y,.011−n
Задача,вданномалгоритмеформулируетсяподобнопредыдущемуалгоритмуиимеетцельюопределитьявляетсялидвузначнаяфункцияпостояннойилисбалансированной,имеющейоднозначениедляоднойполовиныданныхxидругое–длявторой.Квантовыйалгоритмпозволяетрешитьэтузадачузаn-операций,тогдакакклассическийалгоритмимеетрешение
⎜⎜⎝
за 2n-операций.
Алгоритм может быть продемонстрирован на примере следующей игры. Алиса, находясь в Амстердаме, выбирает число x из 0 ÷ 2n − 1ипосылаетегопопочтеБобувБостоне.Бобвычисляетнекоторуюфункциюf(x)исообщаетрезультат,которыйможетбытьили0,или1.ПриэтомБобобещалиспользоватьфункциюf,однуиздвухтипов:Либоf(x)–постояннадлявсехзначенийx,либоf(x)–сбалансирована,приэтомонаравна1точнодляполовинывсехвозможныхзначенийxиравна0длядругойполовины.ЗадачаАлисыопределитьдостовернокакойтипфункциивыбранБобомдлявычислений,затративприэтомминимумкорреспонденции.
В классическом случае Алиса может послать Бобу только одно значение x в каждом письме. Поэтому Алиса будет вынуждена запросить Боба по меньшей мере 2n/2+1раз,таккаконаможетполучить2n/2 нулей для окончательного получения 1, объясняющего ей,
2К.А.Валиев,А.А.Кокин"Квантовыекомпьютеры:надеждыиреальность",Москва.Ижевск.R&C2001г.
3Deutsch D., Jozsa R. Rapid Solution of Problems by Quantum Computation. Proc. Roy. Soc., London, 1992, V A439, № 1907, p.553. Перевод с английского под ред. В.А. Садовничего: Сборн. "Квантовый компьютер и квантовые вычисления". Ижевск: Ред. журн. "Регулярная и хаотическая динамика", 1999, с.191.
010
1000
Uˆf4
≡
CNOT(Iˆ⊗
NOT
). (8.11)
≡
CNOT
;
≡
000
0010
чтоБобиспользуетсбалансированнуюфункцию,поэтомулучшийклассическийалгоритмонаможетприменять2n/2+1раз.Подчеркнем,чтовкаждомписьмеАлисапосылаетБобуn-битинформации.
ЕслиАлисаиБобмогутобмениватьсякубитамииеслиБобсогласенвычислитьf(x)используяунитарноепреобразованиеUf,тогдаАлисаможетдостичьсвоейцелиоднойкорреспонденциейиспользуяследующийалгоритм.
Алисаимеетn-кубитовыйрегистрдлянакапливаниясвоегозапросаиоднокубитовыйрегистр,которыйонапредставляетБобудляразмещенияответа.Алисаприготавливаеткакрегистрзапроса,такирегистрответавсостояниисуперпозиции.Бобпроведетвычислениеf(x)сиспользованиемквантовогопараллелизмаипоместитрезультатврегистрответа.ЗатемАлисаосуществляетинтерференциюсостоянийиспользуягейтАдамарадлярегистразапросаизаканчиваетисследованияпутемпроведенияподходящегоизмерениясцельюопределенияявляетсялиfпостояннойфункциейилисбалансированной.
Пошаговое исполнение алгоритма представлено квантовой цепью на рис. 8.2.
|ψ1� вида: ��
ψ1� = � √|x 2 � n |0�− |. (8.13)
|√21�
x∈{0,1}n
Регистр запроса теперь является суперпозицией всех значений x, а регистр ответа находится в суперпозиции состояний |0� и |1�.
Затем Боб вычисляет функцию f, используя квантовый оракул:
Uˆ: |x,y�→ |x,y ⊕ f(x)� . (8.14)
В результате образуется состояние |ψ2� вида:
(−1)f(x)|x�|0�− |1� . (8.15)
|ψ2� = √2n√2
x
ТеперьАлисаимеетнаборкубитов,вкоторыхрезультатвычисленияфункциисобранвамплитудесуперпозициикубитовогосостояния.АлисадалееиспользуетинтерференциюслагаемыхвсуперпозициипутемдействияГейтаАдамаранарегистрзапроса.ЧтобыопределитьрезультатдействияпреобразованийАдамараполезно,вычислитьдействиепреобразованияАдамаранасостояние|x�. Рассматривая случаи x =0 и x =1 раздельно, мы видим, что для одиночного кубита
H |x� = � (−1)xz |z� /√2. (8.16)
z
Таким образом
1 �
H⊗n |x1...xn� = √2n (−1)x1z1+···+xnzn |z1...zn� ,(8.17)z1...zn
что может быть записано компактно в форме:
1 �
H⊗n |x� = √2n (−1)x·z |z� , (8.18)
z
где xz– побитовое внутреннее произведение x и z по модулю 2. Используя (8.18) можно
·
записатьрезультатвычислениясостоянияψ3� ψ3� = �� 1(−1)x·z+f(x)z�|0�− |1� . (8.19)
| 2n |√2
xz
ТеперьАлисаможетнаблюдатьрегистрзапроса.Отметим,чтоамплитудадлясостояния 0�⊗n есть � (−1)f(x)/2n . |
x
Вслучае,еслиf–константа,амплитудадля|0�⊗n равна +1 или −1,взависимостиотзначенияконстантыf(x).Таккаксостояние|ψ3� имеет единичную длину отсюда следует, что все другие амплитуды должны быть равны 0 и измерение даст нулевые значения для всех кубитов в регистре запроса. Если f сбалансирована тогда положительный и отрицательный вклад в амплитуду для |0�⊗n сокращается,приводякнулевомузначениюамплитуды,аизмерениедолжнодатьрезультат0хотябыодногокубитаврегистрезапроса.Такимобразом,еслиАлисаизмеряетвсе0,тогдафункцияконстанта,впротивномслучаефункциясбалансирована.
Суммарно алгоритм Дойча-Джозса выглядит следующим образом.
Входные данные:
Оракул U, который осуществляет преобразование |x�|y�→ |x�|y ⊕ f(x)� для x ∈ {0,...2n−1} иf(x)∈{0, 1}.
f(x)–либоконстантадлявсехx,либо–сбалансирована,такчтоf(x)=1дляполовинызначенийxиf(x)=0длядругойполовинызначенийx.
Выходные данные: 0 если f – константа.
Время вычислений: одно вычисление Uf .
Алгоритм:
1. |0�⊗n |1� – инициализация состояний.
�2n��
2. → 1−1 ||0�−|1� – создание суперпозиции с использованием гейта Адамара.
√2nx=0x� √2
3. → (−1)f(x)||0�−|1� – вычисление f с использованием оракула U.
xx� √2
→ xz 21 n z+f(x)|z� √2
(−1)x·|0�−|1� – преобразование Адамара.
z – измерение для получения ответа задачи.
→
8.3 Классы квантовых алгоритмов.
Имеется 3 класса квантовых алгоритмов
– алгоритмы основанные на квантовых версиях Фурье преобразований (Дойча, ДойчаДжозса, алгоритм Шора факторизации целых чисел, дискретный логарифм);
– алгоритмы квантового поиска;
– алгоритмы моделирования квантовых систем.
8.3.1 Квантовые алгоритмы, основанные на квантовых Фурье-преобразованиях.
ДискретноеФурье-преобразованиеобычноопределяетсякакпреобразованиенабораx0,x1,...,xn−1N-комплексныхчиселвнаборкомплексныхчиселy0,y1,...,yn−1, определенных соотношением
1 N−1
yk ≡√Ne 2πijk/Nxj.(8.20)
j=0
Такоепреобразованиеимеетмногочисленныеприложениявразличныхотрасляхнауки.РассмотренноевышепреобразованиеАдамара,используемоевалгоритмеДойча-ДжозсаявляетсяпримеромэтогоклассаФурье-преобразований.Имеяввиду,чтомыопределяемлинейноепреобразованиеUнадn-кубитамипутемдействиянавычислительныйбазиссостояний|j�, где 0 � j � 2n − 1 можно написать
1 2n−1
|j�→ √2n e 2πijk/2n |k� . (8.21)
k=0
Можно проверить, что дискретное Фурье-преобразование унитарно и фактически может быть реализовано как квантовая цепь. Более того, если мы записываем его действие на суперпозицию
2n−12n−12n−12n−1
� 1 �� �
xj |j�→ √2n e 2πijk/2n xj |k� = yk |k� (8.22)
j=0k=0j=0k=0
то видно, что преобразование соответствует векторным обозначениям для Фурьепреобразования (8.20) для случая N =2n .
8.3.2 Алгоритмы квантового поиска.
Алгоритм квантового поиска решает следующую задачу:
Задано пространство поиска содержащее N элементов и нет предварительной информации о структуре расположения элементов в пространстве поиска. Необходимо в данном пространстве элементов найти такой, который удовлетворяет заданному свойству.
Классический
алгоритм требует порядка N операций
для осуществления решения такой задачи.
Алгоритмы квантового поиска используют
√N
операций
или шагов.
8.3.3 Алгоритмы квантового моделирования.
Классические компьютеры имеют большие трудности моделирования общих квантовых систем в силу физической природы квантовых процессов, что выражается в экспоненциальном росте шагов при классическом моделировании квантового объекта.
8.4 Квантовое Фурье-преобразование.
ДискретноеФурье-преобразованиенаборакомплексныхчиселx0,x1,...,xN−1внаборкомплексныхчиселy0,y1,...,yN−1 определяется равенством (8.20)
Квантовое Фурье-преобразование есть аналогичное преобразование, хотя общепринятые обозначения для квантовых Фурье-преобразований несколько отличаются. Квантовое Фурье преобразование ортонормированного базиса |0� ... |N − 1� определено как линейный оператор со следующим действием на базисные состояния:
1 N−1� 1 �
|j�→
√N
exp2πijk·
N |k�
.
(8.23)
k=0
Эквивалентное, действие на произвольное состояние может быть записано в виде
N−1N−1
xj |j�→ yk |k� , (8.24)
j=0k=0
гдеамплитудыykявляютсядискретнымиФурьепреобразованиямиамплитудxj.Этопреобразованиеявляетсяунитарными,поэтому,можетопределятьдинамикуквантовыхвычислений.
В последующем N =2n, где n – произвольное целое число, а базис |0� ... |2n − 1�
– вычислительныйбазисдляn-кубитовогоквантовогокомпьютера.Полезнозаписатьсостояние|j�,используябинарноепредставлениеj=j1j2...jn:
j=j12n−1 +j22n−2 ++jn20 . (8.25)
···
ВведемтакжеследующееобозначениеO.j�j�+1...jmдляпредставлениябинарнойфункции
j�/2+j�+1/4++jm/2m−�+1.
···
76
В результате квантовое Фурье-преобразование может быть задано в следующей полезной форме представления в виде произведения
|j1...jn�→ √12n � |0� + e 2πiO.jm |1� �� |0� + e 2πiO.jn−1jn |1� � ...
... |0� + e 2πiO.j1j2...jn |1� . (8.26)
Это представление в виде произведения настолько полезно, что можно его рассматривать как определение квантового Фурье преобразования. Эквивалентность представления в форме произведения (8.26) и определения (8.23) следует из следующих элементарных алгебраических выражений
2n−1
1 �
|j� → √2n exp(2πijk/2n) |k� =
k=011n
1 �� � =√2n ··· exp(2πij(k�· 2−�)) |k1...kn� =
k1=0kn=0�=1
11n
1 � �� =√2n ··· exp(2πijk�· 2−�) |k�� =
k1=0kn=0�=1
�� (8.27)
n1
1
��
=√2n
exp(2πijk�·
2−�)
|k��
=
�=1k�=0n
1 �� �
=√2n |0� +exp(2πij2−�) |1� =
�=1
1
=√2n (|0� +exp(2πiO.jm)|1�)(|0� +exp(2πiO.jn−1jn)|1�) ...
... (|0� +exp(2πiO.j1j2...jn)|1�) .
ПредставлениеФурье-преобразованиявформепроизведения(8.26)позволяетлегковывести эффективные квантовые цепи для квантовых Фурье-преобразований. Такие квантовые цепи изображены на рис. (8.5), на которой гейт Rk обозначает унитарное преобразование вида
10
Rk ≡ 0 e2πi/2k . (8.28)
Чтобы показать, что нарисованные цепи действительно вычисляют квантовые Фурьепреобразования, рассмотрим изменения состояний, если начальное состояние имеет вид |j1,...,jn�. Применяя гейт Адамара к первому биту получим
1 ��
√2 |0� + e 2πiO.j1 |1�|j2...jn� (8.29)
таккакexp(2πiO.j1)=−1когдаj1=1иравна+1впротивномслучае.ИспользуяконтролируемыйR2-гейтпроизводимсостояние:
√12 � |0� + e 2πiO.j1j2 |1� � |j2...jn� . (8.30)
ПродолжаявычислениедействийконтролируемыхR3,R4доRn-гейтов,каждыйизкоторыхдобавляетэкстра-биткфазекоэффициентапри|1� первого кубита. В конце этой процедуры получим состояние:
1 ��
√2 |0� + e 2πiO.j1j2...jn |1�|j2j3...jn� . (8.31)
Преобразуем аналогичной процедурой следующий кубит. В результате получим:
1 � �� �
√2 |0� + e 2πiO.j1j2...jn |1�|0� + e 2πiO.j2...jn |1�|j3j4...jn� . (8.32)
Продолжая последовательно для каждого кубита, находим конечное состояние
1 � �� ���
√2n |0� + e 2πiO.j1j2...jn|1�|0� + e 2πiO.j2...jn|1� ... |0� + e 2πiO.jn|1� (8.33)
Используя далее SWAP – операторы, состояние кубитов приводится к формуле (8.26), т. е. выполненное Фурье преобразование.