Quantum information processing is of interest as it offers the potential for a new generation of very powerful computers supporting novel computational paradigms. Over the last couple of decades, different aspects of quantum computers ranging from quantum algorithms to quantum physical design have received growing attention. One of the most important research areas is the synthesis and post-synthesis optimization of reversible and quantum circuits. Many synthesis and optimization approaches can be found in the literature, yet, due to the complexity of the problem, finding approaches leading to optimal, or near optimal, results is still an open problem. The synthesized circuits are usually evaluated based on quantum cost models. Therefore, they are often technology mapped to circuits of more primitive gates. To this end, various technology mapping approaches have also been proposed in the past few years. Related work shows an existing gap in optimized technology mapping for reversible and quantum circuits. In this dissertation, an optimized technology mapping design flow is introduced for mapping reversible circuits to quantum circuits. The contributions of this dissertation are classified as follows: - New reversible circuit optimization methods. - Optimized reversible to quantum mapping approaches. - New quantum gate libraries and new cost models for reversible gates based on the new libraries. - Quantum circuit optimization approaches. The steps above, form an optimized flow for mapping reversible circuits to quantum circuits. At each step of the design flow optimized and consistent approaches are suggested with the goal of reducing the quantum cost of the synthesized reversible circuits. The evaluations show that the proposed mapping methodology leads to significant improvement in the quantum cost of the existing benchmark circuits. / Graduate

As the number of transistors per unit chip area increases, the power dissipation of the chip becomes a bottleneck. New nano-technology materials have been proposed as viable alternatives to CMOS to tackle area and power issues. The power consumption can be minimized by the use of reversible logic instead of conventional combinational circuits. Theoretically, reversible circuits do not consume any power (or consume minimal power) when performing computations. This is achieved by avoiding information loss across the circuit. However, use of reversible circuits to implement digital logic requires development of new Electronic Design Automation techniques. Several approaches have been proposed and each method has its own pros and cons. This often results in multiple designs for the same function. Consequently, this demands research in efficient equivalence checking techniques for reversible circuits. This thesis explores the optimization and equivalence checking of reversible circuits. Most of the existing synthesis techniques work in two steps — generate an original, often sub-optimal, implementation for the circuit followed optimization of this design. This work proposes the use of Binary Decision Diagrams for optimization of reversible circuits. The proposed technique identifies repeated gate (trivial) as well as non-contiguous redundancies in a reversible circuit. Construction of a BDD for a sub-circuit (obtained by sliding a window of fixed size over the circuit) identifies redundant gates based upon the redundant variables in the BDD. This method was unsuccessful in identifying any additional redundancies in benchmark circuits; however, hidden non-contiguous redundancies were consistently identified for a family of randomly generated reversible circuits. As of now, several research groups focus upon efficient synthesis of reversible circuits. However, little work has been done in identification of redundant gates in existing designs and the proposed peephole optimization method stands among the few known techniques. This method fails to identify redundancies in a few cases indicating the complexity of the problem and the need for further research in this area. Even for simple logical functions, multiple circuit representations exist which exhibit a large variation in the total number of gates and circuit structure. It may be advantageous to have multiple implementations to provide flexibility in choice of implementation process but it is necessary to validate the functional equivalence of each such design. Equivalence checking for reversible circuits has been researched to some extent and a few pre-processing techniques have been proposed prior to this work. One such technique involves the use of Reversible Miter circuits followed by SAT-solvers to ascertain equivalence. The second half of this work focuses upon the application of the proposed reduction technique to Reversible Miter circuits as a pre-processing step to improve the efficiency of the subsequent SAT-based equivalence checking. / Master of Science

Orientador: Anna Diva Plasencia Lotufo / Resumo: A lógica de múltiplos valores, em especial a ternária, apresenta inúmeras vantagens sobre a lógica binária em circuitos reversíveis/quânticos. A realização de funções usando a lógica reversível ternária é conhecida por requerer um menor número de linhas em comparação com a lógica reversível binária convencional. Este aspecto tem motivado as pesquisas em abordagens de síntese. A grande maioria dos métodos existentes requerem entradas adicionais, denominadas de ancillary lines, durante o processo de síntese, o que é dispendioso para implementação em tecnologias quânticas, quando disponíveis. Neste trabalho, foram propostas diferentes metodologias e análises comparativas para o problema da síntese de circuitos reversíveis ternários sem a adição de ancillary lines. A metodologia de síntese proposta, denominada de MMD plus, foi aplicado nos modos backward e top-down como referência a todas as 362880 possíveis funções reversíveis ternárias de 2 variáveis. Além do processamento top-down originário do algoritmo MMD, um processamento bottom-up é implementado e sua eficiência comparativa é avaliada. Por definição, as funções reversíveis ternárias são permutações. Realiza-se a decomposição das permutações em ciclos disjuntos de ordem natural, em ciclos de permutação com 3 elementos, e em transposições, para obtenção dos circuitos reversíveis ternários. Uma métrica é introduzida para mensurar a complexidade e custo dos circuitos, com base nas portas reversíveis de múltiplos valores Muthu... (Resumo completo, clicar acesso eletrônico abaixo) / Doutor