Автоматизированная генерация спецификаций квантовых цепей на основе полиномов Рида-Маллера

Виталий Калмычков
Доцент, СПбГЭТУ “ЛЭТИ”
SECR 2019

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

Transcript

1. Автоматизированная генерация спецификаций квантовых цепей на основе полиномов Рида-Маллера Калмычков В.А., Матвеева И.В. СПбГЭТУ «ЛЭТИ» 14-15 ноября, 2019. Санкт-Петербург
2. Квантовые компьютеры и вычисления: целевое назначение 2 Цели применения квантового компьютера:  решение вычислительных задач значительно быстрее компьютеров классической архитектуры (перебор/поиск, NP-задачи, многокритериальный выбор, оптимизация) – квантовое превосходство (quantum supremacy)1  «одновременная» обработка набора данных на основе классических алгоритмов  высокоскоростные эмуляторы физических и химических систем 1 23 октября 2019 : Arute, F., Arya, K., Babbush, R. et al. Quantum supremacy using a programmable superconducting processor. Nature 574, pages 505–510. https://www.nature.com/articles/s41586-019-1666-5 КВАНТОВАЯ ТЕХНОЛОГИЯ (пока дорогая и не всегда доступная) – В НАЛИЧИИ !! Учимся программировать ? Физически ? Можно какие-то этапы автоматизировать ? a: Компоновка процессора: прямоугольный массив из 54 кубитов (серый), каждый соединен с 4-мя ближайшими соседями (nearest neighbours) регулируемыми соединителями (синий). Выделено неработоспособное состояние кубита. b: Sycamore chip (Google AI Quantum)
3. Квантовые вычисления: математики, физики или специалисты ВТ? 3 1980: математик Юрий Манин – идея квантовых вычислений 1981: физик Ричард Фейнман – базовая модель квантового компьютера (моделирование эволюции квантовой системы) 1981: физик(специалист ВТ) Томмазо Тоффоли – преобразователь 1985: физик Дэвид Дойч – квантовая машина Тьюринга 1994: математик Питер Шор – квантовый алгоритм факторизации 1995: физик Д.П. Дивинченцо (исследователь, IBM) и др. – описание элементарных квантовых преобразователей (gates) 1996: математик Лов Гровер – квантовый алгоритм поиска в БД 1997: физик Алексей Китаев – принципы топологических квантовых вычислений 1997: Д.Кори, А.Фахми и Т.Хавел (Н.Гершенфельд и И.Чанг) – КК на эффекте объемного спинового резонанса или тепловых ансамблей (ЯМР) 1997: Д.П. Дивинченцо – КК с кубитами на собственном моменте импульса отдельных электронов, находящихся в квантовых точках 1998: демонстрация 2-х, 3-х кубитных КК на ЯМР (ЯМР-компьютер)
4. Квантовые компьютеры: препятствия при создании 4 2000: 5-ти кубитный ЯМР-компьютер (Мюнхен), 7-ми кубитный ЯМР- компьютер (Лос-Аламос) Основные задачи (проблемы): - обеспечение стабильного состояния на существенный временной промежуток (+ «температурное» влияние), - физические носители и процессы, - обнаружение и исправление квантовых ошибок при вычислениях, - обработка результатов (измерение), - воспроизводимость, - обеспечение существенного числа - кубитов (даже не сотни, а тысячи !).
5. Квантовые компьютеры: основные технологии 5 Технология Логический кубит Управление Твердотельные квантовые точки на полу- проводниках Зарядовые состояния (электрон) или направление электронного и/или ядерного спина в квантовой точке Внешние потенциалы или лазерный импульс Сверхпроводящие элементы Присутствие/отсутствие куперовской пары в определённой точке пространства Внешний потенциал, магнитный поток Атомы в оптических ловушках (ионы) Состояния внешнего электрона в ионе Лазерные импульсы вдоль оси ловушки или на ионы Дополнительно: приготовление запутанных состояний фотонов для управления атомными ансамблями, генерация квантовых состояний света
6. Общая схема организации вычислений с использованием квантового компьютера 6 M.A. Nielsen, and I.L. Chuang. Quantum Computation and Quantum Information, 2000. Cambridge Univ. Press, Cambridge, UK. 704 стр. Валиев К.А., Кокин А.А. Квантовые компьютеры. Надежды и реальность, 2001. Ижевск: НИЦ «Регулярная и хаотическая динамика». 352 стр.
7. Квантовая цепь – модель квантовых вычислений  Квантовые вычисления (quantum computing) – одно из перспективных направлений исследований в области компьютерных технологий.  В последней трети прошлого века работы Ландауэра и Беннетта стимулировали интерес мирового научного сообщества к обратимым вычислениям и, как следствие, проектированию квантовых цепей на основе реверсивных преобразователей.  Модель квантовой цепи – это способ представления спецификации для реализации квантовых вычислений на основе изменения состояний кубитов. Квантовая цепь представляет способ преобразований, которые позволяют перейти от входных состояний кубитов к выходным.  Проблема в том, что для каждой конкретной вычислительной задачи нужно использовать свой особенный квантовый алгоритм (квантовую цепь), поэтому разработка новых алгоритмов – не менее важная задача, чем разработка квантовых процессоров.  Проектирование и оптимизация квантовых цепей играет важную роль в разработке технологии квантовых вычислений. 7
8. Квантовый бит (кубит) – единичный вектор в двумерном комплексном векторном пространстве, для которого собственный базис фиксирован как {|0>,|1>}. Кубиты могут находиться в суперпозиции базовых состояний |0> и |1>: а|0> + b|1>, где амплитуды вероятности а и b комплексные числа, причем |а|2+ |b|2=1. |а|2 и |b|2 это оценка вероятности получить при измерении в качестве результата одно из состояний: или Квантовый регистр – набор кубитов. В основе двухкубитовой системы находится четырехкомпонентный базис: 8 0 1 0          1 0 1          Квантовая цепь: основные модельные представления
9. Квантовые преобразователи. При вычислениях квантовый регистр подвергается преобразованиям, переводящим регистр в новое состояние. Квантовое преобразование (оператор) над кубитами может быть представлено матрицей U. Квантовая механика требует, чтобы преобразование было унитарным, т.е. UUT=I. Квантовое вычисление представляет из себя выполнение над входным значением регистра | последовательности квантовых унитарных операторов U1 U2 …Um для получения конечного состояния U1 U2 …Um |. Квантовая операция над кубитом можно представлена как матрица 2 x 2. Пример унитарной матрицы преобразователей: Графическая спецификация NOT : Преобразователь NOT выполняет преобразование |0> в |1> и |1> в |0>. 9 Квантовая цепь: основные модельные представления
10. Квантовая цепь: преобразователи (gates), нотации 10
11. Квантовая цепь: преобразователи (gates), нотации 11
12. Преобразователи: инструкции физического уровня 12 Преобразователь Тоффоли: 2 управляющих кубита – слева целевой кубит – справа
13. Для графической спецификации цепи квантовых преобразователей используется нотация, предложенная Дойчем. Кубиты представляются как нити, на которые нанизаны преобразователи, действующие на соответствующие кубиты. Преобразователи представляются как квадратики или кружочки с соответствующими обозначениями. Время в цепи изменяется слева направо. Управляющие преобразователи представлены как кружок или квадратик на целевом кубите, вертикальная линия управления с символами «•» (управление 1-ей) и «o» (управление 0-м) на соответствующих управляющих кубитах. Пример произвольной квантовой цепи: U1 – произвольный n-кубитовый квантовый преобразователь U2 – управляющий трехкубитовый преобразователь U3 – однокубитовый преобразователь Слева представлен n-кубитовый квантовый регистр. 13 Квантовая цепь: графическая спецификация
14. Управляемые (условные) квантовые преобразователи CU введены как обобщенный тип преобразователей. Состоят из кубитов управления и целевого кубита. Матрица U воздействует на целевой кубит, если все кубиты управления принимают требуемое состояние (|0> или |1>). Действие универсального n-кубитового преобразователя с n-1 управляющими кубитами j1 , . . . , jn-1 и одним целевым кубитом j0 на векторах вычислительного базиса (квантового регистра): Самой известной разновидностью управляемого (контролируемого) преобразования является семейство преобразователей CkNOT, где k – целое число, определяющее количество управляющих узлов преобразователя. CkNOT(Z; t) – преобразователь, в котором целевой кубит t управляется набором кубитов Z. Пример справа представляет графическую нотацию для . 14   4 3 2 1 3 ; , , NOT C x x x x Квантовая цепь: основные модельные представления
15. Квантовые компьютеры: квантовое превосходство? 15  D-Wave Systems: 2007: 16 и 28 кубит, 2011: 128 кубит (D-Wave One) 2012: 512 кубит (Vesuvius ) 2015: более 1000 кубит 2017: 2000 кубит (D-Wave 2000Q) [кластеры по 8 кубит]  2017: Гарвардский университет и Массачусетский технологический институт – программируемый квантовый компьютер на базе 51 кубита  2017: Joint Quantum Institute and Joint Center for Quantum Information and Computer Science, University of Maryland – 53-кубитный квантовый симулятор  2018: МГУ, Внешэкономбанк, Фонд перспективных исследований, "ВЭБ-инновации" и АНО "Цифровая экономика" подписали соглашение о создании в России 50-кубитного квантового компьютера  2019: Alibaba Quantum Laboratory – Alibaba Cloud Quantum Development Kit  сентябрь 2019: Google-Sycamore chip (NASA),14-й от IBM на 53 кубита  октябрь 2019: система из 2-х кубитов, собранная учеными МИСиСа, успешно решила алгоритм Гровера (53% вероятность верного ответа)
16. Квантовые языки программирования 16  QCL, 1998 (Quantum Computation Language)  QDK (Microsoft Quantum Development Kit) Q# (2017)  ProjectQ (Python) (2017)
17. Квантовые языки программирования 17  IBM (2019): https://www.ibm.com/quantum-computing/
18. Квантовые языки программирования 18  Open Quantum Assembly Language (OpenQASM), IBM (2017) Пример (A.W. Cross, L.S. Bishop, J.A. Smolin, J.M. Gambetta):
19. Квантовые алгоритмы → квантовые компьютеры 19 Высокоуровневый поток проектирования для отображения квантового алгоритма в среду квантового компьютера: - квантовый алгоритм реализация - квантовый язык программирования (Q#, QCL, …) трансляция - квантовая компиляция (библиотеки, оптимизация, размещение набор инструментов, QASM, …) - целевая платформа (симулятор, квантовый компьютер)
20. 20 Основные особенности системы квантовой компиляции Наш набор приложений для логического уровня: осуществляется переход (компиляция) от математического описания к логическому уровню спецификаций квантовых цепей, после чего становится возможным адаптация к условиям физической реализации на основе реализации квантовых цепей в ЛБС-нотации1.  Автоматическая компиляция всех возможных вариантов квантовых цепей по полиномам Рида-Маллера.  Автоматические режимы:  перехода к линейно ближайшему соседу при минимизации числа преобразователей SWAP на основе масштабируемых шаблонов,  сбора статистики (с расчетом оценочных характеристик),  визуализации,  лексической проверки эквивалентности результатов компиляции квантовых цепей. 1ЛБС – линейно ближайшее соседство (LNN – Linear Nearest Neighbor) кубитов преобразователя – учет обеспечения ограничений на взаимодействие кубитов при физической реализации.
21. Квантовая компиляция – генерация для вычислительной задачи последовательности преобразователей. 21 Общая архитектура системы квантовой компиляции
22. FPRM-представление (поляризованные полиномы Рида-Маллера с фиксированной полярностью: fixed-polarity Reed-Muller expressions) булевых функций (n входов и 1 выход) – это «сложение по модулю 2» EXOR от AND минитермов, в которых каждая булева переменная представлена либо в прямой, либо в инверсной форме, но не в обеих. Набор всех булевых функций 3-х переменных (xk и bi  {0, 1}, 0  k < n, 0  i  2n–1, n = 3 и коэффициенты bi определяют представлен ли минитерм в выражении или нет) может быть представлен как:  На этапе синтеза строится поляризованный полином Рида-Маллера (нулевой полярности) и формируется набор поляризованных полиномов FPRM фиксированной полярности (от 1 до 2n – 1).  На основе полученных полиномов генерируются наборы квантовых цепей в нотации квантовых преобразователей. 22 Математический аппарат полиномов Рида-Маллера   0 1 2 7 1 2 6 0 2 5 2 4 0 1 3 1 2 0 1 0 2 1 0 , , x x x b x x b x x b x b x x b x b x b b x x x f         
23. 23 Многоуровневая спецификация квантовой цепи
24. Формирование по заданной таблице истинности для 3 переменных поляризованного полинома Рида–Маллера нулевой полярности и набора поляризованных полиномов FPRM (от 1 до 2n – 1). 24 Результат генерации полиномов Рида-Маллера
25. 25 Результат генерации спецификаций квантовых цепей Квантовые цепи согласно 8 полярностям FPRM представлены вместе с соответствующими им ЛБС-нотациями. Преобразователь SWAP выполняет обмен состояний кубитов:
26. 26 Результат генерации спецификаций квантовых цепей Квантовые цепи согласно 8 полярностям FPRM представлены вместе с соответствующими им ЛБС-нотациями.
27. 27 Статистика для эквивалентных квантовых цепей Критерии: количество квантовых преобразователей, глубина квантовой цепи при параллельной расстановке одновременно выполняющихся преобразователей (снижение временных затрат), квантовая стоимость для оценки предполагаемой сложности физической реализации преобразователя (принимаем КСNOT =КСCNOT =1, КСC k NOT =5k–1, КСSWAP =3)
28. 28 Симулятор квантовых цепей QUIRK (для 7 полярности)
29. 29 Симулятор квантовых цепей QUIRK (для 7 полярности)
30. 30 Лексическая верификация квантовых цепей Анализ преобразований над кубитами в скомпилированных квантовых цепях проводится нами на основе пространства лексем для символического вида коэффициентов кубитов в вычислительном базисе.
31. 31 Фрагмент статистики для FPRM 8 переменных
32. 32 Результат генерации спецификаций для 141 полярности
33. 33 Полезные сведения Обзор квантовых алгоритмов: Душкин Р.В. Квантовые вычисления и функциональное программирование, 2015. Москва: ДМК Пресс. 232 стр. Квантовые вычисления (Quantum computing) – видеокурс СПбГУ: https://www.coursera.org/learn/kvantovyye-vychisleniya Программа «Введение в квантовые вычисления», МГУ: https://openedu.ru/course/msu/QUANTUMCOMPUTING/ The Joint Center for Quantum Information and Computer Science (QuICS) – a partnership between the University of Maryland (UMD) and the National Institute of Standards and Technology (NIST): https://quics.umd.edu/ Росатом запускает масштабный проект по созданию отечественного квантового компьютера (07 Ноября, 2019 / 10:42) – бюджет более 20 млрд. руб.: - развитие различных платформ создания кубитов: сверхпроводников, холодных атомов и ионов, фотонов; - к 2024 г. планируется создать квантовые компьютеры с 50-100 кубитами. https://www.rosatom.ru/journalist/news/rosatom-zapuskaet-masshtabnyy- proekt-po-sozdaniyu-otechestvennogo-kvantovogo-kompyutera/
34. 34 К сведению ВАК, защиты [2012-2019]: 01.04.03 – Радиофизика: Моделирование работы квантового компьютера на квадрупольных ядрах (2013) ВАК – защиты, 2017: 01.04.02 - Теоретическая физика: Классические и квантовые модели суперсимметричной механики и частиц высших спинов 01.04.05 – Оптика: Трёхфотонное спонтанное параметрическое рассеяние света и квантовые логические операции в кольцевых микрорезонаторах 01.04.02 - Теоретическая физика: Роль энтропийной асимметрии в двусоставных квантовых состояний 01.01.03 - Математическая физика: Экстремумы целевых функционалов в задачах управления двухуровневыми квантовыми системами 05.27.01 - Твердотельная электроника, радиоэлектронные компоненты, микро- и наноэлектроника, приборы на квантовых эффектах: Разработка методов и алгоритмов высокоточной томографии квантовых состояний 01.04.05 – Оптика: Квантовая коммуникация на боковых частотах лазерного фазомодулированного излучения по атмосферному каналу связи
35. 35 К сведению ВАК – защиты, 2018: 01.04.02 - Теоретическая физика: Вероятностные, информационные и корреляционные характеристики квантовых систем 01.04.02 - Теоретическая физика: Топологическая фаза Паули и полуцелый орбитальный момент в двумерных квантовомеханических системах: циркулярных квантовых точках и графене с закритической кулоновской примесью 05.13.18 - Математическое моделирование, численные методы и комплексы программ: Модель квантовых графов с рёбрами меняющейся длины ВАК – защиты, 2019: 05.13.18 - Математическое моделирование, численные методы и комплексы программ: Метод конечных элементов для исследования квантовых систем нескольких частиц СПАСИБО !!!
36. 36 Калмычков Виталий Анатольевич СПбГЭТУ «ЛЭТИ», ФКТИ, каф. САПР vakalmychkov@etu.ru Матвеева Ирина Витальевна СПбГЭТУ «ЛЭТИ», ФКТИ, каф. САПР ir_mat@mail.ru https://etu.ru/ru/fakultety/fakultet-kompyuternyh-tehnologiy-i- informatiki/sostav-fakulteta/kafedra-sistem-avtomatizirovannogo- proektirovaniya/rukovodstvo-sostav-kafedry/professorsko- prepodavatelskiy-sostav1/matveeva-irina-vitalevna Контакты