Article Source - "Quantized gravitational responses, the sign problem, and quantum complexity"



    It is believed that not all quantum systems can be simulated efficiently using classical computational resources. This notion is supported by the fact that it is not known how to express the partition function in a sign-free manner in quantum Monte Carlo (QMC) simulations for a large number of important problems. The answer to the question—whether there is a fundamental obstruction to such a sign-free representation in generic quantum systems—remains unclear. Focusing on systems with bosonic degrees of freedom, we show that quantized gravitational responses appear as obstructions to local sign-free QMC. In condensed matter physics settings, these responses, such as thermal Hall conductance, are associated with fractional quantum Hall effects. We show that similar arguments also hold in the case of spontaneously broken time-reversal (TR) symmetry such as in the chiral phase of a perturbed quantum Kagome antiferromagnet. The connection between quantized gravitational responses and the sign problem is also manifested in certain vertex models, where TR symmetry is preserved.


As much as I hate to play devil's advocate here, I don't think that paper backs up all the claims made by the Cosmos author. Here's why:

1. The result just shows that certain QMC problems take exponential time/resources to simulate.* This means that if we are living in a simulation, the universe simulating us would be exponentially larger than our universe, which does suggest that maybe Musk's argument that it's highly likely that we live in a simulation is flawed. But, it does not suggest that it's impossible for us to live in a simulation.

2. These results are only for classical algorithms. One of the big draws of quantumn computing is, well, efficient simulation of quantumn physics! So this paper doesn't eliminate the possibility we live in a simulation on a quantumn computer.**

In short: simulation isn't impossible, and math/science has yet to determine that simulation must be difficult. Right now, we don't know an efficient simulation technique, but we also don't know that we can't find one.

* But is the problem itself in EXP, or is it perhaps NP-hard and it's just that the only known algorithms to solve the problem take exponential time? Some reading leads me to believe it's "merely" NP-hard, which would mean that efficient (read: polynomial-time) simulation on a classical machine is possible if P=NP.

** Going off the assumption this problem is NP-hard, efficient polynomial-time quantumn simulation may not be a foregone conclusion. On the other hand, if efficient simulation implies that we are being simulated on a quantumn machine, what does that say about the "host" universe's physics?

posted by rene: 410 days ago