可逆逻辑电路的分类和多值量子逻辑电路的综合

Quantum information and quantum computing are the hot research in recent twenty years. This proposal focuses on the classification and decision of reversible logic circuits, and synthesis of multi-valued quantum logic circuits in quantum computing. It includes four aspects: the NP-N classification and decision of Boolean functions; the NP-NP classification and decision of reversible logic circuits; the spectrum classification and decision of reversible logic circuits; synthesis of quantum logic circuits. The classifications have widespread use in design of circuits, such as reusability of moulds, construction of reversible logic libraries, and synthesis of reversible logic circuits. Therefore, the study on these problems is quite important. First, we will study the NP-N classification and the decision of Boolean functions based on algebra; then study the NP-NP classification, spectrum classification and the related decision of reversible logic circuits through their characters; finally, by using decomposition of unitary matrix and Li algebra, combining the characters of synthesis of reversible logic circuits, we will study the universal and synthesis problems of multi-valued quantum logic circuits, design optimal synthesis algorithms and implement them.

量子信息、量子计算是近20年的研究热点。本项目研究量子计算中可逆逻辑电路的分类和判定，多值量子逻辑电路的综合。主要是针对四个方面的研究：布尔函数的NP-N分类及判定；可逆逻辑电路的NP-N分类及判定；可逆逻辑电路的谱分类及判定；多值量子逻辑电路的综合。可逆逻辑电路的分类在电路设计中有广泛应用，如模块复用，可逆逻辑门库的构建，可逆逻辑电路综合等。多值量子系统拥有更强大的量子计算和信息处理能力。因此关于这些内容的研究非常重要。本项目首先用代数方法研究布尔函数的NP-N分类及判定问题，然后结合可逆逻辑电路的特性，研究它的NP-NP分类、谱分类及相关的判定；最后利用酉矩阵分解和李代数等，结合可逆逻辑电路综合的特点，研究多值量子逻辑电路门的一致性问题和综合问题，设计并实现优化的综合算法。

我们用代数方法研究了布尔函数NP-N分类和等价判定、可逆逻辑电路NP-NP分类和等价判定、布尔函数仿射分类和等价判定、多值量子电路综合、多体量子纯态纠缠的判断与测量；研究了量子协议验证、量子进化算法、比较多个参与者私密大小的量子私密比较协议、量子同态加密协议等相关问题。研究了布尔函数的SAT算法和BDD，对SAT算法的改进和它们在生物网络中的应用。针对混合多值量子逻辑电路综合问题，提出了PMX量子门，验证了CNOT门的合成能力，实现了对广义Toffoil门的合成，设计并实现了双向的综合算法。将三值量子计算原理与遗传算法结合起来，设计了一种三值量子遗传算法，引入三值量子比特(qutrit)向量，在三值量子旋转门的作用下，促使染色体演化，从而得到了收敛性更好的随机搜索算法。我们提出了一种无约束的Hash推荐算法能够同时量化内积中的模长和相似度。此外，我们也设计了一个算法学习最优的模长编码位数。我们的方法在公开数据集上的测试结果比经典的基于Hash的推荐系统的精确度提升了11%-15%。我们提出了一个关于全体布尔函数的仿射分类的简明计算公式。通过构造一个从仿射群到排列群的同构，我们极大简化了仿射群的作用。在同等计算环境下，我们可以计算10个变量的布尔函数仿射分类。