Лингвистическое и программное обеспечение автоматизированного проектирования устройств, функционирующих на волновых и квантовых принципах тема диссертации и автореферата по ВАК РФ 05.13.12, кандидат технических наук Матвеева, Ирина Витальевна

• Матвеева, Ирина Витальевна
• кандидат технических наук
• 2011

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

ВВЕДЕНИЕ

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 ПРИЛОЖЕНИЕ Б Шаблоны минимизации для ПРМ-представления в

ЛБС-нотации

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Материалы диссертационной работы использовались в 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 г.г.

Публикации

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

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

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

Заключение диссертации по теме «Системы автоматизации проектирования (по отраслям)», Матвеева, Ирина Витальевна

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ЗАКЛЮЧЕНИЕ

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

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.