Evolving Quantum circuits - Computer Action Team



Multiple-Valued Quantum Logic Synthesis

Marek Perkowski * +, Anas Al-Rabadi+, Pawel Kerntopf &

* Department of Electrical Engineering, Korea Advanced Institute of Science and Technology, 373-1, Kusong-dong, Yusong-gu, Taejeon, 305-701, Korea , +Department of Electrical and Computer Engineering, Portland State University, Portland, OR, 97201. USA, & Institute of Computer Science, Warsaw University of Technology, Nowowiejska 15/19, 00-665 Warsaw, Poland.

Abstract

Multiple-valued quantum logic is in such relation to binary quantum logic as multiple-valued reversible logic to binary reversible logic. Although building quantum computers based on MV logic has many advantages over binary quantum computers and is already technically possible on experimental scale, very little research has been performed so far, both related to practical realization and design theory of MV quantum computers. This paper presents a set of universal MV quantum gates, a general synthesis methodology for them and a proof that Galois logic is realizable in quantum logic using only one-qudit and two-qudit gates. Open problems are formulated.

1. Introduction

1.1. Are quantum computers practical? Is quantum logic synthesis a legitimate research subject?

Binary quantum computers based on NMR technology are already build in several research institutions including KAIST [24,25,29,33,37,38]. They are not useful for any practical application so far, but the problem of minimizing their quantum logic circuits is very practical for their designers. Moreover, because in 2002 these NMR computers have not more than 7 qubits, and a high minimization quality is expected for practical realization purposes, the requirements for logic synthesis and minimization are quite different than in standard CAD tools for logic design. For example, a circuit that has a width 8 of scratchpad register would be not realizable nowadays, and minimizing this circuit to 7 bits would make it practically realizable. This task is directly related to garbage minimization problem discussed below.

1.2. State of the art in multiple-valued quantum computing and theory.

The role of Boolean Algebra in logic synthesis for binary reversible logic is well known [3,4,17,19,27,44]. It has also application to design the so-called permutation (pseudo-binary) sub-circuits which occupy a high percent of quantum computer “real estate” [15,23,33]. The unit of memory (information) for binary quantum computation is a qubit, the simplest quantum system that exists in a linear superposition of two basic states labeled |0> and |1>. In classical quantum logic, every computation can be performed by a circuit composed of 2*2 quantum gates (called also two-qubit gates) and 1*1 quantum gates [6,7,18,42,45]. This result is different from binary reversible logic, where the minimum universal gate is 3*3 [19,44] (all quantum gates are reversible and reversible gates have the same number of inputs and outputs and are one-to-one mappings, k*k gate has k inputs and k outputs).

An interesting question arises. What would be a concept analogous to multiple-valued logic in quantum domain? This question was first posed by H.F. Chau in 1997 [13], where the concept of a qudit, i.e. a d-dimensional quantum system that generalizes a qubit and has basis states |0>, |1>, |2>, … , |d-1> has been introduced (“Trits” of ternary logic were introduced by Mattle et al in 1996 [47], but used only for quantum transmission). Subsequently, limited has been performed in multiple-valued quantum logic and computing. The works of Chau, as well as of Rains in 1999 [39] and Ashikhmin and Knill [5], have extended quantum error-correcting codes to multiple-valued logic for correcting codes in single and multiple qudits. Also in 1999, Gottesman [20] and Aharonov and Ben-Or [1] developed fault-tolerant procedures for implementing two-qudit and three-qudit analogs of universal binary gates. Burlakov [12] proposed to use correlated photon pair to represent the ternary analog of a qubit. Since 2000 the works get momentum. Muthukrishnan and Stroud [32] developed universal multiple-valued logic for multi-level quantum computing systems and showed their realizability in linear ion trap devices [14]. This system produced however circuits of too large dimensions when the number of inputs grows. Universality of n-qudit gates was discussed in [11,32] but no design algorithms were given. Picton [36] presented a Universal Architecture for Multiple-valued reversible logic but this approach produces circuits that are far from the minimum and have not much relation to quantum realization. In 2001 Galois Field approach to quantum logic synthesis was proposed [2,3,4,34] and Galois quantum gates were developed but without the proof that they can be built from only 1*1 and 2*2 gates. De Vos proposed two ternary 1*1 gates and two universal 2*2 ternary gates for reversible computing [17]. New efficient reversible binary gates that can be generalized to MV quantum realizable gates have been proposed by Kerntopf [26]. Generalization of binary quantum algorithms to multiple-valued ones: for Fourier Transform [46], EPR [3], encoding[8], teleportation [9] and entanglement [40] were presented. However, no practical system for logic synthesis using 1*1 and 2*2 quantum gates, and especially permutation gates, has been proposed so far. Realization from only such gates is extremely important since interaction of three particles is nearly impossible to control. Every practical system should be able to realize 3*3 gates only 2*2 and 1*1 gates. This is a very important design objective for nanotechnologies. Moreover, even if a gate is realizable, not every gate sequence may be practically realizable, which property affects crucially the synthesis. While the condition for performing arbitrary unitary operations on pure states to realize binary quantum computation by unitary dynamics is well understood [6,7,16,18], it is not so for the MV case. While it was proved that almost every two-qubit gate is universal and that a set of quantum gates that consists of all one-qubit gates and the 2*2 CNOT (Feynman) gate is universal ( in the sense that all unitary operations on arbitrary many qubits can be expressed as compositions of these gates ) no analogous practical systems have been proposed for MV quantum logic.

2. Multiple-valued quantum logic

The major difference between quantum logic and binary logic is the concept of the information itself. While the classical (binary or multi-valued) representations of information are precise and deterministic, in MV Quantum Computing the concept of bit is replaced by the qudit. Unlike classical bits that are realized as electrical voltages or currents present on a wire, MV quantum logic operations manipulate qudits, which are microscopic entities such as a photon or atomic spin. Ternary logic values of 0, 1 or 2 are represented by a set of distinguishable different states of a qudit. These states can be a photon’s polarizations or an elementary particle’s spins. After encoding these distinguishable quantities into multiple-valued constants, a notation for ternary qudit states is |0>, |1> and |2> (we discuss only ternary quantum logic for simplification, but the principles are the same for any MV logic). At least ternary and quaternary quantum logic is practically possible in year 2002.

Qudits exist in a linear superposition of states, and are characterized by a wavefunction (. As an example (d=2), it is possible to have light polarizations other than purely horizontal or vertical, such as slant 45( corresponding to the linear superposition of (=½[(2|0>+(2|1>]. In ternary logic, the notation for the superposition is (|0> + (|1> + γ |2>. These intermediate states cannot be distinguished, rather a measurement will yield that the qudit is in one of the basis states, |0>, |1> or |2>. The probability that a measurement of a qudit yields state |0> is |(|2, the probability is |(|2 for state |1> and |γ|2 for state γ . The sum of these probabilites is one. The absolute values are required, since in general, ( ( and γ are complex quantities.

Pairs of ternary qudits are capable of representing nine distinct Boolean states, |00>, |01>, |02>, |10>, |11>, |12>, |20>, |21> and |22>, as well as all possible superpositions of the states. This property is known as “entanglement”, and may be mathematically described using the Kronecker product (tensor product) operation ( [33,45]. As an example, consider two qudits with (1=(1|0>+(1|1>+γ1|2> and (2=(2|0>+(2|1>+γ2|2>. When the two qudits are considered to represent a state, that state (12 is the superposition of all possible combinations of the original qubits, where

(12= (1((2 = (1(2|00> + (1(2|01> +...... + γ1 γ2|22>. (1)

Superposition property allows qubit states to grow much faster in dimension than classical bits, and qudits to grow faster than qubits [32,40]. In a classical system, n bits represent 2n distinct states, whereas n ternary qudits correspond to a superposition of 3n states. Observe also that in the above formula some coefficient can cancel, so there exist a constraint bounding the possible states in which the system can exist. As observed in [32] – „Allowing d to be arbitrary enables a tradeoff between the number of qudits making up the quantum computer and the number of levels in each qudit“

These all peculiarities contribute to the difficulty in understanding the concepts of quantum computing and creating efficient analysis, simulation, verification and synthesis algorithms for QC. Generally, however, we believe that much can be learned from the history of Electronic Computer Aided Design as well as from MV logic theory and design. The lessons learned there should be used to design efficient CAD tools for MV quantum computing.

In terms of logic operations, anything that changes a vector of qudit states can be considered as an operator. These phenomena can be modeled using the analogy of a “quantum circuit”. In a quantum circuit wires do not carry ternary constants, but correspond to 3-tuples of complex values, (, ( and γ. Quantum logic gates of the circuit map the complex values on their inputs to complex values on their outputs. Operation of quantum gates is described by matrix operations. Any quantum circuit is a composition of parallel and serial connections of blocks, from small to large. Serial connection of blocks corresponds to standard matrix multiplication of their (unitary) matrices. Parallel connection corresponds to Kronecker multiplication of their matrices. So, theoretically, the analysis, simulation and verification are easy and can be based on matrix methods. Practically they are tough because of the problem dimension – the exponential growth of matrices. Synthesis problem can be formulated as hierarchically decomposing a given unitary matrix to matrix multiplications and Kronecker multiplications (serial and parallel connections) of smaller matrices, until basic directly realizable quantum primitive matrices are reached. This problem is very difficult to solve in such basic formulation and therefore several special optimization methods have been and are being developed for binary QC, especially in the last 5 years. No such efforts are known for MV QC, so far.

Probabilistic calculations based on this representation are used in only very small quantum computers in year 2002, but it has been already experimentally verified that information can be represented as a superposition of states of single qudits, and that in one time step operations can be performed on several qudits. Beside this useful effect of quantum computing, various other effects resulting from qudit encoding emerge, such as qudit entanglement.

3. Multiple-valued quantum logic synthesis.

Efficient design of complex gates is the first task of quantum logic synthesis. Our main idea based on experience is that the synthesis and optimization should be performed: (1) on one hand on a lower level of quantum primitives such as ternary Feynman (P=a, Q= a ( b), conditionally controlled operators [32] and 1*1 gates, and (2) on the other hand on the level of more powerful k*k reversible gates, such as those introduced in [31,35] Such approach simplifies the design search by increasing gate granularity and makes it closer to standard logic synthesis methods since more powerful non-reversible logic functions of many arguments are used in some of their outputs.

3.1. Gate Design

We focus here on ternary logic but our approach is for any logic where two operators – addition and multiplication can be defined and corresponding polynomials can be created. Ternary Feynman gate (P=a, Q= a ( b) is relatively easy to realize and can be treated as a second level primitive above the first level primitive being quantum operations [37,38]. Ternary Toffoli gate is described by equations P=a,Q=b, R= ab ( c. Fredkin gate by equations P=a, Q= a’’b ( ac, R=ab(a’c, ( and * operators in Galois Field, a’=a(1 is a shift and a’’=a(2 is a dual shift).

[pic]

Please observe the difference of binary Toffoli [19] and ternary Toffoli defined here. Realization of Ternary Fredkin using two Feynman and one Toffoli gate is shown in Figure 1. Thus Fredkin gate can be used in synthesis and next macrogeneration transformations are executed in which every Fredkin gate is rewritten to a sequence of gates and next some of these gates are “cancelled” or are replaced by simpler sub-sequences of gates or quantum operations [23,37,38,41]. Observe also that there are many other ternary gates that can be treated as generalizations of binary Toffoli and Fredkin gates. The same is true about ternary generalizations of “complex gates”: De Vos, Kerntopf, Khan, Peres, Perkowski and other gates [2,3,4,26,27,31,32,34,35,36,44]. Such generalizations are achieved by simple analogies of GF2 to GF3, and in general analogies to fileds GF(pk) where p is prime and p>3. We call them complex gates, since even 3*3 gates require a lot of internal 1*1 and 2*2 gates for practical quantum realization. 3*3 Galois gates such as MV Toffoli (MV CCNOT) and MV Fredkin are not always the best gates for quantum computing. Therefore, not necessarily the generalizations of binary algorithms are the best solutions for MV. Situation is even worse for multi-input gates (n>3), such as Toffoli. They look simple in a diagram, but take a lot of realizable primitive quantum gates when redrawn to 2*2 and 1*1 gates [7,43]. Efficient design of complex gates from quantum primitives is thus an important problem. Solving this problem would help experimental physicists in the same way as schematic capture-based CAD tools helped digital designers in the 1980’s. They would be able to capture their ideas on a higher level of macro-blocks and not worry of what is inside them and how practically realizable.

[pic]

In addition to gates such as Chrestenson [2,3,4,46], phase and others [32,33] we use 1*1 elementary gates specifically useful for permutation circuits. The notation for these gates here is the following : we write the vector of outputs for the vector of inputs ;: buffer shift , double shift , multiplication by 2 , ternary inverter and cycle . These are all gates that can be obtained by permutation of values 0,1, and 2. Other ternary universal literals cannot be used since reversible gates do not exist for them. Having such gates, 2*2 gates can be created by controlling them, similarly as the binary Feynman has a controlling input A that controls the controlled input B and an EXOR gate with A and B as inputs. This way, simple conditional gates as in [32] can be created, see Figure 2a, where value 2 of the controlling signal causes application of one-qudit gate X, and other values of this signal cause transmission of unaffected value from input B to output Q. In this paper we introduce the generalization of this scheme based on [31].

[pic]

One example illustrating this scheme is shown in Figure 2b, where not only value d-1 is used to control change, but all its values. Arbitrary quantum one-qudit gates can stand on all the inputs to the multiplexer. Using classical multiplexer notation is very helpful to understand and synthesize by hand circuits using such gates. If the value of ternary controlling input A is 1, the input B goes to Q. When A=0 one-qudit operation y is performed, and operation z is performed when this signal is 2. Observe that in our generalization arbitrary one-qudit gate can be used on multiplexer inputs, not only those listed above, but also such gates as Chrestenson (generalization of Hadamard gate used in the most famous non-permutation quantum circuit applications). This creates a powerful family of realizable “truly quantum” gates that generalize those from [32]. In [17,31] families of multi-input reversible binary gates have been introduced that generalize Fredkin, Toffoli, Kerntopf and other gates. Figure 3a shows the simplest of these gates, generalized even further to ternary logic. Observe that arbitrary non-reversible one-output function control an arbitrary reversible operator (not necessarily the Ternary Galois Addition used in Ternary Feynman gate). The method to implement arbitrary non-reversible functions is shown in Figure 3b. Such functions exist in the complex gates. G-1 is an inverse gate of gate G. H is a reversible gate that includes arbitrary controlled ternary function. Several garbage signals can be internally created between G and G-1. (Garbage is an unused output signal added only to satisfy the reversibility of the gate). But these garbage signals will overlap with analogous signals in next gates in the cascade, so they do not contribute dramatically to the increase of the scratchpad register width. This is because the original inputs are restored at the output terminals, thus allowing the inputs to be used in the next gates in the cascade (see example from Figure 6 – original values can be always restored when necessary, which makes GFSOP’s Galois product terms practically independent). Of course, this approach is restricted to some types of cascades like those of sum-of-products type which reuse inputs, rather than to be used in general cascade types where intermediate signals replace inputs variables, such as nets or lattices. This method is also used to realize ternary Toffoli gates from quantum primitives in a proof of realizability of Galois Field logic in quantum [35]. In brief, the sequence to create Ternary Toffoli is the following. G1= [ 0 ] [ a i (0,2) (0,2)] [b +1 i i ], G2 = [ 1] [G1 +2 (0,1) i] [a i i (1,2)] [b i i (1,2)], R = c ( G2. The meaning of this notation is as follows. [0] and [1] are constants from the left. The sequence is to be read from left to right, [V x y z] describes a gate controlled by controlling signal V, with data inputs 0, 1, and 2 that read some functions of controlled input, respectively. The meaning of symbols used for functions x, y, z is the following: i denotes direct input (no operation), +1 denotes shift applied to input, +2 double shift applied to input. Symbol (i,j) means permuting values of i and j in input. It means, logic value i is changed in cells of ternary Kmap to logic value j and vice versa. For instance, [G1 +2 (0,1) i] means a gate controlled by G1, with double shift on data input 0, permutation (0,1) on data input 1, and direct input connected to data input 2 of the mux. The reader can check the correctness of this sequence using Ternary Kmaps.

[pic]

This exercise would explain also the power of the generalized gates. Next G1 and G2 garbages are converted again to constants 0 and 1, by using the local mirror technique, thus creating a gate with inputs a, b and c, and outputs P=a, Q=b, and R=c ( G2.

[pic][pic] [pic]

3.2. Circuit Design.

The transformation from an optimal reversible circuit (on uses gates of any level(s)) to the minimal quantum sequence for NMR programming is far from being trivial, and currently no combinatorial optimization algorithms (such as dynamic programming) have been created for them. Realistic gate costs for NMR or other technology should be formulated to be used in synthesis. Counting gates as cost evaluation, as is done in binary quantum circuit optimization algorithms is too approximate [35]. In our system, the circuit is designed using complex gates [34,35] and standard 1*1 and 2*2 quantum gates and next the optimizing tautological transforms are applied to the circuit, producing a sequence of practically realizable quantum operations with minimized number of such operations. The general combinatorial problems of gate ordering, input variable ordering, local transformations, removal of swap gates (planarization) and others, are quite similar to technology mapping and physical design areas in classical CAD for binary nonreversible logic.

These hierarchical stages can be compared to standard gate library design, high level synthesis and generic logic synthesis and technology mapping stages of classical CAD systems, respectively. We use an informed genetic algorithm to evolve arbitrary quantum circuit specified by a (target) unitary matrix, specific encoding that reduces the time of calculating the resultant unitary matrices of chromosomes, and an evolutionary algorithm specialized to permutation circuits specified by truth tables [30,31]. Other algorithms are used for specific structures and function types such as ternary symmetric functions [34]. We found ternary counterparts of our previous binary approaches [28] for several special circuit structures and design algorithms. Thus, in the first stage various algorithms can be used to design a circuit from complex gates. Next swap gates should be included for some methods and simplifying transformations are applied again. We proceed towards lower and lower quantum gate granularity and check the realizability of the circuit with lowest level quantum operations. For instance, in some realizations only qudits of certain small distance can interact, which causes the necessity of adding swap gates. Such gates are quite costly in ternary realization so their number should be minimized by the design method [28]. If only “distance “ between quantum wires is allowed, the circuit is made planar. Let us illustrate this problem on an example. Quantum wire B crosses Toffoli gate in Figure 4 and next wire C crosses the second Toffoli gate. If distance one is required, swap gates are added as in Figure 5. Now the circuit is a connection of parallel and serial blocks, and it can be verified by Kronecker (tensor) multiplications and matrix multiplications, respectively. Two examples of GFSOP (Galois Field Sum of Products) circuits after planarization are shown in Figure 6. Remember that in the next stage the swap gates are also replaced with Feynman gates and one-qudit gates. Toffoli gates are replaced with 2-quidit gates. This brings the next possibilities of optimizing transformations on neighboring gates of the lowest level.

In quantum circuits we want to minimize garbage, since it either directly affects the quantum register width (number of horizontal quantum “wires”) or even if garbage signals are reduced back to original input variables (creation of local mirrors), also affects the width. Some tricks related to garbage minimization are used, such as those shown in Figures 7 and 8. In our example we use GFSOP but analogical techniques can be used for any circuit. Figure 8 illustrates also another important technique: the use of local mirrors.

[pic]

4. Open Problems

1. How to select the best gates for permutation circuit synthesis. This set is also included in a set of gates that are universal for general quantum circuits. An interesting problem is the design of the simplest practical realization of a ternary Toffoli-like gate [35], since having Toffoli, all other gates can be relatively inexpensively constructed [35].

2 Best realization, in quantum circuit sense (simplicity and ease of realization), of other Galois gates and non-Galois standard MV operators such as minimum, maximum, truncated sum and others. The methods should use garbage minimization (scratchpad register width minimization), input variables repetition, and the techniques of global spies and mirroring [19] and local mirroring to restore input variables (Figures 3,7, 8 and [28]) .

3. Synthesis algorithms for MV reversible circuit families: GFSOP [4,28], nets [34], lattices [4], PLAs [36], and MV counterparts of Maitra cascades and wave cascades, as well as other reversible cascades [23,41], but tuned to realistic quantum computer realization technologies.

5. Conclusion

CAD developers create traditionally tools for industrial engineers, but the time comes now to design such tools for experimental physicists. The general methodology outlined here has several variants of gates and structures. Some of the briefly mentioned algorithms are already implemented in software. The presented methods can be specialized to some new gate and circuit classes such as MV counterparts of f-controlled-phase-shift gate circuits [25], and mixed multiple-valued quantum logic where binary and ternary variables are mixed in a circuit [35]. In [30,31] we have shown that evolutionary computation can be used for automated QC development in real time using standard PC computers. An interesting research will be to implement evolutionary learning in quantum hardware which will lead to a new area of Evolutionary Quantum Hardware (EQH). This area, as well as neural nets, are naturally well-suited to MV quantum logic. Our GA algorithm [30,31] and its data structure can be applied with little modification to MV quantum circuits [35] and especially the “permutation” circuits that can be used for instance in MV generalizations of the famous Grover’s Quantum Search Algorithm [21,22]. Another areas of MV Quantum logic research are: quantum simulation, quantum circuits verification, and designing theoretical models of MV quantum computers, generalization of efficient garbage-less realizations of k*k gates (k>3) [7,43] for MV gates [35]. We hope also to convince experimental physicists to build in NMR simple circuits as those presented here. Because this research area is new, we are able to provide a complete bibliography of Multiple-Valued Quantum Logic.

Bibliography of Multiple-Valued Quantum Logic

1. D. Aharonov, M. Ben-Or, Polynomial Simulations of Decohered Quantum Computers, (Online preprint quant-ph/9611029), 37th Ann Symp on Found of Comp Sci, pp. 4655, Burlington, Vermont

2. A. Al-Rabadi, “Synthesis and Canonical Representations of Equally Input-Output Binary and Multiple-Valued Galois Quantum Logic: Decision Trees, Decision Diagrams, Quantum Butterflies, Quantum Chrestenson Gate, Multiple-Valued Bell-Einstein-Podolsky-Rosen Basis States,” Technical Report #2001/008, ECE Dept. PSU, August 22, 2001.

3. A. Al-Rabadi, L.W. Casperson, M. Perkowski and X. Song, “Multiple-Valued Quantum Logic,” Booklet of 11th Post-Binary Ultra Large Scale Integration (ULSI)’ 2002 Workshop, pp. 35-45, Boston, Massachusetts, May 15, 2002.

4. A. Al-Rabadi, “Novel Methods for Reversible Logic Synthesis and Their Application to Quantum Computing,” Ph. D. Thesis, Portland State University, Portland, Oregon, USA, October 24, 2002.

5. A. Ashikhmin and E. Knill, “Non-binary quantum stabilizer codes,” quantph/0005008,  

6. A. Barenco, Proc. Soc. London, Ser. A, 449, 679, 1995

7. A. Barenco et al., “Elementary Gates For Quantum Computation”, Physical Review A 52, 1995, pp. 3457-3467

8. S.D. Bartlett, H. de Guise, and B.C. Sanders, „Quantum Encodings in Spin Systems and Harmonic Oscillators,“ arXiv:quant-ph/0109066, v2, May 6, 2002.

9. Brassard G., Braunstein S. L., Cleve R., “Teleportation as Quantum Computation”, in Proceedings of the Fourth Workshop on Physics and Computation, New England Complex System Institute.

10. H. Bechmann-Pasquinucci and A. Peres, ``Quantum cryptography with 3-state systems'', quant-ph/0001083.

11. J.L. Brylinski and R. Brylinski, “Universal Quantum Gates,” (to appear in Mathematics of Quantum Computation, CRC Press, 2002) LANL e-print quant-ph/010862.

12. A.V. Burlakov, M.V. Chekhova, O.V. Karabutova, D.N. Klyshko, and S.P. Kulik, “Polarization state of a biphoton: quantum ternary.” Phys. Rev. A 60, R4209, 1999.

13. H.F. Chau, Phys. Rev. A 55, R839, 1997

14. J.I. Cirac and P. Zoller, Phys. Rev. Lett. 74, pp. 4091, 1995 uses trapped atomic ions as ``qubits

15. D. Deutsch, “Quantum computational networks,” Proc. Roy. Soc. Lond. A. 425, 1989, pp. 73-90.

16. D. Deutsch, A. Barenco, and A. Ekert, Proc. Roy.Soc.Lond A 449, pp. 669, 1995.

17. A. De Vos, B. Raa, and L. Storme, Generating the group of reversible logic gates, March 7, 2002, preprint from the authors.

18. D.P. DiVincenzo, Phys. Rev. A. 51, 1015, 1995

19. E. Fredkin and T. Toffoli, “Conservative logic,” International Journal of Theoretical Physics, 21, pp. 219-253, 1982

20. D. Gottesman, “Fault-tolerant quantum computation with higher-dimensional systems,”Chaos, Solitons, Fractals Vol. 10, No. 10, pp. 1749 – 1758, 1999.

21. L.K. Grover, Quantum Mechanics helps in searching for a needle in a haystack, Phys. Rev. Lett. 79, 325, 1997

22. L.K.Grover, “A Framework for Fast Quantum Mechanical Algorithms,” ACM Symp on Theory of Computing (STOC), 1998.

23. K. Iwama, Y. Kambayashi, and S. Yamashita, “Transformation Rules for Designing CNOT-based Quantum Circuits,” Proc. DAC 2002, New Orleans, Louisiana.

24. J. Kim, J-S Lee, and S. Lee, “Implementation of the refined Deutsch-Jozsa algorithm on a three-bit NMR quantum computer”, Physical Review A, Volume 62, 022312, 2000.

25. J. Kim, J-S. Lee, and S. Lee, “Implementing unitary operators in quantum computation,” Physical Review A, Volume 62, 032312, 2000.

26. P. Kerntopf, “Maximally efficient binary and multi-valued reversible gates,” Proceedings of ULSI Workshop, Warsaw, Poland, May 2001, pp. 55-58.

27. P. Kerntopf, “Synthesis of multipurpose reversible logic gates,” Proceedings of EUROMICRO Symposium on Digital Systems Design, 2002, pp. 259-266.

28. M.H.A. Khan, and M. Perkowski, “Multi-Output Galois Field Sum of Products (GFSOP) Synthesis with New Quantum Cascades,” submitted to ISMVL 2003.

29. J-S. Lee, Y. Chung, J. Kim, and S. Lee, „A Practical Method of Constructing Quantum Combinational Logic Circuits,“ arXiv:quant-ph/9911053v1, 12 Nov. 1999.

30. M. Lukac and M. Perkowski, “Evolving Quantum Circuits Using Genetic Algorithm,” Proc. of NASA/DOD Workshop on Evolvable Hardware, Washington, D.C. July 2002.

31. M. Lukac, M. Pivtoraiko, A. Mishchenko, and M. Perkowski, “Automated Synthesis of Generalized Reversible Cascades using Genetic Algorithms,” Proc.5th Intern Workshop on Boolean Problems, Freiberg, Germany, September 19-20, 2002. pp 33-45

32. A. Muthukrishnan, and C.R. Stroud, Jr., “Multivalued logic gates for quantum computation,” Phys. Rev. A. Vol. 62, 052309.

33. M. Nielsen & I. Chuang, Quantum Computation and Quantum Information, Cambridge Univ. Press, September 2000.

34. M. Perkowski, A. Al-Rabadi, P. Kerntopf, A. Mishchenko, M. Chrzanowska-Jeske, „Three-Dimensional Realization of Multivalued Functions Using Reversible Logic,“ Proc. 10th Int’l Workshop on Post-Binary Ultra-Large-Scale Integration Systems, 2001, pp. 47- 53

35. M. Perkowski, P. Kerntopf, A. Rabadi, M.H.A. Khan, “Multiple-Valued Quantum Computing. Issues, Open Problems, Solutions,” Technical Report,, KAIST, December 2002.

36. P. Picton, A Universal Architecture for Multiple-Valued Reversible Logic,” Multiple-Valued Logic Journal, Vol. 5, 2000, pp. 27-37.

37. M. D. Price, S.S. Somaroo, A.E. Dunlop, T. F. Havel, and D. G. Cory, “Generalized methods for the development of quantum logic gates for an NMR quantum information processor,” Physical Review A, Vol. 60, Number 4, October 1999, pp. 2777-2780.

38. M.D. Price, S.S. Somaroo, C.H. Tseng, J.C. Core, A.H. Fahmy, T.F. Havel and D.G. Cory, “Construction and Implementation of NMR Quantum Logic Gates for Two Spin Systems,”J. of Magnetic Resonance, 140, pp. 371- 378, 1999

39. E.M. Rains, “Nonbinary Quantum Codes,” IEEE Trans. Inf. Thy, 45, pp. 1827 -1832, 1999

40. P. Rungta, W.J. Munro, K. Nemoto, P. Deuar, G.J. Milburn and C.M. Caves, “Qudit Entanglement,” quant/ph/0001075.

41. V.V. Shende, A.K. Prasad, I.L. Markov, J.P. Hayes, “Reversible Logic Circuit Synthesis,” Proc. 11th IEEE/ACM Intern. Workshop on Logic Synthesis, 2002, pp. 125 – 130.

42. T. Sleator and H. Weinfurter, “Realizable Universal Quantum Logic Gates,” Phys. Rev. Lett. 74, pp. 4087-4090, 1995.

43. J. Smolin, D. P. DiVincenzo, “Five two-qubit gates are sufficient to implement the quantum Fredkin gate.” Physical Review A, Vol. 53, no. 4, April 1996, pp. 2855-2856.

44. T. Toffoli, in Automata, Languages and Programming, 7th Colloquium, edited by J.W. De Bakker and J. Van Leenwen, Lecture Notes in Computer Science, Vol. 84, Springer Verlag, Berlin, 1980, pp. 632 – 644

45. C.P. Williams, and S.H. Clearwater., "Explorations in Quantum Computing", Springer-Verlag, New York Inc. (1998)

46. Z. Zilic, K. Radecka, “The Role of Super-Fast Transform for Speeding Up Quantum Computations,” Proc .ISMVL’02, pp. 129—135,Boston, MA, 15-18 May, 2002.

47. K. Mattle, H. Weinfurter, P.G. Kwiat, and A. Zeilinger, “Dense Coding in Experimental Quantum Communication,” Physical Review Letters, Vol. 76, No. 25, pp.4656-4659, 17 June 1996.

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download