置换群与整数间一对一Hash函数的构建

Construction of one-for-one Hash function mapping between permutation group and integral number

为了提高量子可逆逻辑电路自动生成与优化的效率,给出了一个在置换群与整数域上满足一对一映射的Hash函数构建方法.一个n×n的量子可逆逻辑门的输入和输出对可有2n!种组合,若将一个组合对应一个置换,则一切2n次置换的集合就组成一个置换群.Hash函数H(X)利用每一个置换中数字的排列位置,求出该数字的逆序数并计算其函数值,将置换群的元素X(a0a1…a2n-1)映射到整数Z∈{0,1,…,2n!-1}的集合上,快速确定计算位置.该函数不但可以大大提高量子可逆逻辑综合算法的效率,而且结构简单,性质良好,具有一般性意义.

For improving the efficiency of reversible quantum, a construction of one-for-one Hash function logic circuit automation and optimization of mapping between permutation group and integral number is proposed. There are 2^n ! combinatorial duals of input/output in a reversible logic gate of n x n quantum. If a combinatorial dual corresponds to a permutation, then a permutation group can be created with the set composed by all 2^n permutations. The Hash function H（X） maps an element X（αoα1…α2n-1 ） of a permutation group onto an integer Z ∈ { 0,1 ,...,2^n ! - 1 t by counting a- thwart ordinal number of every number in a permutation by using its arrangement and computing its function value, and quickly confirming the position. The efficiency of synthetic algorithms for reversible logic of quantum can be greatly improved by using this function. Moreover, this function has simple structure, good performance and universality.