08-16-2017, 10:48 PM
[attachment=16131]
Introduction
In recent past reversible computing has emerged as a promising technology having applica tions in low power CMOS [1], nanotechnology [2], optical computing [3], DNA computing [4], quantum computing [5] etc. To establish the relevance of reversible and quantum computing it seems appropriate to note that the VLSI industry is moving at high speed towards minia turization. With miniaturization it faces two issues: i) A considerable amount of energy gets dissipated in VLSI circuits and ii) the size of the transistors are approaching the quantum limits where tunnelling and other quantum phenomena are likely to appear. Thus we need a superior technology that can circumvent these problems. Before we talk on the solution of the first problem we would like to say few words about the cause of power dissipation. It is well known that most of the commonly used classical gates are irreversible (except NOT gate and IDENTITY gate which are reversible) and while they operate, erasure of information happens as the number of bits in the output is less than the number of bits in the input. For example, we can note that the common irreversible gates like AND, OR, NAND, NOR erase one bit of information on every operation. Landauer's principle [6] states that any logically irreversible manipulation of information, such as the erasure of a bit or the merging of two computational paths, must be accompanied by a corresponding entropy increase (and consequently energy loss) in non-information bearing degrees of freedom of the information processing apparatus or it's environment. Consequently each bit of lost information will lead to the release of at least kTln2 amount of heat. On the other hand Moore's law states that the number of transistors in a chip gets doubled in every 18 months. Therefore, if we continue to design chips with the help of conventional irreversible logic gates then the amount of power loss will continue to increase. The idea of reversible logic originated from this problem and in the first half of 1970s Bennet and others introduced the idea of reversible computation and reversible logic to circumvent the problem of power loss present in irreversible logic computation. Since quantum mechanics is essentially reversible, quantum mechanical processes appeared as a good candidate to construct reversible logic gates and these gates are known as quantum logic gates. After the introduction of the idea of quantum computation it has also been seen that there exist some protocols and algorithms [5] that establish quantum computing as a superior future technology. For example, the quantum cryptographic protocol guarantee perfectly secure communications, quantum communication protocols like quantum teleporta-tion and dense coding are not possible in classical world, the Shor's algorithm is faster than the best known classical algorithm for factoring, the Grover's algorithm for unsorted data search runs quadratically faster than the best possible classical algorithm for the same task. Implementation of these quantum algorithms and quantum communication protocols require quantum circuits. Consequently a rigorous study of various aspects of quantum circuit is important for the clear understanding of the existing applications of quantum circuit and to propose new applications. Absence of such a rigorous study motivated us to systematically study the synthesis, optimization and testing aspects of quantum and reversible circuits. The study includes reversible classical circuits as they form a subset of quantum circuits.
In quantum computing we use quantum gate, where qubit is used as an input state and in reversible computing we use classical reversible gate, where bit is used as an input state. The difference between a classical reversible gate and a quantum gate is that the classical reversible gate can not handle superposition of states (qubit). For example, ('NOT gate can be achieved both in classical and quantum domains but the HADAMARD gate can be achieved in quantum domain only. Therefore, classical reversible circuits are only a subset of quantum circuits but from the construction point of view they are easy to build. Further, any protocol designed for optimization of particular parameter related to quantum circuits will also be valid for classical reversible circuits. There is no contradiction between these views as long as we are clear about limitations and scope of quantum and classical reversible circuits. It would be justified to note that often classical reversible circuits are called as reversible circuits. Although quantum circuits are also reversible, unless a reversible circuit is specifically mentioned as quantum circuit it would mean a classical reversible circuit in the present work. Further we would like to note that the words synthesis, optimization and testing are used here with the usual meaning. In the literature of reversible and quantum computing, synthesis of a circuit means that a new design is proposed, optimization means that a systematic procedure to reduce a particular cost metric which is used to quantitatively measure the quality of a circuit. Testing is associated with a protocol that can detect faults in the circuit.
The present study aims to answer certain unanswered or vaguely answered questions re lated to reversible and quantum circuits and report some new observations on synthesis, optimization and testing aspects of reversible circuits and quantum circuits in the proposed thesis. Table 1 summarizes the results obtained in that direction and the works reported are published in [7]-[13]. The proposed thesis will consist of 8 Chapters. Chapter 1 provides an introduction to the subject. Chapter 2 provides an algorithm for optimization of quantum cost in reversible circuits and the results are reported in [7]. Chapter 3 discusses synthesis of novel reversible multiplier design and the results are summarized in [8]. Chapter 4 describes some new designs of reversible sequential elements and the major content of this work is re ported in our publication [9]. Chapter 5 elaborates reversible hardware cryptography designs and this work is at present communicated in [10]. Chapter 6 discusses some distinguishing features of quantum fault and a general methodology for detection of functional faults in a quantum circuit. This work is published in [11]. Further, in Chapter 7, we have provided an efficient scheme for perfect and controlled teleportation of n-qubit non-maximally entangled states of generalized Bell-type and the work is included in [12, 13]. Finally Chapter 8 is dedicated to the conclusions and scope of future work.
In this synopsis we provide a brief sketch of the proposed doctoral thesis. To do so, all the work in the proposed thesis is categorized into 7 sections of this synopsis including Section 1 which is the introduction to the subject. Section 2 includes the work of Chapter 3-Chapter 5, which pertains to synthesis of reversible circuits, Section 3 summarizes Chapter 2 which describes our work on optimization of quantum cost of reversible and quantum circuits. Section 4 incorporates the work of Chapter 6 which is related to the testing of the reversible and quantum circuits. In Section 5, we have described our work reported in Chapter 7 towards the synthesis of quantum teleportation circuits. Further, Section 6 briefly discusses the conclusions of the present study and finally Section 7 is dedicated to the scope of future works.
2 Synthesis of reversible circuits
Synthesis of reversible circuits require reversible gates. In our work we have taken NOT universal gate library which consists of NOT, ('NOT and TOFFOLI gates. There are two main approaches of synthesis of reversible circuits. In the first approach, the irreversible gates present in a circuit are replaced by their corresponding reversible counter parts (but in this case we need an existing irreversible circuit). In the other approach, which is also called truth table extension method, we start with an irreversible truth table, then extend it to an augmented truth table and thereafter we use a synthesis approach to obtain a reversible circuit. There are several heuristic methods for designing of a reversible circuit for example, the transformation-based synthesis [15] and references there in. We have followed the latter approach and have used the transformation-based synthesis algorithm [15] to implement the reversible function. The philosophy of the transformation-based algorithm is to cascade some reversible gates such that the output of the truth table is equal to the input. In thesis we have described the procedure in detail. However it is worthy to note that none of these heuristic methods provide minimal reversible circuit (in terms of gate count which is also called circuit cost) for a reversible function. Recently an exact synthesis algorithm is introduced by Grofie et al [16] that provides minimal realization for a given function and thus providing lower bounds for heuristic methods and minimal circuit as "basic blocks" for larger circuits. Grofie et al. [16] have shown that boolean satisfiability (SAT) can be used to exactly optimize the circuit cost of a reversible circuit. This algorithm is incorporated in an excellent toolkit called RevKit [17]. Here it would be appropriate to note that the RevKit is recently introduced and most of the circuits reported in the present thesis were designed before we got exposed to RevKit, however, we have verified the minimality of all such circuits by using RevKit.
Multiplier circuits are of special importance because of the fact that they are the integral component of every computer system, cellular phone and most digital audio/video devices etc. It is important for every processor to have high speed multiplier. We have proposed a 4 x 4 reversible bit multiplier circuit design which is based on reversible logic and has reversible cells as it's building block with minimum number of garbage bits, minimum gate count (circuit cost), optimal quantum cost and optimal delay. We have generalized the results for n x n bits also. We have shown that the gates proposed in literature for designing of a component of multiplier circuit (full adder) for example HNG, TSG and MKG are neither unique nor special and many such 4x4 gates may be proposed which can also perform all boolean operations. As example, four such new gates are introduced in the proposed thesis.
Till now most of the works in reversible circuits have been reported in combinatorial circuits but it is interesting to see what happens in sequential cases. We have designed novel sequential functional blocks namely reversible registers and counters with minimal circuit cost, optimal quantum cost and optimal delay, these designs play an important role in the hardware designing, precisely in designing of reversible memory circuits. To be precise, we have proposed reversible SR latch, D latch, JK latch and T latch and their corresponding gated latches. All the circuits have minimal circuit cost as we have verified from RevKit and also have been optimized with the help of existing local optimization algorithms (e.g. template matching) to obtain the optimal quantum cost. We have also discussed the design process in the thesis. For a fair comparison, the optimized sequential circuits are compared with the earlier proposals on the same measures after converting the non NCT1 circuits into equivalent NCT circuits. The results obtained show that the proposed designs are optimal.
lrThe gates from NCT library are NOT, CNOT and TOFFOLI.
Security is of prime importance and cryptographic protocols are extensively used in se curity purposes thus it needs to be robust against numerous attacks. We are interested in protection of crypto processor against power analysis attacks such as the Differential power analysis (DPA) attack which is used to attack the smart card. Reversible logic is a good candidate to defend the power analysis attack as it ideally does not dissipate any heat. In lit erature, different designs for reversible hardware cryptography have been proposed but they have been implemented using complex gate libraries. Further few theorems, which claim to define lower bound on quantum cost of arithmetic logic unit (ALU) are reported in [18]. We have proposed novel designs for reversible ALU of a crypto processor which have been im plemented in standard gate library and the reported quantum cost are better than the lower bounds reported in [18]. Further, we have calculated delay of the proposed designs. We have verified that our proposed designs are minimal with respect to gate count i.e. circuit cost by simulating it in RevKit.
3 Optimization of reversible and quantum circuits
There exist several algorithms for synthesis of reversible circuits [15] and quantum circuits [19]. But these algorithms and others do not provide an unique output. Therefore, a quan titative measure of the quality of a circuit is required. Some of the important quantitative measures are circuit cost, number of garbage bits, quantum cost and delay. Now once a reversible circuit is designed it is required that the circuit should be optimized or minimized in terms of quantum cost, number of garbage bits, delay and number of gates used (again it will depend on the choice of gate library) which is also called circuit cost.
There does not exist any single convention about the choice of gate library. We have shown that it is important to define an unique gate library for comparison of circuit cost. If we have two circuits for the same computational task and both are made using the gates from the same gate library then the one having lesser circuit cost is considered to be the better circuit. Consequently, comparison of two architectures proposed for the same purpose can not always be compared. The complexity of gates may not be same in two different implementations of quantum circuits. For example, it may be easy to build an arbitrary gate 'A' in Nuclear magnetic resonance technology but it may not be that easy in Superconductivity based technology. We have systematically addressed these issues in the thesis.
It is often observed that reduction of circuit cost leads to increase in garbage bits and reduction of quantum cost leads to increase in circuit cost. Keeping this in mind we have introduced a new parameter called Total cost (TC) [9] which is the sum of circuit cost, number of garbage bits and quantum cost.
Quantum cost is an important cost metric in designing of reversible circuits. It is the total number of elementary gates required to realize a reversible function. A simple minded systematic approach to optimize the quantum cost of reversible circuits is proposed in Maslov et al. [20]. They have used optimization approach such as template matching for the same. These facts have motivated us to design an algorithm for optimization of quantum cost [7] as presented in the thesis. By implementing this algorithm, reported quantum costs for reversible circuits from various sources, are compared with the existing results. It is found that the reported quantum cost is optimal in all the cases. In the thesis we have also provided optimized quantum cost for reversible multiplier circuits, reversible sequential circuits and ALU of hardware cryptography. We have not described them in this section as we have already mentioned them in context of synthesis (see Section 2).
4 Testing of reversible and quantum circuits
Test vector is a well defined idea in VLSI, it can also be extended to reversible circuits and can be used to find the repeat gate fault, missing gate fault, stuck at 0 and stuck 1 fault etc. We have observed that the classical notion of test vector fails in case of quantum circuits which involve probabilistic gates (e.g. HADAMARD gate). The distinguishing nature of quantum fault appears only when we consider probabilistic gates and allow superposition states to be present in qubit line. We have followed an independent approach and reported several new and distinguishing features of quantum fault. We have shown that if probabilistic gate like HADAMARD gate is taken then the classical notion of test vector fails. A detail study along this line yield following new observation/results:
In a quantum circuit, test set for stuck at fault, is different from missing gate fault.
An odd number of repeated gate fault in an optimized circuit is equivalent to missing gate fault. In case of an even number of repeated gate fault it will not be detected. In literature this condition for equivalence was not given clearly.
We have provided a general methodology for detection of quantum fault and an al gorithm to find test vectors for m number of gates (single and two qubit gate) in n qubit lines.
We have also provided test vectors for existing reversible/quantum circuits for example, half adder, teleportation, entanglement, de-entanglement, distributed measurement contain ing qudits and shor code.
Time complexity of fault detection is calculated.
We conclude that since it has a linear relation with the number of fault to be considered and the total number of stuck at fault is infinite so we can not detect all faults in finite time but the methodology will work for all practical purposes where the number of fault is finite because of the physical restrictions.
Introduction
In recent past reversible computing has emerged as a promising technology having applica tions in low power CMOS [1], nanotechnology [2], optical computing [3], DNA computing [4], quantum computing [5] etc. To establish the relevance of reversible and quantum computing it seems appropriate to note that the VLSI industry is moving at high speed towards minia turization. With miniaturization it faces two issues: i) A considerable amount of energy gets dissipated in VLSI circuits and ii) the size of the transistors are approaching the quantum limits where tunnelling and other quantum phenomena are likely to appear. Thus we need a superior technology that can circumvent these problems. Before we talk on the solution of the first problem we would like to say few words about the cause of power dissipation. It is well known that most of the commonly used classical gates are irreversible (except NOT gate and IDENTITY gate which are reversible) and while they operate, erasure of information happens as the number of bits in the output is less than the number of bits in the input. For example, we can note that the common irreversible gates like AND, OR, NAND, NOR erase one bit of information on every operation. Landauer's principle [6] states that any logically irreversible manipulation of information, such as the erasure of a bit or the merging of two computational paths, must be accompanied by a corresponding entropy increase (and consequently energy loss) in non-information bearing degrees of freedom of the information processing apparatus or it's environment. Consequently each bit of lost information will lead to the release of at least kTln2 amount of heat. On the other hand Moore's law states that the number of transistors in a chip gets doubled in every 18 months. Therefore, if we continue to design chips with the help of conventional irreversible logic gates then the amount of power loss will continue to increase. The idea of reversible logic originated from this problem and in the first half of 1970s Bennet and others introduced the idea of reversible computation and reversible logic to circumvent the problem of power loss present in irreversible logic computation. Since quantum mechanics is essentially reversible, quantum mechanical processes appeared as a good candidate to construct reversible logic gates and these gates are known as quantum logic gates. After the introduction of the idea of quantum computation it has also been seen that there exist some protocols and algorithms [5] that establish quantum computing as a superior future technology. For example, the quantum cryptographic protocol guarantee perfectly secure communications, quantum communication protocols like quantum teleporta-tion and dense coding are not possible in classical world, the Shor's algorithm is faster than the best known classical algorithm for factoring, the Grover's algorithm for unsorted data search runs quadratically faster than the best possible classical algorithm for the same task. Implementation of these quantum algorithms and quantum communication protocols require quantum circuits. Consequently a rigorous study of various aspects of quantum circuit is important for the clear understanding of the existing applications of quantum circuit and to propose new applications. Absence of such a rigorous study motivated us to systematically study the synthesis, optimization and testing aspects of quantum and reversible circuits. The study includes reversible classical circuits as they form a subset of quantum circuits.
In quantum computing we use quantum gate, where qubit is used as an input state and in reversible computing we use classical reversible gate, where bit is used as an input state. The difference between a classical reversible gate and a quantum gate is that the classical reversible gate can not handle superposition of states (qubit). For example, ('NOT gate can be achieved both in classical and quantum domains but the HADAMARD gate can be achieved in quantum domain only. Therefore, classical reversible circuits are only a subset of quantum circuits but from the construction point of view they are easy to build. Further, any protocol designed for optimization of particular parameter related to quantum circuits will also be valid for classical reversible circuits. There is no contradiction between these views as long as we are clear about limitations and scope of quantum and classical reversible circuits. It would be justified to note that often classical reversible circuits are called as reversible circuits. Although quantum circuits are also reversible, unless a reversible circuit is specifically mentioned as quantum circuit it would mean a classical reversible circuit in the present work. Further we would like to note that the words synthesis, optimization and testing are used here with the usual meaning. In the literature of reversible and quantum computing, synthesis of a circuit means that a new design is proposed, optimization means that a systematic procedure to reduce a particular cost metric which is used to quantitatively measure the quality of a circuit. Testing is associated with a protocol that can detect faults in the circuit.
The present study aims to answer certain unanswered or vaguely answered questions re lated to reversible and quantum circuits and report some new observations on synthesis, optimization and testing aspects of reversible circuits and quantum circuits in the proposed thesis. Table 1 summarizes the results obtained in that direction and the works reported are published in [7]-[13]. The proposed thesis will consist of 8 Chapters. Chapter 1 provides an introduction to the subject. Chapter 2 provides an algorithm for optimization of quantum cost in reversible circuits and the results are reported in [7]. Chapter 3 discusses synthesis of novel reversible multiplier design and the results are summarized in [8]. Chapter 4 describes some new designs of reversible sequential elements and the major content of this work is re ported in our publication [9]. Chapter 5 elaborates reversible hardware cryptography designs and this work is at present communicated in [10]. Chapter 6 discusses some distinguishing features of quantum fault and a general methodology for detection of functional faults in a quantum circuit. This work is published in [11]. Further, in Chapter 7, we have provided an efficient scheme for perfect and controlled teleportation of n-qubit non-maximally entangled states of generalized Bell-type and the work is included in [12, 13]. Finally Chapter 8 is dedicated to the conclusions and scope of future work.
In this synopsis we provide a brief sketch of the proposed doctoral thesis. To do so, all the work in the proposed thesis is categorized into 7 sections of this synopsis including Section 1 which is the introduction to the subject. Section 2 includes the work of Chapter 3-Chapter 5, which pertains to synthesis of reversible circuits, Section 3 summarizes Chapter 2 which describes our work on optimization of quantum cost of reversible and quantum circuits. Section 4 incorporates the work of Chapter 6 which is related to the testing of the reversible and quantum circuits. In Section 5, we have described our work reported in Chapter 7 towards the synthesis of quantum teleportation circuits. Further, Section 6 briefly discusses the conclusions of the present study and finally Section 7 is dedicated to the scope of future works.
2 Synthesis of reversible circuits
Synthesis of reversible circuits require reversible gates. In our work we have taken NOT universal gate library which consists of NOT, ('NOT and TOFFOLI gates. There are two main approaches of synthesis of reversible circuits. In the first approach, the irreversible gates present in a circuit are replaced by their corresponding reversible counter parts (but in this case we need an existing irreversible circuit). In the other approach, which is also called truth table extension method, we start with an irreversible truth table, then extend it to an augmented truth table and thereafter we use a synthesis approach to obtain a reversible circuit. There are several heuristic methods for designing of a reversible circuit for example, the transformation-based synthesis [15] and references there in. We have followed the latter approach and have used the transformation-based synthesis algorithm [15] to implement the reversible function. The philosophy of the transformation-based algorithm is to cascade some reversible gates such that the output of the truth table is equal to the input. In thesis we have described the procedure in detail. However it is worthy to note that none of these heuristic methods provide minimal reversible circuit (in terms of gate count which is also called circuit cost) for a reversible function. Recently an exact synthesis algorithm is introduced by Grofie et al [16] that provides minimal realization for a given function and thus providing lower bounds for heuristic methods and minimal circuit as "basic blocks" for larger circuits. Grofie et al. [16] have shown that boolean satisfiability (SAT) can be used to exactly optimize the circuit cost of a reversible circuit. This algorithm is incorporated in an excellent toolkit called RevKit [17]. Here it would be appropriate to note that the RevKit is recently introduced and most of the circuits reported in the present thesis were designed before we got exposed to RevKit, however, we have verified the minimality of all such circuits by using RevKit.
Multiplier circuits are of special importance because of the fact that they are the integral component of every computer system, cellular phone and most digital audio/video devices etc. It is important for every processor to have high speed multiplier. We have proposed a 4 x 4 reversible bit multiplier circuit design which is based on reversible logic and has reversible cells as it's building block with minimum number of garbage bits, minimum gate count (circuit cost), optimal quantum cost and optimal delay. We have generalized the results for n x n bits also. We have shown that the gates proposed in literature for designing of a component of multiplier circuit (full adder) for example HNG, TSG and MKG are neither unique nor special and many such 4x4 gates may be proposed which can also perform all boolean operations. As example, four such new gates are introduced in the proposed thesis.
Till now most of the works in reversible circuits have been reported in combinatorial circuits but it is interesting to see what happens in sequential cases. We have designed novel sequential functional blocks namely reversible registers and counters with minimal circuit cost, optimal quantum cost and optimal delay, these designs play an important role in the hardware designing, precisely in designing of reversible memory circuits. To be precise, we have proposed reversible SR latch, D latch, JK latch and T latch and their corresponding gated latches. All the circuits have minimal circuit cost as we have verified from RevKit and also have been optimized with the help of existing local optimization algorithms (e.g. template matching) to obtain the optimal quantum cost. We have also discussed the design process in the thesis. For a fair comparison, the optimized sequential circuits are compared with the earlier proposals on the same measures after converting the non NCT1 circuits into equivalent NCT circuits. The results obtained show that the proposed designs are optimal.
lrThe gates from NCT library are NOT, CNOT and TOFFOLI.
Security is of prime importance and cryptographic protocols are extensively used in se curity purposes thus it needs to be robust against numerous attacks. We are interested in protection of crypto processor against power analysis attacks such as the Differential power analysis (DPA) attack which is used to attack the smart card. Reversible logic is a good candidate to defend the power analysis attack as it ideally does not dissipate any heat. In lit erature, different designs for reversible hardware cryptography have been proposed but they have been implemented using complex gate libraries. Further few theorems, which claim to define lower bound on quantum cost of arithmetic logic unit (ALU) are reported in [18]. We have proposed novel designs for reversible ALU of a crypto processor which have been im plemented in standard gate library and the reported quantum cost are better than the lower bounds reported in [18]. Further, we have calculated delay of the proposed designs. We have verified that our proposed designs are minimal with respect to gate count i.e. circuit cost by simulating it in RevKit.
3 Optimization of reversible and quantum circuits
There exist several algorithms for synthesis of reversible circuits [15] and quantum circuits [19]. But these algorithms and others do not provide an unique output. Therefore, a quan titative measure of the quality of a circuit is required. Some of the important quantitative measures are circuit cost, number of garbage bits, quantum cost and delay. Now once a reversible circuit is designed it is required that the circuit should be optimized or minimized in terms of quantum cost, number of garbage bits, delay and number of gates used (again it will depend on the choice of gate library) which is also called circuit cost.
There does not exist any single convention about the choice of gate library. We have shown that it is important to define an unique gate library for comparison of circuit cost. If we have two circuits for the same computational task and both are made using the gates from the same gate library then the one having lesser circuit cost is considered to be the better circuit. Consequently, comparison of two architectures proposed for the same purpose can not always be compared. The complexity of gates may not be same in two different implementations of quantum circuits. For example, it may be easy to build an arbitrary gate 'A' in Nuclear magnetic resonance technology but it may not be that easy in Superconductivity based technology. We have systematically addressed these issues in the thesis.
It is often observed that reduction of circuit cost leads to increase in garbage bits and reduction of quantum cost leads to increase in circuit cost. Keeping this in mind we have introduced a new parameter called Total cost (TC) [9] which is the sum of circuit cost, number of garbage bits and quantum cost.
Quantum cost is an important cost metric in designing of reversible circuits. It is the total number of elementary gates required to realize a reversible function. A simple minded systematic approach to optimize the quantum cost of reversible circuits is proposed in Maslov et al. [20]. They have used optimization approach such as template matching for the same. These facts have motivated us to design an algorithm for optimization of quantum cost [7] as presented in the thesis. By implementing this algorithm, reported quantum costs for reversible circuits from various sources, are compared with the existing results. It is found that the reported quantum cost is optimal in all the cases. In the thesis we have also provided optimized quantum cost for reversible multiplier circuits, reversible sequential circuits and ALU of hardware cryptography. We have not described them in this section as we have already mentioned them in context of synthesis (see Section 2).
4 Testing of reversible and quantum circuits
Test vector is a well defined idea in VLSI, it can also be extended to reversible circuits and can be used to find the repeat gate fault, missing gate fault, stuck at 0 and stuck 1 fault etc. We have observed that the classical notion of test vector fails in case of quantum circuits which involve probabilistic gates (e.g. HADAMARD gate). The distinguishing nature of quantum fault appears only when we consider probabilistic gates and allow superposition states to be present in qubit line. We have followed an independent approach and reported several new and distinguishing features of quantum fault. We have shown that if probabilistic gate like HADAMARD gate is taken then the classical notion of test vector fails. A detail study along this line yield following new observation/results:
In a quantum circuit, test set for stuck at fault, is different from missing gate fault.
An odd number of repeated gate fault in an optimized circuit is equivalent to missing gate fault. In case of an even number of repeated gate fault it will not be detected. In literature this condition for equivalence was not given clearly.
We have provided a general methodology for detection of quantum fault and an al gorithm to find test vectors for m number of gates (single and two qubit gate) in n qubit lines.
We have also provided test vectors for existing reversible/quantum circuits for example, half adder, teleportation, entanglement, de-entanglement, distributed measurement contain ing qudits and shor code.
Time complexity of fault detection is calculated.
We conclude that since it has a linear relation with the number of fault to be considered and the total number of stuck at fault is infinite so we can not detect all faults in finite time but the methodology will work for all practical purposes where the number of fault is finite because of the physical restrictions.