The Anti-Infinity Parade

Nov 14, 2020

The difference between classical and quantum

Once you imagine physics through the lens of information theory, you can answer some fundamental questions in completely different ways. One of the oft asked questions by physicists, where you can get an interesting answer, is as follows: is a given system classical or quantum mechanical in nature?

The information-theoretic answer is to ask the question, what resources are required to simulate the behavior of the system? The state of computational complexity (informed by relevant physics), at the moment, is as follows. We find that there are certain computational problems, that can be naturally thought of as simulating certain quantum mechanical systems, for which we have not found any efficient algorithms. The easiest class of such problems is called BQP. We also believe that quantum mechanical systems can be engineered to create quantum computers, that can simulate Turing machines efficiently, and that can solve BQP problems efficiently.

Really, the difference between BQP and P (problems efficiently solvable on a Turing machine) is the problems in the former have a solution space that blows up exponentially as the problem size grows, but that blow up is in a way that a quantum computer can exploit the exponential blow up of multi-qubit Hilbert space to solve the problem efficiently. The second condition is necessary so we don't include problems in NP-hard into BQP.

Now, there are many systems, that are conventionally thought of as quantum mechanical by physicists, because they usually describe these systems using the framework of quantum mechanics. But try simulating these systems. Use every trick in the book to reduce the computational time of the simulation. If you discover that the system can be simulated efficiently on a Turing machine, then, the information theorist will say that the system is classical. The Turing machine algorithm captures a description of system that does not blow up as the system size grows, and so the run time of the algorithm is polynomial.

Conversely, if your quantum mechanical equations defy speed up on a classical computer, then you have tamed the beast of the exponential Hilbert space, and you can claim that the problem is quantum mechanical in nature.

And there you have it. If a classical computer can efficiently simulate the behavior of a system, it is a classical system. If not, then it is quantum.