In the early 1980's, Richard Feynman observed that certain quantum mechanical effects could not be simulated efficiently on a computer. This observation led to speculation that perhaps computation in general could be done more efficiently if it made use of these quantum effects. But building quantum computers, computational machines that use these quantum mechanical effects, proved tricky. And as no one was sure how to use these effects to speed up computation anyway, the field developed slowly.
It wasn't until 1994, when Peter Shor surprised the world by describing a polynomial time quantum algorithm for factoring integers, that the field of quantum computing came into its own. Peter Shor's work prompted a flurry of activity, both among experimentalists trying to build quantum computers and theoreticians trying to find other quantum algorithms.
The power of quantum computing comes from quantum parallelism. However, harnessing this power is tricky. In classical parallelism, an exponential decrease in time requires and exponential increase in the number of processors. In quantum systems, the computational space increases exponentially with the number of particles! The catch is that while a quantum system can perform massive parallel computations, accessing the results, which requires measurements that disturb the quantum state, proves tricky. However, in recent years, Shor and others have been able to finesse the measurement problem to take advantage of quantum parallelism.
It is not yet known whether the power of quantum parallelism can be harnessed to solve a wide variety of problems. Many researchers have tried unsuccessfully to find quantum algorithms that solve NP complete problems in polynomial time. Currently classical heuristic algorithms are used widely in industry to attack instances of these problems. Perhaps quantum heuristics could be developed that could substantially improve on these classical heuristics. While a few quantum heuristics have been developed, the efficiency of quantum heuristics, like the efficiency of classical heuristics, is difficult to analyze. Classical heuristics are tested empirically on a large random sample of problems. Perhaps we will have to wait until large enough quantum computers are built before we know whether quantum heuristics are useful.
Quantum computers with small numbers of quantum bits have been built, but no one yet knows how to build a quantum computer with on the order of 100 quantum bits, let alone more.While many open questions remain, quantum computers challenge conventional ideas about speed, complexity, and programming. Just as quantum computing has led to a deeper understanding of the nature of computation, the computational and information theoretic views of quantum mechanics have changed forever how quantum mechanics will be thought about .