Do quantum states contain exponentially more information than classical states?

Question

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?

Answer 1

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 this view is that the information in a wavefunction is not accessible to us. We can only learn a small fraction of it through a measurement, while destroying the rest of it in the process. In fact the Holevo bound states that the amount of information accessible to us is the same as a classical system of the same size. If this is your criteria for the information contained in a quantum state then the answer to your question is no.

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.
On the one hand, we only got one phone number. On the other hand, we could have chosen any number we wanted, so in some sense the quantum state contained the entire phone book.

It is up to you to choose the view you prefer.

Answer 2

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 ~ 2ⁿ 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

• you are getting only one bit out: is the coded state equal to y, or not? If "not", you're barely any wiser as to what x was, and the state no longer contains the same information after the comparison. It might have changed only slightly if it hasn't been destroyed — and indeed, for the probability of success of the comparison to be high, two coded states must be "close" to orthogonal, we would expect it to have changed only little — but the state will degrade with each comparison until it contains essentially no information about x.

• you can't retrieve an arbitrary bit from x individually from the coded state; as I commented on Joe's answer, that would make the state a random access code^† in which m ~ 2ⁿ bits of information are squeezed into n bits of space. But there is a well-established relationship to the success probability in this case: we have H(p) ≥ 1 − n/m , where H(p) is the entropy of the success probability p of extracting any single bit from x. For a success probability of p ≈ (1 + ε)/2 — so that the chance of getting the correct value for the single bit is ε/2 better than the random chance of a coin-flip — we have H(p) ≈ 1 − ε/ln(2); so that if m = 2ⁿ, for example, we obtain $$ \varepsilon \approx n \ln(2) / 2^n $$ which is a pretty miserably small margin above pure chance, and nothing that you can amplify to a constant probability with only polynomially many repetitions.

† 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.

Summary.

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.

Answer 3

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.

Answer 4

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:

P.E. Frenkel and M. Weiner, Classical information storage in an $n$-level quantum system, arXiv:1304.5723.

Answer 5

Experts agree that one qubit stores no more information than one bit.
But a zillion identical qubits (which you can prepare or manufacture to your specifications, even though you can not clone an unknown qubit) contains about a zillion times more information than a zillion identical bits which still contains only a single bit of information.