量子计算电路模型的自动综合算法研究

量子电路是描述复杂量子计算的通用语言,量子电路是可逆的,可逆电路还广泛应用于低功耗CMOS电路、纳米技术、光计算等领域,如何根据要求自动设计出最优的量子电路,这对描述、实现与优化量子算法尤为重要。本课题在长期深入调查研究的基础上,从基于真值表、模板、Reed-Muller与群论的可逆逻辑电路综合算法出发,结合量子电路的特点,提出全新的基于Hash表与基于扑拓变换的3量子与4量子电路的快速综合算法;结合群论,研究量子电路的分解算法,旨在高效设计大规模优化的量子电路;提出基于新型量子逻辑门库的最优NCV量子电路快速综合算法,为基于量子非逻辑门的综合算法提出一种通用高效的新方法;研究新型量子门的自动构造算法,以发现更多更优的新型量子门;研究量子计算中与量子通信、量子测量相关复杂量子电路的自动综合算法。为客观分析、比较与优化各综合算法,构建综合算法统一的运行、测试、分析与辅助设计的通用实验平台。

本项目对量子逻辑电路的综合算法及相关理论进行了深入研究,主要成果包括：.(1) 提出以最小长度综合四量子电路快速算法。构造置换的最短编码,拓扑无损压缩 量子最优电路占用的存储空间近2*n!倍,对已生成的最优电路双向级联,可使用多种量子门,采用最小长度标准,以极高效率生成较长的四量子电路,如率先生成基于NCT量子门库 (NOT,CNOT和Toffoli)的全部前8层电路,还可快速综合任意长度不超过16的最优电路。.(2) 提出以最小代价综合四量子电路的高效算法。构造置换的最短编码,高效的拓扑压缩和灵活的数据结构,节省内存使用。1)使用GT量子门库(NCT 和 Toffoli-4 门)以最小长度综合全部前8层四量子电路,存储于Hash表中。2)对Hash表进行归并与分拆,生成一个更长的Hash表,以提高算法性能。3)使用GTP量子门库 (GT门库, Peres和Peres逆门),以最小量子代价重新综合Hash表中全部量子电路。4)通过各电路量子代价的比较,算法能快速收敛于任一最小代价的四量子可逆逻辑电路。综合目前相关测试函数,与已知最优结果比较,运行时间与电路的量子代价平均分别减少了99.95% 和18.2%。.(3) 提出基于新型量子逻辑门库的最优NCV(NOT、CNOT、CV和CV+门)三量子电路快速综合算法。这为解决量子非逻辑门综合问题提出通用高效的方法。目前仅少数算法能用NCV门库综合三量子逻辑电路,方法是将该问题化简为四值逻辑综合问题。首次提出用NCV门构造新型量子逻辑门库,该库与NCV门库在综合最优的三量子逻辑电路上完全等价,因此又将四值逻辑综合问题简化为更易求解的二值逻辑综合问题,再使用基于Hash表的综合算法,生成全部最优三量子逻辑电路,以最小代价综合电路的平均速度是目前最好结果的127倍。.(4) 以上方法中,用最小的代价构造新型量子逻辑门尤为重要。提出两种通用方法,分别使用控制非门与控制平方根非门和使用控制非门与控制K次方根非门,其中k=4,8,16…,快速直接构造新型最优的量子逻辑门。首次提出了平方根平方根非门的概念,并首次给出其矩阵表示。在4量子电路综合实验中,运用该方法构造全部新型量子门,并综合目前所有相关的测试函数,有近一半的电路比运用GTP门库综合的结果更优。我们给出了两种方法详细的数学证明,为当前综合算法提供了新的思路。