A recursive method for synthesizing quantum/reversible quaternary parallel adder/subtractor with look-ahead carry

Multiple-valued quantum logic circuits are a promising choice for future quantum computing technology since they have several advantages over binary quantum logic circuits. Adder/subtractor is the major component of the ALU of a computer and is also used in quantum oracles. In this paper, we propose a recursive method of hand synthesis of reversible quaternary full-adder circuit using macro-level quaternary controlled gates built on the top of ion-trap realizable 1-qudit quantum gates and 2-qudit Muthukrishnan–Stroud quantum gates. Based on this quaternary full-adder circuit we propose a reversible circuit realizing quaternary parallel adder/subtractor with look-ahead carry. We also show the way of adapting the quaternary parallel adder/subtractor circuit to an encoded binary parallel adder/subtractor circuit by grouping two qubits together into quaternary qudit values.     

Controlled gates for multi-level quantum computation

Multi-level (ML) quantum logic can potentially reduce the number of inputs/outputs or quantum cells in a quantum circuit which is a limitation in current quantum technology. In this paper we propose theorems about ML-quantum and reversible logic circuits. New efficient implementations for some basic controlled ML-quantum logic gates, such as three-qudit controlled NOT, Cycle, and Self Shift gates are proposed. We also propose lemmas about r-level quantum arrays and the number of required gates for an arbitrary n-qudit ML gate. An equivalent definition of quantum cost (QC) of binary quantum gates for ML-quantum gates is introduced and QC of controlled quantum gates is calculated.     

Automatic synthesis of quaternary quantum circuits

Quaternary encoded binary circuits are more compact than their binary counterpart. Although quaternary reversible circuits are realizable, design of such circuits is still in its infancy. This work proposes a new, enhanced method of quaternary Galois field sum of products (QGFSOP) synthesis for quaternary quantum circuits. To reduce QGFSOP product terms, the algorithm makes use of 11 newly defined quaternary Galois field (QGF) expansions (for a total of 21 QGF expansions). This algorithm achieves QGFSOP minimization with the assistance of a pseudo-Kronecker Galois field decision diagram (QGFDD). This is a novel approach for QGFSOP synthesis. Finally, QGFSOP expressions are translated into quantum cost optimized quaternary quantum circuits using: (1) newly developed quaternary quantum gate realizations of controlled Feynman and Toffoli gate that are optimized in terms of quantum cost, (2) use of composite literals consisting of 1 digit and M–S gates. Performance evaluation against existing works in the literature determined that our proposed method achieves an average QGFSOP expression product term savings of 32.66 %. Also, the synthesized QGFSOP circuits were evaluated in terms of quantum cost.     

Minimal universal library for reversible circuits

Reversible logic plays an important role in quantum computing. Several papers have been recently published on universality of sets of reversible gates. However, a fundamental unsolved problem remains: “what is the minimum set of gates that are universal for n-qubit circuits without ancillae bits”. We present a library of 2 gates which is sufficient to realize all reversible circuits of n variables. It is a minimal library of gates for binary reversible logic circuits. We also analyze the complexity of the syntheses.     

扩展Toffoli门及其在多输出电路设计中的应用

用量子计算电路实现布尔逻辑运算是发展量子计算的一个重要目标。提出了量子扩展Toffoli门,及其在实现多输出逻辑电路中的转换算法。该算法将传统PLA文件的SOP积项转换到实现等价逻辑功能的量子Toffoli积项,能够用量子扩展Toffoli门实现。通过MCNC基准电路的测试结果表明,与经典PLA描述相比,用扩展Toffoli门能够更有效地描述多输出逻辑函数。     

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

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

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

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

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

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

On figures of merit in reversible and quantum logic designs

Five figures of merit including number of gates, quantum cost, number of constant inputs, number of garbage outputs, and delay are used casually in the literature to compare the performance of different reversible or quantum logic circuits. In this paper we propose new definitions and enhancements, and identify similarities between these figures of merit. We evaluate these measures to show their strength and weakness. Instead of the number of gates, we introduce the weighted number of gates, where a weighting factor is assigned to each quantum or reversible gate, based on its type, size and technology. We compare the quantum cost with weighted number of gates of a circuit and show three major differences between these measures. It is proved that it is not possible to define a universal reversible logic gate without adding constant inputs. We prove that there is an optimum value for number of constant inputs to obtain a circuit with minimum quantum cost. Some reversible logic benchmarks have been synthesized using Toffoli and Fredkin gates to obtain their optimum values of number of constant inputs. We show that the garbage outputs can also be used to decrease the quantum cost of the circuit. A new definition of delay in quantum and reversible logic circuits is proposed for music line style representation. We also propose a procedure to calculate the delay of a circuit, based on the quantum cost and the depth of the circuit. The results of this research show that to achieve a fair comparison among designs, figures of merit should be considered more thoroughly.      

Quantum ternary parallel adder/subtractor with partially-look-ahead carry

Multiple-valued quantum circuits are a promising choice for future quantum computing technology since they have several advantages over binary quantum circuits. Binary parallel adder/subtractor is central to the ALU of a classical computer and its quantum counterpart is used in oracles – the most important part that is designed for quantum algorithms. Many NP-hard problems can be solved more efficiently in quantum using Grover algorithm and its modifications when an appropriate oracle is constructed. There is therefore a need to design standard logic blocks to be used in oracles – this is similar to designing standard building blocks for classical computers. In this paper, we propose quantum realization of a ternary full-adder using macro-level ternary Feynman and Toffoli gates built on the top of ion-trap realizable ternary 1-qutrit and Muthukrishnan–Stroud gates. Our realization has several advantages over the previously reported realization. Based on this realization of ternary full-adder we propose realization of a ternary parallel adder with partially-look-ahead carry. We also show the method of using the same circuit as a ternary parallel adder/subtractor.     

三值量子基本门及其对量子Fourier变换的电路实现

理论上可以把量子基本门组合在一起来实现任何量子电路和构建可伸缩的量子计算机。但由于构建量子线路的量子基本门数量庞大,要正确控制这些量子门十分困难。因此,如何减少构建量子线路的基本门数量是一个非常重要和非常有意义的课题。提出采用三值量子态系统构建量子计算机,并给出了一组三值量子基本门的功能定义、算子矩阵和量子线路图。定义的基本门主要包括三值量子非门、三值控制非门、三值Hadamard门、三值量子交换门和三值控制CR_k门等。通过把量子Fourier变换推广到三值量子态,成功运用部分三值量子基本门构建出能实现量子Fourier变换的量子线路。通过定量分析发现,三值量子Fourier变换的线路复杂度比二值情况降低了至少50%,表明三值量子基本门在降低量子计算线路复杂度方面具有巨大优势。     

Towards quantum reversible ternary coded decimal adder

Quantum ternary logic is a promising emerging technology for the future quantum computing. Ternary reversible logic circuit design has potential advantages over the binary ones like its logarithmic reduction in the number of qudits. In reversible logic all computations are done in an invertible fashion. In this paper, we propose a new quantum reversible ternary half adder with quantum cost of only 7 and a new quantum ternary full adder with a quantum cost of only 14. We termed it QTFA. Then we propose 3-qutrit parallel adders. Two different structures are suggested: with and without input carry. Next, we propose quantum ternary coded decimal (TCD) detector circuits. Two different approaches are investigated: based on invalid numbers and based on valid numbers. Finally, we propose the quantum realization of TCD adder circuits. Also here, two approaches are discussed. Overall, the proposed reversible ternary full adder is the best between its counterparts comparing the figures of merits. The proposed 3-qutrit parallel adders are compared with the existing designs and the improvements are reported. On the other hand, this paper suggested the quantum reversible TCD adder designs for the first time. All the proposed designs are realized using macro-level ternary Toffoli gates which are built on the top of the ion-trap realizable ternary 1-qutrit gates and 2-qutrit Muthukrishnan–Stroud gates.     

混合量子遗传算法及其性能分析

首先比较了带量子门更新和群体灾变的量子算法(QA)以及加入对量子位的交叉和变异操作的量子遗传算法(QGA);然后结合量子搜索和传统遗传搜索提出了混合量子遗传算法的框架,并给出了基于二进制编码的混合量子遗传算法(BQGA)和基于实数编码的混合量子遗传算法(RQGA).基于典型问题的数值仿真和比较表明,RQGA的性能明显优于其他算法,对参数和初值具有较好的鲁棒性.     

Improved quantum ripple-carry addition circuit

A serious obstacle to large-scale quantum algorithms is the large number of elementary gates, such as the controlled-NOT gate or Toffoli gate. Herein, we present an improved linear-depth ripple-carry quantum addition circuit, which is an elementary circuit used for quantum computations. Compared with previous addition circuits costing at least two Toffoli gates for each bit of output, the proposed adder uses only a single Toffoli gate. Moreover, our circuit may be used to construct reversible circuits for modular multiplication, Cx mod M with x < M, arising as components of Shor’s algorithm. Our modular-multiplication circuits are simpler than previous constructions, and may be used as primitive circuits for quantum computations.     

Realization and synthesis of reversible functions

Reversible circuits play an important role in quantum computing. This paper studies the realization problem of reversible circuits. For any n-bit reversible function, we present a constructive synthesis algorithm. Given any n-bit reversible function, there are N distinct input patterns different from their corresponding outputs, where N≤2ⁿ, and the other (2ⁿ−N) input patterns will be the same as their outputs. We show that this circuit can be synthesized by at most 2n⋅N ‘(n−1)’-CNOT gates and 4n²⋅N NOT gates. The time and space complexities of the algorithm are Ω(n⋅4ⁿ) and Ω(n⋅2ⁿ), respectively. The computational complexity of our synthesis algorithm is exponentially lower than that of breadth-first search based synthesis algorithms.     

基于控制K次平方根非门的类Toffoli门构造方法

在量子电路综合算法中,由于非置换量子门比置换量子门具有更复杂的规则,直接使用非置换量子门会大幅度提高综合算法的复杂性,因此可先使用非置换量子门生成相应的置换量子门,然后再用这些置换量子门综合所求量子可逆逻辑电路,从而提高算法性能。本文重点研究如何用非置换量子门构造新的置换量子门,为此吸收了格雷码的思想,提出了一种高效的递归构造方法,实现使用控制非门和控制K次平方根非门(非置换量子门),快速生成最优的类Toffoli门(置换量子门)。     

Efficient experimental design of high-fidelity three-qubit quantum gates via genetic programming

We have designed efficient quantum circuits for the three-qubit Toffoli (controlled–controlled-NOT) and the Fredkin (controlled-SWAP) gate, optimized via genetic programming methods. The gates thus obtained were experimentally implemented on a three-qubit NMR quantum information processor, with a high fidelity. Toffoli and Fredkin gates in conjunction with the single-qubit Hadamard gates form a universal gate set for quantum computing and are an essential component of several quantum algorithms. Genetic algorithms are stochastic search algorithms based on the logic of natural selection and biological genetics and have been widely used for quantum information processing applications. We devised a new selection mechanism within the genetic algorithm framework to select individuals from a population. We call this mechanism the “Luck-Choose” mechanism and were able to achieve faster convergence to a solution using this mechanism, as compared to existing selection mechanisms. The optimization was performed under the constraint that the experimentally implemented pulses are of short duration and can be implemented with high fidelity. We demonstrate the advantage of our pulse sequences by comparing our results with existing experimental schemes and other numerical optimization methods.     

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

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

模糊量子遗传算法及其应用

将模糊逻辑与量子理论相结合,提出了基于模糊逻辑的量子遗传算法（FQGA）。该方法使用模糊推理机指导量子门染色体更新和变异,自适应地调整量子门旋转角和变异概率。仿真结果表明：FQGA具有全局寻优能力、收敛速度快和计算时间短等优越性。     

Optimization of Quantum Cost for Low Energy Reversible Signed/Unsigned Multiplier Using Urdhva-Tiryakbhyam Sutra

One of the elementary operations in computing systems is multiplication. Therefore, high-speed and low-power multipliers design is mandatory for efficient computing systems. In designing low-energy dissipation circuits, reversible logic is more efficient than irreversible logic circuits but at the cost of higher complexity. This paper introduces an efficient signed/unsigned 4 × 4 reversible Vedic multiplier with minimum quantum cost. The Vedic multiplier is considered fast as it generates all partial product and their sum in one step. This paper proposes two reversible Vedic multipliers with optimized quantum cost and garbage output. First, the unsigned Vedic multiplier is designed based on the Urdhava Tiryakbhyam (UT) Sutra. This multiplier consists of bitwise multiplication and adder compressors. Compared with Vedic multipliers in the literature, the proposed design has a quantum cost of 111 with a reduction of 94% compared to the previous design. It has a garbage output of 30 with optimization of the best-compared design. Second, the proposed unsigned multiplier is expanded to allow the multiplication of signed numbers as well as unsigned numbers. Two signed Vedic multipliers are presented with the aim of obtaining more optimization in performance parameters. DesignI has separate binary two’s complement (B2C) and MUX circuits, while DesignII combines binary two’s complement and MUX circuits in one circuit. DesignI shows the lowest quantum cost, 231, regarding state-of-the-art. DesignII has a quantum cost of 199, reducing to 86.14% of DesignI. The functionality of the proposed multiplier is simulated and verified using XILINX ISE 14.2.