The tunneling between the two ground states of an Ising ferromagnet is a typical example of many-body tunneling processes between two local minima, as they occur during quantum annealing. Performing quantum Monte Carlo (QMC) simulations we find that the QMC tunneling rate displays the same scaling with system size, as the rate of incoherent tunneling. The scaling in both cases is O(Δ^{2}), where Δ is the tunneling splitting (or equivalently the minimum spectral gap). An important consequence is that QMC simulations can be used to predict the performance of a quantum annealer for tunneling through a barrier. Furthermore, by using open instead of periodic boundary conditions in imaginary time, equivalent to a projector QMC algorithm, we obtain a quadratic speedup for QMC simulations, and achieve linear scaling in Δ. We provide a physical understanding of these results and their range of applicability based on an instanton picture.
The tunneling between the two ground states of an Ising ferromagnet is a typical example of many-body tunneling processes between two local minima, as they occur during quantum annealing. Performing quantum Monte Carlo (QMC) simulations we find that the QMC tunneling rate displays the same scaling with system size, as the rate of incoherent tunneling. The scaling in both cases is O(Δ^{2}), where Δ is the tunneling splitting (or equivalently the minimum spectral gap). An important consequence is that QMC simulations can be used to predict the performance of a quantum annealer for tunneling through a barrier. Furthermore, by using open instead of periodic boundary conditions in imaginary time, equivalent to a projector QMC algorithm, we obtain a quadratic speedup for QMC simulations, and achieve linear scaling in Δ. We provide a physical understanding of these results and their range of applicability based on an instanton picture.
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/{\mathrm{\ensuremath{\Delta}}}^{2}$, where $\mathrm{\ensuremath{\Delta}}$ is the tunneling gap. Since incoherent quantum tunneling is employed by quantum annealers (QAs) to solve optimization problems, this result suggests that there is no quantum advantage in using QAs with respect to quantum Monte Carlo (QMC) simulations. A counterexample is the recently introduced shamrock model (Andriyash and Amin, arXiv:1703.09277), where topological obstructions cause an exponential slowdown of the PIMC tunneling dynamics with respect to incoherent quantum tunneling, leaving open the possibility 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/\mathrm{\ensuremath{\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 indicates an exponential scaling of the computational cost required to keep a fixed relative error as the system size increases.
Recent theoretical and experimental studies have suggested that quantum Monte Carlo (QMC) simulation can behave similarly to quantum annealing (QA). The theoretical analysis was based on calculating transition rates between local minima, in the large spin limit using WentzelKramers-Brillouin (WKB) approximation, for highly symmetric systems of ferromagnetically coupled qubits. The rate of transition was observed to scale the same in QMC and incoherent quantum tunneling, implying that there might be no quantum advantage of QA compared to QMC other than a prefactor. Quantum annealing is believed to provide quantum advantage through large scale superposition and entanglement and not just incoherent tunneling. Even for incoherent tunneling, the scaling similarity with QMC observed above does not hold in general. Here, we compare incoherent tunneling and QMC escape using perturbation theory, which has much wider validity than WKB approximation. We show that the two do not scale the same way when there are multiple homotopy-inequivalent paths for tunneling. We demonstrate through examples that frustration can generate an exponential number of tunneling paths, which under certain conditions can lead to an exponential advantage for incoherent tunneling over classical QMC escape. We provide analytical and numerical evidence for such an advantage and show that it holds beyond perturbation theory.
Quantum tunneling is ubiquitous across different fields, from quantum chemical reactions and magnetic materials to quantum simulators and quantum computers. While simulating the real-time quantum dynamics of tunneling is infeasible for high-dimensional systems, quantum tunneling also shows up in quantum Monte Carlo (QMC) simulations, which aim to simulate quantum statistics with resources growing only polynomially with the system size. Here we extend the recent results obtained for quantum spin models [Phys. Rev. Lett. 117, 180402 (2016)], and we study continuous-variable models for proton transfer reactions. We demonstrate that QMC simulations efficiently recover the scaling of ground-state tunneling rates due to the existence of an instanton path, which always connects the reactant state with the product. We discuss the implications of our results in the context of quantum chemical reactions and quantum annealing, where quantum tunneling is expected to be a valuable resource for solving combinatorial optimization problems.
The tunneling decay event of a metastable state in a fully connected quantum spin model can be simulated efficiently by path-integral quantum Monte Carlo (QMC) [Isakov et al., Phys. Rev. Lett. 117, 180402 (2016)]. This is because the exponential scaling with the number of spins of the thermally assisted quantum tunneling rate and the Kramers escape rate of QMC are identical [Jiang et al., Phys. Rev. A 95, 012322 (2017)], a result of a dominant instantonic tunneling path. In Isakov et al., it was also conjectured that the escape rate in open-boundary QMC is quadratically larger than that of conventional periodic-boundary QMC; therefore, open-boundary QMC might be used as a powerful tool to solve combinatorial optimization problems. The intuition behind this conjecture is that the action of the instanton in open-boundary QMC is a half of that in periodic-boundary QMC. Here, we show that this simple intuition---although very useful in interpreting some numerical results---deviates from the actual situation in several ways. Using a fully connected quantum spin model, we derive a set of conditions on the positions and momenta of the end points of the instanton, which remove the extra degrees of freedom due to open boundaries. In comparison, the half-instanton conjecture incorrectly sets the momenta at the end points to zero. We also found that the instantons in open-boundary QMC correspond to quantum tunneling events in the symmetric subspace (maximum total angular momentum) at all temperatures, whereas the instantons in periodic-boundary QMC typically lie in subspaces with lower total angular momenta at finite temperatures. This leads to a lesser-than-quadratic speedup at finite temperatures. The results provide useful insights in utilizing open-boundary QMC to solve hard optimization problems. We also outline the generalization of the instantonic tunneling method to many-qubit systems without permutation symmetry using spin-coherent-state path integrals.
Quantum tunneling is a valuable resource exploited by quantum annealers to solve complex optimization problems. Tunneling events also occur during projective quantum Monte Carlo (PQMC) simulations, and in a class of problems characterized by a double-well energy landscape their rate was found to scale linearly with the first energy gap, i.e., even more favorably than in physical quantum annealers, where the rate scales with the gap squared. Here we investigate how a guiding wave function---which is essential to make many-body PQMC simulations computationally feasible---affects the tunneling rate. The chosen test beds are a continuous-space double-well problem, the ferromagnetic quantum Ising chain, and the recently introduced shamrock model. As guiding wave function, we consider an approximate Boltzmann-type ansatz, the numerically exact ground state of the double-well model, and a neural-network wave function based on a Boltzmann machine. Remarkably, for each ansatz we find the same asymptotic linear scaling of the tunneling rate that was previously found in the PQMC simulations performed without a guiding wave function. We also provide a semiclassical theory for the double-well with exact guiding wave function that explains the observed linear scaling. These findings suggest that PQMC simulations guided by an accurate ansatz represent a valuable benchmark for physical quantum annealers and a potentially competitive quantum-inspired optimization technique.
Recent numerical result (arXiv:1512.02206) from Google suggested that the D-Wave quantum annealer may have an asymptotic speed-up than simulated annealing, however, the asymptotic advantage disappears when it is compared to quantum Monte Carlo (a classical algorithm despite its name). We show analytically that the asymptotic scaling of quantum tunneling is exactly the same as the escape rate in quantum Monte Carlo for a class of problems. Thus, the Google result might be explained in our framework. We also found that the transition state in quantum Monte Carlo corresponds to the instanton solution in quantum tunneling problems, which is observed in numerical simulations.