四量子可逆逻辑电路快速综合算法

Fast Algorithms for 4-qubit Reversible Logic Circuits Synthesis

量子可逆逻辑电路综合是以较小量子代价自动构造所求量子可逆逻辑电路.本文提出了一种新颖高效的4量子电路综合算法,巧妙构造置换的最短编码,通过对量子电路进行特定拓扑变换,无损压缩n量子最优电路占用内存空间近2×n!倍,通过对已生成最优电路的双向级联,可使用多种量子门,采用最小长度标准,以极高效率生成较长的4量子电路,如率先生成基于控制非门、非门、Toffoli门库的全部前8层共3120218828个电路,还可快速综合任意长度不超过16的最优电路,并对4量子标准测试电路进行快速且全面的优化.

Synthesis of quantum reversible logic circuits means to automatically construct desired quantum reversible logic circuit with minimal quantum cost. We present a novel and efficient algorithm which can construct almost all optimal 4-qubit reversible logic circuits with various types of gates and minimum length cost based on constructing the shortest coding and the specific topological compression, whose lossless compression ratios of the space of n-qubit circuits is near2 × n!. We firstly have created all 3120218828 optimal 4-qubit circuits whose length is less than 9 for the Controlled-Not gate, NOT gate and Toffoli gate library, and our method can achieve 16 steps through cascading created circuits. Our algorithm can not only synthesizes all the 4-qubit bench- mark circuits, but also runs extremely fast.