a quantum computer is a computing device that makes use of the fact that, in terms of quantum mechanics, physical systems can be in a superposition of several states at the same time. Using a number of 2-state systems (qubits), binary information can be encoded just the way as in classical computation - with the difference, that all possible binary states can be encoded in the q-register simultaniously. the quantum computer carries out the computation by means of reversible operations on the qubits and processes the whole superposition of inputs at once - that's where the quantum parallelism comes in.
Quantum computers have first been proposed by Richard Feynman in the early 80's. When David Deutsch wrote his famous paper "Quantum theory, the Church-Turing principle and the universal quantum computer" in 1985 the hype started. He formulated the notion of the quantum-Turing machine and made quantum computers accessible to both computer scientists and physisists.
In 1994 Peter Shor finally presenented his prime-factorizing algorithm which factorizes products of large primenumbers efficiently on a quantum computer while no efficient algorithm for the classical computer has yet been found. This algorithm is of particular interest for the cryptography-industry as the security of most of the common cryptoalgorithms (as RSA) relies on the fact that large numbers can not be factorized efficiently.
The implementation of quantum computers still lies in the far future (it is y2k now). For computation in a quantum computer it is crucial to maintain the coherence of the superposition of the qubits in order to keep q-parallelism and do reversible computation. As physical systems tend to interact with their environment they are subject to decoherence (they entangle themselves with the environment and turn into mixed states). The main task therefore lies in completely shielding the qubits from their environment which is as yet impossible for more than 7 qubits.