Journal of Global Research in Computer Sciences
MenuISSN: 2229-371X
ISSN: 2229-371X
| Joyshree Nath*1, Asoke Nath2 Department of Computer Science St. Xavier’s College (Autonomous) Kolkata, India |
| Corresponding Author: Joyshree Nath, E-mail: joyshreenath@gmail.com |
| Related article at Pubmed, Scholar Google |
Visit for more related articles at Journal of Global Research in Computer Sciences
Quantum computing is the theory of quantum bits, or qubits, and their associated linear transformations. A quantum computer is more powerful than classical computers, with the problems being solvable. Quantum computing is expected to play an increasingly important role in building more compact and less power-consuming computers. Quantum Computing has emerged to be a very effective field where numerous scientists are doing research in this area. It is true that quantum computing system is now in its initial theoretical state, a lot of aspects of this logic has been proposed by scientists over the years. Quantum computing promises to compute a whole set of intractable problems easily and within a very small amount of time. From binary to multi-valued logic quantum computing systems have a lot of properties to be explored, but mainly theoretically and not in a form of some tangible hardware logic. In the present study the authors have made a thorough study of the properties of binary and multi-valued quantum logic along with the impact of Quantum Information Decision Diagram (QUIDD), Quantum Multi-Valued Decision Diagrams in quantum logic.
Keywords |
| Quantum, qubits, Multi-Valued, QUIDD, hardware |
INTRODUCTION |
| In the present study we have made a study on Binary and Multi-Valued Quantum Computing and impact of decision diagrams with Kronecker Multiplication operation on multi-valued quantum computing. We have introduced initial concepts of quantum computing and its advantages. We have made a study on qubits and its different properties and aspects. We have also made study on few quantum gates, the concepts of multi-valued quantum computing, its advantages and properties of qudits and qutrits respectively. We have also made systematic study on the concepts of quantum decision diagrams, quantum information decision diagrams and the implications of kronecker products on it respectively. The details of quantum multiple-valued decision diagrams is discussed in detail. Finally we have also given the future scope in this area. |
| What is a quantum computing?: |
| The classical computing is the theory of classical bits and the functions acting on them, quantum computing is the theory of quantum bits, or qubits, and their associated linear transformations or conversions. Although a viable quantum computer still remains indefinable, quantum computing has emerged into a major area of research for numerous computer scientists all over the world[1]. Quantum computers go beyond the classical boundaries of complexity, which define the difference between tractable and intractable problems [2]. Theoretically intractable problems in classical domain may be easily solvable in quantum domain. One has to redefine the intractable problem in quantum domain. |
| The advantages of quantum computing that are proposed to exist theoretically are: Quantum computing theoretically allows designers to build more efficient computers than the classical ones, that can very easily solve computationally intractable problems [6]. Very little or theoretically no power will be needed for these applications[6]. Quantum logic involves high speed parallel computations [6].Due to its high speed it is applicable on different aspects of technologies. Quantum computing logic can be of Binary and Multi-valued types. |
| Properties of qubits: |
| What is Qubit and how is it denoted?: |
| The unit of memory for binary logic quantum system is qu-bit(quantum bit). Here a quantum system exists in a linear superposition of two basis states, labeled |0> and |1> [8]. |0> is represented by and |1> is represented by . The equation to represent these 2 qubits in a superposition will be, |φ> = α0|0> + α1|1>, where, |αo|2 + |α1|2= 1. α0 and α1 are the complex probability amplitudes [2]. |
| Superposition property of Qubits: |
| Qubits exist in a linear superposition of states. Superposition is a property which, unlike of classical computing, is present in quantum computing and is of huge relevance. A classical bit can only be in one of the two states 0 or 1, but a qubit can exist simultaneously not only in |0> or |1> but also in any of the infinite range of combination of |0> and |1>. A measurement of a qubit will yield |0> with probability |α0|2 and |1> with probability |α1|2. But when we measure a qubit it boils down to one of the 2 values |0> or |1> with a probability of α0 or α1 respectively, destroying the respective superposition [1]. Thus a qubit on measurement loses its quantum character and resembles its corresponding classical character, i.e, a bit [5]. |
| The combination of quantum state qubits can be represented in entangled states. By entanglement the quantum systems showcase correlations between the qubit states within a superposition. One cannot possibly determine the individual quantum state as one depends on the measurement of the other [9]. |
| Qubits and Parallelism: |
| With more and more qubits there is a massive involvement of quantum parallelism. Parallelism is that property of quantum circuits by which, theoretically all the possible outcomes of the quantum circuit can be calculated at the same instant of time. So a number of quantum computations can result simultaneously. The quantum computations are high speed due to this parallelism property [6]. |
| Kronecker Product (tensor product) of Qubits: |
| Kronecker product (also known as tensor product) can be used to depict superposition of qubits. Kronecker product is represented by a sign. The Kronecker product of 2 matrices (say A and B) is computed by multiplying each element of the 1st matrix(A) by the entire 2nd matrix(B): |
 |
| For example, in a 2-qubit system we can represent the 4 basis states, |00>, |01>, |10> and |11> using Kronecker products [6]: |
 |
| For n qubits we have simultaneous and possible 2n different values as the output [5]. In a quantum circuit parallel connection and computation corresponds to Kronecker multiplication of their matrices [7]. |
QUANTUM GATES |
| A quantum circuit consists of quantum logic gates. Through a quantum gate one qubit state is mapped to the same or some other qubit state. These gates can be composed by taking tensor(Kronecker) products (if gates are applied in parallel to different parts of the register) and ordinary products (if gates are applied sequentially) [7]. Now we will be discussing few basic quantum gates. |
| NOT gate: |
| Quantum NOT gate is a one qubit gate.Here the state |0 maps to the state |1 and the state |1 maps to the state |0 . Quantum NOT gate can be represented by the matrix representation: |
 |
| Hadamard(also called square-root of NOT gate): |
| Here the state |0 maps to the state and the state |1 maps to the state . The matrix representation of this gate is: |
 |
| Controlled-NOT (CN) Gate: |
| This gate is a two-qubit gate. If the bit on the control register is 1, the target bit gets inverted. This CNOT gate can be represented by the matrix representation [3], |
 |
| 3*3 Toffoli gate(also called controlled-controlled (CCN) gate): |
| This gate is important for three-qubit input. Here we have 2 control registers and one target register. If both the controls bits are 1, then the target bit gets inverted. The Toffoli gate is can also self-sufficiently implement NOT and NAND gates[8]. The matrix representation of a 3*3 Toffoli gate is: |
 |
MULTI-VALUED QUANTUM COMPUTING AND CONECEPT OF QUDITS AND QUTRITS: |
| Multi-valued quantum logic circuits are a more improved and powerful option for quantum computing technology(although only in theory and not in a proper hardware form). In multi-valued quantum domain the unit of memory is the qudit(quantum digit), and it is a multidimensional( say n) quantum system with a number of basis states (say, |0>,|1> . . . , |n − 1>) [4]. If we limit the number of quantum basis states to 3, then these basis states {0,1,2} are referred to as qutrit (quantum ternary digit) [8]. Like qubits in binary quantum logic, qutrit states are represented by |0>, |1> , and |2> respectively. |
| In multi-valued quantum logic, the qutrit states |0>, |1> , and |2> are represented by the vector that corresponds |
 |
| In case of multi-valued quantum logic circuit the superposition can be denoted as α|0> + β|1> + γ |2>, where , , and are the respective complex probability amplitudes. Similar to binary logic the intermediate states cannot be distinguished, rather a measurement of a qudit will yield one of the basis states, |0>,|1> or |2>. The probability that this measurement yields state |0> is |α|2, state |1> is |β|2 and |2> as |γ|2 where, |α|2+ |β|2 + |γ|2 =1 [8]. Like binary logic if we take 2 qutrit system we retrieve nine distinct states (for n qutrits we have 3n possible states), |00> , |01>, |02>, |10>, |11>, |12>, |20>, |21>, and |22>, which also can be shown using Kornecker products [6]: |
 |
| The Kronecker product of many such qutrits is essential for the efficient storage of information [4]. |
| Advantages of Multi-valued quantum logic over Binary quantum logic: |
| This logic has some proposed advantages and efficiency over the binary quantum logic. This offers more flexibility in the storage and processing of quantum information and an alternate route to the scaling up of quantum computation. Multi-valued quantum systems can be theoretically used for quantum cryptography. Theoretically one more advantage of multi-valued logic is that the circuit becomes more compact if more and more large multi-valued quantum gates are used. Here the error-correction and fault-tolerance are advanced [4],[9]. |
QUANTUM DECISION DIAGRAMS(QDD): |
| Decision diagrams allow for efficient representation of large matrices representing and analyzing the logic circuits. Quantum decision diagrams (QDDs) were introduced as an attempt of developing and representing binary quantum logic in a compact format [6].The Quantum Information Decision Diagram (QUIDD) data structure allow for implicit parallelism when executing Kronecker multiplications on them. |
| Properties of QuIDD: |
| The values associated with terminal nodes are complex numbers. QuIDD terminal nodes contain integer indices which map into a separate array of complex numbers. The variable ordering of QuIDDs interleaves row and column variables, which favors compression of repeated sub-structure. The sizes of all vectors and matrices are a power of 2. The redundant nodes are removed (be it a row or a column index) in the QuIDD, to make it more compact [10]. |
| Kronecker product in QuIDD: |
| Kronecker products have an advantageous effect of representing QuIDD. This showcases redundancy and a block pattern which effectively makes the representation compact. Now we will show the effect of kronecker product in 2 one-qubit hadamard matrices. Here first 3 matrix blocks are the same leaving the bottom rightmost block different. Thus only one block from the former 3 and the last rightmost block can be shown in the QuiDD for a composite 2 one-qubit hadamard matrix. This property is shown in the diagram below: |
 |
| For an n-qubit circuit, the transformation matrix is of size 2n×2n and the vector representing the initial state of the set of qubits is of size 2n. So, the simulation of quantum logic circuits using a matrix-vector multiplication method is only useful with a very small number of qubits. This led to the devising of Quantum Multiple-valued Decision Diagram (QMDD). |
QUANTUM MULTIPLE-VALUED DECISION DIAGRAMS |
| The decision diagram structure eliminates the problem of exponential growth of the size of representational matrices. QMDD is a decision diagram structure for the compact representation and manipulation of quantum logic circuits. The QMDD structure can be extended to manipulate multi-valued quantum circuits in a small amount of time and that too with less complexity. |
| Characteristics of a QMDD: |
| QMDD is created for representing the matrices that can be built from an n-variable r-valued quantum circuit. There is only one terminal vertex with a value of “1” and has no outgoing edges. There are some number of non-terminal vertices each labeled by an r2-valued selection variable. The variable order, to be labeled for those edges, is x0, x1, …, xn-1 from the terminal node to the start node. Each selection variable appears at most once on each path from the start vertex to the terminal vertex. Each non-terminal vertex has r2 outgoing edges. For example, for 2 qubit quantum system the number of edges will 4 . Each of these edges has a complex-valued weight associated with it. An edge from a non-terminal vertex or node xi points to a non-terminal vertex or node xj( j < i), or to the terminal vertex. Every edge with a weight of 0 points to the terminal node. No non-terminal vertex has all its outgoing edges all with the same weight and pointing to a common vertex. All non-terminal vertices are normalized. |
| QMDD Evaluation: |
| During a QMDD traversal, from the initial node to the terminal node, each variable is traversed at most one time. For a particular selection variable, the path from the starting vertex to the terminal vertex determined by a particular assignment is followed (including the edge leading to the start vertex, which is represented just by an arrow). From a variable or node, say, xi one follows edge number j where j is the value that is assigned to xi. Some traversal paths will not include every variable. This particular variable does not affect the result for this particular valuation of xi. The skipped variables only occur when the exiting edge points directly to the terminal vertex of the QMDD and has a “0” edge multiplier value. The value associated with a path in a QMDD is the product of the edge multipliers on the path including the edge leading to the start vertex. |
| Creating a QMDD Structure for a combination of gates: |
| It is necessary to first build a QMDD structure for each individual gate. Each quantum logic gate is specified by the base transition matrix M. Since, for binary circuits, the dimensions of these matrices are always powers of 2, the matrices can always be partitioned into 4 quadrants. Each partition has the dimension 2n-1 × 2n-1 which are recursively further partitioned and ultimately the sub-matrices boil down to single values representing the weights of the 4 outgoing edges from a node of the decision diagram. In some quantum circuit, the QMDD structure may be a redundant node or vertex. If a certain QMDD has redundant nodes, then this means that, two or more separate vertices with the same weights in all its edges are pointing to the same node. The diagram is made a more compact one by removing all those vertices and replacing and representing it by just one vertex. Therefore the redundant vertex and all its information is stored once and no information is lost and yet the quantum logic becomes concise. All the QMDD structures developed for each gate of the quantum logic circuit are amalgamated with the help of a separate operation called QMDD multiplication [11]. |
CONCLUSION & FUTURE SCOPE: |
| In the present study we have concentrated on the initial concepts of quantum computing(binary and multi-valued logic), qubits, qutrits, quantum gates and decision diagrams for multi-valued quantum computing logic( QUIDD,QMDD). |
| This study to be further extended to design more logic circuits, Quantum Logic Simulators using QUIDD,QMDD etc. Multi-valued quantum logic is still theoretical concept. There is a tremendous scope in both theoretical as well as hardware implementation to support multi valued quantum logic circuit. Many more aspects to be explored in Quantum computing especially designing quantum algorithm which may drastically change the present classical computer algorithm. Quantum computing may drastically reduce the real power consumption and which may help us to move towards green computing. Research area is still open in the hardware implementation area of quantum logic. |
ACKNOWLEDGEMENT |
| AN expresses his gratitude to Fr. Dr. Felix Raj, Principal of St. Xavier’s College to give opportunity to work in this new Research area. AN is also very grateful to staff members of the Computer Lab of St. Xavier’s College for their constant support to finish this work. JN is grateful to her mother Mala Nath for her constant encouragement to finish the present work. |
References |
|