Вычисление периода
Из этого состояния мы хотим выделить информацию о периоде r. Временно сделаем предположение, что l при разных испытаниях принимает
одно и тоже значение. Пусть мы провели 3 испытания и получили три копии ϕ2
x1 = j1r +l, |
x2 = j2r +l, x3 = j3r +l, |
Далее находим |
x1 − x2 =( j1 − j2 )r, x1 − x3 =( j1 − j3 )r |
Поскольку j равновероятны, то с высокой вероятностью gcd(j1 − j2 , j1 − j3 ) =1
Поэтому период легко вычисляется так как
gcd(x1 − x2 ,x1 − x3 ) = gcd((j1 − j2 )r,( j1 − j3 )r) = r
Пример: x1 = 27, x2 =15, x3 = 7,
gcd(x1 − x2 ,x1 − x3 ) = gcd(( 27 −15 ),( 27 −7 )) gcd(12,20 ) = 4
К сожалению, l изменяется случайно (определяется случайным измерением регистра Y 
, поэтому принципиально необходимо применение квантового преобразования Фурье, устраняющего этот недостаток.
42
ДискретноепреобразованиеФурье для
функции f ( x ) = 2x mod 15
yk = |
1 |
N −1 |
2πi |
jk |
|
||||
|
∑ x j e |
|
N |
N j=0
43
Рассмотрим сначала частный случай, когда r делит N нацело. Тогда A = N / q −1
Запишем состояние регистра |
|
x в следующем виде |
||||
|
||||||
где |
|
|
|
|
|
|
f (x) = r / N , если x−l кратно r, |
||||||
|
||||||
|
f (x) = 0, если x−l не кратно r |
|||||
ϕl 
= N∑−1 f (x) x
x=0
Это λ
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
N / r −1 |
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
r |
|
|
||||||||
Тогда состояние регистра можно переписать так |
|
ϕl |
= |
|
|
∑ |
|
jr +l |
|
|||||||||||||||||||||||||||||||||||
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||||
|
|
N |
|
|||||||||||||||||||||||||||||||||||||||||
f(x) |
|
l |
|
|
|
|
|
|
|
r |
|
|
|
r |
|
|
|
|
|
r |
|
|
|
амплитуда |
|
|
j=0 |
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
r / N |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
x |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
КвантовоепреобразованиеФурье |
|
||||||||||||||||||||||||||||||||||||||||||
|
|
Выполняя ДПФ для состояния |
|
ϕl |
|
, получаем |
|
|
DFT |
|
ϕl = ∑ f ( c ) |
|
c |
|
||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||
|
|
где амплитуда |
f ( c ) DFT от f (x) |
N/r |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
c |
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
N / r −1 |
2πi( jr |
+l )c |
|
|
|
|
N / r −1 |
|
|
jc |
|
|
|
|
lc |
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
r |
|
|
|
r |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||
|
|
f (c) = |
|
|
|
|
|
∑ exp( |
|
|
|
|
) = |
|
|
|
|
∑ exp( |
2πi |
|
|
|
) exp( 2πi |
|
|
|
) |
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
N |
|
|
|
N |
|
N |
|
|
N / |
r |
|
|
N |
|
|
|
|
|
|
|
|
|
||||||||||||||||||
|
|
|
|
|
|
|
|
j=0 |
|
|
|
|
|
|
j=0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
Используя свойство комплексной функции в показательной форме, |
|
|||||||||||||||||||||||||||||||||||||||||||
T |
|
|
jn |
|
|
|
T ,n = 0 mod T , |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
∑exp 2πi |
= |
|
|
|
|
можно записать, что в последнем выражении |
|
|||||||||||||||||||||||||||||||||||||
T |
0,n ≠ 0 mod T |
44 |
||||||||||||||||||||||||||||||||||||||||||
j |
|
|
|
|
|
|||||||||||||||||||||||||||||||||||||||
член в квадратных скобках равен нулю за исключением с кратных N / r, поэтому
|
|
|
|
|
N |
|
lc |
|
1 |
|
|
lc |
|
N |
|
||
|
r |
exp( 2πi |
) = |
|
exp( 2πi |
), если c кратно |
, |
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
N r |
N |
|
|
|
|
N |
r |
||||||||||
f (c) = |
|
|
|
|
r |
|
|
|
|
||||||||
|
|
|
|
|
|
|
0, в |
противномслучае. |
|
|
|||||||
|
|
|
|
|
|
|
|
|
|||||||||
f ( c ) |
N/r |
N/r |
|
N/r |
N/r |
|
амплитуда |
||
|
|
|
|
|
|
|
|
|
r |
0 |
|
|
|
|
|
|
r-1 |
c |
|
Полагая, c = j |
N |
запишем |
|
|
|
|
|
|
|
|
|
r |
|
|
|
|
|
|
|
|
|
|
|
|
r −1 |
|
jl ) j |
N |
|
|
|
|
DFT ϕl |
= |
1 ∑exp( 2πi |
|
|||
|
|
|
|
|
r j=0 |
|
r |
r |
|
Измерение состояния с меткой c будет давать множитель λ = jl , имеющий случайное распределение от 0 до r-1, в силу случайности l.
Однако начальный сдвиг l |
в этом случае не влияет, поскольку |
можно рассматривать λ |
как новый множитель, который принимает |
значения от 0 до r-1 в каком то порядке, когда j принимает значения в |
|
порядке 0,1,2,…, r-1. |
45 |
|
Для нашего примера f ( x ) = 2x mod 15 состояние регистра после КПФ будет таким, как показано на рисунке, то есть, ненулевые вероятности имеют состояния 
Вероятность какого либо из этих состояний
|
|
|
|
|
|
N |
−1 |
2 |
|
|
|
|
|
|
|
|
r |
|
|
|
|
|
|
|
|||
|
|
|
|
r |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|||||
P |
c |
= |
|
|
∑exp( 2πij( rc mod N ) / N ) |
|
|
|
|
|
|||
N |
2 |
|
|
|
|
|
|||||||
|
|
|
|
j=0 |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
||
После преобразований можно получить |
P |
|
c ≥ |
4 |
1 |
||||||||
|
|||||||||||||
|
π2 |
r |
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||
Окончательно мы хотим выделить информацию о периоде r. Для этого проводится измерение состояния регистра x
46
Мы рассмотрели частный случай, когда r делит N нацело. Тогда rc mod N = 0 Если от этого условия отказаться, то
−r / 2 ≤ rc mod N ≤ r / 2 |
(1) |
||||||||||||||
Пусть rc mod N = kN ±r / 2 , тогда условие (1) запишем так |
|||||||||||||||
|
rc −kN |
|
≤ r / 2 |
( 2 ) |
|
||||||||||
|
|
|
|||||||||||||
Разделав обе части (2) |
на Nr, получим |
|
|||||||||||||
|
|
|
c |
|
− k |
|
≤ |
1 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
N |
|
|
2N |
|
|
|
|
|||||
|
|
|
|
r |
|
|
|
|
|
|
|||||
По результатам измерения регистра |
|
x |
мы получили величину c/N, |
||||||||||||
|
|||||||||||||||
тогда используя разложение c/N в цепную дробь, можно рассчитать |
|||||||||||||||
подходящую дробь и найти r. |
|
|
|
|
|||||||||||
Вероятность успеха |
|
P c |
0.4 |
. Для повышения вероятности проводим |
|||||||||||
испытания несколько раз с разными значениями а.
47
Вопросы реализации квантовых вычислений
•Внастоящее время квантовые вычисления находятсяна начальной стадииразвития. Дальнейший прогресс будет зависеть отрешения техническихзадач,связанныхс созданиемэлементной базыквантовых компьютеров.
•Существуюти практические реализации квантового алгоритма Шора. Созданный квантовый компьютер основан на явлении ядерно-магнитного резонанса и состоялизсеми кубитов,чегохватило для разложения числа 15 на простые множители 3 и 5.
•Типы квантовых компьютеров:
-Ядерный магнитный резонанс(NMR) -Ионные ловушки
-Квантовые точки
48
Исследованияквантового компьютера
Компании |
Квантовая среда |
Особенности |
|
|
|
Очень высокая вероятность |
|
|
Исследования квантовой среды |
квантовых ошибок, что не |
|
IBM |
на основе схем из |
позволяет создавать |
|
|
сверхпроводящих металлов |
полноценные квантовые |
|
|
|
компьютеры |
|
|
Исследование теоретически |
Существование квазичастиц, |
|
Microsoft |
более надежной квантовой |
используемых в |
|
среды и создание |
топологическом кубите, пока |
||
|
|||
|
топологического кубита |
не доказано |
|
Alcatel- |
Исследования |
Создание топологического |
|
Lucent |
конденсированного состояния |
кубита на основе дробного |
|
(Bell |
вещества с целью создания |
квантового эффекта Холла |
|
Labs) |
топологического кубита |
пока в стадии исследований |
|
|
Исследования по созданию |
Пока не доказано, что чипы |
|
D-Wave |
квантового компьютера на |
||
построены на основе |
|||
Systems |
основе сверхпроводящего чипа, |
||
квантовых эффектов |
|||
|
содержащего 512 кубитов |
||
|
|
||
|
Разноплановые исследования |
Google адаптирует свои |
|
|
компьютеров D-Wave Systems, |
||
технологии под возможности |
|||
|
построенных на основе |
квантовых компьютеров |
|
|
контактов Джозефсона |
||
|
|
1 Топологический кубит – это теоретический кубит на основе двухмерных квазичастиц
(анионов), являющихся более стабильными, что позволяет уменьшить ошибки декогеренции.
49