“School of Computer Science”

Back to Papers Home
Back to Papers of School of Computer Science

Paper   IPM / Computer Science / 10842
School of Computer Science
  Title:   computational power of the quantum turing automata
  Author(s): 
1.  S. Jafarpour
2.  M. Ghodsi
3.  K. Sadri
4.  Z. Montazeri
  Status:   In Proceedings
  Proceeding: ITNG
  Year:  2007
  Pages:   1077-1082
  Publisher(s):   IEEE Computer Society
  Supported by:  IPM
  Abstract:
Lots of efforts in the last decades have been done to prove or disprove whether the set of polynomially bounded problems is equal to the set of polynomially verifiable problems. This paper will present an overview of the current beliefs of quantum complexity theorists and discussion detail the impacts these beliefs may have on the future of the field. We introduce a new form of Turing machine based on the concepts of quantum mechanics and investigate the domain of this novel definition for computation. The main object is to show the domain of these Computation machines and the new definition of Algorithms using these automata. In section one we give a brief fundamental overview of classical complexity theory, Turing machine and all the fundamental concepts required for the next chapters. In section two we describe various classes of classical complexity automata. In next chapter we introduce quantum complexity featuring Quantum Turing Machines and discuss its relationship to classical complexity. Section four presents a relationship between Quantum complexity classes based on the quantum Turing machines and Quantum oracles, and their relationship with corresponding classical complexity classes. And section five presents a discussion on the practical phenomena in problem solving using quantum computers. Finally in section five we speculate briefly on the direction we believe the field to be headed, and what might reasonably be expected in the future.

Download TeX format
back to top
scroll left or right