# How does a classical computer simulate nonclassical correlations?

This may be a dumb question, if so please forgive me, it is late at night.

I have learned that a classical computer can simulate a quantum computer in exponential time and space, but classical computers are bound to non-quantum phenomenon.

How then, would one be able to simulate say CHSH, which produces fundamentally quantum probabilities that cannot be explained locally/classically? Am I misinterpreting the meaning of simulate?

In general, how could a classical computer simulate quantum phenomena that cannot be explained classically (such as the dynamics of more than a single particle)? I would think that one could not generate random numbers violating any of Bell's inequalities, i.e. necessarily quantum correlations are off limits.

• – glS
Jun 14 '20 at 12:50

How then, would one be able to simulate say CHSH, which produces fundamentally quantum probabilities that cannot be explained locally/classically? Am I misinterpreting the meaning of simulate?

Quantum phenomena cannot be "explained classically" only when locality is taken into consideration. In other words, classical phenomena cannot reproduce (some types of) quantum correlations provided that we don't allow for certain types of correlations.

As a concrete example, consider a standard CHSH scenario. We can compute the outcome probability distributions for each measurement setting (it's what you do when you study the protocol), therefore you can trivially write some code to "simulate" the results of an experiment, meaning to draw a possible sequence of measurement outcomes you would find in an experiment. But this is clearly not the same as observing nonlocality with a classical computer: you would just be crunching some numbers that you know, in some situations, can be interpreted as markers of nonclassical correlations.

Put in another way, you can always sample from an arbitrary probability distribution $$p(ab|xy)$$. Whether such a distribution is "nonclassical" is only meaningful in relation to some imposed restriction (e.g. defining "classical" when it can be written as $$p(ab|xy)=\sum_\lambda p_\lambda p_\lambda(a|x) p_\lambda(b|y)$$). When you simulate such a distribution on a computer, you don't need to respect such restrictions, so there is no problem.

In general, how could a classical computer simulate quantum phenomena that cannot be explained classically

Aside from locality constraints, such as those described above, quantum mechanics does not predict output probability distributions that are incompatible with classical physics. The difference is in how those outputs can be obtained: quantum mechanic can produce output probability distributions in a radically different way than what classical physics allows for, and in some cases these new behaviours are more efficient.

There are two definitions of simulation that are commonly used in this context.

We consider a quantum computation to be: 1. loading an input 2. performing some processing 3. doing a measurement

This defines a distribution on possible measurement outcomes for each input.

Weak Simulation would be a classical randomised algorithm that could sample from these distributions, given a suitable description of the quantum computation as defined above.

Strong Simulation is the ability to approximately calculate individual probabilities.

A naive simulation algorithm that uses exponential time and space is to store the state as a big vector (of length $$2^n$$) and then multiply it by the matrices for each of the gates (size $$2^n \times 2^n$$). Then measurement probabilities can also be calculated by finding the eigenspaces for the measurement operator, and projecting the final state vector onto the one of interest.

This doesn't violate any laws of quantum physics, because it is simulating the whole system, not simulating each qubit locally