Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComputational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations
122
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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 NP-hard, implying that a generic solution of the sign problem would also solve all problems in the complexity class NP (nondeterministic polynomial) in polynomial time.
rate research
Read More
We tutorially review the determinantal Quantum Monte Carlo method for fermionic systems, using the Hubbard model as a case study. Starting with the basic ingredients of Monte Carlo simulations for classical systems, we introduce aspects such as importance sampling, sources of errors, and finite-size scaling analyses. We then set up the preliminary steps to prepare for the simulations, showing that they are actually carried out by sampling discrete Hubbard-Stratonovich auxiliary fields. In this process the Greens function emerges as a fundamental tool, since it is used in the updating process, and, at the same time, it is directly related to the quantities probing magnetic, charge, metallic, and superconducting behaviours. We also discuss the as yet unresolved minus-sign problem, and two ways to stabilize the algorithm at low temperatures.
The term analytic continuation emerges in many branches of Mathematics, Physics, and, more generally, applied Science. Generally speaking, in many situations, given some amount of information that could arise from experimental or numerical measurements, one is interested in extending the domain of such information, to infer the values of some variables which are central for the study of a given problem. For example, focusing on Condensed Matter Physics, state-of-the-art methodologies to study strongly correlated quantum physical systems are able to yield accurate estimations of dynamical correlations in imaginary time. Those functions have to be extended to the whole complex plane, via analytic continuation, in order to infer real-time properties of those physical systems. In this Review, we will present the Genetic Inversion via Falsification of Theories method, which allowed us to compute dynamical properties of strongly interacting quantum many--body systems with very high accuracy. Even though the method arose in the realm of Condensed Matter Physics, it provides a very general framework to face analytic continuation problems that could emerge in several areas of applied Science. Here we provide a pedagogical review that elucidates the approach we have developed.
The dynamics of samples in the continuous-imaginary-time quantum world-line Monte Carlo simulations with extended ensembles are investigated. In the case of a conventional flat ensemble on the one-dimensional quantum S=1 bi-quadratic model, the asymmetric behavior of Monte Carlo samples appears in the diffusion process in the space of the number of vertices. We prove that a local diffusivity is asymptotically proportional to the number of vertices, and we demonstrate the asymmetric behavior in the flat ensemble case. On the basis of the asymptotic form, we propose the weight of an optimal ensemble as $1/sqrt{n}$, where $n$ denotes the number of vertices in a sample. It is shown that the asymmetric behavior completely vanishes in the case of the proposed ensemble on the one-dimensional quantum S=1 bi-quadratic model.
In simple ferromagnetic quantum Ising models characterized by an effective double-well energy landscape the characteristic tunneling time of path-integral Monte Carlo (PIMC) simulations has been shown to scale as the incoherent quantum-tunneling time, i.e., as $1/Delta^2$, where $Delta$ is the tunneling gap. Since incoherent quantum tunneling is employed by quantum annealers (QAs) to solve optimization problems, this result suggests there is no quantum advantage in using QAs w.r.t. quantum Monte Carlo (QMC) simulations. A counterexample is the recently introduced shamrock model, where topological obstructions cause an exponential slowdown of the PIMC tunneling dynamics with respect to incoherent quantum tunneling, leaving the door open for potential quantum speedup, even for stoquastic models. In this work, we investigate the tunneling time of projective QMC simulations based on the diffusion Monte Carlo (DMC) algorithm without guiding functions, showing that it scales as $1/Delta$, i.e., even more favorably than the incoherent quantum-tunneling time, both in a simple ferromagnetic system and in the more challenging shamrock model. However a careful comparison between the DMC ground-state energies and the exact solution available for the transverse-field Ising chain points at an exponential scaling of the computational cost required to keep a fixed relative error as the system size increases.
In this note, we provide a unifying framework to investigate the computational complexity of classical spin models and give the full classification on spin models in terms of system dimensions, randomness, external magnetic fields and types of spin coupling. We further discuss about the implications of NP-complete Hamiltonian models in physics and the fundamental limitations of all numerical methods imposed by such models. We conclude by a brief discussion on the picture when quantum computation and quantum complexity theory are included.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
