Юрий Кругляк_Квантовое моделирование в квантовой химии на квантовых компьютерах_399_стр
.pdfоткуда | u00 | =| u11 | и | u01 | =| u10 |. Таким |
образом, коэффициенты uij |
можно |
||||
выразить через sine и cosine некоторого угла β : |
|
|
|
|||
Q = |
eiθ00 |
cosβ |
eiθ01 sin β |
|
|
|
|
|
|
|
|
|
|
−eiθ10 |
sin β |
eiθ11 cosβ . |
|
|
||
Более того, фазы не независимы: u00u10 +u01u11 = 0 |
означает, |
что θ10 −θ00 |
=θ11 −θ01 . |
|||
Поскольку |
|
|
|
|
|
|
K(δ)T (α)R(β)T |
|
ei(δ+α+γ ) cosβ |
ei(δ+α−γ ) sin β |
|
||
(γ) = |
|
|
|
, |
|
|
|
|
−ei(δ−α+γ ) sin β |
ei(δ−α−γ ) |
cosβ |
|
мы можем для данного Q найти δ,α,γ , решив уравнения
δ +α +γ |
= |
θ00, |
δ +α −γ |
= |
θ01, |
δ −α +γ |
= |
θ10. |
Воспользовавшись равенством θ11 =θ10 −θ00 +θ01 , убеждаемся также, что имеет место равенство δ −α −γ =θ11 .
5.5.2. Одиночно контролирующие преобразования одиночных кубитов
Пусть Q = K(δ)T (α)R(β)T (γ) будет произвольным однокубитным унитарным преобразованием. Контролирующий вентиль ΛQ (§ 5.3.3) может быть реализован посредством ΛK(δ) с последующим ΛQ′ для Q′=T (α)R(β)T (γ) , а именно: ΛQ = (ΛK(δ))(ΛQ′). Сейчас покажем, как реализовать эти два
преобразования посредством базисных вентилей.
Обусловленный фазовый сдвиг может быть реализован посредством простых однокубитных операций:
ΛK(δ) =|0 0 | I +|1 1| K(δ) =|0 0 | I +eiδ |1 1| I =(K(δ/2)T (−δ/2)) I
или в виде квантовой схемы
Может показаться удивительным, что обусловленный фазовый сдвиг K(δ) может быть реализован схемой, действующей только на первый кубит в
190
отсутствии прямых преобразований над вторым кубитом. Причиной достаточности преобразований над первым кубитом является то обстоятельство, что фазовый сдвиг влияет на квантовое состояние в целом, а не только на одиночный кубит. В частности, | x a | y = a | x | y .
Реализация ΛQ′ несколько более сложная. Определим для Q′=T (α)R(β)T (γ) следующие преобразования:
Q0 |
= |
T (α)R(β/2), |
|
||
Q |
= |
R(−β/2)T −γ −α |
, |
||
1 |
|
|
|
2 |
|
Q |
= |
T γ −α . |
|
||
2 |
|
|
2 |
|
|
Квантовая схема ΛQ′ может быть определена как
ΛQ′=(I Q0)Cnot (I Q1)Cnot (I Q2 )
или графически
Эта схема выполняет следующее преобразование:
|0 | x →|0 Q0Q1 | x ,
|1 | x →|1 Q0 X Q1X Q2 | x .
Если учесть, что R(β)R(−β) = I и T (α)T (γ) =T (α +γ ) , равенство Q0 Q1 Q2 = I немедленно следует из определения Qi . С целью показать, что Q0 X Q1 X Q2 =Q′,
воспользуемся тем, что X R(β)X = R(−β) и X T (α)X =T (−α) . Тогда
Q0 X Q1X Q2 |
=T (α)R(β/2)(X R(−β/2)X ) |
X T (− |
γ +α)X T |
γ −α |
|
=Q′. |
|
|
|
|
2 |
|
2 |
|
|
Мы можем таким образом реализовать произвольное однокубитное преобразование, контролируемое одиночным кубитом.
5.5.3. Множественно контролирующие преобразования одиночных кубитов
Графические образы контролирующих операций (§§ 5.3.3, 5.5.2) обобщаются на более чем один контролирующий кубит. Пусть ΛkQ будет
191
преобразование (k+1)-кубита, в результате которого Q применяется к кубиту 0,
когда кубиты от 1 до |
k все имеют значение 1. Примером может служить |
трехкубитный вентиль |
Λ2 X Тоффоли CCnot (Controlled-Controlled-NOT), |
который меняет значение последнего, третьего кубита, если два первых кубита равны единице:
Двойка в Λ2 X указывает, что есть два контролирующих кубита. В этом смысле вентиль Cnot иногда обозначают как Λ1 X или просто Λ X .
Конструкцию, описанную в предыдущем параграфе 5.5.2, можно обобщить на управление одиночным кубитом со стороны остальных k кубитов. Для реализации Λ2Q , трехкубитного вентиля, контролирующего третий кубит
первыми двумя, заменяют каждый из Q0 ,Q1,Q2 в предыдущей схеме, а именно:
Дальнейшее расширение можно продолжить вплоть до ΛkQ .
5.6. Стандартная модель квантовых схем
Модель квантовых схем для квантовых вычислений описывает все расчеты посредством схем, содержащих простые вентили. Завершаются квантовые схемы измерениями, которые обозначаются значком . Стандартная модель квантовых схем для квантовых вычислений использует вентиль Cnot вместе со
всеми однокубитными преобразованиями с последующими однокубитными измерениями в стандартном базисе. Известны иные модели квантовых схем
[2, 15].
192
Глава 6. Квантовый алгоритм вычисления фазы
6.1. Введение
Начнем с квантового преобразования Фурье/КПФ (Quantum Fourier Transformation /QFT), уникальной наиболее часто используемой квантовой процедуры. Именно КПФ используется во многих квантовых алгоритмах для достижения большей скорости выполнения вычислений по сравнению с классическими алгоритмами. КПФ берет свое начало еще в классическом дискретном преобразовании Фурье/ДПФ (Discrete Fourier Transformation/DFT) [16] и в его эффективной реализации, получившей название быстрого преобразования Фурье/БПФ (Fast Fourier Transformation/FFT) [17]. Мы сначала кратко обсудим классическое преобразование Фурье, а затем подробнее рассмотрим его квантовую реализацию [18, 19] и перейдем к обсуждению алгоритма вычисления фазы (АВФ), квантового алгоритма для нахождения собственного значения унитарного оператора U = eiH , где H – эрмитов оператор. АВФ есть квантовый аналог процедуры классической диагонализации в классической квантовой химии. В части III книги, посвященной квантовой химии на квантовых компьютерах, мы будем пользоваться АВФ и его различными вариантами.
6.2. Классическое преобразование Фурье
Сначала обратимся к стандартному ДПФ, которое в качестве входа требует дискретную комплексную функцию a : [0,1,..., N −1] , а на выходе дает функцию
A : [0,1,..., N −1],
|
|
|
|
|
|
1 |
|
|
|
N −1 |
|
|
|
|
|
|
|||
|
|
|
A(x) = |
|
|
|
|
∑a(k)exp 2πi kx |
, |
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|||||||||
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
N k=0 |
|
|
N |
|
|
|
|||||||
и может |
рассматриваться |
как |
|
линейное преобразование |
вектора-столбца |
||||||||||||||
(a(0),a(1),...,a(N −1))T в другой вектор-столбец (A(0), A(1),..., A(N −1))T |
посредством |
||||||||||||||||||
матрицы |
с |
элементами |
F = |
|
|
1 |
|
exp |
2πi |
kx . |
Значения |
A(0), A(1),..., A(N −1) |
|||||||
|
|
|
|
|
|
||||||||||||||
|
|||||||||||||||||||
|
|
|
|
xk |
|
N |
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
N |
|
|
|
|
|||||
называют коэффициентами Фурье функции a . |
|
|
|
|
|||||||||||||||
Пример |
6.2.1. |
Пусть |
a : [0,1,..., N −1] |
будет |
периодической |
функцией |
|||||||||||||
|
−2πi |
ux |
некоторой частоты 0 < u < N . Фурье-коэффициентами этой |
||||||||||||||||
a(x) = exp |
|
||||||||||||||||||
|
|
N |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
193 |
|
|
|
|
|
Преобразование (| 0 0 | I (k ) + |1 1|) D(k ) ) применяет D(k ) к кубитам низкого порядка, контролируемым кубитом высокого порядка.
Поскольку оба преобразования D(k ) и R(k ) могут быть реализованы посредством O (k) операций, k -шаг в рекурсии добавляет O (k) шагов в имплементации UF(n) . Всего UF(n) для реализации требует O (n2 ) вентилей, что экспоненциально быстрее по сравнению с O (n2n ) шагами в случае классического БПФ. Схема такой реализации КПФ показана на рис. 14.
Рис. 14. Рекурсивная квантовая схема квантового преобразования Фурье.
Итак, при действии оператора КПФ на кубит имеем:
|
|
1 |
|
N −1 |
|
kj |
|
|
UQFT|k = |
|
|
∑exp 2πi |
| j , N =2n, |
||||
|
|
|
N |
|||||
N |
||||||||
|
|
|
j=0 |
|
|
|||
| j =| jn jn−1... j1 , |
ji {0,1}, |
j =∑in=1 ji 2i−1. |
||||||
Можно показать, что оператор UQFT |
унитарный [15]. |
В дополнение к описанным выше четырем шагам, ведущим к квантовой схеме на рис. 14, приведем также квантовую схему (рис. 15), реализующую КПФ посредством вентилей Адамара H (§ 5.3.2) и
R |
|
|
1 |
|
0 |
|
, |
j |
= |
|
|
2πi/2 |
j |
||
|
|
0 |
e |
|
|
||
|
|
|
|
|
|
доказательство которой можно найти в [15]. Эта схема нашла применение в квантово-химических расчетах [20].
Рис. 15. Схема квантового преобразования Фурье на вентилях H и Rj ; обратите внимание на обратный порядок результирующих кубитов qi после выполнения этой схемы.
197
Несмотря на то, что КПФ экспоненциально быстрее чем БПФ, им все же нельзя напрямую заменить собственно преобразование Фурье. Требуется подготовить n кубитов, а также в конце концов измерить их амплитуды, что эффективно выполнить непросто. Тем не менее, КПФ является ключевым блоком рассматриваемого ниже алгоритма вычисления фазы (АВФ/PEA, Phase Estimation Algorithm) [15, 19, 21].
6.5. Квазиклассический подход к квантовому преобразованию Фурье
Квантовую схему КПФ на рис. 15 можно существенно упростить [22]. Обратим внимание, что вентили, действующие на каждый кубит, кроме первого и последнего, однотипны. Сначала действуют вентили Rj , контролируемые
предыдущими кубитами, затем вентиль Адамара и, наконец, они выполняют роль контролирующих вентилей над следующими кубитами. Поскольку состояние каждого кубита не изменяется после применения вентиля Адамара, мы фактически можем выполнить измерение сразу после этого вентиля. Вместо использования контролируемых вентилей Rj можно применять только
соответствующие однокубитные вентили в зависимости от результатов индивидуальных измерений. Более того, все вентили Rj , действующие на k-ый
кубит, можно объединить в единственный вращательный вентиль
R |
|
|
1 |
|
0 |
|
, |
(ω ) = |
|
|
|
|
|||
z |
k |
|
0 |
e |
2πiωk |
|
|
|
|
|
|
|
|
угол ωk которого зависит от результатов до этого измеренных кубитов qi в соответствии с формулой
n−k+1 q
ωk = ∑ k+ii−1. k : n →1 i=2 2
Образец квазиклассической схемы КПФ, одинаковой для всех кубитов, показан на рис. 16.
Рис. 16. Упрощенная, основанная на измерении, схема для k-го кубита КПФ.
Существенное преимущество такого подхода состоит в том, что двукубитные вентили заменяются на однокубитные, контролируемые классическим битом. Такой подход особенно удобен применительно к
198
алгоритму вычисления фазы и он позволяет сформулировать итерационную версию АВФ (ИАВФ/Iterative Phase Esmation Algorithm, IPEA).
6.6. Квантовый алгоритм вычисления фазы
Алгоритм вычисления фазы (АВФ) – это квантовый алгоритм для нахождения собственного значения унитарного оператора U , предполагающий задание пробного собственного вектора [15]. Поскольку унитарный оператор U = eiH , где H – эрмитов оператор, АВФ есть квантовый аналог процедуры классической диагонализации.
Пусть | u есть собственный вектор оператора U ,
U |u =e2πiφ |u , φ 0,1)
где φ – значение фазы, определяемое в результате выполнения алгоритма. Квантовый регистр состоит из двух частей. Первая часть – результативная, состоит из m кубитов, измеренных в конце и порождающих состояние | 0 m . Вторая часть содержит соответствующий собственный вектор | u .
Квантовая схема АВФ показана на рис. 17.
Рис. 17. Квантовая схема алгоритма вычисления фазы с выделенным блоком обратного КПФ QFT† .
Применение вентилей Адамара ко всем кубитам первой части регистра
дает
|
|
|
|
m |
|reg = |
|
1 |
|
2∑−1| j |u . |
|
|
|
||
m |
||||
|
|
2 |
|
j=0 |
Далее, после выполнения последовательности контролирующих степеней U регистр трансформируется следующим образом:
|
|
1 |
|
2m −1 |
1 |
|
2m −1 |
|
|reg = |
|
|
∑U j| j |u = |
|
|
∑e2πijφ | j |u . |
||
|
|
|
|
|
|
|||
|
m |
|
m |
|||||
|
|
2 |
|
j=0 |
2 |
|
j=0 |
|
|
|
|
199 |
|
|
|
|