4 ms·

Thanks for mentioning the term that I was able to find: https://en.wikipedia.org/wiki/Numerical_sign_problem https://en.wikipedia.org/wiki/Numerical_sign_probl

by acqq 7y ago

Thanks for mentioning the term that I was able to find: https://en.wikipedia.org/wiki/Numerical_sign_problem https://en.wikipedia.org/wiki/Numerical_sign_problem https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.94.170201 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 https://arxiv.org/abs/cond-mat/0408370

eigenspace 7y ago
It should be noted as well that the sign-problem shows up for many (most of the interesting ones anyway) bosonic systems as well.
AstralStorm 7y ago
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.)
- eigenspace 7y ago
  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 https://en.wikipedia.org/wiki/Quantum_simulator
  - AstralStorm 7y ago
    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.
    - eigenspace 7y ago
      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.

by acqq 7y ago

eigenspace 7y ago

It should be noted as well that the sign-problem shows up for many (most of the interesting ones anyway) bosonic systems as well.

AstralStorm 7y ago

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.)

eigenspace 7y ago
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 https://en.wikipedia.org/wiki/Quantum_simulator
- AstralStorm 7y ago
  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.
  - eigenspace 7y ago
    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.