Whether or not it will ever become a practical technology, there is a beauty to the theory of quantum computation that gives it a powerful appeal (a) as a lovely branch of abstract mathematics, (b) as a generalization of the paradigm of classical computer science that had completely escaped the attention of computer scientists until the 1980’s, demonstrating that in a very deep sense the theory of computation cannot be divorced from the physics of the devices that carry out the computation, and (c) as a source of new examples that illustrate and illuminate the surprising and often mysterious kinds of phenomena that the quantum behavior of matter can give rise to.
You may or may not find point (a) compelling. Many physicists (not including me) are immune to the songs of this particular siren.
The most striking manifestation of point (b) is that for certain special computational tasks of practical interest, a quantum computer can be vastly more efficient than anything ever imagined in the classical theory of computational complexity, in that the time it takes the quantum computer to accomplish the task scales up much more slowly with the size of the input than it can in any classical computer. Much of what follows will be devoted to examining the most celebrated examples of this speed-up.
Item (c) brings us to our first topic. Several years ago I mentioned to a distinguished theoretical physicist (an authority on string theory and director of a great theoretical physics institute, who was later awarded a Nobel prize in physics for his work on quark confinement) that I spent the first four or five lectures of a course in quantum computation giving an introduction to quantum mechanics for mathematically literate people who knew nothing about quantum mechanics and quite possibly little if anything about physics. His response was that any application of quantum mechanics that can be taught after only a four hour introduction to the subject, cannot have serious intellectual content. After all, he remarked, it takes any physicist many years to develop a feeling for quantum mechanics.
It’s a good point. Nevertheless computer scientists and mathematicians with no background in physics have been able quickly to learn enough quantum mechanics to understand and contribute importantly to the theory of quantum computation. I believe there are two main reasons for this.
First of all, a quantum computer — or, more accurately, the abstract quantum computer that one hopes some day to be able to embody in actual hardware — is an extremely simple example of a physical system. It is discrete, not continuous. It is made up out of a finite number of units, each of which is the simplest possible kind of quantum mechanical system, a so-called two-state system, whose possible behavior, as we shall see, is highly constrained and easily analyzed. Much of the analytical complexity of learning quantum mechanics is connected to mastering the description of continuous (infinite-state) systems.
By restricting attention to collections of two-state (or even d-state systems for finite d) one can avoid much suffering. Of course one also loses much wisdom, but hardly any of it — at least at this stage of the art — is relevant to the theory of quantum computation.
Second, and just as important, the most difficult part of learning quantum mechanics is to get a good feeling for how the abstract formalism can be applied to actual phenomena.
This almost invariably involves formulating oversimplified abstract models of the real phenomena, to which the quantum formalism can then be applied. The best physicists have an extraordinary intuition for what features of the phenomena are essential and must be represented in an abstract model, and what features are inessential and can be ignored. It takes years to develop such intuition. Some never do. The theory of quantum computation, however, is entirely concerned with the abstract model — the easy part of the problem.
To understand how to build a quantum computer, or even to study what physical systems are promising candidates for realizing such a device, you must indeed have many years of experience in quantum mechanics and its applications under your belt. But if you only want to know what such a device is capable of doing in principle, then there is no reason to get involved in the really difficult physics of the subject.
--LECTURE NOTES ON QUANTUM COMPUTATION
Cornell University, Physics 481-681, CS 483; Spring, 2006
c 2006, N. David Mermin