Synthesis of quantum circuits based on incompletely specified functions and if-decision diagrams

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