News for hackers. Stuff that matters.
Re:Superconductivity Theory Under Attack by acqq on Sunday December 01, 2019 @05:43PM (#21678315)
Thanks for mentioning the term that I was able to find:

https://en.wikipedia.org/wiki/Numerical_sign_problem

https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.94...

"Computational Complexity and Fundamental Limitations to Fermionic Quantum Monte Carlo Simulations, Matthias Troyer and Uwe-Jens Wiese, Phys. Rev. Lett. 94, 170201, 4 May 2005"

"Quantum Monte Carlo simulations, while being efficient for bosons, suffer from the “negative sign problem” when applied to fermions — causing an exponential increase of the computing time with the number of particles. A polynomial time solution to the sign problem is highly desired since it would provide an unbiased and numerically exact method to simulate correlated quantum systems. Here we show that such a solution is almost certainly unattainable by proving that the sign problem is nondeterministic polynomial (NP) hard, implying that a generic solution of the sign problem would also solve all problems in the complexity class NP in polynomial time."

https://arxiv.org/abs/cond-mat/0408370

Re:Superconductivity Theory Under Attack by eigenspace on Sunday December 01, 2019 @06:59PM (#21678692)
It should be noted as well that the sign-problem shows up for many (most of the interesting ones anyway) bosonic systems as well.
Re:Superconductivity Theory Under Attack by AstralStorm on Monday December 02, 2019 @12:49PM (#21684767)
NP hard means that a quantum computing will not solve this problem efficiently either, as that's BQP class.

(We do not know how to implement any MA or QMA efficiently.)

Re:Superconductivity Theory Under Attack by eigenspace on Monday December 02, 2019 @03:52PM (#21686766)
These quantum Monte Carlo simulations are only necessary because we don't have quantum simulators [1], so yes while a quantum computer would not necessarily solve the sign problem, it would make it irrelevant.

[1] https://en.wikipedia.org/wiki/Quantum_simulator

Re:Superconductivity Theory Under Attack by AstralStorm on Tuesday December 03, 2019 @04:04AM (#21690950)
QMC computes multiple superimposed versions of classical MC at the same time, giving a polynomial speedup, not good enough for NP hard problems.

QMC cannot speed up simulation of a different quantum system - unless you're simulating a strict subset of your specific machine.

Quantum simulator is not a QMC system - it is designed to exhibit same behavior as a modelled system. That makes it somewhat useless for a system whose properties you do not understand. Any grid of fermions does not act like any other - if it did, BCS version would be accurate.

Re:Superconductivity Theory Under Attack by eigenspace on Tuesday December 03, 2019 @12:37PM (#21694539)
I don't think you understand what quantum monte carlo is or why it works. Nearly everything you've said is just plain incorrect.

Furthermore, I never said quantum simulation was QMC. I said that having quantum computers able to simulate many-body Hamiltonians would make QMC irrelevant, or at the very least would not suffer the same limitations that QMC suffers, specifically for strongly correlated fermion problems.

I suggest getting a stronger grasp on the literature before you go around making claims like this. Whether you know it or not, you're actively spreading misinformation and making the internet a worse place.