Quantum Computability and Complexity and the Limits of Quantum Computation

Abstract

This paper will present an overview of the current beliefs of quantum complexity theorists and discuss in detail the impacts these beliefs may have on the future of the field. In section one we give a brief fundamental overview of classical complexity theory, defining the time and space hierarchies and providing examples of problems that fit into several important categories thereon. In section two we introduce quantum complexity and discuss its relationship to classical complexity. Section three presents an overview of the successful existing quantum algorithms, and section four presents a discussion on the actual practical gains that might be realized by quantum computation. 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.