Auxiliary qubit selection: a physical synthesis technique for quantum circuits

Quantum circuit design flow consists of two main tasks: synthesis and physical design. Addressing the limitations imposed on optimization of the quantum circuit objectives because of no information sharing between synthesis and physical design processes, we introduced the concept of “physical synthesis” for quantum circuit flow and proposed a technique for it. Following that concept, in this paper we propose a new technique for physical synthesis using auxiliary qubit selection to improve the latency of quantum circuits. Moreover, it will be shown that the auxiliary qubit selection technique can be seamlessly integrated into the previously introduced physical synthesis flow. Our experimental results show that the proposed technique decreases the average latency objective of quantum circuits by about 11% for the attempted benchmarks.     

Quantum circuit physical design methodology with emphasis on physical synthesis

In our previous works, we have introduced the concept of “physical synthesis” as a method to consider the mutual effects of quantum circuit synthesis and physical design. While physical synthesis can involve various techniques to improve the characteristics of the resulting quantum circuit, we have proposed two techniques (namely gate exchanging and auxiliary qubit selection) to demonstrate the effectiveness of the physical synthesis. However, the previous contributions focused mainly on the physical synthesis concept, and the techniques were proposed only as a proof of concept. In this paper, we propose a methodological framework for physical synthesis that involves all previously proposed techniques along with a newly introduced one (called auxiliary qubit insertion). We will show that the entire flow can be seen as one monolithic methodology. The proposed methodology is analyzed using a large set of benchmarks. Experimental results show that the proposed methodology decreases the average latency of quantum circuits by about 36.81 % for the attempted benchmarks.     

Synthesis of quantum circuits for linear nearest neighbor architectures

While a couple of impressive quantum technologies have been proposed, they have several intrinsic limitations which must be considered by circuit designers to produce realizable circuits. Limited interaction distance between gate qubits is one of the most common limitations. In this paper, we suggest extensions of the existing synthesis flow aimed to realize circuits for quantum architectures with linear nearest neighbor interaction. To this end, a template matching optimization, an exact synthesis approach, and two reordering strategies are introduced. The proposed methods are combined as an integrated synthesis flow. Experiments show that by using the suggested flow, quantum cost can be improved by more than 50% on average.     

Design of a universal logic block for fault-tolerant realization of any logic operation in trapped-ion quantum circuits

This paper presents a physical mapping tool for quantum circuits, which generates the optimal universal logic block (ULB) that can, on average, perform any logical fault-tolerant (FT) quantum operations with the minimum latency. The operation scheduling, placement, and qubit routing problems tackled by the quantum physical mapper are highly dependent on one another. More precisely, the scheduling solution affects the quality of the achievable placement solution due to resource pressures that may be created as a result of operation scheduling, whereas the operation placement and qubit routing solutions influence the scheduling solution due to resulting distances between predecessor and current operations, which in turn determines routing latencies. The proposed flow for the quantum physical mapper captures these dependencies by applying (1) a loose scheduling step, which transforms an initial quantum data flow graph into one that explicitly captures the no-cloning theorem of the quantum computing and then performs instruction scheduling based on a modified force-directed scheduling approach to minimize the resource contention and quantum circuit latency, (2) a placement step, which uses timing-driven instruction placement to minimize the approximate routing latencies while making iterative calls to the aforesaid force-directed scheduler to correct scheduling levels of quantum operations as needed, and (3) a routing step that finds dynamic values of routing latencies for the qubits. In addition to the quantum physical mapper, an approach is presented to determine the single best ULB size for a target quantum circuit by examining the latency of different FT quantum operations mapped onto different ULB sizes and using information about the occurrence frequency of operations on critical paths of the target quantum algorithm to weigh these latencies. Experimental results show an average latency reduction of about 40 % compared to previous work.     

Novel low power reversible binary incrementer design using quantum-dot cellular automata

This paper demonstrates the design of n-bit novel low power reversible binary incrementer in Quantum-Dot Cellular Automata (QCA). The comparison of quantum cost in quantum gate based approach and in QCA based design agreed the cost efficient implementation in QCA. The power dissipation by proposed circuit is estimated, which shows that the circuit dissipates very low heat energy suitable for reversible computing. All the circuits are evaluated in terms of logic gates, circuit density and latency that confirm the faster operating speed at nano scale. The reliability of the circuit under thermal randomness is explored which describes the efficiency of the circuit.     

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

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

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.     

量子可逆逻辑电路综合的快速算法研究

可逆逻辑有许多应用,尤其在量子计算领域,量子可逆逻辑电路是构建量子计算机的基本单元,量子可逆逻辑电路综合就是根据电路功能,以较小的量子代价自动构造量子可逆逻辑电路.文中结合可逆逻辑电路综合的多种算法,提出了一种新颖高效的算法,自动构造正极性Reed-Muller展开式(RM),在生成量子可逆逻辑电路的解空间树上,采用总体层次遍历,局部深度搜索,借鉴模板优化技术,构造限界函数快速剪去无解或非最优解的分枝,优先探测RM中的因子,以极高的效率生成最优电路.以国际公认的3变量可逆函数测试标准,该算法不仅能够生成全部最优电路,而且运行速度远远超过同类算法.     

Considering nearest neighbor constraints of quantum circuits at the reversible circuit level

Since many underlying quantum algorithms include a Boolean component, synthesis of the respective circuits is often conducted by a two-stage procedure: First, a reversible circuit realizing the Boolean component is generated. Afterwards, this circuit is mapped into a respective quantum gate cascade. In addition, recent physical accomplishments have led to further issues to be considered, e.g. nearest neighbor constraints. However, due to the lack of proper metrics, these constraints usually have been addressed at the quantum circuit level only. In this paper, we present an approach that allows the consideration of nearest neighbor constraints already at the reversible circuit level. For this purpose, a recently introduced gate library is assumed for which a proper metric is proposed. By means of an optimization approach, the applicability of the proposed scheme is illustrated.     

使用逻辑锥分割的组合电路等价性验证

为了提高等价性验证在数字电路中的验证效率,提出一种逻辑锥分割和可满足性相结合的方法。通过划分规则把参照电路和实现电路划分成若干个逻辑锥,利用匹配技术对两者的逻辑锥进行匹配,将已匹配的两个逻辑锥的输出用一个异或门连接,从而得到Miter电路,将该结构转换成相应的合取范式,用可满足性引擎来验证Miter电路是否功能等价。在ISCAS’85基准电路的实验结果表明该方法的可行性。     

Heuristic methods to use <Emphasis Type="Italic">don’t cares</Emphasis> in automated design of reversible and quantum logic circuits

This paper introduces a broad concept of don’t cares in reversible and quantum logic circuits. Don’t cares are classified into three categories: inputs, outputs, and conditions. Some heuristic methods to use these don’t cares, when an optimization algorithm such as genetic algorithm is used, are also presented. We show that, these methods decrease the quantum cost of the reversible or quantum logic circuit, as well as the design time of the resulting circuit. Some examples are also synthesized and optimized using the don’t care concept and genetic algorithms.      

Designing new ternary reversible subtractor circuits

The reducing of the width of quantum reversible circuits makes multiple-valued reversible logic a very promising research area. Ternary logic is one of the most popular types of multiple-valued reversible logic, along with the Subtractor, which is among the major components of the ALU of a classical computer and complex hardware. In this paper the authors will be presenting an improved design of a ternary reversible half subtractor circuit. The authors shall compare the improved design with the existing designs and shall highlight the improvements made after which the authors will propose a new ternary reversible full subtractor circuit. Ternary Shift gates and ternary Muthukrishnan–Stroud gates were used to build such newly designed complex circuits and it is believed that the proposed designs can be used in ternary quantum computers. The minimization of the number of constant inputs and garbage outputs, hardware complexity, quantum cost and delay time is an important issue in reversible logic design. In this study a significant improvement as compared to the existing designs has been achieved in as such that with the reduction in the number of ternary shift and Muthukrishnan-Stroud gates used the authors have produced ternary subtractor circuits.     

Depth-optimized reversible circuit synthesis

In this paper, simultaneous reduction of circuit depth and synthesis cost of reversible circuits in quantum technologies with limited interaction is addressed. We developed a cycle-based synthesis algorithm which uses negative controls and limited distance between gate lines. To improve circuit depth, a new parallel structure is introduced in which before synthesis a set of disjoint cycles are extracted from the input specification and distributed into some subsets. The cycles of each subset are synthesized independently on different sets of ancillae. Accordingly, each disjoint set can be synthesized by different synthesis methods. Our analysis shows that the best worst-case synthesis cost of reversible circuits in the linear nearest neighbor architecture is improved by the proposed approach. Our experimental results reveal the effectiveness of the proposed approach to reduce cost and circuit depth for several benchmarks.     

Reversible binary subtractor design using quantum dot-cellular automata

In the field of nanotechnology, quantum dot-cellular automata (QCA) is the promising archetype that can provide an alternative solution to conventional complementary metal oxide semiconductor (CMOS) circuit. QCA has high device density, high operating speed, and extremely low power consumption. Reversible logic has widespread applications in QCA. Researchers have explored several designs of QCA-based reversible logic circuits, but still not much work has been reported on QCA-based reversible binary subtractors. The low power dissipation and high circuit density of QCA pledge the energy-efficient design of logic circuit at a nano-scale level. However, the necessity of too many logic gates and detrimental garbage outputs may limit the functionality of a QCA-based logic circuit. In this paper we describe the design and implementation of a DG gate in QCA. The universal nature of the DG gate has been established. The QCA building block of the DG gate is used to achieve new reversible binary subtractors. The proposed reversible subtractors have low quantum cost and garbage outputs compared to the existing reversible subtractors. The proposed circuits are designed and simulated using QCA Designer-2.0.3.     

Novel designs of nanometric parity preserving reversible compressor

Reversible logic is a new field of study that has applications in optical information processing, low power CMOS design, DNA computing, bioinformatics, and nanotechnology. Low power consumption is a basic issue in VLSI circuits today. To prevent the distribution of errors in the quantum circuit, the reversible logic gates must be converted into fault-tolerant quantum operations. Parity preserving is used to realize fault tolerant in this circuits. This paper proposes a new parity preserving reversible gate. We named it NPPG gate. The most significant aspect of the NPPG gate is that it can be used to produce parity preserving reversible full adder circuit. The proposed parity preserving reversible full adder using NPPG gate is more efficient than the existing designs in term of quantum cost and it is optimized in terms of number of constant inputs and garbage outputs. Compressors are of importance in VLSI and digital signal processing applications. Effective VLSI compressors reduce the impact of carry propagation of arithmetic operations. They are built from the full adder blocks. We also proposed three new approaches of parity preservation reversible 4:2 compressor circuits. The third design is better than the previous two in terms of evaluation parameters. The important contributions have been made in the literature toward the design of reversible 4:2 compressor circuits; however, there are not efforts toward the design of parity preservation reversible 4:2 compressor circuits. All the scales are in the nanometric criteria.     

Controllable decoding for automated analog circuit structure design

The decoding scheme is a major problem in automated analog circuit topology synthesis since decoding schemes bias synthesized circuit structures. However, the proper decoding scheme varies depending on the method to realize a given function. In this paper, a controllable decoding scheme is proposed in which the method to realize a function is controlled by a set of prototype circuits. Thus, the system can generate different types of analog circuits in a unified method. The prototype circuits are designed by a human and suggested to the system as hints of configurations of new analog circuits to be synthesized by the system. In the synthesis process, the information on circuit connections is stored as sub-circuits extracted from the prototype circuits. A genetic algorithm is then used to search for an optimum combination of the sub-circuits that achieves the desired electronic specifications. The combinations of sub-circuits are generated with a proposed technique where the terminals of the sub-circuits are shared. The capabilities of the proposed method are demonstrated through synthesis examples of a cubing circuit synthesis as a current-mode design and a logic circuit synthesis as a voltage-mode.The authors would like to thank the reviewers for their valuable comments. The authors would like to express special thank to Dr. Andrew M. Abo for English corrections.