Non-Computability of Hidden Variables

[DarMM]

I was just reading this paper:
https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.118.130401

It essentially shows that if the dynamics of the signalling mechanism in a nonlocal hidden variable theory were computable, then Alice and Bob in the typical EPR set up could use it to signal to each other faster than light.

Just to note there is an assumption that the hidden variable state $\lambda$ can be resolved or fully known, Bohmian Mechanics for example escapes the result by having fundamentally unknowable initial conditions (though even there the complexity class of Bohmian mechanics is larger than that of a quantum computer, $BQP$)

I have seen little discussion of the result outside of the doctoral thesis of one of the authors:
http://www.glyc.dc.uba.ar/santiago/papers/thesisSenno.pdf

Do people here have any opinions on the result?

 

[DrChinese]

Full article available:

https://arxiv.org/abs/1606.08403

 

[atyy]

At least heuristically it seems to make sense, and doesn't conflict with Bohmian mechanics. The authors state in their introduction that this is because Bohmian mechanics does allow faster than light communication (in principle, if the initial conditions are not suitably random, as discussed eg. by Valentini). A variant of this reasoning is stated in their conclusion, as DarMM mentioned above.

"But, since quantum correlations are non-signaling, such signaling mechanism must be re-stricted to the so-called hidden variables, and not reach the phenomenological level. Known examples of deterministic non-local theories violating the non-signaling principle (also referred to as parameter independence [6]) at the hidden-variable level are: the hidden variable model with communication of Toner and Bacon [7] and, more prominently, Bohmian mechanics [8]."

I guess the work has more implications on using Bell inequality violations plus the non-signalling assumption to guarantee security of a code. I think this result grew out of earlier work from some of the same authors (eg. Acin) showing that the Bell inequality plus non-signalling could guarantee randomness. In the paper mentioned in the OP, the authors say: "Our result imply that, under the well established assumption that no observable signaling exists, we need to accept the existence of truly unpredictable physical processes. Earlier work includes Pironio et al, https://arxiv.org/abs/0911.3427. There's a review by Acin and Masanes of randomness certification in https://arxiv.org/abs/1708.00265.

 

[DarMM]

I personally find it one of the most shocking results I've seen, the possibility of fundamental dynamics that cannot be computed/is not algorithmic. I wonder could one find the complexity class, i.e. is it equivalent to the Halting Problem or the Totality Problem?

It seems to split Hidden Variable theories into three camps, either the dynamics cannot be computed or the physical state can never be exactly known or (the obvious one) there's a regime where it disagrees with quantum theory.

The first two imply, despite determinism, the hidden variable theory would be unpredictable. Learning the "true" theory underneath might not give you much increased predictive power. Might tie in with Colbeck and Renner's paper:
https://arxiv.org/abs/1005.5173

 

[Strilanc]

I personally find it one of the most shocking results I've seen, the possibility of fundamental dynamics that cannot be computed/is not algorithmic.

I'm not sure why you would take that bullet instead of the "okay it's random" bullet or the "okay it's a communication mechanism in principle" bullet.

Keep in mind that the inference process from the paper is horrendously inefficient. In practice, even if I promised you that there was some non-local program deciding on the outputs of Bell tests, you wouldn't actually be able to figure out what the program was before the heat death of the universe. So you wouldn't actually be able to use it as a communication mechanism. E.g. the non-local program could be a cryptographic pseudo random number generator with a million-bit seed. To make matters worse you may not even be seeing sequential outputs, e.g. the entire rest of the universe could be constantly pulling samples from the same CPRNG.

I wonder could one find the complexity class, i.e. is it equivalent to the Halting Problem or the Totality Problem?

The proof in the paper relies very strongly on the computation having some bound on the amount of time it takes, e.g. linear time. Otherwise there would be some hidden programs that "stayed ahead" of any given inference process, since the inference process has to pick some specific rate at which to dovetail over all possible programs.

 

[DarMM]

I'm not sure why you would take that bullet instead of the "okay it's random" bullet or the "okay it's a communication mechanism in principle" bullet.

There isn't any reason to, it's just one of the possibilities I've listed. Like most hidden variable no-go theorems it simply reduces things to a set of options. However it's an option I haven't seen in other no-go theorems and a pretty surprising one.
"Okay it's random" would be standard Dirac-VonNeumann QM and not common in hidden variable theories, "okay it's a communication mechanism in principle" is covered by the third option.

Keep in mind that the inference process from the paper is horrendously inefficient. In practice, even if I promised you that there was some non-local program deciding on the outputs of Bell tests, you wouldn't actually be able to figure out what the program was before the heat death of the universe. So you wouldn't actually be able to use it as a communication mechanism. E.g. the non-local program could be a cryptographic pseudo random number generator with a million-bit seed. To make matters worse you may not even be seeing sequential outputs, e.g. the entire rest of the universe could be constantly pulling samples from the same CPRNG.

Yes, but QM would predict such a thing couldn't be done even if it were inefficient, hence this falls under the third option I listed.

 

[atyy]

I personally find it one of the most shocking results I've seen, the possibility of fundamental dynamics that cannot be computed/is not algorithmic. I wonder could one find the complexity class, i.e. is it equivalent to the Halting Problem or the Totality Problem?

OK, I admit that is a little surprising, but maybe not so given the existing research programme of randomness certification. Sometime ago on PF we discussed https://arxiv.org/abs/1502.04135 and https://arxiv.org/abs/1502.04573, which I don't understand well.

It seems to split Hidden Variable theories into three camps, either the dynamics cannot be computed or the physical state can never be exactly known or (the obvious one) there's a regime where it disagrees with quantum theory.

The first two imply, despite determinism, the hidden variable theory would be unpredictable. Learning the "true" theory underneath might not give you much increased predictive power. Might tie in with Colbeck and Renner's paper:
https://arxiv.org/abs/1005.5173

That's what's nice about Bohmian Mechanics - there is a regime where it disagrees with quantum theory, and in principle predicts new physics. I don't mean to support Bohmian mechanics specifically, but I like it as the idea that trying to solve the measurement problem as exactly analogous to the problem of quantum gravitation - there should be new physics (here I'm including asymptotic safety as new physics). Dirac himself thought that this would be the most likely solution to the measurement problem: https://blogs.scientificamerican.com/guest-blog/the-evolution-of-the-physicists-picture-of-nature/

 

[DarMM]

Thanks atyy, I'll read those threads and papers and get back to you.