Лекция n 9 курса "Современные задачи теоретической информатики"



Скачать 277.44 Kb.
Pdf просмотр
Дата24.02.2017
Размер277.44 Kb.
Просмотров206
Скачиваний0
ТипЛекция

Введение в квантовые вычисления
Лекция N 9 курса
“Современные задачи теоретической информатики”

СПбГУ ИТМО
Юрий Лифшиц yura@logic.pdmi.ras.ru
Лаборатория мат. логики ПОМИ РАН
Осень’2005 1 / 27

... Мы не можем применить здесь здравый смысл, мы можем только стремиться понять внутреннюю логику этого безумия, которая наверняка есть...
Александр Шень
2 / 27

План лекции
1
Роль квантовых вычислений
2
Квантовые биты и квантовые схемы
Квантовый бит
Квантовые схемы
3
Телепортация и суперплотное кодирование
Суперплотное кодирование
Телепортация
4
Задача
3 / 27

План лекции
1
Роль квантовых вычислений
2
Квантовые биты и квантовые схемы
Квантовый бит
Квантовые схемы
3
Телепортация и суперплотное кодирование
Суперплотное кодирование
Телепортация
4
Задача
4 / 27

Мотивация для квантовых вычислений
Эффективные алгоритмы
Разложение чисел на множители за n
2
Алгоритм для дискретного логарифма
Полный перебор за

n
5 / 27

Мотивация для квантовых вычислений
Эффективные алгоритмы
Разложение чисел на множители за n
2
Алгоритм для дискретного логарифма
Полный перебор за

n
Криптография
Стойкая криптосистема без предположений о вычислительной сложности каких-либо задач
5 / 27

Мотивация для квантовых вычислений
Эффективные алгоритмы
Разложение чисел на множители за n
2
Алгоритм для дискретного логарифма
Полный перебор за

n
Криптография
Стойкая криптосистема без предположений о вычислительной сложности каких-либо задач
Кванты как модель вычисления
Сравнить с другими моделями
Переоценить пределы вычислимых задач
5 / 27

Модели вычислений
Стандартные модели
6 / 27

Модели вычислений
Стандартные модели
Машина Тьюринга
Логическая схема
RAM-машина
6 / 27

Модели вычислений
Стандартные модели
Машина Тьюринга
Логическая схема
RAM-машина
Альтернативные модели
Real-RAM и Real-Тьюринг
Оптический компьютер
Квантовые вычисления
Аналоговые вычисления
Бильярдный компьютер
6 / 27

Идея квантовых вычислений
1
Есть задача: вычислить функцию f
(x)
7 / 27

Идея квантовых вычислений
1
Есть задача: вычислить функцию f
(x)
2
Создаем систему из нескольких квантов “кодирующих”
x
7 / 27

Идея квантовых вычислений
1
Есть задача: вычислить функцию f
(x)
2
Создаем систему из нескольких квантов “кодирующих”
x
3
Строим систему физических преобразований (аналог алгоритма)
7 / 27

Идея квантовых вычислений
1
Есть задача: вычислить функцию f
(x)
2
Создаем систему из нескольких квантов “кодирующих”
x
3
Строим систему физических преобразований (аналог алгоритма)
4
Проводим измерения (получаем классическую информацию)
7 / 27

Идея квантовых вычислений
1
Есть задача: вычислить функцию f
(x)
2
Создаем систему из нескольких квантов “кодирующих”
x
3
Строим систему физических преобразований (аналог алгоритма)
4
Проводим измерения (получаем классическую информацию)
5
Интерпретируем результат
7 / 27

План лекции
1
Роль квантовых вычислений
2
Квантовые биты и квантовые схемы
Квантовый бит
Квантовые схемы
3
Телепортация и суперплотное кодирование
Суперплотное кодирование
Телепортация
4
Задача
8 / 27

Квантовый бит
Два базисных состояния:
Обозначение
|0
и
|1 9 / 27

Квантовый бит
Два базисных состояния:
Обозначение
|0
и
|1
Смешанные состояния:
α|0 + β|1
, где
α, β ∈ C
и
|α|
2
+ |β|
2
= 1
Домножение всех коэффициентов на e
i ϕ
не меняет состояние
9 / 27

Квантовый бит
Два базисных состояния:
Обозначение
|0
и
|1
Смешанные состояния:
α|0 + β|1
, где
α, β ∈ C
и
|α|
2
+ |β|
2
= 1
Домножение всех коэффициентов на e
i ϕ
не меняет состояние
9 / 27

Физические реализации
Законам модели квантового бита подчиняются разные физические эффекты:

Электрон возбужден/не возбужден

Фотон поляризован/не поляризован

Спин атомного ядра

Фотон в ловушке/нет фотона
10 / 27

Физические реализации
Законам модели квантового бита подчиняются разные физические эффекты:

Электрон возбужден/не возбужден

Фотон поляризован/не поляризован

Спин атомного ядра

Фотон в ловушке/нет фотона
Успехи физиков:

Передача квантового бита на 100 км.

Квантовый компьютер на 7 q-битах
10 / 27

Два q-бита
Состояние системы из двух q-битов
α
00
|00 + α
01
|01 + α
10
|10 + α
11
|11 11 / 27

Два q-бита
Состояние системы из двух q-битов
α
00
|00 + α
01
|01 + α
10
|10 + α
11
|11

00
|
2
+ |α
01
|
2
+ |α
10
|
2
+ |α
11
|
2
= 1 11 / 27

Два q-бита
Состояние системы из двух q-битов
α
00
|00 + α
01
|01 + α
10
|10 + α
11
|11

00
|
2
+ |α
01
|
2
+ |α
10
|
2
+ |α
11
|
2
= 1
Домножение на e
i ϕ
не меняет состояние
11 / 27

Измерение
Есть q-бит в состоянии
|ψ = α|0 + β|1 12 / 27

Измерение
Есть q-бит в состоянии
|ψ = α|0 + β|1
Измерение в стандартном базисе:
С вероятностью
|α|
2
получим “0”, с вероятностью
|β|
2
— “1”
Сам q-бит перейдет в соответствующее состояние
12 / 27

Измерение
Есть q-бит в состоянии
|ψ = α|0 + β|1
Измерение в стандартном базисе:
С вероятностью
|α|
2
получим “0”, с вероятностью
|β|
2
— “1”
Сам q-бит перейдет в соответствующее состояние
Измерение в базисе
φ, φ
:
C вероятностью
ψ|φ
получим

C вероятностью
ψ|φ
получим

Сам q-бит перейдет в

или

12 / 27

13 / 27

Частичные измерения
14 / 27

Квантовая схема
Квантовая схема:
последовательность физических преобразований из конечного набора (базисных) гейтов.
15 / 27

Квантовая схема
Квантовая схема:
последовательность физических преобразований из конечного набора (базисных) гейтов.
15 / 27

Что могут физики?
Физически реализуемые преобразования:

Над малым количеством q-битов

Только линейные преобразования

Только преобразования, сохраняющие длину
(унитарные)
16 / 27

Что могут физики?
Физически реализуемые преобразования:

Над малым количеством q-битов

Только линейные преобразования

Только преобразования, сохраняющие длину
(унитарные)
Следствие:
Любое преобразование однозначно задается значениями на базисных состояниях
Преобразование над k
q-битами можно записать в виде матрицы
16 / 27

Что могут физики?
Физически реализуемые преобразования:

Над малым количеством q-битов

Только линейные преобразования

Только преобразования, сохраняющие длину
(унитарные)
Следствие:
Любое преобразование однозначно задается значениями на базисных состояниях
Преобразование над k
q-битами можно записать в виде матрицы
2
k
× 2
k
16 / 27

Гейт Адамара
H
=
1

2 1
1 1 −1 17 / 27

Гейт Адамара
H
=
1

2 1
1 1 −1
Действие на базисных состояниях:
|0 →
1

2
|0 +
1

2
|1
|1 →
1

2
|0 −
1

2
|1 17 / 27

Гейт Адамара
H
=
1

2 1
1 1 −1
Действие на базисных состояниях:
|0 →
1

2
|0 +
1

2
|1
|1 →
1

2
|0 −
1

2
|1
Геометрическая интерпретация:
Отражение относительно луча под углом
π/8 17 / 27

Гейт CNOT
Факт:
с помощью схем из гейтов Адамара, CNOT и Toffoli
(двойное коннтролированное отрицание) можно сколь угодно точно приблизить любое унитарное преобразование.
18 / 27

План лекции
1
Роль квантовых вычислений
2
Квантовые биты и квантовые схемы
Квантовый бит
Квантовые схемы
3
Телепортация и суперплотное кодирование
Суперплотное кодирование
Телепортация
4
Задача
19 / 27

Суперплотное кодирование
Постановка задачи
Алиса хочет передать Бобу 2 классических бита в одном q-бите
У них есть по биту из пары
1

2
|00 +
1

2
|11 20 / 27

Суперплотное кодирование
Постановка задачи
Алиса хочет передать Бобу 2 классических бита в одном q-бите
У них есть по биту из пары
1

2
|00 +
1

2
|11
Идея
Алиса применяет одно из четырех преобразований к своему q-биту и посылает его Бобу
Боб проводит ряд действий над парой кубитов и узнает, какое преобразование сделала Алиса
20 / 27

Суперплотное кодирование
Постановка задачи
Алиса хочет передать Бобу 2 классических бита в одном q-бите
У них есть по биту из пары
1

2
|00 +
1

2
|11
Идея
Алиса применяет одно из четырех преобразований к своему q-биту и посылает его Бобу
Боб проводит ряд действий над парой кубитов и узнает, какое преобразование сделала Алиса
Исходное состояние системы
1

2
|00 +
1

2
|11 20 / 27

Алгоритм кодирования
Исходное состояние:
1

2
|00 +
1

2
|11 21 / 27

Алгоритм кодирования
Исходное состояние:
1

2
|00 +
1

2
|11
Четыре преобразования Алисы:
Ничего не делать
Поменять знак коэффициента у
|1
“1

2”
Поменять знак коэффициента у
|1
и “1

2”
21 / 27

Алгоритм кодирования
Исходное состояние:
1

2
|00 +
1

2
|11
Четыре преобразования Алисы:
Ничего не делать
Поменять знак коэффициента у
|1
“1

2”
Поменять знак коэффициента у
|1
и “1

2”
Состояния пары q-битов:
1

2
|00 +
1

2
|11 1

2
|00 −
1

2
|11 1

2
|10 +
1

2
|01 1

2
|10 −
1

2
|01 21 / 27

Квантовая телепортация
Постановка задачи
Хотим передать неизвестное состояние
|ψ = a|0 + b|1
от Алисы к Бобу
У них есть по биту из пары
1

2
|00 +
1

2
|11 22 / 27

Квантовая телепортация
Постановка задачи
Хотим передать неизвестное состояние
|ψ = a|0 + b|1
от Алисы к Бобу
У них есть по биту из пары
1

2
|00 +
1

2
|11
Идея
Алиса перемешает неизвестный q-бит со своим представителем пары
Алиса проведет измерения и перешлет результаты Бобу
Боб проделает вспомогательное преобразование и получит

22 / 27

Квантовая телепортация
Постановка задачи
Хотим передать неизвестное состояние
|ψ = a|0 + b|1
от Алисы к Бобу
У них есть по биту из пары
1

2
|00 +
1

2
|11
Идея
Алиса перемешает неизвестный q-бит со своим представителем пары
Алиса проведет измерения и перешлет результаты Бобу
Боб проделает вспомогательное преобразование и получит

Исходное состояние системы a

2
|000 +
a

2
|011 +
b

2
|100 +
b

2
|111 22 / 27

Алгоритм телепортации
Исходное состояние:
a

2
|000 +
a

2
|011 +
b

2
|100 +
b

2
|111 23 / 27

Алгоритм телепортации
Исходное состояние:
a

2
|000 +
a

2
|011 +
b

2
|100 +
b

2
|111
После CNOT:
a

2
|000 +
a

2
|011 +
b

2
|110 +
b

2
|101 23 / 27

Алгоритм телепортации
Исходное состояние:
a

2
|000 +
a

2
|011 +
b

2
|100 +
b

2
|111
После CNOT:
a

2
|000 +
a

2
|011 +
b

2
|110 +
b

2
|101
После измерения среднего бита:
Или a
|00 + b|11
Или a
|01 + b|10 23 / 27

Алгоритм телепортации
Исходное состояние:
a

2
|000 +
a

2
|011 +
b

2
|100 +
b

2
|111
После CNOT:
a

2
|000 +
a

2
|011 +
b

2
|110 +
b

2
|101
После измерения среднего бита:
Или a
|00 + b|11
Или a
|01 + b|10
Если средний бит равен 1, Боб применяет “0

1”:
Или a
|00 + b|11
Или a
|00 + b|11 23 / 27

Алгоритм телепортации II
Продолжаем:
a
|00 + b|11 24 / 27

Алгоритм телепортации II
Продолжаем:
a
|00 + b|11
Алиса применила
H
к первому биту:
a

2
|00 +
a

2
|10 −
b

2
|11 +
b

2
|01 24 / 27

Алгоритм телепортации II
Продолжаем:
a
|00 + b|11
Алиса применила
H
к первому биту:
a

2
|00 +
a

2
|10 −
b

2
|11 +
b

2
|01
После измерения верхнего бита:
Или a
|0 + b|1
Или a
|0 − b|1 24 / 27

Алгоритм телепортации II
Продолжаем:
a
|00 + b|11
Алиса применила
H
к первому биту:
a

2
|00 +
a

2
|10 −
b

2
|11 +
b

2
|01
После измерения верхнего бита:
Или a
|0 + b|1
Или a
|0 − b|1
Если нужно, Боб меняет знак у
|1
:
a
|0 + b|1 24 / 27

План лекции
1
Роль квантовых вычислений
2
Квантовые биты и квантовые схемы
Квантовый бит
Квантовые схемы
3
Телепортация и суперплотное кодирование
Суперплотное кодирование
Телепортация
4
Задача
25 / 27

Задача
Опираясь на слайд “Что могут физики?” докажите, что невозможно реализовать преобразование, получающее на вход пару битов в состояниях

и
|0
и выдающее

и

. Этот факт известен как No-Cloning Theorem
26 / 27

Последний слайд
Если не запомните ничего другого:

Квантовые вычисления основаны на проведении преобразований над системой из нескольких q-битов и последующих измерениях
27 / 27

Последний слайд
Если не запомните ничего другого:

Квантовые вычисления основаны на проведении преобразований над системой из нескольких q-битов и последующих измерениях

Передав один квантовый бит можно передать два классических
27 / 27

Последний слайд
Если не запомните ничего другого:

Квантовые вычисления основаны на проведении преобразований над системой из нескольких q-битов и последующих измерениях

Передав один квантовый бит можно передать два классических

Передав два классических бита можно передать квантовое состояние
27 / 27

Последний слайд
Если не запомните ничего другого:

Квантовые вычисления основаны на проведении преобразований над системой из нескольких q-битов и последующих измерениях

Передав один квантовый бит можно передать два классических

Передав два классических бита можно передать квантовое состояние
27 / 27

Последний слайд
Если не запомните ничего другого:

Квантовые вычисления основаны на проведении преобразований над системой из нескольких q-битов и последующих измерениях

Передав один квантовый бит можно передать два классических

Передав два классических бита можно передать квантовое состояние
Вопросы?
27 / 27

Document Outline

  • Ðîëü êâàíòîâûõ âû÷èñëåíèé
  • Êâàíòîâûå áèòû è êâàíòîâûå ñõåìû
    • Êâàíòîâûé áèò
    • Êâàíòîâûå ñõåìû
  • Òåëåïîðòàöèÿ è ñóïåðïëîòíîå êîäèðîâàíèå
    • Ñóïåðïëîòíîå êîäèðîâàíèå
    • Òåëåïîðòàöèÿ
  • Çàäà÷à
  • Èòîãè


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал