# Do quantum states contain exponentially more information than classical states?

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?

## 5 Answers

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.

• However, as far as I understood, this dense coding and other similar scheme do not allow an exponential gap between the quantum and the classical case. In superdense coding ( en.wikipedia.org/wiki/Superdense_coding ), the gain is at most a factor of 2. – Frédéric Grosshans May 25 '11 at 9:03
• The above is not "dense coding", but a "random access code". There are even stronger bounds on what you can do with a random access code. If you want to retrieve a single bit of an $m$ bit string, and you want to do this with success probability $p$ when that string is represented as an $n$ qubit state, then you require $n \geqslant m[1−H(p)]$, where $H(p)$ is the Shannon entropy of the probability $p$. If you wanted $n = 2m$, for example, you require $H(p) = 0.5$, which entails $p < 0.89$. Worse, you don't know whether you've failed. – Niel de Beaudrap Oct 8 '11 at 10:58
• Good answer, +1. See also my answer below. – Anixx Mar 19 '12 at 4:27
• @Joe I didn't understand the "we could have chosen any number we wanted" bit, how? If the whole book is stored in a single state of superposition of all numbers, isn't the outcome random? Otherwise we wouldn't lose the rest of the numbers upon the acquisition of one, right? Thanks for any clarification. – user929304 Jan 6 '15 at 9:11
• @user929304 - I didn't say the whole book is stored in a single state of superposition of all numbers. The way the book is stored is more complicated and described in the paper cited in my answer. The point is that we can choose any measurement basis we want to perform a measurement. Each phone number has a corresponding measurement basis, so by correctly choosing the basis, we can retrieve any number we like. However, the book is destroyed by the measurement so we can't retrieve more than one number. I hope I clarified the issue. – Joe Jan 6 '15 at 9:24

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

• 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 ~ 2n 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 = 2n, 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.

• It's not just us, the best possible representation of a quantum state is clearly going to scale exponentially. – Ron Maimon Dec 13 '11 at 14:28
• There are a number of physicists who are somewhat convinced that the vast bulk of Hilbert space is not in fact occupied by physical states, eg those arising through realistic evolution of quantum systems. Even if you consider states preparable by uniform quantum circuit families (which can approximate arbitrary states to arbitrary precision), the circuit itself is a more concise representation of the state being prepared, for any state which you can prepare in a realistic amount of time. So I'm not really convinced that your statement is true in any obvious way. – Niel de Beaudrap Dec 13 '11 at 20:22
• About the only thing I can say in response is that if you write up a proof of your claim w.r.t Shor's algorithm, you could have yourself a very well-cited publication for your effort. – Niel de Beaudrap Dec 14 '11 at 6:33
• @Ron: your description of Shor's algorithm is a little bit of a caricature. Suffice it to say that if you can show that there is anything that a quantum computer can do that cannot be simulated on a traditional computer efficiently, you stand to win a Turing award. – Niel de Beaudrap Dec 14 '11 at 16:05
• Shor's algorithm (ignore factoring) is something a QC can do. You can interrupt it and ask about properties of the state at that time. If you can prove a classical computer cannot compute that, you have proven something nontrivial. In any case, whatever you stipulate about "scientific reasoning", a state does not contain an exponential amount of information in any operational sense, by Holevo. If classical joint probability vectors are efficiently describable for you in terms of how they're prepared, you must extend the some courtesy to QM. – Niel de Beaudrap Dec 14 '11 at 22:25

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.

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.

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.

• -1. Why would N qubits in an identical state (where N = a zillion, for instance) contain O(N) times more information than N bits in an identical state? – Niel de Beaudrap May 14 '12 at 23:34