Explorations on Quantum Logic Gates

by

Agung Trisetyarso

 

The History of Quantum Computer

 

     Gordon Moore’s Law about the future of transistor emerges many theories explaining about transistor model. From observation of transistor size trend in last three decades showing transistor size was decrease year by year, Moore predicted that transistor size would same as electron or atom size in 2020. Unlike the other theories, quantum computation seems as the greatest concept offering Moore’s Law. The notion of Quantum Computer was emerged by Richard Feynman who constructed quantum algorithm showed that no classical computation could simulate a random quantum system efficiently but not finished. Shor continued his work and he was success to make Shor Algorithm using quantum fourier transformations. Then, IBM researcher Charles Bennett also continued Feynman’s work and made great achievement in Quantum Hardware. He was the first man who introduced Qubit (Quantum Binary Digit) and quantum gate which is the foundations of quantum computation. Since it was developed in early 1980s, it has been applied in both hardware and software computer science. Quantum information, algorithm, turing machine and error coding codes are covered in quantum computer software. For physicists, of course quantum computation is very attractive, because it reconciles between computer science and quantum theory (Remember, one of the most difficult problems in physics is unifying or reconciling between general relativity and quantum theory).

      In this Essay, I’d like to briefly describe the differences and similarities between quantum and classical computation using universal gates. Based on the explanation of reversible logic gates, quantum logic gates, and relationship between Schrödinger equation and quantum logic gates shown successively, we will prove that quantum computation is general case of classical computation.

 

 

 

 

Reversible Universal Gates: Controlled-Controlled NOT 

 

     The central issue on the notion of computation is universal gate. In classical computation, we can construct every gate like NOT, AND, and OR gate by NAND gate. On the other hand, every gate in quantum computation is constructed by Controlled – Controlled NOT gate. This is resulted from the assumption that we can describe every logic gate by transformations from a set of input to a set of output revealed by . Different from classical computation requiring not only reversibility but also irreversibility of logic gates, quantum computation using Controlled-Controlled NOT gate computation requires that it must be irreversible only. Reversible (Irreversible) logic gates means that the degree between a set input and a set output binary digit must equal (not equal). It is easy to shown that the relationship between NAND gate and the other gates revealed by:

  • fNAND(x1, x1) =  fNAND (x1,1) = fNOT (x1)   
  • fNAND (fNAND(x1, x2), fNAND(x1, x2))  =  fAND(x1, x2)
  • fNAND (fNAND(x1, x1), fNAND(x2, x2)) =    fOR(x1, x2)

And, by same manner, we can expose some intriguing connections between Controlled-Controlled NOT gate and the other gates like NOT, AND, and OR gate by NAND gate,

  • fCCN (1,1,z) = fNOT (z)
  • fCCN (1,y,z) = fCN (y,z)
  • fCCN (x,y ,0) = fAND (x,y)
  • fCCN (x,y ,1) = fNAND (x,y)
  • fCCN (fCCN (x,x ,1), fCCN (y,y ,1)  ,1) = fOR (x,y)  karena  fNAND (fNAND(x1, x1), fNAND(x2, x2)) =    fOR(x1, x2)

So, it is well proven that Controlled-Controlled NOT acts as universal reversible gate.

    

 

 

 

 

Quantum Logic Gates and Quantum Binary Digit

 

     Before we explore about quantum logic gate, we will previously discuss about qubit acting as the foundations of quantum computation. The other differences between classical and quantum computation is in classical computation we usually use string of binary digits using Boolean values as state representation, but in quantum computation we will use string of quantum binary digits based on Hilbert space. Scientists, who are the founder of quantum computation like Bennett, Benioff, Deustch, etc., successfully related between Boolean algebra and Hilbert space resulting quantum binary digit (qubit). Using qubit, it is necessary to express state of representation as arbitrary superposition, .

    Above calculations is very useful to understand about quantum logic gate. It emerges from the fascinating mix of Reversible gate (for example is Controlled-NOT or Controlled-Controlled NOT) and Schrödinger equation. We can see easily the relationship between them by choosing Nuclear Magnetic Resonant as Hamiltonian for Schrödinger equation acting on two-dimensional Hilbert space. The set of output depends on given pulse. If we give π-pulse to Hamiltonian (or we set that NMR pulse is π), Hamiltonian will act as NOT gate for arbitrary input. And for arbitrary pulse given to Hamiltonian, the set of output will be the superposition of first state and second state. From this manner, it can be generalized that we can construct Hamiltonian for n-dimensional Hilbert space. Furthermore, logic gates in quantum computation must impose unitary and similarity transformations, the consequence is we can replace NOT by arbitrary matrix, U, requiring those transformations.

      It is important to consider that every Controlled-Controlled …- U can be expressed by CC …U =  remembering to representation in group theory (It is said that Controlled-Controlled …- U is decomposable to many irreducible representation represented by identity and unitary operator). And it is also important to consider that every Controlled-Controlled …- U can be formulated by

  • Controlled – U =
  • Controlled Controlled – U =

                                                 = 

 

CONCLUSION

 

     The emerging of quantum logic gates is the consequences of mixing between reversible logic gate and operator in quantum theory. Quantum theory imposes that every operator must be invariant with respect to unitary and similarity transformations. Those transformations affect to the requirement of quantum logic gates, that it must be decomposable to many irreducible representation represented by identity and unitary operator.

 

Bibliography

1.                  Preskill, John.,  Lecture Notes for Physics 229: Quantum Information and  

Computation , http://www.theory.caltech.edu/~preskill/ph229, California (1998)

2.                  Colin, P.W., Scott H.C., Explorations in Quantum Computing, Springer-verlag,

New York (1998)

 

 

"Back To My Homepage"