- •Понятие о квантовых вычислениях
- •n- кубитовый регистр
- •Вычисление функции в кубитовом регистре
- •Идея квантовых вычислений
- •Решение
- •Алгоритм Дойча-Джоза
- •Алгоритм ускоренного поиска (алгоритм Гровера)
- •Представлене булевой функции таблицей истинности
- •Пример алгоритма Гровера
- •Выводы
- •Криптосистема РША
- •Квантовый компьютер и криптосистема РША
- •Пример длинного числа
- •Идеи квантовых вычислений
- •Алгоритм Шора 1994г.
- •Пример факторизации на основе поиска периода
- •Реализация алгоритма Шора на двух квантовых регистрах
- •Этапы алгоритма Шора
- •Вычисление периода
- •Способы практической реализации квантовых компьютеров
- •Ядерные магнитно-резонансные компьютеры
Решение
Сначала возьмемсистему из одного кубита в базисномсостоянии,соответствующемлоги
ческомунулю.
q |
= λ0 |
|
0 + λ1 |
|
1 |
|
|
|
1 |
|
||||
|
|
|||||||||||||
0 |
=1 |
|
0 + 0 |
|
1 или |
|
0 |
|||||||
|
|
|
||||||||||||
|
|
|
= |
0 |
|
|||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
1 = 0 |
|
0 +1 |
|
1 |
или |
|
1 |
|
0 |
|
|
|
|
||||||||
|
|
|
= |
1 |
|
|||||
|
|
|
|
|
|
|
|
|
|
К полученномукубиту применяем преобразованиеАдамара
H = |
1 |
|
1 |
1 |
||
|
|
|
|
|
||
|
|
|
||||
2 |
||||||
|
|
1 |
−1 |
11
Построениематриц Адамара
H |
|
=1, |
H1 |
1 |
1 |
0 |
= |
|
|||
|
|
|
1 |
−1 |
1 |
|
1 |
|
|
|
H |
n−1 |
H |
n−1 |
|
Hn = |
|
|
Hn−1 |
= |
|
|
||||
1 |
|
−1 |
|
|
Hn−1 |
−Hn−1 |
||||
|
|
1 |
1 |
1 |
1 |
|
|
|
|
|
|
|
|
−1 |
1 |
−1 |
|
|
|
|
|
H2 |
= |
1 |
|
|
|
|
|
|||
|
1 |
−1 |
|
|
|
|
|
|
||
|
|
1 |
−1 |
|
|
|
|
|||
|
|
1 |
−1 |
−1 |
1 |
|
|
|
|
|
12
H |
|
0 |
= |
1 |
|
1 |
1 |
1 |
|
= |
1 |
|
1 |
= |
1 |
|
( |
|
0 |
+ |
|
1 ) |
|||
|
|
|
|
||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
2 |
|
1 |
−1 |
0 |
|
|
2 |
|
1 |
|
2 |
|
|
|
|
|
|
|
• Далеевыполняемещеодно преобразование,котороеназывается фазовыйзапрос Of
|
|
|
|
|
|
|
|
− |
f (0) |
|
|
1 |
|
|
|
|
− |
f (0) |
|
|
|
|
|
|
|
|
|
Of H |
|
0 = |
1 |
|
|
( |
|
1) |
0 |
|
1 = |
1 |
|
|
( 1) |
|
= |
1 |
|
(−1) f (0) ( |
|
0 +(−1) f (1) |
|
1 ) |
|||
|
|
|
|
|
|
|
|
|
|||||||||||||||||||
|
|
|
|
|
|
0 |
− |
f (1) |
|
|
|
− |
f (1) |
|
|
|
|
|
|||||||||
|
2 |
|
|
|
2 |
|
2 |
||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||
|
|
|
|
|
|
|
( 1) |
|
|
|
|
( 1) |
|
|
|
|
|
|
|
|
•Далееещераз применяемпреобразование Адамара.
|
|
|
|
1 |
1 |
− |
f (0) |
|
|
|
f (0) |
|
f (1) |
|
f (0) |
|
f (1) |
||
HOf H |
|
0 == |
1 |
|
|
( 1) |
|
= |
(−1) |
|
+(−1) |
|
0 + (−1) |
|
−(−1) |
|
|
1 |
|
|
|
|
|
|
|||||||||||||||
|
|
|
2 |
1 |
−1 |
(−1) f (1) |
|
|
|
|
2 |
|
|
|
2 |
|
|
|
13
•Таким образомпосле этих преобразований мы получаем суперпозициюсостоянийс
амплитудами λ = (−1) f (0) +(−1) f (1) |
λ = (−1) f (0) −(−1) f (1) |
||||||||
0 |
|
|
|
|
2 |
1 |
2 |
||
|
|
|
|
|
|
|
|
||
• Для функции типа константы |
f (0) = f (1) |
||||||||
получаем амплитуды |
λ0 = ±1, λ1 = 0 и |
|
|||||||
измерениеконечногосостоянияс |
|
||||||||
вероятностью P = |
|
λ |
|
2 |
=1 определит,что |
||||
|
|
||||||||
|
|
0 |
|
|
|
|
|
|
|
системанаходится |
|
в |
|
состоянии |
|
|
0 |
14 |
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
• Для функции, неявляющейся константой f (0) ≠ f (1) амплитуды равны λ0 = 0,λ1 = ±1
и с вероятностью P = λ1 2 =1 получим состояние 1 .
•Таким образомв процесстолько одного измерения мыполучаем результат 0,
который означает, что функция f (x) является константой или не константой в противном случае.
15