A computer is generally considered to be a universal computational device; that is, it is believed able to simulate any physical computational device with a cost in computation time of at most a polynomial factor. It is not clear whether this is still true when quantum mechanics is taken into consideration. A quantum computer is a hypothetical machine which uses quantum mechanics to perform computations. We will explain quantum computing, and give an algorithm for prime factorization on a quantum computer that takes a number of steps which is polynomial in the number of digits of the integer to be factored. This problem is generally considered hard on a classical computer. So far, quantum computers are purely thought experiments; it is not clear whether it will be possible to build one. One of the main difficulties in building quantum computers is in manipulating coherent quantum states without losing coherence. We briefly discuss quantum error-correcting codes, which to some extent can protect quantum states from decoherence and other forms of error.