1 of 36

Квантовите алгоритми, както никой не ги представя

Десислав Андреев

#TAC Sofia, 2021

2 of 36

Какво толкова и защо ни пука?

Един камък – много зайци
Паметта (ми) не стига
Location, location, location…
След рекламите става по-интересно
Да научим децата на нещо

д-р инж. Д. Андреев

#TAC Sofia, 2021

3 of 36

Колко не знаем и как да разберем?

д-р инж. Д. Андреев

#TAC Sofia, 2021

4 of 36

А какво бяха компютрите?

д-р инж. Д. Андреев

#TAC Sofia, 2021

5 of 36

Колко не знаем и как да разберем?

д-р инж. Д. Андреев

#TAC Sofia, 2021

6 of 36

Първи и последни понятия

Кюбит и квантов регистър

д-р инж. Д. Андреев

#TAC Sofia, 2021

7 of 36

Първи и последни понятия

Кюбит и квантов регистър

д-р инж. Д. Андреев

#TAC Sofia, 2021

8 of 36

Първи и последни понятия

Кюбит и квантов регистър

https://qiskit.org/textbook/ch-states/representing-qubit-states.html

д-р инж. Д. Андреев

#TAC Sofia, 2021

9 of 36

ЦСхТ за неопитни

Гейт на Адамар – винаги трябва да инициализираме

Гейт на Паули по Х – квантова логическа инверсия

CNOT – гейт – два бита, като инвертирането настъпва, когато контролиращият бит е в 1

д-р инж. Д. Андреев

#TAC Sofia, 2021

10 of 36

ЦСхТ за опитни

Гейт на Тофоли – контролиран-контролиран-NOT

swap-гейт

CSWAP – или гейт на Фредкин – теоретично всяка логическа или аритметична операция може да се реализира с него

д-р инж. Д. Андреев

#TAC Sofia, 2021

11 of 36

Колко не знаем?

д-р инж. Д. Андреев

#TAC Sofia, 2021

12 of 36

Какво не знаем?

д-р инж. Д. Андреев

#TAC Sofia, 2021

13 of 36

Какво не знаем?

д-р инж. Д. Андреев

https://github.com/dandree2/Quantum-Computing/blob/main/Index.md

#TAC Sofia, 2021

14 of 36

No Cloning Theorem

Можем ли да подслушваме? Ако пресечем q0 и q1, тогава "да" - man in the middle.
Двата кюбита минават по различни трасета, т.е. вероятно е да се подслушва само един.

д-р инж. Д. Андреев

#TAC Sofia, 2021

15 of 36

No Cloning Theorem

Който и кюбит да бъде прочетен, ще се развали суперпозицията.
Копираме състоянието на q1 в q2. Добавянето на CX-гейт може да доведе до фазов откат, т.е. суперпозицията е нарушена.
Съобщението е разрушено и за получателя, и за man-in-the-middle.
Математически не можем да клонираме кюбити, освен ако вече не знаем състоянието им.

д-р инж. Д. Андреев

#TAC Sofia, 2021

16 of 36

Квантови логически схеми

Измерване на разстояние
Алгоритъм на Гроувър
Квантово минимизиране - QMA

д-р инж. Д. Андреев

#TAC Sofia, 2021

17 of 36

Квантови логически схеми

д-р инж. Д. Андреев

#TAC Sofia, 2021

18 of 36

Квантови логически схеми

д-р инж. Д. Андреев

#TAC Sofia, 2021

Повече тук

19 of 36

Квантови логически схеми

Алгоритъм на Гроувър

Пример с булева алгебра
Пример – 3SAT – Conjunctive Normal Form – getting NP-complete

д-р инж. Д. Андреев

#TAC Sofia, 2021

20 of 36

Квантови логически схеми

Алгоритъм на Гроувър

Пример с булева алгебра
Пример – 3SAT – Conjunctive Normal Form – getting NP-complete

д-р инж. Д. Андреев

#TAC Sofia, 2021

21 of 36

Последователност на операциите при на алгоритъм за машинно обучение

д-р инж. Д. Андреев

#TAC Sofia, 2021

22 of 36

Как да подходим?

д-р инж. Д. Андреев

#TAC Sofia, 2021

23 of 36

Квантова система за препоръки

ORB дескриптори
Swap-тест и измерване на разстояние
Разстояние спрямо Жакард-Нийдхам
Мажоритарен избор

д-р инж. Д. Андреев

#TAC Sofia, 2021

24 of 36

Квантова система за препоръки

ORB дескриптори
Swap-тест и измерване на разстояние
Дистанция на Жакард-Нийдхам
Мажоритарен избор

д-р инж. Д. Андреев

#TAC Sofia, 2021

25 of 36

Квантова система за препоръки

д-р инж. Д. Андреев

#TAC Sofia, 2021

26 of 36

IBM Quantum Composer

И още…

д-р инж. Д. Андреев

#TAC Sofia, 2021

27 of 36

Реална задача – k-means

Задача: Намиране на клъстери в множество от данни, като намираме/предполагаме идеален брой K центроиди. Всяка точка от данните притежава етикет - кореспондиращ клъстър.

Сложност: K x N

Търси се: За всеки етикет към всеки вектор от данни намираме най-близкият центроид

Обновяваме всеки центроид, на база средно-статистическата стойност на данните във всеки клъстър.

д-р инж. Д. Андреев

#TAC Sofia, 2021

28 of 36

Реална задача – k-means (квантово)

Всички вектори в множеството данни са инициализирани в суперпозиция
Изчисляваме всички дистанции на данните до K-центроидите
Всички вектори от данни получават етикети спрямо най-близкия им центроид
Записваме това в квантово състояние - също е било в суперпозиция
На случаен принцип можем да видим само един етикет - останалата информация е в суперпозиция за всички вектори с този етикет
Чрез квантови изчисления можем да получим квантовото състояние, описващо нов центроид
Измерваме класически и получаваме класическа репрезентация на новия центроид
Изпълняваме тези стъпки за K нови центроида

N-вектора са винаги в суперпозиция, така че времето за изпълнение е log(N), но зависимостта от K и D остава като при класическия вариант, т.е. O(N)

д-р инж. Д. Андреев

#TAC Sofia, 2021

29 of 36

Реална задача – k-means (квантово)

д-р инж. Д. Андреев

#TAC Sofia, 2021

30 of 36

Квантови невронни мрежи – QNN

Средства на квантовата механика	Невронни мрежи
Вълнова функция	Неврони
Суперпозиция (кохерентност)	Взаимовръзки или тежести
Измерване (декохерентност)	Еволюция към привличащия (атрактор)
Сплитане	Обучаващо правило
Унитарна трансформация	Усилваща функция

д-р инж. Д. Андреев

#TAC Sofia, 2021

31 of 36

Квантови невронни мрежи – QNN

Квантова телепортация? Сплитане?

д-р инж. Д. Андреев

#TAC Sofia, 2021

32 of 36

Квантови невронни мрежи – QNN

Квантови канали?

д-р инж. Д. Андреев

#TAC Sofia, 2021

33 of 36

Изводи

Още ни е рано, но не пречи да се трудим
Тук дизайнът предхожда коденето
Test-driven development не е изгоден понякога
Очакваме някога General Purpose QPC

д-р инж. Д. Андреев

#TAC Sofia, 2021

34 of 36

Благодаря ви за вниманието!

д-р инж. Десислав Андреев

#TAC Sofia, 2021

35 of 36

Въпроси?

д-р инж. Д. Андреев

#TAC Sofia, 2021

36 of 36

Бонус материали

д-р инж. Д. Андреев

#TAC Sofia, 2021