Компьютер и здоровье
<<  Компьютер и моё здоровье Уроку информатики свойства алгоритм решение задач  >>
Компиляторы для квантовых компьютеров
Компиляторы для квантовых компьютеров
Квантовые компьютеры: взгляд разработчика компиляторов
Квантовые компьютеры: взгляд разработчика компиляторов
Что говорят физики
Что говорят физики
Алгоритм Шора факторизации целого числа
Алгоритм Шора факторизации целого числа
Факторизация целого числа: оценка времени
Факторизация целого числа: оценка времени
На пути к вычислительной модели языков квантового программирования
На пути к вычислительной модели языков квантового программирования
Физические основания квантовых вычислений
Физические основания квантовых вычислений
Пространство состояний
Пространство состояний
Кубит: квантовый бит
Кубит: квантовый бит
Эволюция
Эволюция
Полезные квантовые операторы: операторы Паули
Полезные квантовые операторы: операторы Паули
Полезные квантовые операторы: оператор Адамара
Полезные квантовые операторы: оператор Адамара
Составные системы
Составные системы
Двухкубитовый оператор CNOT (управляемое NOT): CNOT переворачивает
Двухкубитовый оператор CNOT (управляемое NOT): CNOT переворачивает
Квантовые измерения
Квантовые измерения
Квантовые измерения
Квантовые измерения
x
x
Задача доставки состояния кубита Алисы и Боба
Задача доставки состояния кубита Алисы и Боба
H
H
Архитектура квантового компьютера
Архитектура квантового компьютера
Архитектура отказоустойчивого квантового компьютера Кросса
Архитектура отказоустойчивого квантового компьютера Кросса
Потенциальные технологии целевой машины
Потенциальные технологии целевой машины
Симулятор ионной ловушки MIT
Симулятор ионной ловушки MIT
Квантовый компьютер, основанный на ионной ловушке: реальность
Квантовый компьютер, основанный на ионной ловушке: реальность
Топологический квантовый компьютер
Топологический квантовый компьютер
Критерии ДиВинченцо для квантового компьютера
Критерии ДиВинченцо для квантового компьютера
Универсальные наборы квантовых элементов
Универсальные наборы квантовых элементов
Квантовый алгоритм факторизации Шора
Квантовый алгоритм факторизации Шора
Задача нахождения порядка
Задача нахождения порядка
Квантовое нахождение порядка
Квантовое нахождение порядка
Предлагаемые квантовые языки программирования
Предлагаемые квантовые языки программирования
Абстракции и ограничения языка
Абстракции и ограничения языка
Методы разработки квантовых алгоритмов
Методы разработки квантовых алгоритмов
Инуструменты разработки для квантового компьютера: желаемое
Инуструменты разработки для квантового компьютера: желаемое
Иерархия инструментов квантовой разработки
Иерархия инструментов квантовой разработки
Языки и абстракции в Design Flow
Языки и абстракции в Design Flow
Design Flow for Ion Trap
Design Flow for Ion Trap
Устойчивость к ошибкам
Устойчивость к ошибкам
Устойчивость к ошибкам
Устойчивость к ошибкам
Среда разработки с устойчивостью к ошибкам и исправлением ошибок
Среда разработки с устойчивостью к ошибкам и исправлением ошибок
Топологическая робастность
Топологическая робастность
=
=
=
=
Вырожденные основные состояния (in punctured system) действуют как
Вырожденные основные состояния (in punctured system) действуют как
Универсальные набор топологически робастных логических элементов
Универсальные набор топологически робастных логических элементов
Брейд целевого кода для элемента CNOT с оптимизацией Соловея-Китаева
Брейд целевого кода для элемента CNOT с оптимизацией Соловея-Китаева
Задачи для исследования
Задачи для исследования
Соавторы
Соавторы
Компиляторы для квантовых компьютеров
Компиляторы для квантовых компьютеров

Презентация: «Компиляторы для квантовых компьютеров». Автор: Al Aho. Файл: «Компиляторы для квантовых компьютеров.ppt». Размер zip-архива: 4549 КБ.

Компиляторы для квантовых компьютеров

содержание презентации «Компиляторы для квантовых компьютеров.ppt»
СлайдТекст
1 Компиляторы для квантовых компьютеров

Компиляторы для квантовых компьютеров

Al Aho aho@cs.columbia.edu

KAUST 27 февраля 2011 г.

TexPoint fonts used in EMF. Read the TexPoint manual before you delete this box.: AAAA

2 Квантовые компьютеры: взгляд разработчика компиляторов

Квантовые компьютеры: взгляд разработчика компиляторов

Откуда воодушевление насчет квантовых компьютеров? Вычислительная модель для квантового программирования Потенциальные технологии целевой машины Языки квантового программирования Нерешенные проблемы в построении квантовых компьютеров

3 Что говорят физики

Что говорят физики

«Квантовая информация – это радикальный скачок в области информационных технологий, отличающаяся от современных технологий более глубоко, чем цифровой компьютер – от абака.» William D. Phillips, лауреат Нобелевской премии в области физики 1997 г.

4 Алгоритм Шора факторизации целого числа

Алгоритм Шора факторизации целого числа

Задача: Дано составное n-битное число, найти нетривиальный множитель. Наилучший известный детерминистический алгоритм на классическом компьютере имеет вычислительную сложность exp(O( n1/3 log2/3 n )). Квантовый компьютер способен решить эту задачу за O( n3 ) операций.

Peter Shor Algorithms for Quantum Computation: Discrete Logarithms and Factoring Proc. 35th Annual Symposium on Foundations of Computer Science, 1994, pp. 124-134

5 Факторизация целого числа: оценка времени

Факторизация целого числа: оценка времени

Классический алгоритм: просеивание по числовым полям Вычислительная сложность: exp(O(n1/3 log2/3 n)) Время для 512-битового числа: 8400 MIPS лет Время для 1024-битового числа: в 1.6 миллиардов раз дольше Квантовый алгоритм: алгоритм Шора Вычислительная сложность: O(n3) Время для 512-битового числа: 3,5 часа Время для 1024-битового числа: 31 час (для квантового прибора 1 GHz)

M. Oskin, F. Chong, I. Chuang A Practical Architecture for Reliable Quantum Computers IEEE Computer, 2002, pp. 79-87

6 На пути к вычислительной модели языков квантового программирования

На пути к вычислительной модели языков квантового программирования

7 Физические основания квантовых вычислений

Физические основания квантовых вычислений

Четыре постулата квантовой механики

М. Нильсен, И. Чанг Квантовые вычисления и квантовая информация М.: «Мир», 2006 M. A. Nielsen and I. L. Chuang Quantum Computation and Quantum Information Cambridge University Press, 2000

8 Пространство состояний

Пространство состояний

Постулат 1

Состояние изолированной квантовой системы описывается единичным вектором комплексного гильбертова пространства.

9 Кубит: квантовый бит

Кубит: квантовый бит

Состояние квантового бита в 2-мерном комплексном гильбертовом пространстве описывается единичным вектором (в обозначениях Дирака) где ? и ? — комплексные коэффициенты, называемые амплитудами базисных состояний |0i и |1i и В привычных алгебраических обозначениях

10 Эволюция

Эволюция

U

Эволюция замкнутой квантовой системы описывается унитарным оператором U. (Оператор U унитарный, если U y = U ?1.)

Постулат 2

Состояние системы в момент времени t1

Состояние системы в момент времени t2

11 Полезные квантовые операторы: операторы Паули

Полезные квантовые операторы: операторы Паули

Операторы Паули

В привычной линейной алгебре эквивалентно

12 Полезные квантовые операторы: оператор Адамара

Полезные квантовые операторы: оператор Адамара

Матричное представление оператора Адамара: Действие H на состояния вычислительного базиса: Заметим, что HH = I.

13 Составные системы

Составные системы

Постулат 3

Пространство состояний составной системы представляет собой тензорное произведение пространств состояний входящих в нее систем. Если одна система находится в состоянии а другая система — в состоянии , то составная система находится в состоянии . Вместо часто пишут или .

14 Двухкубитовый оператор CNOT (управляемое NOT): CNOT переворачивает

Двухкубитовый оператор CNOT (управляемое NOT): CNOT переворачивает

управляемый бит t тттк управляющий бит c принимает значение 1:

Полезные квантовые операторы: оператор CNOT

Действие элемента CNOT

15 Квантовые измерения

Квантовые измерения

Квантовые измерения описываются набором операторов , действующих на пространстве состояний системы. Если состояние системы до измерения — , то вероятность получения результата m составляет а состояние системы после измерения —

Постулат 4

16 Квантовые измерения

Квантовые измерения

Операторы измерения удовлетворяют уравнению полноты: Уравнение полноты говорит о том, что сумма вероятностей равна единице:

17 x

x

H

y

Квантовые схемы: модель квантовых вычислений

Квантовая схема для создания состояний Белла (Эйнштейна-Подольского-Розена): Действие схемы: Каждый результат – запутанное состояние, которое не может быть представлено в виде произведения. (Эйнштейн: «Пугающее действие на расстоянии.»)

18 Задача доставки состояния кубита Алисы и Боба

Задача доставки состояния кубита Алисы и Боба

Алиса знает, что в будущем ей потребуется послать Бобу состояние важного секретного кубита. Ее друг Боб уезжает далеко, и у него будет очень узкополосное интернет-соединение. Таким образом, Алисе потребуется послать состояние ее кубита Бобу как можно дешевле. Как могут решить такую задачу Алиса и Боб?

19 H

H

Z

X

Решение для Алисы и Боба: квантовая телепортация!

Алиса и Боб генерируют ЭПР-пару. Алиса берет одну половину пары; Боб берет другую половину. Боб уезжает. Алиса приводит свой секретный кубит во взаимодействие со своей ЭПР-половиной и проводит измерение двух кубитов. Алиса посылает два получившихся классических измерения Бобу. Боб декодирует свою половину ЭПР-пары, с 2 битами, получая .

M1

M2

20 Архитектура квантового компьютера

Архитектура квантового компьютера

Knill [1996]: Квантовая память, классический компьютер с квантовым прибором с операциями для инициализации регистров кубитов и применения квантовых операций и измерений

Квантовая память

Классический компьютер

Квантовое логическое устройство

E. Knill Conventions for Quantum Pseudocode Los Alamos National Laboratory, LAUR-96-2724, 1996

21 Архитектура отказоустойчивого квантового компьютера Кросса

Архитектура отказоустойчивого квантового компьютера Кросса

Квантовая память

Классический компьютер

Служебная фактория (ancilla factory)

Фактория квантового ПО

Квантовое логическое устройство

Andrew W. Cross Fault-Tolerant Quantum Computer Architectures Using Hierarchies of Quantum Error-Correcting Codes PhD Thesis, MIT, June 2008

22 Потенциальные технологии целевой машины

Потенциальные технологии целевой машины

Ионные ловушки Переходы Джозефсона Ядерный магнитный резонанс Оптические фотоны Квантовая электродинамика оптического резонатора Квантовые точки Неабелевы анионы дробного квантового эффекта Холла

23 Симулятор ионной ловушки MIT

Симулятор ионной ловушки MIT

24 Квантовый компьютер, основанный на ионной ловушке: реальность

Квантовый компьютер, основанный на ионной ловушке: реальность

Немасштабируемая оптика!

Ионная ловушка (скрыта)

25 Топологический квантовый компьютер

Топологический квантовый компьютер

Теорема: В любом топологическом квантовом компьютере все вычисления могут быть произведены посредством передвижения единственной квазичастицы!

S. Simon, N. Bonesteel, M. Freedman, N. Petrovic, and L. Hormozi Topological Quantum Computing with Only One Mobile Quasiparticle Phys. Rev. Lett, 2006

26 Критерии ДиВинченцо для квантового компьютера

Критерии ДиВинченцо для квантового компьютера

Масштабируемая система с хорошо определенными кубитами Возможность инициализации в простое фидуциальное состояние Большое время декогеренции Наличие универсального набора квантовых логических элементов Возможность эффективных покубитовых измерений

David DiVincenzo Solid State Quantum Computing http://www.research.ibm.com/ss_computing

27 Универсальные наборы квантовых элементов

Универсальные наборы квантовых элементов

Набор логических элементов универсален для квантовых вычислений, если любой унитарный оператор может быть аппроксимирован до произвольной точности квантовой схемой, использующей элементы из этого набора. Фазовый элемент S = ; элемент ?/8 T = Примеры универсальных наборов квантовых элементов: { H, S, CNOT, T } { H, I, X, Y, Z, S, T, CNOT } Однокубитовый и CNOT-элементы точно универсальны для квантовых вычислений.

28 Квантовый алгоритм факторизации Шора

Квантовый алгоритм факторизации Шора

Ввод: Составное число N Вывод: Нетривиальный делитель N если N четное, то возврат 2; если N = ab для целых a >= 1, b >= 2, то возврат a; x := rand(1,N-1); если нод(x,N) > 1, то возврат нод(x,N); r := порядок(x mod N); // квантовый шаг если r четное и xr/2 != (-1) mod N, то {f1 := нод(xr/2-1,N); f2 := нод(xr/2+1,N)}; если f1 – нетривиальный делитель, то возврат f1; иначе если f2 – нетривиальный делитель, то возврат f2; иначе возврат неудача;

Nielsen and Chuang, 2000

29 Задача нахождения порядка

Задача нахождения порядка

Для натуральных чисел x и N, x < N, таких что нод(x, N) = 1, порядок x (mod N) – это наименьшее натуральное r такое, что xr ? 1 (mod N). Например, порядок 5 (mod 21) равен 6. Задача нахождения порядка состоит в нахождении порядка x (mod N) при данных x и N. Все известные классические алгоритмы нахождения порядка суперполиномиальны по числу бит в N.

30 Квантовое нахождение порядка

Квантовое нахождение порядка

Задача нахождения порядка может быть решена с помощью квантовой схемы, содержащей O((log N)2 log log (N) log log log (N)) элементарных квантовых логических элементов. Лучшие из известных классических алгоритмов требуют exp(O((log N)1/2 (log log N)1/2 ) времени.

31 Предлагаемые квантовые языки программирования

Предлагаемые квантовые языки программирования

Квантовый псевдокод [Knill, 1996] Императивные: напр., QCL [?mer, 1998-2003] синтаксис на основе C классическое управление потоком передачи данных классические и квантовые данные перемежающиеся измерения и квантовые операторы Функциональные: напр., QFC, QPL, QML линейная логика Жирара квантовое лямбда-исчисление

32 Абстракции и ограничения языка

Абстракции и ограничения языка

Состояния — это суперпозиции Операторы — это унитарные преобразования Состояния кубитов могут стать запутанными Измерения приводят к разрушению Теорема о невозможности копирования: нельзя копировать неизвестное квантовое состояние!

33 Методы разработки квантовых алгоритмов

Методы разработки квантовых алгоритмов

Оценка фазы Квантовое преобразование Фурье Нахождение периода Оценка собственных значений Алгоритм поиска Гровера Усиление амплитуды

34 Инуструменты разработки для квантового компьютера: желаемое

Инуструменты разработки для квантового компьютера: желаемое

Среда разработки (design flow), которая переводит высокоуровневые квантовые программы в эффективные устойчивые к ошибкам реализации на различных квантовых вычислительных машинах с различной технологией Языки, компиляторы, эмуляторы и инструменты разработки для поддержки среды разработки Хорошо определенные интерфейсы между компонентами Эффективные методы инкорпорирования устойчивости к ошибкам и квантового исправления ошибок Эффективные алгоритмы для оптимизации и верификации квантовых программ

35 Иерархия инструментов квантовой разработки

Иерархия инструментов квантовой разработки

Представление: послойная иерархия с хорошо определенными интерфейсами

Языки программирования

Компиляторы

Оптимизаторы

Симуляторы

Инструменты макетирования (layout tools)

K. Svore, A. Aho, A. Cross, I. Chuang, I. Markov A Layered Software Architecture for Quantum Computing Design Tools IEEE Computer, 2006, vol. 39, no. 1, pp.74-83

36 Языки и абстракции в Design Flow

Языки и абстракции в Design Flow

Квантовый компилятор

Исходная квантовая программа

QIR

QASM

QPOL

Независимые от технологии CG+Optimizer

Независимые от технологии CG+Optimizer

Front End

Симулятор технологии

QIR: quantum intermediate representation – квантовое промежуточное представление QASM: quantum assembly language – квантовый ассемблер QPOL: quantum physical operations language – квантовый язык физических операций

37 Design Flow for Ion Trap

Design Flow for Ion Trap

38 Устойчивость к ошибкам

Устойчивость к ошибкам

В квантовом компьютере, устойчивом к ошибкам, более 99% ресурсов вероятно будут расходоваться на квантовое исправление ошибок [Chuang, 2006]. Схема, содержащая N (свободных от ошибок) элементов может быть симулирована с вероятностью ошибки, не превосходящей ?, с использованием N log(N/?) неустойчивых к ошибкам логических элементов, дающих ошибку с вероятностью p, покуда p < pth [von Neumann, 1956].

39 Устойчивость к ошибкам

Устойчивость к ошибкам

Препятствия к применению классического исправления ошибок к квантовым цепям: запрет клонирования непрерывность ошибок измерения уничтожают информацию Shor [1995] и Steane [1996] показали, что эти препятствия могут быть преодолены с помощью с помощью каскадированных квантовых кодов, исправляющих ошибки.

P. W. Shor Scheme for Reducing Decoherence in Quantum Computer Memory Phys. Rev. B 61, 1995 A. Steane Error Correcting Codes in Quantum Theory Phys. Rev. Lett. 77, 1966

40 Среда разработки с устойчивостью к ошибкам и исправлением ошибок

Среда разработки с устойчивостью к ошибкам и исправлением ошибок

QCC: QIR, QASM

Software: QPOL

Математическая модель: Квантовая механика, унитарные операторы, тензорные произведения

Вычислительная формулировка: Квантовые биты, логические элементы и схемы

Физическая система: Лазерные импульсы применяемые к ионам в ловушках

Создание пары ЭПР

QIR

Машинные инструкции

Физический прибор

Модель квантовой схемы

QASM

QPOL

41 Топологическая робастность

Топологическая робастность

42 =

=

Топологическая робастность

43 =

=

Брейд («косичка»)

Bonesteel, Hormozi, Simon, … ; PRL 2005, 2006; PRB 2007

44 Вырожденные основные состояния (in punctured system) действуют как

Вырожденные основные состояния (in punctured system) действуют как

кубиты. 2. Унитарные операторы (логические элементы) выполняются на основном состоянии путем сплетения punctures (квазичастиц) вокрг друг друга. Конкретные брейды соответствуют конкретным вычислениям. 3. Состояние может быть инициализовано путем “вытягивания” пары из вакуума. Состояние может быть измерено попыткой возврата пары в вакуум. 4. Возможны варианты схем 2,3.

Преимущества: Топологическая квантовая «память» хорошо защищена от шума Операции (логические элементы) также топологически робастны

C. Nayak, S. Simon, A. Stern, M. Freedman, S. DasSarma Non-Abelian Anyons and Topological Quantum Computation Rev. Mod. Phys., June 2008

45 Универсальные набор топологически робастных логических элементов

Универсальные набор топологически робастных логических элементов

Вращение одного кубита:

Управляемое NOT:

Bonesteel, Hormozi, Simon, 2005, 2006

46 Брейд целевого кода для элемента CNOT с оптимизацией Соловея-Китаева

Брейд целевого кода для элемента CNOT с оптимизацией Соловея-Китаева

47 Задачи для исследования

Задачи для исследования

Больше кубитов Масштабируемые, устойчивые к ошибкам архитектуры Естественные языки программирования Больше алгоритмов!

48 Соавторы

Соавторы

Isaac Chuang MIT

Топологические квантовые компьютеры: Steve Simon Bell Labs now Oxford

Andrew Cross MIT now SAIC

Igor Markov U. Michigan

Krysta Svore Columbia now Microsoft Research

49 Компиляторы для квантовых компьютеров

Компиляторы для квантовых компьютеров

Спасибо за внимание!

Al Aho aho@cs.columbia.edu

KAUST 27 февраля 2011 г.

Перевел П. Новиков с разрешения автора

TexPoint fonts used in EMF. Read the TexPoint manual before you delete this box.: AAAA

«Компиляторы для квантовых компьютеров»
http://900igr.net/prezentacija/informatika/kompiljatory-dlja-kvantovykh-kompjuterov-70275.html
cсылка на страницу

Компьютер и здоровье

23 презентации о компьютере и здоровье
Урок

Информатика

130 тем
Слайды
900igr.net > Презентации по информатике > Компьютер и здоровье > Компиляторы для квантовых компьютеров