Boston University | Center for Computational Science
HomeNews and EventsResearchEducationPeopleSeminarsFacilitiesContact Us

Quantum Computability

Steve Homer
CAS Computer Science
Boston University
October 19, 2001
A major impetus for the recent activity in quantum computation is a small number of quantum algorithms, which have been developed, that (in principle) exhibit an advantage of quantum computation over classical computation. These examples raise questions concerning the power and limits of quantum computation. One aspect of this topic is the development of the general theory of efficient quantum
The two standard models for quantum computing, quantum Turing machines and quantum circuits, will be considered. We show how efficient computations using these models can be related computations of standard (probabilistic) Turing machines. Using this correspondence, we consider natural classes of quantum algorithms and discuss their efficiency. We do this by providing a classification for quantum algorithms and measuring the efficiency of these algorithms using traditional complexity measures.

copyright © 2006, Center for Computational Science | Boston University , MA, 02215