关键词: 量子电路综合,FPRM展开式,可逆逻辑函数,NP-NP等价,等价判定

Abstract: In reversible logic synthesis,the templates can be used repeatedly through classification．Extending the definition of NP-N equivalence for Boolean functions to the reversible logic functions,the definition of NP-NP equivalence for reversible logic functions can be given.Divide all 3-varible Boolean functions in which everyone of them has exactly four minterms into five classes by their cofactor weight vectors,and calculate the fixed polarity Reed-Muller Form of each class.By comparing the sorted cofactor weight vectors,whether the reversible logic functions are NP-NP equivalent can be judged preliminarily．When the sorted cofactor weight vectors are identical,the reversible logic functions should be judged as NP-NP equivalence if and only if their every corresponding output which is Boolean function has the same vari-able mappings．Otherwise,the reversible logic functions are not NP-NP equivalent．Thus,whether two 3-bit reversible logic functions are NP-NP equivalent can be judged by this method.

Key words: Synthesis of quantum circuit,Fixed polarity reed-muller form,Reversible logic function,NP-NP equivalence,Equivalence judgment