Quantum computing is computing that uses the properties of matter at atomic and sub-atomic levels. Matter at this level is the quantum level. At the quantum level, matter's behavior is fundamentally different than its behavior at a larger level. The larger level includes everything you can see without scientific equipment and assume to be true about nature. The larger level also includes computers as most people know them. The computing done on computers as we know them is called classical computing.
The question is whether we can create computers that function at a quantum level. Experiments show it is possible, though we can demonstrate it in only a very limited way. Mathematics indicates that we can do amazing things with quantum computers, if we can construct them at a sufficiently large scale. Industry is trying, but success is limited as of 2011.
Take heart however. The mathematics of classical computing were defined in the 1930's by Turing and Church, but commercial viability took until the 1960's. The quantum computing timeline has already taken longer, but it is moving steadily.
If you are interested in quantum computing, it helps tremendously to be well versed in classical computing--specifically, to have a degree in Computer Science (CS)--because quantum computing principles map nicely to the principles of classical computing.
This is not to say being a CS major makes understanding quantum computing easy! Even with a CS degree, moving into the quantum world is non-trivial. Still, it is vastly easier to learn quantum computing from a base of classical computing than it is to learn quantum physics, per se, then try to determine for yourself the subset of that knowledge that applies to computing.
Also be warned that while mapping from classical computing to quantum computing provides some lift, the two computing paradigms are quite different. Two interesting things I found:
1) The classical Turing Machine breaks--it no longer defines the limits of computation. That was rather shocking when I first heard it. I had always taken a certain comfort in knowing there were strict bounds.
2) Factoring is not an NP problem in quantum computing. This should not be possible according to classical computing. It is also significant because all modern computer security counts on factoring being NP. Yet in quantum computing, factoring is (log n)^3. Amazing! And scary if we ever figure out how to do quantum computing at scale.
The best text to start is:
Quantum Computing for Computer Scientists
by Yanofsky and Mannucci
The reviews on Amazon that compelled me to read it noted how well it connects quantum computing to classical computing. The authors also claim this as one of their goals, and also to keep it highly consumable while remaining rigorous. I found the opinions of the community to be accurate and the goals of the authors achieved.
The next text on my list is:
Quantum Computation and Quantum Information
by Nielsen and Chuang
According to Yanofsky and Mannucci, the Nielsen and Chuang text is advanced and hard to consume without sufficient background. But Yanofsky and Mannucci humbly assert that their text provides sufficient background.
While actual quantum computers are hard to come by, a simulator for one is not. It has been proven mathematically that a quantum Turing Machine exists and can be simulated by a classical Turing Machine. Thus a quantum computer can be simulated by a classical computer. The tradeoff, of course, is performance. Where a quantum computer can factor in (log n)^3 time, a classical computer simulating a quantum computer reverts to NP time.
Performance aside, it is quite exhilarating to run a program that is behaving like a quantum computer. The one I prefer is here:
Written in C, this simulator installs easily on Linux and compiles flawlessly with gcc. It comes with Shor's factoring algorithm (the one that runs in (long n)^3 time) as a sample program.
The two communities I have found helpful are Quantiki and a group on LinkedIn. I recommend LinkedIn over Facebook since the former tends to have a more focused, educated, and professional community.
The Quantiki site is here:
The LinkedIn group is here:
Quantum Computing and Quantum Information
Three companies are at the leading edge of commercial viability:
As of 2011, the success by these companies appears limited, and their claims in press releases are often challenged by the academic community.