Лингвистическое и программное обеспечение автоматизированного проектирования устройств, функционирующих на волновых и квантовых принципах

Матвеева, Ирина Витальевна

Системы автоматизации проектирования (по отраслям)

автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Лингвистическое и программное обеспечение автоматизированного проектирования устройств, функционирующих на волновых и квантовых принципах

кандидата технических наук: Матвеева, Ирина Витальевна
город: Санкт-Петербург
год: 2011
специальность ВАК РФ: 05.13.12
цена: 450 рублей

Диссертация по информатике, вычислительной технике и управлению на тему «Лингвистическое и программное обеспечение автоматизированного проектирования устройств, функционирующих на волновых и квантовых принципах»

Автореферат диссертации по теме "Лингвистическое и программное обеспечение автоматизированного проектирования устройств, функционирующих на волновых и квантовых принципах"

005005037

На правах рукописи

^/У

Матвеева Ирина Витальевна

ЛИНГВИСТИЧЕСКОЕ И ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ АВТОМАТИЗИРОВАННОГО ПРОЕКТИРОВАНИЯ УСТРОЙСТВ ФУНКЦИОНИРУЮЩИХ НА ВОЛНОВЫХ И КВАНТОВЫХ ПРИНЦИПАХ

Специальность: 05.13.12 - Системы автоматизации проектирования (промышленность)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

- 8 ДЕК 2011

Санкт-Петербург - 2011

005005037

Работа выполнена в Санкт-Петербургском государственном электротехническом университете "ЛЭТИ" им. В.И. Ульянова (Ленина)

Научный руководитель -

доктор технических наук, профессор Герасимов Игорь Владимирович Официальные оппоненты:

доктор технических наук, профессор, заведующий кафедрой Информатики и прикладной математики Санкт-Петербургского национального исследовательского университета информационных технологий, механики и оптики Немолочнов Олег Фомич

кандидат технических наук, доцент кафедры «Подъемно-транспортные, путевые и строительные машины» Петербургского государственного университета путей сообщения

Быков Владислав Павлович

Ведущая организация - Санкт-Петербургский государственный университет аэрокосмического приборостроения (ГУАП)

Защита диссертации состоится ¿ 11 г. в ^ часов

на заседании совета по защите докторских и кандидатских диссертаций Д 212.238.02 Санкт-Петербургского государственного электротехнического университета "ЛЭТИ" им. В.И. Ульянова (Ленина) по адресу: 197376, г. Санкт-Петербург, ул. Проф. Попова, д. 5.

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан « /^С " 011 г.

Ученый секретарь совета

по защите докторских

и кандидатских диссертаций Д.212.238.02

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность исследования. В основу современных компьютерных технологий положены достижения не только в базовых областях - электротехника и информатика но и исследования и разработки из принципиально новых разделов науки - квантовая физика, нанотехнологии, биомсдицинское проектирование и т.д.

Проблематика организации волновых вычислений в системах малой размерности (квантовых) является составной частью фундаментальных исследований в рамках Приоритетных направлений развития науки, технологий и техники в Российской Федерации' - «Индустрия наносистем» и критических технологий федерального уровня - «Нано-, био-, информационные, когнитивные технологии».

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

Современные квантовые технологии ведут к полностью новым проблемам для разработчиков САПР, которые должны быть решены при создании практического квантового устройства, в частности:

• разработка среды проектирования квантовых устройств в настоящее время является трудной задачей в первую очередь из-за сложности описаний объектов на языке квантовой теории, а также ввиду ограниченного числа известных квантовых алгоритмов,

• точный состав модулей среды проектирования квантовых устройств не определен,

• модель программирования также является неопределенной, поскольку существуют разные предложения организации квантового компьютера, например как приложение или процессор общего назначения,

• разработка практических алгоритмов синтеза для квантовой цепи является чрезвычайно сложной из-за быстрого роста размеров данных и отсутствия стандартных методов синтеза, а так же инструментов их поддерживающих,

• так же не решен вопрос масштабируемости квантовых вычислений.

На сегодняшний день не существует инструментов, позволяющих проектировать масштабируемые квантовые цепи с учетом ограничений физической реализуемости - в ЛБС2-нотации.

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

1 Указ Президента РФ от 07.07.2011 N 899

ЛЕС - линейно ближайшее соседство кубитов преобразователя, ограничение взаимодействия кубитов

рает синтез квантовых цепей.

Адекватно решить многоплановую задачу построения устройств, работающих на квантовых принципах, в будущем можно будет на основе создания интегрированной системы автоматизированного проектирования У1-среды3 САПР квантовых устройств. В настоящее время алгоритмы выполнения отдельных этапов проектирования квантовых цепей уже достаточно хорошо формализованы, поэтому в рамках восходящего подхода к проектированию актуальной является разработка У1-среды проектных решений для квантовых цепей, исследованию и разработке подсистем которой и посвящена настоящая диссертация.

Диссертационная работа выполнена в рамках научных исследований У1-сред САПР в соответствии с планами факультета компьютерных технологий и информатики (ФКТИ) по реализации инновационной научно-образовательной программы «Информатика, управление и компьютерные технологии»: раздел 3 «Обработка информации в наноси-стемах» (проект «Разработка информационного базиса для элементов квантового компьютинга»).

Цели и задачи исследования

Цель работы - Автоматизация проектирования многоуровневых спецификаций квантовых цепей и верификация их реализаций в рамках подсистемы У1-среды САПР устройств, функционирующих на волновых и квантовых принципах. Достижение поставленной цели позволит повысить степень успешности разработок большого класса квантовых устройств в VI-среде САПР за счет выгод от использования формальных языков проектных спецификаций на концептуальном уровне проектирования.

Для достижения поставленной цели необходимо решить следующие задачи:

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

2. Разработка программного обеспечения, алгоритмов и методик компиляции, минимизации, анализа и имитационного моделирования квантовых цепей с учетом ограничений физической реализуемости (в ЛБС-нотации).

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

4. Исследование интероперабельности комплекса разработанных программных модулей с существующими программными средами симуляции квантовых вычислений.

Основные методы исследования

Для решения поставленных задач в диссертационной работе используются методы математического аппарата квантовой физики, алгебры полиномов Рида-Маллера (ПРМ), теории клеточных автоматов, линейной алгебры, положения теории построения САПР, методы объектно-ориентированного проектирования и программирования.

3 VI - УЫиа! Ь^гитеШаИоп

Достоверность научных результатов

Подтверждается корректностью использования математического аппарата, теории клеточных автоматов, алгебры полиномов Рида-Маллера, теории обработки сигнадов, линейной алгебры, методов объектно-ориентированного проектирования и профаммирова-ния, а так же результатами тестирования в среде реконфигурируемого модульного клеточного автомата и совместимости с внешними средами проектирования (симуляторами) на уровне формата описания - обмен проектными данными в формате STEP (язык описания-XML).

Новые научные результаты

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

1. Разработана новая архитектура подсистемы VI-среды САПР проектных решений для квантовых цепей, основанная на новой методике проектирования многоуровневой спецификации для класса CNOT масштабируемых квантовых логических цепей с учетом ограничений физической реализуемости.

2. Предложены новые алгоритмы проектирования (формирования) многоуровневых спецификаций CNOT и SCNOT классов квантовых логических цепей: алгоритм генерации мастабированной квантовой цепи на основе алгебры полиномов Рида-Маллера; алгоритм преобразования к ЛБС-потации квантовых логических целей и алгоритм лексического анализа для проверки корректности выполнения трассировки квантовых цепей.

3. Предложен усовершенствованный алгоритм рекурсивно-лексического обобщения унифицированного квантового Фурье-преобразования на основе новой схемы перестановки коэффициентов с использованием преобразователей CNOT, а также единая спецификация для квантового унифицированного управляемого Фурье-преобразователя.

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

5. Впервые предложен реконфигурируемый кластерный клеточный автомат (РККА) для имитационного моделирования проектных решений.

Научные положения, выносимые на защиту

1. Адаптация математического аппарата полиномов Рида-Маллера к проблематике описания квантовых цепей, позволяющая автоматизировать процесс проектирования и масштабирования квантовых цепей.

2. Методики и алгоритмы формирования многоуровневых спецификаций квантовых цепей на различных этапах проектирования.

3. Методика автоматизированной многопроходной минимизации квантовой цепи в ЛБС-нотации с применением предложенных шаблонов.

4. Архитектура LNNQCAD - подсистемы VI-среды САПР проектных решений для квантовых цепей.

Практическая ценность

Значение результатов диссертационной работы для практического применения заключается в программной реализации модульной архитектуры подсистемы LNNQCAD, которая позволяет повысить степень успешности разработок квантовых устройств в нотации квантовых цепей в VI-среде САПР за счет выгод от использования формальных языков проектных спецификаций на концептуальном уровне проектирования:

1. Проектировщику предоставляется многоуровневая спецификация квантовой цепи -комплект документации, включающий математическое описание, статистическое описание (СО), ПРМ, ЛБС и минимизированную ЛЕС (МЛБС) спецификации на выбранную квантовую цепь (набор цепей) и имитационную модель (РККА).

2. Подсистема LNNQCAD может быть использована совместно с внешними симулято-рами квантовых вычислений за счет обеспечения интероперабельности комплекса разработанных программных модулей для тестирования и минимизации как новых, так и разработанных в других средах квантовых цепей.

Практическая реализация и внедрение результатов работы

Разработанный в ходе исследования набор модулей подсистемы VI-среды САПР LNNQCAD был реализован в среде разработки ПО Visual Studio, предлагающей объектно-ориентированную модель программирования. Практическим результатом работы является подсистема САПР квантовых цепей LNNQCAD, обеспечивающая проектирование и моделирование С"NOT и SCNOT классов квантовых цепей в ЛБС-нотации и формирующая многоуровневую спецификацию квантовой цепи.

Результаты диссертационной работы использовались:

Применение разработанной подсистемы LNNQCAD в учебном процессе обеспечивает поддержку дисциплины «Моделирование и анализ инженерных данных» учебного плана подготовки магистров по направлению «Информатика и вычислительная техника».

Материалы диссертационной работы использовались в 2010 г. в проекте «Разработка и реализация сетевой распределенной системы масштабной подготовки магистров и аспирантов, на основе интеграции образовательного процесса с научной и проектной деятельностью, с использованием ресурсов вузов, внедряющих инновационные образовательные программы» (Государственный контракт N° П707 от 10 октября 2008 г.) при апробации совместно с ВятГУ (г. Киров) сетевых магистерских образовательных программ по направлению «Информатика и вычислительная техника».

По заявленной тематике автор является победителем конкурса научных достижений студентов и аспирантов СПбГЭТУ 2003 г., конкурса проектов аспирантов и докторантов по разделу III Темплана СПбГЭТУ на 2003-2004 г.г. по теме «Реверсивная логика в пространстве волновых функций».

Апробация работы

вые математические методы и компьютерные технологии в проектировании, производстве и научных исследованиях» - Гомель, ГГУ, Белоруссия, 2004 г.; ПЭБЧ'07 - 5-ая международная конференция "Приборостроение в экологии и безопасности человека" - СПб., ГУАП, 31.01 - 02.02 2007 г.; Всероссийская научно-техническая конференция «Наука-Производство-Технологии-Экология» - Киров, ВятГУ, 21.04 - 26.04 2005 г.; 7-ая Международная научно-практическая конференция «Образовательные, научные и инженерные приложения в среде LabView и технологии National Instruments - 2008», Москва, РУДН, 28.11-29.11 2008 г.; Всероссийская научно-техническая конференция "Общество-Наука-Инновации" - Киров, ВятГУ, 18.04 - 29.04 2010 г.; Конференции профессорско-преподавательского состава СПбГЭТУ, Санкт-Петербургский государственный электротехнический университет 2003,2004, 2006, 2007, 2011 г.

Публикации

Основные теоретические и практические результаты диссертации опубликованы в 15 статьях и докладах, среди которых 5 публикаций в ведущих рецензируемых изданиях, рекомендованных в действующем перечне ВАК, 5 публикаций в других журналах. Доклады доложены и получили одобрение на 5 международных и всероссийских научно-практических конференциях перечисленных в конце автореферата.

Структура и объем диссертации

Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы, включающего 141 наименований, 4-х приложений. Работа изложена на 143 страницах, содержит 77 рисунков и 17 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Квантовый бит (кубит) - единичный вектор в двумерном комплексном векторном пространстве, его собственный базис, определенный как {|0),|l)} фиксирован, где

I')= 1 • Кубиты могут находиться в суперпозиции

|0) и |l), такой как a|o) + 6|l), где а и Ъ комплексные числа, и \а\ +|6|2=1. Квантовый регистр - набор кубитов. В процессе вычислений регистр находится в состоянии суперпозиции.

|Ц1> —

1ч2> —

1чз>

!qp-> —

-ш

. . _—¿1—

Квантовый преобразователь (оператор) V над и-кубитовым РисЛ. Пример произ-регистром представляется унитарной матрицей 2"х2". вольной квантовой цепи.

Квантовая цепь - это способ представления функциональных спецификации для реализации квантовых вычислений на основе изменения состояний регистра. При проектировании квантовой цепи осуществляется подбор конкретной композиции матриц преобразований, воздействующих на отдельные кубиты или их совокупность. Для графического представления квантовой цепи общепринята нотация Дойча. В этой нотации кубиты представляются как нити, на которые «нанизаны» преобразователи, воздействующие на них. Преобразователи представляются как квадратики или кружочки с соответствующими обозначениями. Управляющие преобразователи представлены как кружок или квадратик на целевом кубите и вертикальная линия управления с символами «•» (управление 1-ей) и «°» (управление 0-м) на управляющих кубитах. Время в цепи изменяется слева направо. Пример произвольной квантовой цепи приведен на рис. 1. Здесь U\ - некий произвольный и-кубитовый квантовый преобразователь, U2 - управляющий трехку-битовый преобразователь и U} - однокубитовый преобразователь. Слева представлен п-кубитовый квантовый регистр.

На основе проведенного анализа и с учетом ограничений, вносимых существующими нанотехнологиями реализации квантовых цепей, главное из которых линейно-ближайшее соседство (ЛБС) кубитов преобразователя, сформулированы требования к разрабатываемой подсистеме VI-среды САПР:

1. Подсистема САПР должна иметь программные средства генерации масштабированных спецификаций квантовых вычислений в нотации квантовых цепей.

2. Подсистема САПР должна включать программные средства для преобразования спецификации квантовой цепи к ЛБС-нотации, а так же для минимизации квантовых цепей в ЛБС-нотации для задач квантовых вычислений.

3. Подсистема должна обрабатывать результаты генерации и позволять получать статистические характеристики библиотеки квантовых цепей для выбора минимальной цепи по различным критериям.

4. Подсистема САПР должна позволять выполнить проверку корректности и имитационное моделирование как разработанных, так и существующих квантовых цепей.

5. Подсистема САПР должна интегрироваться с другими системами моделирования (симуляции) квантовых цепей.

Во второй главе рассматриваются принципы построения и архитектурные решения подсистемы САПР для проектирования квантовых цепей. Дано краткое введение в основные положения квантовой теории, определены различные классы квантовых преобразователей и способы их описания (табл. 1). Типичное квантовое вычисление представляет собой выполнение над входным значением регистра |ф) последовательности квантовых унитарных операторов U,U2...U„ для получения конечного состояния U]U2...Um\(p). Управляемые преобразователи CmU, где т - число кубитов управления, состоят из кубитов управления и целевого кубита, могут быть поняты как обобщенный тип преобразователей, где для однокубитовых преобразователей т=0. Матрица V воздействует на целевой кубит, если все кубиты управления принимают требуемое состояние (|0> или |1>). Определен класс квантовых цепей CNOT. Рассмотрены библиотеки квантовых преобразователей С NOT и SCNOT.

Рассмотрены различные методы построения модели квантовой цепи на классическом компьютере. Типичные методы проектирования квантовой цепи основаны на декомпозиции матрицы унитарного оператора - квантовой компиляции. Упрощенная схема построения цепи:

Унита рный опера торК

Декомпозиц ия матрицы Ub

промежуточ ную цепь

Проме ; жуточ |—N ноя цепь L-^y-

Построение цепи элементарных лреобразовате лей

Цепь ! элемен

уIпреобра ^ зовате I лей

Квантовое устройство

симулятор

Ч ___Компилятор квантовой^цепи __ у

Квантовый компилятор преобразует унитарный оператор в массив элементарных квантовых преобразователей аналогично классическим компиляторам. Плюс этого метода - могут быть созданы любые классы квантовых цепей. Основной недостаток - ограниченная масштабируемость при реализации на классическом компьютере, поскольку требуется выразить матрицу унитарного оператора явно, что ведет к экспоненциальному росту ресурсов (времени и памяти).

Таблица 1

Таблица истинности для преобразовате ля Фейнмана:

к) /сют

|00) и

|01> |01)

и И

И И

Таблица истинности для преобразователя SWAP-.

1^) Sswap

И И

|0.) |10>

и И

1») 1»)

Преобразователь

ЫОТ

CNOT (Фейнмана)

С'NOT (Тоффоли)

SWAP

CSWAP (Фредкина)

Матричная спецификация квантового преобразователя

Графическая спецификация с учетом поведения преобразователя

1 О О 1

о о о о

0 1

1 о

0 0 0 0 0 0 0

о о о о

0 1 0 0 0 0 0 10 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 о о о

0 0 0 0 0 0 0 0 0

1 о о о

О 1

1 о

О 1

о о

0 0 0

0 1 о

1 о о О о 1

|Xo>-t-|Xo> |»1>-ф-|Х1>ф|Хо>

|хо>.

|Х3>.

-|х0>

• |Х2>$ Но>|Х1>

1Х0>Л^|Х1>

|«1>-Х-|хо>

|"а>12У|Х1>

В последнее время сформировался другой подход к моделированию квантовой цепи на классическом компьютере, предложенный в 2002 году К. 1\л'ата, У. КатЬауазЫ и Б. УатаБЬйа, который и рассматривается в диссертации. Он основан на следующем наблюдения: квантовая цепь для стандартной квантовой задачи существенно отличается в той части цепи, которая вычисляет логические функции в зависимости от функциональной спецификации экземпляра данной задачи (например, в случае поиска Гровера).

Например, для цепи:

можно выразить состояние третьего кубита |х3) в виде \х3 ® f(xx,x2)),

где f(xhx2) -хух2 -х2 ■ Таким образом, эта цепь может быть использована (как часть квантового алгоритма) для вычисления логической функции /. Данный метод позволяет выполнять масштабирование при моделировании на классических компьютерах. Некоторое ограничение метода - применимость к классу CNOT квантовых цепей.

В главе рассмотрено ПРМ4-представление логических функций - «сложение по модулю 2» EXOR от AND минитермов, в которых каждая логическая переменная либо в прямой, либо в инверсной форме, но не в обеих. Например, набор всех логических функций 3-х переменных хк и Ь, е{0, 1}, 0 < к< п, 0 < / < 2"-1, п = 3 (коэффициенты Ъ, определяют наличие минитерма в выражении) может быть представлен как-

/(*0 >ХЬХ2) ~ bo®b]XQ ®bjX\ ®b3xix0®b4x2®bsx2XQ®b6X2Xi ®Ьух2Х]Х0

Для логической функции н переменных, чтобы сохранить результат в конце вычисления, генерируется квантовая цепь (и + 1)х(л + 1) с вспомогательным результирующим кубитом, инициализированным в ноль. Первоначально строится ПРМ (полином 0 полярности) и формируется набор ФПРМ полиномов (от 1 до 2й- 1). На основе полиномов генерируются наборы квантовых схем в нотации квантовых преобразователей. В диссертации описаны процедуры генерации ФПРМ и СПРМ.

В главе также представлена архитектура подсистемы VI-среды САПР LNNQCAD (рис.2), включающая модули инструментов автоматизированного проектирования, охватывающие основные задачи синтеза, мини____мизации, анализа и моделирова-

Рис.2. Архитектура LNNQCAD ния квантовой цепи.

Третья глава посвящена вопросам лингвистического обеспечения подсистемы LNNQCAD и методикам формирования многоуровневых спецификаций.

Рассматривается алгоритм лексического анализа квантовых преобразований, на котором основан лексический анализатор (ЛАПР), позволяющий выполнять проверку корректности трассировки квантовых цепей.

Jill iih ТРАНСЛЯТОР СПЕЦИФИКАЦИЙ (кметомо. цепей) В Л5С

МИНИМИЗАТОР ЛБС-СПЕЦИФИКАЦИЯ (квантовых целей)

СТАТИСТИЧЕСКИЙ АНАЛИЗАТОР НАБОРА СПЕЦИФИКАЦИЙ

4 Полином Рида-Маллера (ПРМ) Дх0.....*„_,) имеет фиксированную полярность (ФПРМ), если на протяжении

расширения каждая переменная Хк исключительно, либо хь либо щ. Если для некоторых переменных появляются и Хк и Хк . ТО полярности смешанные (СПРМ).

l«o>

Пример: Iх-О

|хо> |xi>

ab 'abl

ad CNOT cd

cb cb

cd ad

•1ШШ

NOT

SWAP

Рассмотрены основы рекурсивно-лексической методики генерации квантовых цепей и предложен алгоритм расстановки квантовых преобразователей, как способа представления спецификации для реализации квантовых вычислений на основе изменения состояний кубитов на примере квантового преобразования Фурье (0Г7). Предложено семейство рекурсивных структурных схем IV; (рис. 3)для реализации квантового преобразователя перестановки сопряженных коэффициентов при числе кубитов / а 3.

--J-9- -<®-

-Ф—

-®-< —Ф--

где при значении |0) на управляющем кубите

Рис.3. Рекурсивная расстановка преобразователей Для реализации используется СЫОТ библиотека квантовых преобразователей. Для прямого и обратного преобразования дРГ в веден унифицированный управляемый преобразователь СишТ, состоящий из преобразователя Фурье № и управляемого ¡¥4:

Ситр -1 ^'если к)'битУпРавления | о) |С/рЖ,есликубитуправления 11)'

выполняется прямое преобразование дРТ - ир, а |1) - последовательность преобразований: перестановка Ш и прямое преобразование QFT.

Предложены критерии для оценки квантовой цепи. В большинстве работ по синтезу квантовых цепей используются критерии с точки зрения аппаратурных затрат: количество преобразователей (КП) и квантовая сложность (КС). КС преобразователя определяется как количество элементарных операций, необходимых для реализации данного преобразователя в конкретной квантовой технологии. КС элементарного квантового преобразователя равна 1, а КС составного квантового преобразователя считается равной количеству элементарных преобразователей5, требующихся для его реализации.

При расчетах КС было принята, ориентируясь на технологию ЯМР. При этом для элементарных преобразователей КСлет= КСстг =1, КСсзтт =5, стандартная декомпозиция С2МОТ включает 5 элементарных преобразователей, а КСЗШР=2, с учетом известной реализации ¡Ц'АР с помощью трех САЮТ. Для (УНОТ КС рассчитываем следующим об-

5 A. Barenco, C. Bennett, R. Cleve, D. DiVincenzo, N. Margolus, P. Shor, T. Sleator, J. Smolin, and H. Weinfurter. Elementary gates for quantum computation. APS Physical Review A, 52:3457-3467,1995.

разом: КС =2"+I - З6, где п - число кубитов в регистре. Так же для анализа набора спецификаций введены дополнительные критерии, учитывающие нанотехнологические ограничения реализации: сложность ЛБС-нотации (СБС) - учитывает число перестановок кубитов, глубина цепи (ГЦ) - учитывает параллельность выполнения преобразователей в цепи, сложность управления (СУ) - количество управляющих кубитов преобразователя.

Рассматривается процедура преобразования квантовой цепи к ЛБС-нотации, при этом выполняется переход от библиотеки CNOT к библиотеке SCNOT. СБС цепи в ЛБС-нотации равна 0. Минимизация цепи выполнена по двум критериям - КС и ГЦ. Для минимизации последовательностей преобразователей SWAP разработаны решения на основе шаблонов (рис.4). При увеличении размерности квантового регистра шаблоны наращиваются рекурсивно.

Начальное состояние Конечное состояние Начальное состояние Конечное состояние

Шаблон «Лестница вверх» Шаблон «Лестница вниз»

-у-у -А- Ио>-у— ИО-Л-у р<а>- --Л-у-. Л-у-Ц,- и -у- -Л-у -¡Ц,-л.

Шаблон «Бочка» Шаблон «Каскад»

SS-bac: |Хо>-Л,-у- |МЭ>-Л- l/Ha'}-у——у у— -*-л-К |х,>- 1»1>-

Шаблон «V<->X>>

Рис. 4. Примеры шаблонов Предлагается методика последовательной минимизации квантовой цепи в ЛБС-нотации, с точки зрения КП, КС и ГЦ, основанная на многопроходное™ и применении шаблонов.

Для имитационного моделирования предложен реконфигурируемый кластерный клеточный автомат с настраиваемой окрестностью в качестве среды реализации квантовых цепей. Процесс функционирования квантовой цепи моделируется на основе набора реконфигурируемых клеточных элементов (РКЭ). Методика использования РКЭ предполагает формирование сложных структурных схем для моделирования спроектированных квантовых цепей в виде реконфигурируемого клеточного автомата на основе кластерного подхода (РККА). Для моделирования поведения клеток кластеров введена обобщенная модель клетки с виртуальными функциями, каждая из которых при едином алгоритме параметрически настраивается на вариант клетки для ее обслуживания приданными ей методами:

class Kletka

{char Zn,Act,01dZn,0IdAct; public: KletkaQ {Zn='*'; Act=0;}

class KIetka9: public Kletka {public:

Kletka9(chars): KletkaQ {}

6 D. Maslov, G. W. Dueck, D. M. Miller, and C. Negrevergne. Quantum circuit simplification and level compaction IEEE Trans, on CAD, 27(3):436-444, March 200S.

~Kletka9() {}

virtual

void risKIetka(unsigned x,unsigned y) {Kletka::risKletka(x,y); risZona(9,x,y); if(GetAct()) risFaza(9,x,y); } virtual charZapros() {return 9;}

Генерация КЕ-1итт лой иеггк

Ьхоц: тчйгааа ксткнкостк Ком гаотятср Eirfimff^KS1 C'NOT Вьвод шборРМ. спецификации, статистки

virtual ~K!etka() {} void SetZn(char s) {Zn=s;} char GetZnQ {return Zn;} void SetAct(char s) {Act=s;} char GetAct() {return Act;} virtual void risK!etka(unsigned x.unsigned y); virtual char ZaprosQ {return 0;} void save01d() {0!dZn=Zn; 01dAct=Act;} char GetOldO {return OldZn;} };

Четвертая глава содержит описание про'граммной реализации, примеры применения разработанной подсистемы САПР для проектирования квантовых цепей, анализ результатов минимизации для контрольных квантовых цепей. Подсистема LNNQCAD организована по модульному принципу и обеспечивает гибкую пе-рестраиваемость маршрутов проектирования в зависимости от решаемых задач, в том числе и с привлечением внешних сред проектирования (симуляции) на разных стадиях.

Пример маршрута проектирования квантовой цепи (рис. 5). Генерируется набор полиномов Рида-Маллера с трансляцией в нотацию квантовой цепи и формируется набор эквивалентных квантовых цепей (рис. 6), которые имеют разный состав (качественный и количественный) преобразователей. Далее выполняется преобразование к ЛВС-нотации и минимизация с последующим имитационным моделированием выбранных квантовых цепей. После каж- Обобщенный маршрут ПРМ-генерации дого преобразования выполняется анализ: проверка корректности набора спецификаций с помощью ЛАПР и статистический анализ. В итоге формируется многоуровневая спецификация. Пример построения набора квантовых цепей представлен в табл. 2.

Прео5р»ование к ЛБС-нотщкн

Вход: каСор РМ-спедафюэдий Рас стало ь гцик SWAP Ен5лютека SC4-1GT Выход ¡«Rop паитовьк цепей в ЛБС-котоацин, ста тис тш л

Млипюадач, *г*л*нгятгия от технчппгин

Вгод: ф4ш спецификаций вЛБС-нотацкн Мкиимизатср ЛБС-цгпек Оькоп: шбор м ккии гоироваккьп цепей, ггеттетгаа

-гг-" АНАЛИЗ

Ммкгационкое иоделнрогадиг/ Сюпдопди

Вход: графк^скал смцифншш квантовой цепи Клеточный «л том ак нм угопор Еьаои: стулхщи квакгоьой at г®, файл 0ТЧРТ8

Формирование многоуровневой спецификации мантов ой цепи по выбранному ксмеру.

№ *0 х2 /(х0,хьх2) Полиномы FPRM всех полярностей Квант, цепь

и и и и 0 Дх0,xi,x2) = x0x1®Х0Х2 ®Хв ©*) рис. 6, а

1 0 0 1 0 /(*0. хг) = Х0*1 © © X, рис. 6, б

2 и 1 0 1 Дх0, х,, х2) = хох1@х0х29х1Ф1 рис. 6, в

3 и 1 1 1 /(х0, хи x2)~x0xt &>х0х2 Фх0 ©г, ©1 рис. 6, г

4 1 и и 1 f(x0, xhx2) = х0х, ©х0х2 ©х2 ©г0 е 1 рис. 6, д

5 1 0 1 и Я*о. . *2 ) = ® *о*2 ® Ч рис. 6, е

0 1 1 и 1 Дхй, X,, х2) = хах, ф х0х2 © х2 © I рис. 6, ж

) 1 1 1 0 Дх0, хих2) = х0х, ®х0х2 Фх2Фх0 рис. 6, 3

|Хо>. |*1>-|*2>-а I '>6 6 (Ь (Ь

|Xl>— |*2>— <)Ю-

-ф 6 ф ф ф'

|Х„>— |*1>— 1хг>-ф-б lf>~ |х0>-ф-

1*1>-

1*г>-ф-

-ф-ф

-Ф-

|«о>— 1*1>-ф-|*3>—

ю—

4-Ф

Но>-

|*2>-ф-

о—ф-е-ф-4-ф-

-ф-Ф

|*0>-ф-|*1>-ф-

1*г>-Ж I ' >"

1*о>-Ф-|xi>-®-

444-©-

1*2>-ф-

-44

Рис. 6. Экранные формы в виде графических ПРМ-спецификаций квантовых цепей Синтез квантовых логических цепей основан на библиотеке SCNOT Первичный анализ сгенерированных цепей выполняется статистическим ашшшатором, результаты анализа автоматически передаются в Excel (табл. 3).

Таблица 3

№ полинома

__0

_ 1

Mm:

NOT-л

C'NOT

СКОТ CNOT 2

N ОТ/

КП

КП,,

Kn + KIW I КС

120

125

113

116

ПреоЬразование цепи к ЛБС-нотации показай^а примере цепи № 0 (рис 7) Ис пользуется 12 преобразователей SWAP. КП цепи может быть минимизировано, например исключением расположенных подряд преобразователей SWAP, что уменьшает общее КП цепи на 2 и как следствие общую КС цепи. СБС левой цепи - б, СБС правой - 0

|хо>-

|Х2>-

I о-Ф Ф сЬ 6

Рис. 7. Эквивалентные спецификации ПРМ и в ЛБС-нотация В примере минимальные цепи по разным критериям: по КП минимальна цепь № 0' по КП в ЛБС-нотации - № 1; По КС - № 6. Окончательный выбор цепи зависит от требовании конкретной нанотехнологии. Далее цепь в ЛБС-нотации последовательно минимизируется (МЛБС-спецификации), существенно уменьшая показатели КС и ГЦ

В четвертой главе и приложениях приведены результаты проектирования квантовых цепей для 4-11 кубитов. Статистическое описание (СО) контрольной 8-кубитовой цепи: Сложность цепи

гаг

NOT-* 6

C'NOT I

1 П

C°NOT

CJNOT СШТ C^NOT I C;NOT~l CNOT I NOT"

CAqubits SWAPs CAqubits+SWAPs SWAPs Opt I

27 154 181 96

,-----------длл вьшраннои квантовой цепи строится РККА

В основе построения РККА лежит процесс декомпозиции комплектной квантовой цепи в последовательность РКЭ. Выполняется распределение квантовых преобразователей в

процессе проектирования на основе предварительного анализа расстановки преобразователей согласно ПРМ-спецификации квантовой цепи, для описания взаимодействия клеток в пределах общей схемы привлекаются принципы теории клеточных автоматов. Подобная модель функциональной адаптации спроектированной квантовой цепи на РККА позволяет оформить технологическую топологическую двухмерную структурную реализацию для проведения экспериментальной апробации.

Правила поведения РКЭ в составе РККА: 1) клетка активна, если хотя бы одна соседняя клетка активна, 2) активная клетка получает логическое значение соседней клетки при степени взаимодействия 1, иначе получает 0, 3) после передачи активности клетка неактивна, 4) смена состояний клеток происходит одновременно с образованием волнового фронта, 5) направление входов - выходов РККА может быть изменено, возможна замена отдельных виртуальных клеток на их дополнение (обмен входов-выходов), что характерно для обратимых РККА. Базовые РКЭ: CNOT (прямой, обратный и с нижним управлением), And и задержки.

Фрагмент программного описания для кластера CNOT и обратного для него:

Iclass RevCNOT : public CNOT {public:

class CNOT

{protected: Kletka* FwldCNOT[3][4]; unsigned x,y public: CNOT 0 {} CNOT (unsigned xl,unsigned yl) {x=xl; y=yl; FieMCNOT[0J[0]=new Kletka 1(1) FieldOVOT-flHOHiew Kletka8(8);... FieldCMW[l][l]=new Kletka3(3); FieldCAW[2][1 ]=new Kletka2(2); ...} virtual -CNOT ();

void lnit(char с 1,char c2,char Z,char A) {FieldCNOT [с 1 ][c2]->SetZn(Z); FieldCM?7"[cl][c2]->SetAct(A);} void risCNOTQ; void saveO!d(); char Step(); char GetZn(char str.char sib) {return FieldCJVOT [str][slb]->GetZn();} }; |

Получены конкретные схемы функционирования РККА для различных квантовых цепей. На рис. 8 приведены примеры архитектурного построения композиционных РККА для преобразователей SWAP из 3-х кластеров CNOT (начальное состояние - рис. 8, а, заключительное состояние - рис. 8, б) и Фредкина (рис. 8, в), построенный на основе C^NOT

RevCNOT (unsigned xl,unsigned yl) {x=xl; y=yl;

FieldOVOr [0][0]=new Kletkal(l) FieldCjVOr[l][()]=new Kletka2(2) FieldCM3T[l)[l]=new Kletkai(l) FieldCM?r [2][l]=new Kletkal(l)

-RsvCNOT (); };

- 0>1 > > А

А У V >

Ч V > *

> А. > >

V X А. >

(С > > >

> > > 2 Уя\

А У V >

> > >/1

> ч > 1 •

А у v>

> V >

>!А \ >

V X J\

> > >

/ V А > >

> > > /И

А У V

> V > ¡1 / ;

А >

X А >

> >

Рис. 8. РККА модели квантовых цепей 15

Для имитируемой технологии получена КСмастера =1, KCSW/IP =3, КСст07=2. Число тактов автомата (ТА): T>W>17, ТАфредкин=23. TIW= 3 кластера, 4. Получе-

ны конкретные схемы функционирования РККА для различных квантовых цепей.

Подсистема VI-среды САПР LNNQCAD реализует следующие функции:

1. Автоматически генерирует квантовые цепи на основе ПРМ-представления В результате автоматически создаются библиотека ПРМ-спецификаций и библиотека графических спецификаций в ПРМ-представлении.

2. Преобразует спецификации квантовой цепи к ЛБС-нотации, автоматически формируя библиотеку графических ЛБС-спецификаций, а так же позволяет минимизировать квантовые цепи (МЛБС-спецификации) по ГЦ и КС на основе разработанных шаблонов.

3. Позволяет автоматически обработать ПРМ- и ЛБС-спецификации и получить протоколы статистического анализатора квантовых цепей в виде файлов Excel для выбора минимальной цепи по различным критериям.

4. Выполняет автоматическую проверку корректности квантовых цепей на разных стадиях проектирования (ЛАПР) и предоставляет соответствующие протоколы.

5. Решает задачи интеграции подсистемы с другими системами моделирования (симуляции) - обеспечивает интерфейсное взаимодействие с внешними симуляторами, например ZENO , на основе спецификации квантовых цепей в формате LNNQCAD. •

6. Обеспечивает автоматическое построение имитационной модели на РККА по выбранной спецификации квантовой цепи.

7. Функционирует под управлением операционных систем семейства Windows, исходный код модулей и компонентов подсистемы кроссплатформенпый.

В итоге работы подсистемы пользователь получает многоуровневую спецификацию квантовой цепи - комплект документации, включающий математическое описание, СО, ПРМ, ЛВС и МЛБС спецификации на конкретную, выбранную по номеру цепь и РККА.

Таким образом, подсистема VI-среды LNNQCAD включает набор модулей и компонентов для автоматизации проектирования квантовых цепей и может быть использована для проведения научно-исследовательских работ, выполнения лабораторных работ, а также при курсовом и дипломном проектировании.

В заключении сформулированы основные научные и практические результаты диссертационной работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

1. Предложена методика расширения маршрутов синтеза, учитывающих реализацию квантовой цепи с учетом ограничений физической реализуемости квантовых технологий (в ЛБС-нотации), при концептуализации предметной области VI-среды САПР в проектной деятельности при проектировании квантовых цепей.

2. Проведена адаптация алгебры полиномов положительной полярности Рида-Маллера (ПРМ) для проектирования масштабируемых квантовых цепей. Описана процедура преобразования ПРМ к ЛБС-нотации.

7 Cabral G. E. M., Lula B„ Lima A. F. ZENO: a new graphical tool for design and simulation of quantum circuits // Proc of Defense and Security Symposium, Quantum Information and Computation III, vol. 5815,2005. - p.p. 127-137.

3. Подготовлен набор правил преобразований спецификаций квантовых цепей классов CNOT и SCNOT и рекурсивно масштабируемый набор шаблонов для автоматической минимизации в соответствии с введенными критериями оценки сложности.

4. Разработана лингвистическая модель для квантовых преобразователей классов CNOT и SCNOT, обеспечивающая лексический анализ квантовых преобразований и позволяющая проводить проверку корректности трассировки квантовых цепей.

5. Представлена архитектура подсистемы VI-среды САПР LNNQCAD, включающая инструменты автоматизированного проектирования для процедур генерации квантовых цепей, минимизации (топологической и временной), анализа и моделирования (обеспечена совместимость с внешними симуляторами).

6. Предложены маршруты проектирования для подсистемы VI-среды САПР LNNQCAD на основе выделение классов С"NOT и SCNOT квантовых преобразователей.

7. Разработана архитектура реконфигурируемого кластерного клеточного автомата для проведения имитационного моделирования по спецификации квантовой цепи.

8. Разработано программное обеспечение подсистемы VI-среды САПР LNNQCAD, обеспечивающей в соответствии с предложенными проектными процедурами формирование многоуровневых спецификаций (комплект документации, включающий математическое описание, СО, ПРМ-, ЛБС- и МЛБС-спецификации) для классов CNOT и SCNOT квантовых логических цепей на основе ПРМ представления по номеру цепи.

Публикации в изданиях, рекомендованных ВАК России:

1. Матвеева И.В. Алгебраическая структура волнового пакета [Текст] // Известия Государственного электротехнического университета, сер. «Информатика, управление и компьютерные технологии». - СПб., 2003. №2 - С.31-34.

2. Матвеева И.В. Концептуальные модели псевдоквантового поведения клеточного автомата [Текст] // Известия Государственного электротехнического университета, сер. «Информатика, управление и компьютерные технологии». - СПб., 2004. №1. - С.9-17.

3. Матвеева И.В. Квантовые логические элементы [Текст] // Известия Государственного электротехнического университета, сер. «Информатика, управление и компьютерные технологии». - СПб., 2005. №1 - С.7-12.

4. Матвеева И. В. Рекурсивно-лексическая методика расстановки квантовых преобразователей для задач автоматизированного проектирования [Текст] / И. В.Матвеева, В. А. Калмычков // Известия СПбГЭТУ «ЛЭТИ». - СПб., 2010. №. 6 - С.52-57.

5. Матвеева И.В. Моделирование квантовых цепей на виртуальном клеточном автомате [Текст] / И. В.Матвеева, В. А. Калмычков // Известия СПбГЭТУ «ЛЭТИ». - СПб., 2011. №. 5 - С.33-39.

Другие статьи и материалы конференций:

6. Матвеева И.В. Квантовые логические преобразователи [Текст] // Известия Белорусской инженерной академии (рецензируемый научно-технический журнал). - Минск, 2002. № 1(13)/2 - С. 106-110.

7. Матвеева И.В. Формальное описание поведения автоматной возбудимой среды с привлечением языка диаграмм Маллера [Текст] // Известия Белорусской инженерной академии (рецензируемый научно-технический журнал). - Минск, 2003. № 1(15)/1. - С. 39-44.

8. Матвеева И.В. Функционально-структурная полнота операционного базиса квантовых логических цепей [Текст] // Известия Белорусской инженерной академии (рецензируемый научно-технический журнал). - Минск, 2004. № 1(1.7)/3. - С. 202-206.

9. Матвеева И.В. Логическая интерпретация поведения квантовой системы в Гильбертовом пространстве состояний [Текст] // Материалы VII Международной конференции по мягким вычислениям и измерениям SCM'2004 17-19 июня 2004г. - СПб., 2004. Сборник докладов. Т. 1.-С. 199-203.

10. Матвеева И.В. Волновая логика поведения клеточного автомата/ И.В. Матвеева, A.C. Новосельский // Известия Белорусской инженерной академии (рецензируемый научно-технический журнал). - Минск, 2005. № 1 (19)/1. - С. 158-161.

П.Матвеева И.В. Моделирование квантового объекта на клеточном автомате [Текст] / И.В. Матвеева, Л.И. Матвеева // Материалы Всероссийской научно-технической конференции «Наука-Производство-Технологии-Экология» - Киров, 2005. Т. 1. -С.149-151.

12. Матвеева И.В. Методы и средства виртуализации квантовых объектов информации в антропометрических исследованиях безопасности жизнедеятельности [Текст] / И.В. Герасимов, В.А. Калмычков, И.В. Матвеева // ПЭБЧ'07 / Труды Пятой Международной конференции «Приборостроение в экологии и безопасности человека» - СПб., ГУАП, 2007. - С. 134.

13. Матвеева И.В. Парадигма виртуальности: место и роль в проектной деятельности [Текст] / И. В. Герасимов, Л. Н. Лозовой, В.А. Калмычков, И.В. Матвеева // Известия СПбГЭТУ «ЛЭТИ», «Информатика, управление и компьютерные технологии». -СПб., 2008. № 1.-С. 3-7.

14. Матвеева И.В. Моделирование в среде LAB VIEW поведения квантовых логических преобразователей [Текст] / И: В. Герасимов, В.А. Калмычков, И.В. Матвеева, С.А. Кузьмин // РУДН: 7-ая Международная научно-практическая конференция «Образовательные, научные и инженерные приложения в среде Lab View и технологии National Instruments - 2008», Москва, 2008. - С.130-135.

15. Матвеева И.В. Оптимизация проектирования квантовых цепей. [Текст] / И.В. Матвеева, В.А. Калмычков, Л.И. Матвеева // Всероссийская научно-техническая конференция "ОБЩЕСТВО-НАУКА-ИННОВАЦИИ": Сборник материалов: В 4 т. - Киров: Изд-во ГОУ ВПО "ВятГУ", 2010. Том 2 (ФАВТ, ФПМТ, ЭТФ). - С. 48-52.

Подписано в печать 16.11.11. Формат 60x84 1/16. Бумага офсетная. Печать офсетная. Печ. л. 1,0. Гарнитура «Times New Roman». Тираж 100 экз. Заказ 127.

Издательство СПбГЭТУ «ЛЭТИ» 197376, С.-Петербург, ул. Проф. Попова, 5

Оглавление автор диссертации — кандидата технических наук Матвеева, Ирина Витальевна

ВВЕДЕНИЕ

1 МЕТОДЫ И СРЕДСТВА АВТОМАТИЗАЦИИ ПРОЕКТИРОВАНИЯ КВАНТОВЫХ ЦЕПЕЙ

1.1 Фундаментальные основы и основополагающие принципы функционирования квантовых устройств. Ретроспективный взгляд на предметную область

1.2 Основные модельные представления. Квантовая цепь как объект проектирования

1.3 Обзор основных направлений исследования в области синтеза обратимой и квантовой логики

1.4 Принципы построения и примеры реализации систем проектирования квантовых устройств

1.5 Парадигма виртуальности на концептуальном этапе проектирования сред виртуальных инструментов (У1-сред) САПР квантовых устройств

1.6 Выводы

2 АРХИТЕКТУРНЫЕ РЕШЕНИЯ И ПРИНЦИПЫ ПОСТРОЕНИЯ ПОДСИСТЕМЫ САПР

2.1 Краткое введение в основы квантовых вычислений

2.2 Квантовые преобразователи

2.2.1 Однокубитовые квантовые преобразователи

2.2.2 Управляемые (условные) преобразователи

2.2.3 Семейство преобразователей С"Ж)Т.

2.2.4 Библиотеки квантовых преобразователей

2.3 Методы проектирования квантовой цепи

2.4 Преобразование Рида-Маллера

2.5 Преобразование к ЛБС-нотации

2.6 Архитектура подсистемы Ь]чПЧС)САЕ)

2.7 Выводы

3 ЛИНГВИСТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ПОДСИСТЕМЫ LNNQCAD.

МЕТОДИКИ ФОРМИРОВАНИЯ МНОГОУРОВНЕВЫХ

СПЕЦИФИКАЦИЙ

3.1 Рекурсивно-лексическая методика расстановки квантовых преобразователей для задач автоматизированного проектирования

3.1.1 Лексический анализатор квантовых преобразований

3.1.2 Квантовое преобразование Фурье как символическая конструкция

3.1.3 Лексический анализ трассировки квантовых цепей для задачи перестановки сопряженных коэффициентов QFT

3.2 Методика минимизации квантовых логических цепей

3.2.1 Критерии оценки квантовой цепи

3.2.2 СБС оптимальный синтез квантовой логики

3.2.3 Шаблоны эквивалентных квантовых схем

3.3 Методика имитационного моделирования на реконфигурируемом клеточном автомате

3.3.1 Моделирование квантовой физики на клеточном автомате

3.3.2 Реконфигурируемые клеточные элементы для квантовых преобразователей

3.4 Выводы 119 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ПОДСИСТЕМЫ LNNQCAD

4.1 Маршрут проектирования квантовой цепи

4.2 Интерфейсный модуль подсистемы LNNQCAD

4.3 Информационный фонд подсистемы LNNQCAD

4.4 Процедуры генерации квантовых цепей

4.5 Процедура генерации квантовых цепей по ПРМ

4.6 Декомпозиция квантовой цепи в архитектуре близкого соседства

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

4.8 Процедура проверки корректности трассировки квантовых цепей

4.9 Процедура многопроходной минимизация квантовой цепи

4.10 Анализ результатов минимизации для контрольных квантовых цепей

4.11 Виртуально-кластерная архитектура клеточного автомата на плоскостной решетке РККА

4.12 Выводы 161 ЗАКЛЮЧЕНИЕ 163 СПИСОК ЛИТЕРАТУРЫ 166 ПРИЛОЖЕНИЕ А Акт о внедрении результатов 180 ПРИЛОЖЕНИЕ Б Шаблоны минимизации для ПРМ-представления в

ЛБС-нотации

Введение 2011 год, диссертация по информатике, вычислительной технике и управлению, Матвеева, Ирина Витальевна

В основу современных компьютерных технологий положены достижения не только в базовых областях - электротехника и информатика, но и исследования и разработки из принципиально новых разделов науки, таких как, квантовая физика, нанотехнологии и биомедицинское проектирование. Развитие новых направлений чрезвычайно важно - в перечень1 Приоритетных направлений развития науки, технологий и техники в Российской Федерации включена «Индустрия наносистем», к числу критических направлений Российской Федерации относятся в частности «Нано-, био-, информационные, когнитивные технологии». В рамках развития этих направлений в качестве составной части входит проблематика организации волновых (квантовых) вычислений в системах наноуровня.

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

Естественно, глобальной целью остается квантовый компьютер. Развитие исследований в области квантового компьютинга привело к получению не только фундаментальных теоретических результатов, но и дало конкретные практические результаты. Квантовые вычислительные устройства, превосходят (при решении, по крайней мере, некоторых классов задач, например, разложение чисел на сомножители или сравнение заданного образа с содержимым большой базы данных) самый лучший классический компьютер [33]. Квантовые компьютеры полезны также в управляющих квантово-механических системах, в появляющихся приложениях нанотехнологии, на

1 Указ Президента РФ от 07.07.2011 N 899 пример, таких как безопасные оптические коммуникации, в которых современные компьютеры не могут работать с квантовыми данными естественным образом. По оценкам специалистов рабочие прототипы квантовых компьютеров будут созданы через десять лет, но многие интересные решения возникают уже сейчас. Существуют прототипы конкретных элементов квантового компьютера, но это все системы с малым числом кубитов. Основная проблема при его реализации - масштабируемость. Еще одной первостепенной задачей является разработка квантовых алгоритмов. При решении этих задач ключевую роль играет синтез квантовых цепей.

Сложность проектирования вычислительных устройств на наноуровне требует адекватных решаемым проблемам средств разработки, что ведет за собой необходимость расширения и изменение направленности традиционных областей применения систем автоматизированного проектирования (САПР).

Возникают полностью новые проблемы для разработчиков САПР, которые должны быть решены при создании практического квантового устройства, в частности:

• Разработка среды проектирования квантовых устройств в настоящее время является трудной задачей в первую очередь из-за сложности описаний объектов на языке квантовой теории, а также ввиду ограниченного числа известных квантовых алгоритмов.

• Вопрос точного состава набора модулей среды проектирования квантовых устройств остается открытым.

• Модель программирования также является неопределенной, поскольку существуют разные предложения организации квантового компьютера, например как приложение или процессор общего назначения.

• Разработка практических алгоритмов синтеза для квантовой цепи чрезвычайно сложна из-за быстрого роста размеров данных и отсутствия стандартных методов синтеза, а так же инструментов их поддерживающих.

• Так же не решен вопрос масштабируемости квантовых вычислений.

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

Указанные проблемы определили основное направление выполненных диссертационных исследований, тематика которых связана с научными исследованиями в соответствии с планами факультета компьютерных технологий и информатики (ФКТИ) по реализации инновационной научно-образовательной программы «Информатика, управление и компьютерные технологии»: раздел 3 «Обработка информации в наносистемах» (проект «Разработка информационного базиса для элементов квантового компьютинга»).

Адекватно решить многоплановую задачу построения устройств работающих на квантовых принципах в будущем можно будет на основе создания интегрированной системы автоматизированного проектирования квантовых устройств (У1-среды САПР). В настоящее время достаточно хорошо формализованы алгоритмы выполнения отдельных этапов проектирования квантовых цепей, поэтому в рамках восходящего подхода к проектированию актуальной является разработка подсистем интегрированной САПР квантовых устройств, позволяющих уже сегодня получить проектные спецификации для определенных классов квантовых вычислителей с возможностью реализации их в рамках развивающихся нанотехнологий. К таким подсистемам относится У1-среда проектных решений для квантовых цепей, исследованию и раз-работу которой и посвящена настоящая диссертация.

Целью настоящей диссертационной работы является - Автоматизация проектирования квантовых цепей и верификация их реализаций в рамках подсистемы У1-среды САПР устройств, функционирующих на волновых и квантовых принципах. Достижение поставленной цели позволит повысить степень успешности разработок большого класса квантовых устройств в У1-среде САПР за счет выгод от использования формаль

2 VI - УиШа! ¡пзШхтеШаиоп ных языков проектных спецификаций на концептуальном уровне проектирования.

Для достижения поставленной цели необходимо решить следующие задачи:

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

Основные методы исследования

Достоверность научных результатов

Подтверждается корректностью использования математического аппарата, теории клеточных автоматов, алгебры полиномов Рида-Маллера, тео

3 ЛБС - линейно ближайшее соседство кубитов преобразователя, ограничение взаимодействия кубитов рии обработки сигналов, линейной алгебры, методов объектно-ориентированного проектирования и программирования, а так же результатами тестирования в среде реконфигурируемого модульного клеточного автомата и совместимости с внешними средами проектирования (симулятора-ми) на уровне формата описания - обмен проектными данными в формате STEP (язык описания - XML)

Новые научные результаты

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

1. Разработана новая архитектура подсистемы VI-среды САПР проектных решений для квантовых цепей, основанная на новой методике проектирования многоуровневой спецификации для класса С"NOT масштабируемых квантовых логических цепей с учетом ограничений физической реализуемости.

2. Предложены новые алгоритмы проектирования (формирования) многоуровневых спецификаций CmNOT и SCmNOT классов квантовых логических цепей: алгоритм генерации мастабированной квантовой цепи на основе алгебры полиномов Рида-Маллера; алгоритм преобразования к ЛБС-нотации квантовых логических цепей и алгоритм лексического анализа для проверки корректности выполнения трассировки квантовых цепей.

3. Предложен усовершенствованный алгоритм рекурсивно-лексического обобщения унифицированного квантового Фурье-преобразования на основе новой схемы перестановки коэффициентов с использованием преобразователей CmNOT, а также единая спецификация для квантового унифицированного управляемого Фурье-преобразователя.

Научные положения, выносимые на защиту

3. Методика автоматизированной многопроходной минимизации квантовой цепи в ЛБС=нотации с применением предложенных шаблонов.

4. Архитектура ЫчПМС^САБ - подсистемы У1-среды САПР проектных решений для квантовых цепей.

Практическая ценность

Значение результатов диссертационной работы для практического применения заключается в программной реализации модульной архитектуры подсистемы ЫчГМЗСАО, которая позволяет повысить степень успешности разработок квантовых устройств в нотации квантовых цепей в У1-среде САПР за счет выгод от использования формальных языков проектных спецификаций на концептуальном уровне проектирования:

1. Проектировщику предоставляется многоуровневая спецификация квантовой цепи - комплект документации, включающий математическое описание, статистическое описание (СО), ПРМ, ЛБС и минимизированную ЛБС (МЛБС) спецификации на выбранную квантовую цепь (набор цепей) и имитационную модель (РККА).

2. Подсистема ЬМЫС^САГ) может быть использована совместно с внешними симуляторами квантовых вычислений за счет обеспечения инте-роперабельности комплекса разработанных программных модулей для тестирования и минимизации как новых, так и разработанных в других средах квантовых цепей.

Практическая реализация и внедрение результатов работы

Разработанный в ходе исследования набор модулей подсистемы VI-среды САПР LNNQCAD был реализован в среде разработки ПО Visual Studio, предлагающей объектно-ориентированную модель программирования. Практическим результатом работы является подсистема САПР квантовых цепей LNNQCAD, обеспечивающая проектирование и моделирование CmNOT и SCmNOT классов квантовых цепей в ЛБС-нотации и формирующая многоуровневую спецификацию квантовой цепи.

Результаты диссертационной работы использовались:

Материалы диссертационной работы использовались в 2010 г. в проекте «Разработка и реализация сетевой распределенной системы масштабной подготовки магистров и аспирантов, на основе интеграции образовательного процесса с научной и проектной деятельностью, с использованием ресурсов вузов, внедряющих инновационные образовательные программы» (Государственный контракт № П707 от 10 октября 2008 г.) при апробации совместно с ВятГУ (г. Киров) сетевых магистерских образовательных программ по направлению «Информатика и вычислительная техника».

По заявленной тематике автор является победителем конкурса научных достижений студентов и аспирантов СПбГЭТУ 2003 г., конкурса проектов аспирантов и докторантов по разделу III Темплана СПбГЭТУ на 20032004 г.г. по теме «Реверсивная логика в пространстве волновых функций».

Апробация работы.

Основные теоретические результаты диссертационной работы докладывались на конференциях: VII Международная конференции по мягким вычислениям и измерениям SCM'2004 17.06-19.06 2004 г., V-IX Международные летние школы-семинары аспирантов и студентов «Современные информационные технологии» - Минск, БГУИР, Белоруссия, 2002-2006 г.г.; VII Республиканская научная конференция студентов и аспирантов «Новые математические методы и компьютерные технологии в проектировании, производстве и научных исследованиях» - Гомель, ГГУ, Белоруссия, 2004 г.; ПЭБЧ'07 - 5-ая международная конференция "Приборостроение в экологии и безопасности человека" - СПб., ГУАП, 31.01 - 02.02 2007 г.; Всероссийская научно-техническая конференция «Наука-Производство-Технологии-Экология» - Киров, ВятГУ, 21.04 - 26.04 2005 г.; 7-ая Международная научно-практическая конференция «Образовательные, научные и инженерные приложения в среде Lab View и технологии National Instruments - 2008», Москва, РУДН, 28.11-29.11 2008 г.; Всероссийская научно-техническая конференция "Общество-Наука-Инновации" - Киров, ВятГУ, 18.04 - 29.04 2010 г.; Конференции профессорско-преподавательского состава СПбГЭТУ, Санкт-Петербургский государственный электротехнический университет 2003, 2004, 2006, 2007, 2011 г.г.

Публикации

Структура и объем диссертации

Заключение диссертация на тему "Лингвистическое и программное обеспечение автоматизированного проектирования устройств, функционирующих на волновых и квантовых принципах"

Основные результаты работы состоят в следующем:

1. Установлено, что возникающие проблемы при концептуализации предметной области У1-среды САПР в проектной деятельности для различных форм маршрутов проектирования квантовых цепей мотивируют приложение парадигмы виртуальности. Определено, что решение задачи проектирования квантовых цепей требует расширения маршрутов синтеза, учитывающих реализацию цепи в ЛБС-нотации и обеспечивающих выполнение процедур ее минимизации.

2. Определены основания для разработки подсистемы У1-среды САПР Ь>ШС2САО на основе выделение семейства СШЖ)Т квантовых преобразователей в качестве ядра для формирования проектных процедур.

3. Показана возможность использования математических методов и моделей на основе алгебры полиномов Рида-Маллера для проектирования масштабируемых квантовых логических цепей. В качестве основы взят метод представления полиномов положительной полярности Рида-Маллера (ПРМ). Представлено описание процедуры преобразования ПРМ к ЛБС-нотации.

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

5. Разработана лингвистическая модель для квантовых преобразователей, обеспечивающая лексический анализ квантовых преобразований и позволяющая проводить проверку корректности трассировки квантовых цепей.

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

7. Представлена архитектура подсистемы У1-среды САПР ЫчТЫС^САБ, включающая инструменты автоматизированного проектирования, которые охватывают основные задачи процедур генерации квантовых цепей, минимизации (топологической и временной), анализа и моделирования.

8. Представлены конкретные схемы функционирования подсистемы У1-среды САПР ЬКЫОСАО, обеспечивающей подготовку спецификаций при проектировании квантовых цепей:

- предложена методика проектирования квантовых цепей с учетом ограничений физической реализуемости квантовых технологий (ЛБС-нотация квантовой цепи),

- предложен маршрут проектирования для класса СтЫОТ квантовых логических цепей с учетом ограничений физической реализуемости,

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

- выполнена разработка и реализация подсистемы подготовки спецификаций (квантовых цепей) Ь>ШС)САВ, выполняющей генерацию, минимизацию, анализ и симуляцию квантовых цепей.

Разработано программное обеспечение (Приложение Г) подсистемы У1-среды САПР ЬКЫХ^САБ, обеспечивающей в соответствии с разработанными проектными процедурами формирование многоуровневых спецификаций для класса СтЫОТ квантовых логических цепей на основе ПРМ представления с выполнением их минимизации, лексический анализ корректности трассировки квантовых цепей, трансляцию спецификации квантовой цепи в язык внешней среды моделирования, а также возможность проведения имитационного моделирования с использованием реконфигурируемого кластерного клеточного автомата.

Применение разработанной подсистемы У1-среды САПР ЬМЫХ^САО в учебном процессе обеспечивает поддержку дисциплины «Моделирование и анализ инженерных данных» учебного плана подготовки магистров по направлению «Информатика и вычислительная техника».

Материалы диссертационной работы использовались в 2010 г. в проекте «Разработка и реализация сетевой распределенной системы масштабной подготовки магистров и аспирантов, на основе интеграции образовательного процесса с научной и проектной деятельностью, с использованием ресурсов вузов, внедряющих инновационные образовательные программы» (Государственный контракт № П707 от 10 октября 2008 г.) при апробации совместно с ВятГУ (г. Киров) сетевых магистерских образовательных программ по направлению «Информатика и вычислительная техника», что подтверждено актом внедрения материалов диссертационного исследования в учебный процесс (Приложение А).

Теоретические и практические результаты работы использовались в научно-исследовательских работах, выполненных на кафедре систем автоматизированного проектирования Санкт-Петербургского государственного электротехнического университета «ЛЭТИ» им. В.И. Ульянова (Ленина). Диссертационная работа выполнена в рамках научных исследований УГсред1 САПР в соответствии с планами факультета компьютерных технологий и информатики (ФКТИ) по реализации инновационной научно-образовательной программы «Информатика, управление и компьютерные технологии»: раздел 3 «Обработка информации в наносистемах» (проект «Разработка информационного базиса для элементов квантового компьютинга»).

1 VI - Утиа! ЬгвйитеШгЛюп

ЗАКЛЮЧЕНИЕ

Библиография Матвеева, Ирина Витальевна, диссертация по теме Системы автоматизации проектирования (по отраслям)

1. Валиев К.А., Кокин A.A. Квантовые компьютеры: надежды и реальность. //Москва-Ижевск, R&C Dynamics, 2001,2002 352 с.

2. Быков В.П. Методическое обеспечение САПР в машиностроении / В.П. Быков. Л. : Машиностроение, Ленингр. отд-ние, 1989. - 254 с. :

3. Быков В.П. Ковалева Т.И. Свитин В.В. Полякова Л.Ф. Подклетнов С.Г. Моделирование в автоматизированном проектирование. Учебное пособие. 2008.

4. Герасимов В. И., Сафьянников Н. М. Квантовый объект информации // Известия СПбГЭТУ «ЛЭТИ», сер. «Управление, информатика и вычислительная техника». 2001. №1. С. 19-22.

5. Герасимов И. В., Калмычков В. А., Лозовой Л. Н. Комплементарное моделирование в средах САПР: виртуализация квантовых объектов информации. СПб.: Изд-во СПбГЭТУ «ЛЭТИ», 2007. 208 с.

6. Калмычков В. А. Виртуализация квантовых объектов информации в моделирующих средах САПР // Автореферат диссертации на соискание ученой степени кандидата технических наук : 05.13.12 СПб., 2006 16 с.

7. Калмычков В.А. Интерпретационная модель операторов преобразования Фурье // Известия Белорусской инженерной академии. 2002. - № 1 (13)/2. - С. 96-101.

8. Ю.Калмычков В.А. Квантовый алгоритм классификации логической функции // Известия СПбГЭТУ «ЛЭТИ», сер. «Информатика, управление и компьютерные технологии». 2005. - № 2 - С. 47-54.

9. Кнут Д.Э. Искусство программирования, т.2, Получисленные алгоритмы, 3-е изд. М.: Издательский дом "Вильяме", 2001

10. Манин Ю.И. Вычислимое и невычислимое. М.: Сов. Радио, 1980. с.128.

11. Матвеева И.В., Герасимов И. В., Лозовой Л. Н., Калмычков В.А., Парадигма виртуальности: место и роль в проектной деятельности // Известия СПбГЭТУ «ЛЭТИ», «Информатика, управление и компьютерные технологии». СПб., 2008. № 1 - С. 3-7

12. Матвеева И. В. Квантовые логические элементы // Известия СПбГЭТУ «ЛЭТИ», сер. «Информатика, управление и компьютерные технологии». СПб., 2005. №1 - С.7-12.

13. Матвеева И. В., Калмычков В. А. Рекурсивно-лексическая методика расстановки квантовых преобразователей для задач автоматизированного проектирования // Известия СПбГЭТУ «ЛЭТИ». СПб., 2010. №. 6 - С.52-57.

14. Матвеева И.В., Новосельский A.C. Волновая логика поведения клеточного автомата // Известия Белорусской инженерной академии (рецензируемый научно-технический журнал). Минск, 2005. № 1(19)/1. - С.158-161.

15. Матвеева И.В., Матвеева Л.И. Моделирование квантового объекта на клеточном автомате // Материалы Всероссийской научно-технической конференции «Наука-Производство-Технологии-Экология» Киров, 2005. Т. 1. - С. 149-151.

16. Матвеева И.В. Концептуальные модели псевдоквантового поведения клеточного автомата // Известия СПбГЭТУ «ЛЭТИ», сер. «Информатика, управление и компьютерные технологии». СПб., 2004. №1. - С.9-17.

17. Матвеева И.В. Функционально-структурная полнота операционного базиса квантовых логических цепей // Известия Белорусской инженерной академии (рецензируемый научно-технический журнал). -Минск, 2004. № 1(17)/3. С. 202-206.

18. Матвеева И.В., Калмычков В.А.Моделирование квантовых цепей на виртуальном клеточном автомате //Известия СПбГЭТУ «ЛЭТИ». -СПб., 2010. №. 5 С.33-39.

19. Матвеева И.В. Алгебраическая структура волнового пакета // Известия СПбГЭТУ «ЛЭТИ», сер. «Информатика, управление и компьютерные технологии». СПб., 2003. №2 - С.31-34.

20. Наумов Л. Как увеличить скорость "Жизни", или Эффективная организация данных для повышения скорости поиска клеток и разрешения отношений соседства при реализации клеточного автомата Джона Хортона Конвея "Жизнь"/ Информатика, 2001, № 33-34.

21. Немолочнов О.Ф., Зыков А.Г., Осовецкий Л.Г., Поляков В.И. Методы тестирования вычислительных процессов // Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2007. № 45. С. 121125.

22. Немолочнов О.Ф., Зыков А.Г., Поляков В.И. Импликация и эквивалентность как основа верификации //Научно-технический вестник Санкт-Петербургского государственного университета информационных технологий, механики и оптики. 2010. № 4 (68). С. 122-122.

23. Норенков И.П. Основы автоматизированного проектирования. Учебник для вузов М.: Изд-во МГТУ им. Н.Э. Баумана, 1986. 336

24. Ораевский А.Н. О квантовых компьютерах. Квантовая электроника, том 30, № 5, 2000.

25. Стин Э. Квантовые вычисления./пер. С англ. Пасынкова и.д. -ижевск:РХД,2000.-112с.

26. Тоффоли Т., Марголус Н. Машина клеточных автоматов. М.; Мир, 1991.280 с.

27. Abdalla М.М., Gurdal Z. Strctural design using cellular automata for eigenvalue problems. Struct. Multidisc. Optim., Vol. 26, № 3, 2004, pp. 200-208.

28. Al-Rabadi A., "Quantum Circuit Synthesis Using Classes of GF(3) Reversible Fast Spectral Transforms," Int'l Symp. on Multi Valued Logic, 2004, pp. 87-93.

29. B.I.P. Rubinstein. Evolving quantum circuits using genetic programming. In Congress on Evolutionary Computation (CEC2001), pages 114-121, 2001.

30. Balensiefer S., Kregor-Stickles L., and Oskin M. An evaluation framework and instruction set architecture for ion-trap based quantum microarchitectures. Proc. 32nd Annual International Symposium on Computer Architecture, 2005.1.

31. Barenco A. A Universal Two-Bit Gate for Quantum Computation. // Proc. R. Soc. London A. Vol. 449. P. 679-683

32. Barenco A., Bennett С. H., Cleve R., DiVincenzo D. P., Margolus N., Shor P., Sleator Т., Smolin J. A., and Weinfurter H. Elementary gates for quantum computation. Physical Review A, 52:3457-3467, 1995.

33. Benioff P., The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing mashines. J. Statist. Phys., 22, 1980. - p.p. 563-591.

34. Bennet С. H. Logical Reversibility of Computation // IBM Journal of Research and Development, vol. 17, 1973. pp. 525-532.

35. Bennett C.H. Notes on the history of reversible computation. IBM J. Res. Dev., 32, 16-23 (1988).

36. Bettelli S., Calarco T., and Serafini L., "Toward an Architecture for Quantum Programming," The European Physics J. D, vol. 25, no. 2, 2003, pp. 181-200.

37. Biham E., Boyer M., Boykin P.O., Mor T., Roychowdhury V., A Proof of the Security of Quantum Key Distribution, quant-ph/9912053.

38. Cabral G. E. M., LulaB., Lima A. F. ZENO: a new graphical tool for design and simulation of quantum circuits // Proc. of Defense and Security Symposium, Quantum Information and Computation III, vol. 5815, 2005. -p.p. 127-137.

39. Chakrabarti A. and Sur-Kolay S. Nearest neighbour based synthesis of quantum boolean circuits. Engineering Letters, 15:356-361, December 2007.

40. Cheung D., Maslov D., and Severini S. Translation techniques between quantum circuit architectures. Workshop on Quantum Information Processing, December 2007.

41. Conditional Quantum Dynamics and Logic Gates. / A. Barenco, D. Deutsch, A. Ekert, R. Jozsa. // Phys. Rev. Lett. 1995. Vol. 74, № 20. P. 4083-4086.

42. Cuccaro S. A., Draper T. G., Kutin S. A., and Moulton D. P. A new quantum ripple-carry addition circuit, 2004. http://arxiv.org/abs/quant-ph/0410184.

43. De Micheli G., Design and Optimization of Digital Circuits, McGraw-Hill, (1996)

44. De Micheli G. Synthesis and Optimization of Digital Circuits. McGraw-Hill, Inc., 1994.

45. De Vos A.et al., "Generating the Group of Reversible Logic Gates," Journal of Physics A: Mathematical and General,35, 2002, pp. 7063-7078.

46. Desoete B. and De Vos A., A reversible carry-look-ahead adder using control gates. Integration. The VLSI Journal, 33(1):89 104, 2002.

47. Deutsch D., Barenco A. and Ekert A. Universality in Quantum Computation. // Proc. R. Soc. London A. Vol. 449, P. 669-677.

48. Deutsch D., Quantum computation, Physics World, June 1992.

49. DiVincenzo D. P. Two-bit gate for quantum computation. Physical Review A, 50:1015, 1995.

50. Eeles P. What is a software architecture? http://www/ibm.com/developerworks/ rational/library/feb06/eeles

51. Fanjoy D., Crossley W. Using a genetic algorithm to design beam corss-sectional topology for bending, torsion, and combined loading, Structural Dynamics and Material Conference and Exhibit, AIAA, Atlanta, GA, April 2000, pp. 1-9.

52. Fowler A. G., Devitt S. J., and Hollenberg L. С. L. Implementation of shor's algorithm on a linear nearest neighbor qubit array. Quantum Information and Computation, 4:237-245, 2004.

53. Fowler A. G., Hill C. D., and Hollenberg L. C. L. Quantum error correction on linear nearest neighbor qubit arrays. Physical review. A, 69:042314.1042314.4, 2004.

54. Fredkin E., Toffoli T. Conservative logic // Intl. J. of Theoretical Physics, vol.21, 1982.-pp. 219-253.

55. GroverL. K. Quantum computers can search arbitrarily large databases by a single query // Phys. Rev. Lett. 79, 23, 1997. pp. 4709^1012.

56. Haffner H., Hansel W., Roos C. F. et al. Scalable multiparticle entanglement of trapped ions. Nature, 438:643-646, December 2005.

57. Hajela P., Kim B. On the use of energy minimization for CA based analysis in elasticity. Struct. Multidisc. Optim., Vol. 23, 2001, pp. 24-33.

58. IEEE. IEEE Recommended Practice for Architectural Description of Software-Intensive Systems. Institute of Electrical and Electronics Engineers, Sept. 2000. IEEE Std 1471-2000.

59. Jakiela M.J., Chapman C., Duda J., Adewuya A., Saitou K. Continuum structural topology design with genetic algorithms. Comput. Methods Appl. Mech. Engrg, Vol. 186, 2000, pp. 339-356.74.jQuantum (http://sourceforge.net/projects/simqubit/)

60. Kerntopf P., "A Comparison of Logical Efficiency of Reversible and Conventional Gates," Intl. Workshop Logic Synthesis, 2000, pp. 261-269.

61. Khan F. S., Perkowski M. A.: Synthesis of Ternary Quantum Logic Circuits by Decomposition. Proceedings of the 7th International symposium on representations and methodology of future computing technologies, RM2005, Tokyo, Japan.

62. Khan M. H. A. Cost reduction in nearest neighbour based synthesis of quantum boolean circuits. Engineering Letters, 16:1-5, 2008.

63. Khlopotine A., Perkowski M., Kerntopf P., "Reversible Logic Synthesis by Iterative Compositions," IWLS, 2002, pp. 261-266.

64. Kita E., Toyoda T. Structural design using cellular automata. Struct. Multidisc. Optim., Vol. 19, 2000, pp. 64-73.

65. Knill E., Laamme R., and Milburn G. J., A scheme for eficient quantum computation with linear optics. Nature, 409:46-52, 2001.

66. Kutin S. A. Shor's algorithm on a nearest-neighbor machine. Asian Conference on Quantum Information Science, 2007.

67. Laforest M., Simon D., Boileau J.-C., Baugh J., Ditty M., and Laamme R. Using error correction to determine the noise model. Physical Review A, 75:133-137, 2007.

68. Landauer R. Irreversibility and Heat Generation in the Computational Process //IBM Journal of Research and Development, vol. 5, 1961. pp. 183-191.

69. Lukac M. et al, "Evolutionary Approach to Quantum and Reversible Circuits Synthesis," Artificial Intelligence in Logic Design, Kluwer Academic Publisher, 2004, pp. 361-417.

70. Lukac M., Perkowski M., and Kameyama M. Evolutionary quantum logic synthesis of boolean reversible logic circuits embedded in ternary quantum space using structural restrictions. In Proceedings of the WCCI2010, 2010.

71. M. Lukac, A. Sasaki, and M. Kameyama. Cellular automata based robotics architecture for behavioral decision making, to be published.

72. Margolus N. Physics-like model of computation. Physica, 10D, 81-95 (1984).

73. Maslov D. Linear depth stabilizer and quantum fourier transformation circuits with no auxiliary qubits in finite neighbor quantum architectures. Physical Review A, 76, 2007.

74. Maslov D., Dueck G. W., and Miller D. M. Toffoli network synthesis with templates. IEEE Trans, on CAD, 24(6):807 817, 2005.

75. Maslov D., Dueck G. W., and Miller D. M. Synthesis of Fredkin-Toffoli reversible networks. IEEE Transactions on VLSI, 13(6):765-769, 2005.

76. Meter R. V. and Oskin M., Architectural implications of quantum computing technologies. J. Emerg. Technol. Comput. Syst., 2(l):31-63, 2006.

77. Metodi T., Thaker D., Cross A., Chong F., and Chuang. A Quantum Logic Array Microarchitecture: Scalable Quantum Data Movement and Computation. Proceedings of the 38th International Symposium on Microarchitecture (MICRO), 2005.

78. Metodi T.S., Thaker D.D., Cross A.W., Chong F.T., and Chuang I.L. Scheduling physical operations in a quantum information processor. Proceedings of SPIE, 6244:62440T, 2006.

79. Miller D. M. and Dueck G.W. Spectral techniques for reversible logic synthesis. In Proc. RM, pages 56-62, 2003.

80. Miller D. M. and Thornton M. A. QMDD: A decision diagram structure for reversible and quantum circuits. In Proc. of the IEEE International Symposium on Multiple-Valued Logic, page 30, May 2006.

81. Miller D. M., Maslov D., Dueck G. W., "A Transformation Based Algorithm for Reversible Logic Synthesis,"Design Automation Conf. 2003, pp. 318-323.

82. Miller D.M.,"Spectral and Two-Place Decomposition Techniques in Reversible Logic," Midwest Symp. on Circuits and Systems, CD-ROM, 2002.

83. Mischenko A. and Perkowski M. Logic synthesis of reversible wave cascades, hi Proceedings o/IWLS, pages 197-202, 2002.

84. Monroe C., Meekhof B. E., ind King D. M., Leibriefd D., Itano W. M., and Wineland D. J. Manipulating the motion of a single trapped atom. Acc. Chem. Res., 29(12):585590, 1998.

85. Nielsen M. A., Chuang I. L. Quantum Computation and Quantum Information. Cambridge University Press, 2000.

86. Omer B., "A Procedural Formalism for Quantum Computing," doctoral dissertation, Dept. Theoretical Physics, Technical Univ. of Vienna, 1998.

87. Paige C. C., Wie M.: History and generality of the CS decomposition. Linear Algebra and its Applications Vol. 208-209, pp. 303-326 (1994).

88. Peres A. Reversible logic and quantum computers. Physical review,(32)\3266-3216, 2000.

89. Perkowski M et. al.,. Quantum logic synthesis by symbolic reachability analysis. In Proceedings ofDAC, 2004.

90. Perkowski M., et. al., "Regularity and Symmetry as a Base for Efficient Realization of Reversible Logic Circuits," IWLS, 2001, pp. 90-95.

91. Perry D.E. and A.L. Wolf. Foundations for the Study of Software Architecture. ACM SIGSOFT Software Eng. Notes, Oct. 1992, pp. 40-52.

92. QCE (http://rugth30.phys.rug.nl/compphys0/qce.htm)

93. Quantomic http://dream.inf.ed.ac.uk/projects/quantomatic/

94. Ross M. and Oskin M., Quantum computing. Commun. ACM, 51(7): 1213, July 2008.

95. Rozvany G. I. N., Zhou M., Gollub W. Continuum-type optimality criteria methods for large finite-element systems with a displacement constraint. -Struct. Optim., Vol. 2, № 2, 1990, pp. 77-104.

96. Saeedi M., Wille R., Drechsler R., Kane B., A silicon-based nuclear spin quantum computer. Nature, 393:133-137, 1998.

97. Saxena A., Ananthasuresh G. K. On an optimal property of compliant topologies. Struct. Multidisc. Optim., Vol. 19, 2000, pp. 36-49.

98. Schmit L.A., Farsi B. Some approximation concepts for structural synthesis. AIAA J., Vol. 12, № 5, 1974, pp. 692-699.

99. Schmit L.A., Miura, H. Approximation concepts for efficient structural synthesis. NASA CR-2552 , March 1976.

100. Shah D. and Perkowski M., "Synthesis of quantum arrays with low quantum costs from kronecker functional lattice diagrams," in IEEE Congress on Evolutionary Computation, pp. 1-7, 2010.

101. Shende V. V., Bullock S. S., and Markov I. L. Synthesis of quantum-logic circuits. IEEE Trans, on CAD, 25(6):1000 1010, June 2006.

102. Shende V. V., Prasad A. K., Markov I. L.,. Hayes J. P, "Synthesis of Reversible Logic Circuits," IEEE Trans, on Computer Aided Design of Integrated Circuits and Systems, vol. 22(6), 2003, pp. 710-722.

103. SimQbit (http://sourceforge.net/projects/simqubit/)

104. Smolin J. and DiVincenzo D. P. Five two-qubit gates are sufficient to implement the quantum fredkin gate. Physical Review A, 53(4):2855-2856, 1996.

105. Software Engineering Institute // http://www.sei.cmu.edu

106. Stewart G. W.: Computing the CS Decomposition of a Partitioned orthogonal Matrix. Numerische Mathematik Vol. 40, pp. 297-306 (1982).

107. Storme L. et al., "Group Theoretical Aspects of Reversible Logic Gates," Journal of Universal Computer Science 5, 1999, pp 307-321.

108. Svanberg K. The method of moving asymptotes a new method for structural optimization. - Int. J. Numer. Meth. Engrg., Vol. 24, 1987, pp. 359-373.

109. Svore K,, Aho A,, Cross A,, Chuang I,, and Markov I,, A Layered Software Architecture for Quantum Computing Design Tools. Computer, 39(1):74—83, 2006.

110. Svore K., Cross A., Aho A., Chuang I., and Markov I. Toward a software architecture for quantum computing design tools. Proceedings of the 2nd International Workshop on Quantum Programming Languages (QPL), pages 145-162, 2004.

111. Takahashi Y., Kunihiro N., and Ohta K. The quantum fourier transform on a linear nearest neighbor architecture. Quantum Information and Computation, 7:383-391, 2007.

112. Tatting B., Gurdal Z. Cellular automata for design of two-dimensional continuum structures. Proceedings of 8th AIAA/USAF/NASA/ISSMO Symposium on Multidisciplinary Analysis and Optimization, 2000.

113. Thaker D.D., Metodi T.S., Cross A.W., Chuang I.L., and Chong F.T. Quantum Memory Hierarchies Efficient Designs to Match Available Parallelism in Quantum Computing. Proceedings of the 33rd International Symposium on Computer Architecture (ISCA), 2006.

114. Toffoli T., Margolus N. Invertible cellular automata: a review. Physica D, 45, 229-253 (1990).

115. Toffoli T., Reversible Computing, Lab. for Computer Science, MIT, Cambridge, MA, Technical Memo. MIT/LCS/TM-151, 1980.

116. Tucci R.R., "An Introduction to Cartan's KAK Decomposition for QC Programmers", quant-ph/0507171

117. Vanderplaats G.N., Salajegheh E. A new approximation method for stress constraints in structural synthesis. AIAA J., Vol. 27, № 3, 1989, pp. 352358.

118. Venkayya V. B. Optimality criteria: a basis for multidisciplinary design optimization. Comp. Mech., Vol. 5,1989, pp. 1-21.

119. Wille R. and Drechsler R. Effect of BDD optimization on synthesis of reversible and quantum logic. Workshop on Reversible Computation, 2009.

120. Wille R., Große D., Miller D.M., and Dreschler R. Equivalence checking of reversible circuits. In Proceedings of the ISMVL, 2009.

121. Wineland D.J.et al.,"Experimental Issues in Coherent Quantum-State Manipulation of Trapped Atomic Ions," J. Research of NIST, vol. 103, no. 3, 1998, pp. 259-328.

122. Xie Y.M., Steven G.P. A simple evolutionary procedure for structural optimization. Comput. Struct., 1993, pp. 885-896.

123. Xie Y.M., Steven G.P. Evolutionary Structural Optimization Springer, 1993.

124. Yabuki T., Genetic algorithms for quantum circuit design evolving a simpler teleportation circuit -. In In Late Breaking Papers at the 2000 Genetic and Evolutionary Computation Conference, 2000.

Похожие работы

Информатика, вычислительная техника и управление
05.13.00