Algoritmos para a síntese de circuitos reversíveis ternários: análise comparativa
Carregando...
Data
2018-08-24
Autores
Barbieri, Caroline Domingues Porto do Nascimento
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Estadual Paulista (Unesp)
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 Muthukrishnan-Stroud (MS). A eficiência do procedimento de síntese do MMD plus empregado aos ciclos de permutação é avaliada e comparada com a aplicação direta, isto é, sem decomposição das permutações em ciclos. Em seguida, propõem-se duas metodologias com base em Algoritmos Genéticos para o projeto de circuitos reversíveis ternários como um problema de otimização, utilizando-se, também, das portas MS. A influência de diferentes tipos de seleção e variação do tamanho dos indivíduos é avaliada em relação à quantidade de portas e custos dos circuitos resultantes da síntese.
Multiple-valued logic, especially ternary logic, has many advantages over binary logic in reversible/quantum circuits. Performing functions using ternary reversible logic is known to require fewer rows compared to conventional binary reversible logic. This aspect has motivated the researches in synthetic approaches. The vast majority of existing methods require additional lines, called ancillary lines, during the synthesis process, which is expensive for implementation in quantum technologies, when available. In this work, were proposed different methodologies and comparative analysis for the problem of the synthesis of ternary reversible circuits without the addition of ancillary lines. The proposed synthesis methodology, called MMD plus, in backward top-down modes was applied as a reference to all 362880 possible ternary 2-variable reversible functions. In addition to the original top-down processing of the MMD algorithm, a bottom-up processing is implemented and its comparative efficiency is evaluated. By definition the ternary reversible functions are permutations. The decomposition of the permutations is performed in disjoint cycles of the natural order, in permutation cycles with 3 elements and in transpositions, to obtain the circuits. A metric is introduced to estimate the complexity or cost of circuits based on Muthukrishnan-Stroud (MS) multivalued reversible gates. The efficiency of the MMD plus synthesis employed in the permutation cycles is evaluated and compared with the direct application, without decomposition. Then, two methodologies based on Genetic Algorithms are proposed for the design of ternary reversible circuits as an optimization problem, using also the MS gates. The influence of different types of selection and variation of the individual's size is evaluated in relation to the number of gates and costs of the circuits resulting from the synthesis.
Multiple-valued logic, especially ternary logic, has many advantages over binary logic in reversible/quantum circuits. Performing functions using ternary reversible logic is known to require fewer rows compared to conventional binary reversible logic. This aspect has motivated the researches in synthetic approaches. The vast majority of existing methods require additional lines, called ancillary lines, during the synthesis process, which is expensive for implementation in quantum technologies, when available. In this work, were proposed different methodologies and comparative analysis for the problem of the synthesis of ternary reversible circuits without the addition of ancillary lines. The proposed synthesis methodology, called MMD plus, in backward top-down modes was applied as a reference to all 362880 possible ternary 2-variable reversible functions. In addition to the original top-down processing of the MMD algorithm, a bottom-up processing is implemented and its comparative efficiency is evaluated. By definition the ternary reversible functions are permutations. The decomposition of the permutations is performed in disjoint cycles of the natural order, in permutation cycles with 3 elements and in transpositions, to obtain the circuits. A metric is introduced to estimate the complexity or cost of circuits based on Muthukrishnan-Stroud (MS) multivalued reversible gates. The efficiency of the MMD plus synthesis employed in the permutation cycles is evaluated and compared with the direct application, without decomposition. Then, two methodologies based on Genetic Algorithms are proposed for the design of ternary reversible circuits as an optimization problem, using also the MS gates. The influence of different types of selection and variation of the individual's size is evaluated in relation to the number of gates and costs of the circuits resulting from the synthesis.
Descrição
Palavras-chave
Lógica ternária, Computação quântica, Síntese de circuitos reversíveis, Permutação, Ciclos de permutação disjuntos, Algoritmo genético, Ternary logic, Quantum computation, Synthesis of reversible circuits, Permutation, Disjunct permutation cycles, Genetic algorithm