Share
Embed
Автоматизированная генерация спецификаций квантовых цепей на основе полиномов Рида-Маллера
Виталий Калмычков
Доцент, СПбГЭТУ “ЛЭТИ”
SECR 2019
В докладе охарактеризовано современное положение в квантовых вычислениях, и возможно слушатели узнают новую информацию из перспективной области создания и программирования квантовых компьютеров. Будет представлен опыт разработки модульной системы автоматической генерации спецификаций квантовых цепей, используемых в качестве основы для логического представления квантового вычислительного процесса. В докладе рассматриваются предложенные способы по автоматической минимизации квантовых цепей на основе масштабируемых шаблонов, их оценки и верификации.
SECR 2019
November 15, 2019
Transcript
36 slides
-
Автоматизированная генерация спецификаций квантовых цепей на основе полиномов Рида-Маллера Калмычков
В.А., Матвеева И.В. СПбГЭТУ «ЛЭТИ» 14-15 ноября, 2019. Санкт-Петербург -
Квантовые компьютеры и вычисления: целевое назначение 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 1980: математик
Юрий Манин – идея квантовых вычислений 1981: физик Ричард Фейнман – базовая модель квантового компьютера (моделирование эволюции квантовой системы) 1981: физик(специалист ВТ) Томмазо Тоффоли – преобразователь 1985: физик Дэвид Дойч – квантовая машина Тьюринга 1994: математик Питер Шор – квантовый алгоритм факторизации 1995: физик Д.П. Дивинченцо (исследователь, IBM) и др. – описание элементарных квантовых преобразователей (gates) 1996: математик Лов Гровер – квантовый алгоритм поиска в БД 1997: физик Алексей Китаев – принципы топологических квантовых вычислений 1997: Д.Кори, А.Фахми и Т.Хавел (Н.Гершенфельд и И.Чанг) – КК на эффекте объемного спинового резонанса или тепловых ансамблей (ЯМР) 1997: Д.П. Дивинченцо – КК с кубитами на собственном моменте импульса отдельных электронов, находящихся в квантовых точках 1998: демонстрация 2-х, 3-х кубитных КК на ЯМР (ЯМР-компьютер) -
Квантовые компьютеры: препятствия при создании 4 2000: 5-ти кубитный ЯМР-компьютер
(Мюнхен), 7-ми кубитный ЯМР- компьютер (Лос-Аламос) Основные задачи (проблемы): - обеспечение стабильного состояния на существенный временной промежуток (+ «температурное» влияние), - физические носители и процессы, - обнаружение и исправление квантовых ошибок при вычислениях, - обработка результатов (измерение), - воспроизводимость, - обеспечение существенного числа - кубитов (даже не сотни, а тысячи !). -
Квантовые компьютеры: основные технологии 5 Технология Логический кубит Управление Твердотельные
квантовые точки на полу- проводниках Зарядовые состояния (электрон) или направление электронного и/или ядерного спина в квантовой точке Внешние потенциалы или лазерный импульс Сверхпроводящие элементы Присутствие/отсутствие куперовской пары в определённой точке пространства Внешний потенциал, магнитный поток Атомы в оптических ловушках (ионы) Состояния внешнего электрона в ионе Лазерные импульсы вдоль оси ловушки или на ионы Дополнительно: приготовление запутанных состояний фотонов для управления атомными ансамблями, генерация квантовых состояний света -
Общая схема организации вычислений с использованием квантового компьютера 6 M.A.
Nielsen, and I.L. Chuang. Quantum Computation and Quantum Information, 2000. Cambridge Univ. Press, Cambridge, UK. 704 стр. Валиев К.А., Кокин А.А. Квантовые компьютеры. Надежды и реальность, 2001. Ижевск: НИЦ «Регулярная и хаотическая динамика». 352 стр. -
Квантовая цепь – модель квантовых вычислений Квантовые вычисления (quantum
computing) – одно из перспективных направлений исследований в области компьютерных технологий. В последней трети прошлого века работы Ландауэра и Беннетта стимулировали интерес мирового научного сообщества к обратимым вычислениям и, как следствие, проектированию квантовых цепей на основе реверсивных преобразователей. Модель квантовой цепи – это способ представления спецификации для реализации квантовых вычислений на основе изменения состояний кубитов. Квантовая цепь представляет способ преобразований, которые позволяют перейти от входных состояний кубитов к выходным. Проблема в том, что для каждой конкретной вычислительной задачи нужно использовать свой особенный квантовый алгоритм (квантовую цепь), поэтому разработка новых алгоритмов – не менее важная задача, чем разработка квантовых процессоров. Проектирование и оптимизация квантовых цепей играет важную роль в разработке технологии квантовых вычислений. 7 -
Квантовый бит (кубит) – единичный вектор в двумерном комплексном векторном
пространстве, для которого собственный базис фиксирован как {|0>,|1>}. Кубиты могут находиться в суперпозиции базовых состояний |0> и |1>: а|0> + b|1>, где амплитуды вероятности а и b комплексные числа, причем |а|2+ |b|2=1. |а|2 и |b|2 это оценка вероятности получить при измерении в качестве результата одно из состояний: или Квантовый регистр – набор кубитов. В основе двухкубитовой системы находится четырехкомпонентный базис: 8 0 1 0 1 0 1 Квантовая цепь: основные модельные представления -
Квантовые преобразователи. При вычислениях квантовый регистр подвергается преобразованиям, переводящим регистр
в новое состояние. Квантовое преобразование (оператор) над кубитами может быть представлено матрицей U. Квантовая механика требует, чтобы преобразование было унитарным, т.е. UUT=I. Квантовое вычисление представляет из себя выполнение над входным значением регистра | последовательности квантовых унитарных операторов U1 U2 …Um для получения конечного состояния U1 U2 …Um |. Квантовая операция над кубитом можно представлена как матрица 2 x 2. Пример унитарной матрицы преобразователей: Графическая спецификация NOT : Преобразователь NOT выполняет преобразование |0> в |1> и |1> в |0>. 9 Квантовая цепь: основные модельные представления -
Преобразователи: инструкции физического уровня 12 Преобразователь Тоффоли: 2 управляющих кубита
– слева целевой кубит – справа -
Для графической спецификации цепи квантовых преобразователей используется нотация, предложенная Дойчем.
Кубиты представляются как нити, на которые нанизаны преобразователи, действующие на соответствующие кубиты. Преобразователи представляются как квадратики или кружочки с соответствующими обозначениями. Время в цепи изменяется слева направо. Управляющие преобразователи представлены как кружок или квадратик на целевом кубите, вертикальная линия управления с символами «•» (управление 1-ей) и «o» (управление 0-м) на соответствующих управляющих кубитах. Пример произвольной квантовой цепи: U1 – произвольный n-кубитовый квантовый преобразователь U2 – управляющий трехкубитовый преобразователь U3 – однокубитовый преобразователь Слева представлен n-кубитовый квантовый регистр. 13 Квантовая цепь: графическая спецификация -
Управляемые (условные) квантовые преобразователи 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 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 QCL, 1998 (Quantum Computation Language)
QDK (Microsoft Quantum Development Kit) Q# (2017) ProjectQ (Python) (2017) -
Квантовые языки программирования 18 Open Quantum Assembly Language (OpenQASM),
IBM (2017) Пример (A.W. Cross, L.S. Bishop, J.A. Smolin, J.M. Gambetta): -
Квантовые алгоритмы → квантовые компьютеры 19 Высокоуровневый поток проектирования для
отображения квантового алгоритма в среду квантового компьютера: - квантовый алгоритм реализация - квантовый язык программирования (Q#, QCL, …) трансляция - квантовая компиляция (библиотеки, оптимизация, размещение набор инструментов, QASM, …) - целевая платформа (симулятор, квантовый компьютер) -
20 Основные особенности системы квантовой компиляции Наш набор приложений для
логического уровня: осуществляется переход (компиляция) от математического описания к логическому уровню спецификаций квантовых цепей, после чего становится возможным адаптация к условиям физической реализации на основе реализации квантовых цепей в ЛБС-нотации1. Автоматическая компиляция всех возможных вариантов квантовых цепей по полиномам Рида-Маллера. Автоматические режимы: перехода к линейно ближайшему соседу при минимизации числа преобразователей SWAP на основе масштабируемых шаблонов, сбора статистики (с расчетом оценочных характеристик), визуализации, лексической проверки эквивалентности результатов компиляции квантовых цепей. 1ЛБС – линейно ближайшее соседство (LNN – Linear Nearest Neighbor) кубитов преобразователя – учет обеспечения ограничений на взаимодействие кубитов при физической реализации. -
Квантовая компиляция – генерация для вычислительной задачи последовательности преобразователей. 21
Общая архитектура системы квантовой компиляции -
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 -
Формирование по заданной таблице истинности для 3 переменных поляризованного полинома
Рида–Маллера нулевой полярности и набора поляризованных полиномов FPRM (от 1 до 2n – 1). 24 Результат генерации полиномов Рида-Маллера -
25 Результат генерации спецификаций квантовых цепей Квантовые цепи согласно 8
полярностям FPRM представлены вместе с соответствующими им ЛБС-нотациями. Преобразователь SWAP выполняет обмен состояний кубитов: -
26 Результат генерации спецификаций квантовых цепей Квантовые цепи согласно 8
полярностям FPRM представлены вместе с соответствующими им ЛБС-нотациями. -
27 Статистика для эквивалентных квантовых цепей Критерии: количество квантовых преобразователей,
глубина квантовой цепи при параллельной расстановке одновременно выполняющихся преобразователей (снижение временных затрат), квантовая стоимость для оценки предполагаемой сложности физической реализации преобразователя (принимаем КСNOT =КСCNOT =1, КСC k NOT =5k–1, КСSWAP =3) -
30 Лексическая верификация квантовых цепей Анализ преобразований над кубитами в
скомпилированных квантовых цепях проводится нами на основе пространства лексем для символического вида коэффициентов кубитов в вычислительном базисе. -
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 К сведению ВАК, защиты [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 К сведению ВАК – защиты, 2018: 01.04.02 - Теоретическая
физика: Вероятностные, информационные и корреляционные характеристики квантовых систем 01.04.02 - Теоретическая физика: Топологическая фаза Паули и полуцелый орбитальный момент в двумерных квантовомеханических системах: циркулярных квантовых точках и графене с закритической кулоновской примесью 05.13.18 - Математическое моделирование, численные методы и комплексы программ: Модель квантовых графов с рёбрами меняющейся длины ВАК – защиты, 2019: 05.13.18 - Математическое моделирование, численные методы и комплексы программ: Метод конечных элементов для исследования квантовых систем нескольких частиц СПАСИБО !!! -
36 Калмычков Виталий Анатольевич СПбГЭТУ «ЛЭТИ», ФКТИ, каф. САПР [email protected]
Матвеева Ирина Витальевна СПбГЭТУ «ЛЭТИ», ФКТИ, каф. САПР [email protected] 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 Контакты