量子可逆逻辑综合的关键技术及其算法

最优化量子可逆逻辑的关键在于用最小的量子代价自动构造量子可逆逻辑.为了提高可逆逻辑自动生成与优化的效率,提出了类模板技术和一种快速算法.模板技术是一个有效的优化工具,类模板技术可以显著提高模板技术的匹配效率;R-M算法是可逆逻辑综合的一种较好的迭代方法,基于R-M算法的原始思想,构造了一个Hash函数,并在此基础上提出了一种可逆逻辑综合的快速算法.实验结果表明,在同等实验环境下使用类模板技术与快速算法,其优化的效果与效率远远优于已知的其他算法.     

基于矩阵初等变换的量子可逆逻辑电路双向综合算法

基于矩阵初等变换,提出了量子可逆逻辑电路双向综合算法。该算法依据两数字间的汉明距离,通过交换矩阵行号或矩阵元素对量子可逆逻辑电路的矩阵进行初等行变换。在变换的过程中,利用邻接矩阵的电路转化规则,生成任意给定置换的量子可逆逻辑电路。与其它同类算法相比,由于不需要穷尽搜索,该算法的时空复杂度有大幅降低;又由于采用任意n量子扩展通用Toffoli门,该算法可综合任一置换(奇或偶置换)的量子可逆逻辑电路,并且电路中门的数量有所减少。     

基于正反控制模型的可逆逻辑综合

对一般Toffoli门进行了衍变和推广,给出了一个正反控制可逆级联模型(PNCRC),该模型拥有五种基本线型,并能正反控制目标位的输出.基于该模型给出了相应的可逆综合算法.对输入数不大于16的NCMCBench-mark函数进行测试并与已有的可逆综合方法比较,结果表明,利用该模型进行的可逆综合,垃圾信息数和可逆门数的优化效果都具有一定程度的改善.     

混合多值可逆逻辑中广义Toffoli门仅用CNOT门的实现

混合多值量子可逆逻辑电路综合问题中,Toffoli门的合成是整个合成过程中最为关键的一步。针对混合多值5-qubits量子可逆逻辑电路综合问题,构造了PMX量子门,验证了CNOT门的合成能力,实现了对Toffoli门的合成,并设计了双向的BDS搜索算法,高效实现了量子电路的最优或者较优综合。     

基于正反控制门的可逆逻辑综合

提出一种基于正反控制(PNC)门可逆网络的级联算法,为3位输入/输出函数设计相应的模板,给出级联网络的约简算法。实验结果表明,与Toffoli门级联成的网络相比,使用PNC门的可逆网络中门的数量较少,在降低网络代价方面具有一定优势。     

基于Hash表的量子可逆逻辑电路综合的快速算法

量子可逆逻辑电路是构建量子计算机的基本单元,通过量子门的级联与组合构成量子计算机,量子可逆逻辑电路的综合就是根据电路功能,以较小的量子代价自动构造量子可逆逻辑电路.结合可逆逻辑电路综合的多种算法,提出了一种新颖高效的量子电路综合算法,巧妙构造最小完备的Hash函数,可使用多种量子门,采用任意量子代价标准,以极高的效率生成最优的量子可逆逻辑电路.为实现量子电路综合的自动化,首次提出了利用量子线的置换自动构造各种量子门库的通用算法.采用国际同行认可的3变量可逆函数测试标准,该算法不仅能够生成全部最优电路,而且运行速度远远超过其他算法.实验结果表明,该算法按最小长度、最小代价标准综合电路的平均速度分别是目前最好结果的49.15倍、365.13倍.     

基于规则的可逆Toffoli电路优化算法

可逆电路的优化是可逆逻辑综合的关键问题之一.为了解决可逆Toffoli电路优化问题中算法复杂度高和电路规模可扩充性差的问题,分析归纳了相邻Toffoli门的关系,提出并证明了可逆Toffoli电路中子序列的移动和化简规则,并基于这些规则给出了可逆Toffoli电路的优化算法.根据移动规则对可逆电路进行正向和反向扫描,寻找满足化简规则的子序列进行优化,直到可逆电路不发生变化为止.该优化算法与可逆电路的输入线数无关,无需存储额外信息,适用于各种不同类型的Toffoli电路合成方法,算法复杂度为O(s3),优于通常使用的模板优化的复杂度O(n!t2s3).在具体实例和国际认可的所有3变量可逆函数上的验证结果表明,该优化算法能有效地减少可逆电路的门数和控制位数,降低可逆电路的代价.     

基于固定极Reed Muller展开式的3阶可逆

在可逆逻辑函数综合中,分类可以使模块重复使用.把布尔函数NP-N等价的概念推广到可逆逻辑函数中,得到了可逆逻辑函数NP-NP等价的概念;把最小项数为4的3元布尔函数根据辅因子的码值向量分成5类,并计算出了这5类布尔函数的固定极Reed-Muller(FPRM)展开式;把可逆逻辑函数的辅因子码值向量排序后是否相同作为可逆逻辑函数是否NP-NP等价的初步判定,当它们相同时,两个可逆逻辑函数NP-NP等价当且仅当它们的各个对应的输出分量有相同的变量映射,否则它们不是NP-NP等价的.运用这个方法可以判定任意的两个3阶可逆逻辑函数是否NP-NP等价.     

基于卡诺图的三变量可逆逻辑综合算法

提出了一种基于卡诺图的可逆逻辑综合算法,该算法可以快速地求解带垃圾位的可逆逻辑综合问题。大量特定的可逆逻辑门都不可避免地带有一定的垃圾位, 如果使用真值表、置换群等经典可逆逻辑综合算法求解这些带垃圾位的可逆逻辑门,则因无法获得全局状态而很难得到结果。根据卡诺图的特点,将可逆逻辑问题分解为多个变量分别求解,无需关心全局状态。提出的卡诺图可逆逻辑综合算法 根据在卡诺图上的邻接性将3变量可逆逻辑问题划分为5个等价类;对每个等价类分别进行计算,在常数时间内解决了带垃圾位的可逆逻辑综合问题。     

Reversible computing and cellular automata—A survey

Reversible computing is a paradigm where computing models are defined so that they reflect physical reversibility, one of the fundamental microscopic physical property of Nature. In this survey/tutorial paper, we discuss how computation can be carried out in a reversible system, how a universal reversible computer can be constructed by reversible logic elements, and how such logic elements are related to reversible physical phenomena. We shall see that, in reversible systems, computation can often be carried out in a very different manner from conventional (i.e., irreversible) computing systems, and even very simple reversible systems or logic elements have computation- or logical-universality. We discuss these problems based on reversible logic elements/circuits, reversible Turing machines, reversible cellular automata, and some other related models of reversible computing.     

有限域上模逆电路的可逆逻辑设计

为了进一步提高加密系统的可靠性,提出了一种新颖的可逆逻辑门,利用它和存在的可逆门,设计了模逆电路所需的基本模块,并在有限域上设计了基于可逆逻辑的模逆电路。根据量子代价和延迟对其基本模块进行了性能评估,结果证明构建模逆电路的基本模块比现有可逆电路的性能提高5%~20%。以有限域GF(23)上求二进制多项式的乘法逆元为例,对提出的模逆电路进行建模仿真,结果表明电路的逻辑结构正确,性能可靠。提出的设计可用于加密算法的量子电路系统。     

基于位运算的量子可逆逻辑电路快速综合算法

量子可逆逻辑电路是构建量子计算机的基本单元.本文结合可逆逻辑电路综合的多种算法,根据可逆逻辑电路综合的本质是置换问题,巧妙应用位运算构造高效完备的Hash函数,提出了基于Hash表的新颖高效的量子可逆逻辑电路综合算法,可使用多种量子门,以极高的效率生成最优的量子可逆逻辑电路,从理论上实现制造量子电路的成本最低.按照国际同行认可的3变量可逆函数测试标准,该算法不仅能够生成全部最优电路,而且运行速度远远超过其它算法.实验结果表明,该算法按最小长度标准综合电路的平均速度是目前最好结果的69.8倍.     

基于正反控制门的可逆网络化简

提出并证明正反控制(PNC)门级联电路中的合并、移动和分解规则,利用此规则给出基于PNC门的可逆网络的化简算法。根据移动规则对门序列进行正向和反向双向扫描,寻找符合化简条件的两门,直到可逆网络不发生变化为止。所有3变量可逆函数上的实验结果表明,该算法能减少PNC门级联网络的门数和控制位数,降低可逆网络的代价。     

经典逻辑门与量子逻辑门之比较

本文通过经典逻辑门与量子逻辑门之比较,论述了量子计算的特点、量子算法的巨大威力及量子逻辑门的实现问题。     

基于相似函数与相似网络的可逆网络化简

提出了可逆函数的相似函数及可逆网络的相似网络,在此基础上构建了可逆网络化简方法。由可逆函数求出其所有的相似函数,对每个相似函数利用可逆逻辑综合算法生成可逆网络,再将其转换成对应的相似网络,并从中选取最优。该网络化简算法实现了生成三变量全部可逆函数和多变量可逆函数的可逆网络,与相关文献及Benchmark中的例题相比,构造可逆网络的门数较少,具有一定的优势。     

具有过去时态算子的计算树逻辑模型检测

在计算树逻辑(CTL)中引入过去时态算子,得到了表达力更强的属性规约语言CTLP,给出了CTLP 的模型检测算法及其固定点刻画.该算法的复杂性和CTL一样.固定点刻画使得CTLP的符号模型检测过程能够实现,从而有效克服了模型检测中的状态爆炸问题.     

Compositional and holistic quantum computational semantics

In quantum computational logic meanings of sentences are identified with quantum information quantities: systems of qubits or, more generally, mixtures of systems of qubits. We consider two kinds of quantum computational semantics: (1) a compositional semantics, where the meaning of a compound sentence is determined by the meanings of its parts; (2) a holistic semantics, which makes essential use of the characteristic “holistic” features of the quantum-theoretic formalism. We prove that the compositional and the holistic semantics characterize the same logic.     

可编程可逆计数器电路的逻辑设计与功能验证

计数器电路在集成电路领域有着很广泛的应用,常作为集成电路的基本器件使用。计数器电路可以输出多种可控的信号,配合其它电路一起使用。以一种八位可编程可逆计数器为例,阐述了这类计数器电路具体的电路逻辑设计,及形成电路逻辑后的功能验证。     

ScaffCC: Scalable compilation and analysis of quantum programs

We present ScaffCC, a scalable compilation and analysis framework based on LLVM (Lattner and Adve, 2004), which can be used for compiling quantum computing applications at the logical level. Drawing upon mature compiler technologies, we discuss similarities and differences between compilation of classical and quantum programs, and adapt our methods to optimizing the compilation time and output for the quantum case. Our work also integrates a reversible-logic synthesis tool in the compiler to facilitate coding of quantum circuits. Lastly, we present some useful quantum program analysis scenarios and discuss their implications, specifically with an elaborate discussion of timing analysis for critical path estimation. Our work focuses on bridging the gap between high-level quantum algorithm specifications and low-level physical implementations, while providing good scalability to larger and more interesting problems.