Is an exponentially large state space unique to quantum physics?

Question

The exponential growth in the dimension of a many-body Hilbert space with increasing particle number is often presented as something that makes quantum physics very different from classical physics. But is this really true? Doesn't a classical stochastic system also have an exponentially large state space?

Consider n (not necessarily statistically independent) copies of a system that can take on $d$ different values. If the systems are quantum mechanical, then the state space of the full system is the complex projective space $\mathrm{CP}^{d^n-1}$. This is the famous "exponentially large (in $n$) Hilbert space" of quantum physics. If we ignore the complex structure, then this is a manifold (without boundary) with $2(d^n-1)$ real dimensions.

But if the systems are classically stochastic (e.g. described by a local-hidden-variable theory), then the state space of the full system is a ($d^n-1$)-simplex. This is a manifold (with boundary) with $d^n-1$ real dimensions. This is also exponentially large in $n$; in fact, it's just half the dimension of the quantum-mechanical case.

Now, I'm well aware of the many ways that quantum systems are qualitatively differently from classical stochastic systems: Bell's theorem, the Kochen-Specker theorem, the fact that BQP is probably strictly larger than BPP, etc. etc. But it seems to me that the fundamental difference between quantum and classical systems is not the exponentially large Hilbert space of quantum mechanics, but instead the fact that in quantum mechanics, amplitudes are complex rather than nonnegative-real (and are converted into "real" probabilities via the Born rule), which allows for the possibility of destructive interference between amplitudes.

Here's one concrete example to make the point sharper: people often say that the power of quantum computers is that they can "use" the exponentially large Hilbert space to perform computations. But I would argue that a (classical) probabilistic Turing machine can also "use" an exponentially large state space to compute (although I know that some people will object that that is a very different sense of the word "use" than in the case of a quantum computer). And yet, the class of problems BPP that can be efficiently solved by a probabilistic Turing machine is suspected not to be any larger than the class of problems P that can be efficiently solved by a deterministic Turing machine. So it seems to me that in the case of a probabilistic Turing machine, an exponentially large state space is not useful for qualitatively improving a computer's performance.

Am I missing some mathematical distinction that makes the "exponentially large state space" unique to quantum physics? Or is it just that, for philosophical reasons, people consider the exponentially large Hilbert space of quantum physics to be "real" (in the colloquial rather than the mathematical sense of the word) but not the exponentially large simplex of stochastic classical physics? (I don't mean that question dismissively; that's certainly a reasonable philosophical position to hold.)

Answer 1

The exponential growth in the dimension of a many-body Hilbert space with increasing particle number is often presented as something that makes quantum physics very different from classical physics.

Since you didn't provided any specific reference or citation, I decided to search some to take as reference. In Nielsen and Chuang, Quantum Information and Quantum Computation, section 1.2.1 and page 17 of 10th edition, we could find the following

More generally, we may consider a system of $n$ qubits. The computational basis states of this system are of the form $|x_1x_2\dots x_n\rangle$, and so a quantum state of such a system is specified by $2^n$ amplitudes. For $n = 500$ this number is larger than the estimated number of atoms in the Universe! Trying to store all these complex numbers would not be possible on any conceivable classical computer. Hilbert space is indeed a big place. In principle, however, Nature manipulates such enormous quantities of data, even for systems containing only a few hundred atoms. It is as if Nature were keeping 2500 hidden pieces of scratch paper on the side, on which she performs her calculations as the system evolves. This enormous potential computational power is something we would very much like to take advantage of. But how can we think of quantum mechanics as computation?

Observe that, even if they are directly talking about Hilbert space dimension, the figure of merit is the inconceivable memory necessary to register all the complex amplitudes necessary to specify a single state. This changes a lot the meaning of the dimensional advantage.

I think a good comparison could be made by analogy:consider a coin. If we think about the state of it, we could say that it is well represented by a bit, 0 for heads 1 for tails. But the coin is being tossed, and we could say that it's probability $p(H)$ is the state of the system. Now we are in the Classical stochastic regime as you considered. It is true that now its state is a real number, and it should represented by a floating-point in base 2, with would take not only one but a lot of bits to represent it with enough precision.

If we want to simulate a coin, it doesn't take a bit. It would need a pseudorandom number generator, or any source of randomness to simulate it. To simulate $n$ tossing coins, it would take a exponentially growing number of deterministic bits to simulate, or to register a single state.

Now imagine that we build a computer such that each unit of memory is a tossing coin. A complete stochastic classical computer. We could call such unit of memory by cbits (coin bits). Of course it would need a single cbit to simulate a tossing coin (by construction).

While a construction of a tossing coin computer is not conceivable, the quantum one is a project. The exponential advantage comes from this aspect: in the resource point of view, about its construction. I don't know other meaning for such affirmation, so if this not covers your question, I would like to ask a source with the aforementioned claim.