Do quantum states contain exponentially more information than classical states? It might seem so at first sight, but what about in light of this talk?
This is exactly the question to which I was seeking with a colleague of mine to give some sort of answer. We considered a game played by a team of two - say Alice and Bob - in which the value of a random variable $x$ is revealed to Alice only, who cannot freely communicate with Bob. Instead, she is given a quantum $n$-level system, respectively a classical $n$-state system, which she can put in possession of Bob in any state she wishes. We thought about evaluating how successfully they managed to store and recover the value of $x$ in the used system by requiring Bob to specify a value $z$ and giving a reward of value $f(x,z)$ to the team.
Now Holevo's bound in itself does not imply that the expected reward in the quantum case could not be larger than in the classical case. (One can easily give an example of 2 channel matrices such that the first one has a greater capacity, yet in a certain game - if it is played only a few times - it is better to use the second channel.)
Nevertheless, we've managed to show that whatever the probability distribution of $x$ and the reward function $f$ are, when using a quantum $n$-level system, the maximum expected reward obtainable with the best possible team strategy is equal to that obtainable with the use of a classical $n$-state system.
See the details in my article on the arXiv:
Joe's earlier answer is even-handed in a way which reflects the ambivalence of a number of computer scientists about the meaning of the mathematical operators involved in quantum information. So, as a computer scientist, I feel free to answer on a somewhat different basis.
What does it mean to store information in a quantum state?
Quantum states are not linear operators (neither vectors of numbers, nor trace-1 square matrices). We represent quantum states by such mathematical objects, but that isn't what quantum states are; and those notations are terribly inefficient space-wise in the sense that the state of an electron requires no more space than the electron itself. Though we have no better representations ourselves, we may as well recognize that the notation is not the state itself. If you want to ask how much information a quantum state contains, looking at the way we represent those states is the wrong answer; you have to consider what information can actually be extracted from the physical system.
The amount of information contained by a state is that which is available to be retrieved, and which you can reliably retrieve from it by physical procedures. The question you have to ask is: "What do you mean by reliably?" This is perhaps subject to interpretation, but if what you're interested in is extracting information in polynomial time (i.e. in an amount of time which scales like a polynomial in the size of your storage system) with at least some threshold probability of success (say p > 0.9, but any constant larger than 0.5 will be about the same), then the answer is NO: the amount of information you can reliably extract will not scale exponentially as the system size.
You might think that you can get around this by also asking "What do you mean by extract?" Perhaps by being very sneaky, you can find alternative ways of squeezing an exponential amount of information into a system in a way that you can use later. And the study of quantum communication complexity has some excellent examples! But none of them enable an exponential information to be reliably obtained from a state.
For example: quantum fingerprinting
For instance, suppose you want to store an m-bit string x, but all you really care about being able to do is to compare it against some other m-bit string y some time in the future, and see if x = y (possibly destroying the state by making the comparison). In that case, you can squeeze m ~ 2n bits into an n-qubit state, and successfully make the comparison with constant probability! (This is called quantum fingerprinting.) Is this not squeezing an exponential amount of information into a handful of qubits? The answer is no: because although this is a clever use of coding which allows you to compare an exponential number of possible entities, in the end
† Random access codes are sometimes, but now it seems quite rarely, referred to as a "dense code". However, superdense coding refers to something else: a communication protocol with two bits of communication between Alice and Bob (one qubit in each direction). This protocol is also interesting, but a different sort of thing to random access codes.
If you want to talk about the information stored in a quantum state, you have to talk about how you're going to get that information out of the state. In the end, Holevo puts a bound of one bit per qubit, of the amount of information you can extract with near certainty, out of a quantum state on a very large number of qubits; and any attempts to do better than this will come at a cost of diminishing success probability.
So in the end, no, you cannot squeeze an exponential amount of information into a quantum state.
Experts agree that one qubit stores no more information than one bit.
Look, classical information and processing devices can be of two types: analog and digital.
Analog information has a disadvantage: every time analog information is copied it decreases in quality. Some of the information gets lost. Thus analog information is not suitable for any extensive information processing that involves repeated copying.
But digital information also has its own limitation: unlike an analog device, digital device can only manipulate with quantities of information that are no smaller than one bit. If you have a variable that carries less than a bit of information, you still have to use a whole bit to store it (you can manipulate with quantities of information that represent non-integer number of bits, say a trit which is about 1.6 bits but it is still greater than a bit with bit remaining the smallest unit).
The main feature of quantum information in this respect is that it allows to digitally (i.e., without loss) independently manipulate with quantities of information that are less than one bit.
Suppose you have a database with 1000 variables that take 1/1000 of a bit each. In a classical digital computer you would have to employ 1000 bit to store this database. In a quantum device, conversely, you would need only one bit register to store the same information.
The disadvantage with the quantum information devices is that while you can freely manipulate with quantities of information below one bit, if you want to copy the information from quantum device into a classical digital medium, only one variable gets copied from one bit register and other variables stored in that register get lost.
That means that if you want to avoid information loss in this process you have to lead the quantum information in your device to such a state, before the reading, in which one variable occupies one register (and as the number of quantum registers is usually less than the number of variables used in the process, this usually means that unnecessary variables will be lost).
The art of quantum programming is to invent a process in which the result of a quantum computation includes much less number of variables than is used in the process, so that the result to fit in a quantum register in such a way so that each variable to occupy one qubit, which allows to read the result by a classical device without loss.
Not necessary to say that simulating a quantum device on a classical digital computer also requires allocating at least one bit per variable which may require much excess memory.
So to answer your question directly, a quantum register of n qubits stores exactly the same amount of information as a classical register of n bits. But it can store more than n independently-controllable variables of less than one bit capacity each, which a classical register cannot do.
The answer depends on what you mean by the information contained in a quantum state.
If you think of the wavefunction itself as a real physical entity then the answer is yes.
The problem with the second view is that under some conditions it is possible to choose in advance which part of the information in the wavefunction we want (see this paper for example). For example, imagine storing a whole phone book in a single quantum state, for which the accessible information is only the size of a single phone number. After retrieving a phone number of our choice, the phone book is destroyed.
It is up to you to choose the view you prefer.