  In the last few years, theoretical study of quantum systems serving as
computational devices has achieved tremendous progress. We now have strong
theoretical evidence that quantum computers, if built, might be used as a
dramatically powerful computational tool. This review is about to tell the
story of theoretical quantum computation. I left out the developing topic of
experimental realizations of the model, and neglected other closely related
topics which are quantum information and quantum communication. As a result of
narrowing the scope of this paper, I hope it has gained the benefit of being an
almost self contained introduction to the exciting field of quantum
computation.
  The review begins with background on theoretical computer science, Turing
machines and Boolean circuits. In light of these models, I define quantum
computers, and discuss the issue of universal quantum gates. Quantum
algorithms, including Shor's factorization algorithm and Grover's algorithm for
searching databases, are explained. I will devote much attention to
understanding what the origins of the quantum computational power are, and what
the limits of this power are. Finally, I describe the recent theoretical
results which show that quantum computers maintain their complexity power even
in the presence of noise, inaccuracies and finite precision. I tried to put all
results in their context, asking what the implications to other issues in
computer science and physics are. In the end of this review I make these
connections explicit, discussing the possible implications of quantum
computation on fundamental physical questions, such as the transition from
quantum to classical physics.
