Quantum Complexity Classes-a survey

Lots of efforts in the last decades have been done to prove or disprove whether the set of polynomiallybounded 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.

کلیدواژه ها:

Quantum ، Computation ، Complexity ، Turing machine ، Oracle ، Computation Theory ، Grover algorithm