Stoquastic Hamiltonians are characterized by the property that their off-diagonal matrix elements in the standard product basis are real and non-positive. Many interesting quantum models fall into this class including the Transverse field Ising Model (TIM), the Heisenberg model on bipartite graphs, and the bosonic Hubbard model. Here we consider the problem of estimating the ground state energy of a local stoquastic Hamiltonian $H$ with a promise that the ground state of $H$ has a non-negligible correlation with some `guiding' state that admits a concise classical description. A formalized version of this problem called Guided Stoquastic Hamiltonian is shown to be complete for the complexity class $\MA$ (a probabilistic analogue of $\NP$). To prove this result we employ the Projection Monte Carlo algorithm with a variable number of walkers. Secondly, we show that the ground state and thermal equilibrium properties of the ferromagnetic TIM can be simulated in polynomial time on a classical probabilistic computer. This result is based on the approximation algorithm for the classical ferromagnetic Ising model due to Jerrum and Sinclair (1993).Stoquastic Hamiltonians are characterized by the property that their off-diagonal matrix elements in the standard product basis are real and non-positive. Many interesting quantum models fall into this class including the Transverse field Ising Model (TIM), the Heisenberg model on bipartite graphs, and the bosonic Hubbard model. Here we consider the problem of estimating the ground state energy of a local stoquastic Hamiltonian $H$ with a promise that the ground state of $H$ has a non-negligible correlation with some `guiding' state that admits a concise classical description. A formalized version of this problem called Guided Stoquastic Hamiltonian is shown to be complete for the complexity class $\MA$ (a probabilistic analogue of $\NP$). To prove this result we employ the Projection Monte Carlo algorithm with a variable number of walkers. Secondly, we show that the ground state and thermal equilibrium properties of the ferromagnetic TIM can be simulated in polynomial time on a classical probabilistic computer. This result is based on the approximation algorithm for the classical ferromagnetic Ising model due to Jerrum and Sinclair (1993).

Quantum Information and ComputationOct 1, 201536 citations

Monte Carlo simulation of stoquastic Hamiltonians

Sergey B. Bravyi

Stoquastic Hamiltonians are characterized by the property that their off-diagonal matrix elements in the standard product basis are real and non-positive. Many interesting quantum models fall into this class including the Transverse field Ising Model (TIM), the Heisenberg model on bipartite graphs, and the bosonic Hubbard model. Here we consider the problem of estimating the ground state energy of a local stoquastic Hamiltonian $H$ with a promise that the ground state of $H$ has a non-negligible correlation with some `guiding' state that admits a concise classical description. A formalized version of this problem called Guided Stoquastic Hamiltonian is shown to be complete for the complexity class MA (a probabilistic analogue of NP). To prove this result we employ the Projection Monte Carlo algorithm with a variable number of walkers. Secondly, we show that the ground state and thermal equilibrium properties of the ferromagnetic TIM can be simulated in polynomial time on a classical probabilistic computer. This result is based on the approximation algorithm for the classical ferromagnetic Ising model due to Jerrrum and Sinclair (1993).Stoquastic Hamiltonians are characterized by the property that their off-diagonal matrix elements in the standard product basis are real and non-positive. Many interesting quantum models fall into this class including the Transverse field Ising Model (TIM), the Heisenberg model on bipartite graphs, and the bosonic Hubbard model. Here we consider the problem of estimating the ground state energy of a local stoquastic Hamiltonian $H$ with a promise that the ground state of $H$ has a non-negligible correlation with some `guiding' state that admits a concise classical description. A formalized version of this problem called Guided Stoquastic Hamiltonian is shown to be complete for the complexity class MA (a probabilistic analogue of NP). To prove this result we employ the Projection Monte Carlo algorithm with a variable number of walkers. Secondly, we show that the ground state and thermal equilibrium properties of the ferromagnetic TIM can be simulated in polynomial time on a classical probabilistic computer. This result is based on the approximation algorithm for the classical ferromagnetic Ising model due to Jerrrum and Sinclair (1993).

arXiv:1402.2295Feb 10, 201413 citations

Determining quantum Monte Carlo simulability with geometric phases

Itay Hen

Although stoquastic Hamiltonians are known to be simulable via sign-problem-free quantum Monte Carlo (QMC) techniques, the nonstoquasticity of a Hamiltonian does not necessarily imply the existence of a QMC sign problem.We give a sufficient and necessary condition for the QMC-simulability of Hamiltonians in a given basis: We prove that a QMC simulation will be sign-problem-free if and only if all the overall total phases along the chordless cycles of the weighted graph whose adjacency matrix is the Hamiltonian are zero (modulo 2π ).We use our findings to provide a construction for nonstoquastic, yet sign-problem-free and hence QMC-simulable, quantum many-body models.We also demonstrate why the simulation of truly sign-problematic models using the QMC weights of the stoquasticized Hamiltonian is generally suboptimal.We offer a superior alternative.Although stoquastic Hamiltonians are known to be simulable via sign-problem-free quantum Monte Carlo (QMC) techniques, the nonstoquasticity of a Hamiltonian does not necessarily imply the existence of a QMC sign problem.We give a sufficient and necessary condition for the QMC-simulability of Hamiltonians in a given basis: We prove that a QMC simulation will be sign-problem-free if and only if all the overall total phases along the chordless cycles of the weighted graph whose adjacency matrix is the Hamiltonian are zero (modulo 2π ).We use our findings to provide a construction for nonstoquastic, yet sign-problem-free and hence QMC-simulable, quantum many-body models.We also demonstrate why the simulation of truly sign-problematic models using the QMC weights of the stoquasticized Hamiltonian is generally suboptimal.We offer a superior alternative.

arXiv:2012.02022Physical Review ResearchApr 29, 202120 citations

Exponential Enhancement of the Efficiency of Quantum Annealing by Non-Stoquastic Hamiltonians

Hidetoshi Nishimori, Kabuki Takada

Non-stoquastic Hamiltonians have both positive and negative signs in off-diagonal elements in their matrix representation in the standard computational basis and thus cannot be simulated efficiently by the standard quantum Monte Carlo method due to the sign problem. We describe our analytical studies of this type of Hamiltonians with infinite-range non-random as well as random interactions from the perspective of possible enhancement of the efficiency of quantum annealing or adiabatic quantum computing. It is shown that multi-body transverse interactions like XX and XXXXX with positive coefficients appended to a stoquastic transverse-field Ising model render the Hamiltonian non-stoquastic and reduce a first-order quantum phase transition in the simple transverse-field case to a second-order transition. This implies that the efficiency of quantum annealing is exponentially enhanced, because a first-order transition has an exponentially small energy gap (and therefore exponentially long computation time) whereas a second-order transition has a polynomially decaying gap (polynomial computation time). The examples presented here represent rare instances where strong quantum effects, in the sense that they cannot be efficiently simulated in the standard quantum Monte Carlo, have analytically been shown to exponentially enhance the efficiency of quantum annealing for combinatorial optimization problems.Non-stoquastic Hamiltonians have both positive and negative signs in off-diagonal elements in their matrix representation in the standard computational basis and thus cannot be simulated efficiently by the standard quantum Monte Carlo method due to the sign problem. We describe our analytical studies of this type of Hamiltonians with infinite-range non-random as well as random interactions from the perspective of possible enhancement of the efficiency of quantum annealing or adiabatic quantum computing. It is shown that multi-body transverse interactions like XX and XXXXX with positive coefficients appended to a stoquastic transverse-field Ising model render the Hamiltonian non-stoquastic and reduce a first-order quantum phase transition in the simple transverse-field case to a second-order transition. This implies that the efficiency of quantum annealing is exponentially enhanced, because a first-order transition has an exponentially small energy gap (and therefore exponentially long computation time) whereas a second-order transition has a polynomially decaying gap (polynomial computation time). The examples presented here represent rare instances where strong quantum effects, in the sense that they cannot be efficiently simulated in the standard quantum Monte Carlo, have analytically been shown to exponentially enhance the efficiency of quantum annealing for combinatorial optimization problems.

arXiv:1609.03785Frontiers in ICTFeb 17, 201797 citations

Simultaneous stoquasticity

Jacob Bringewatt, Lucas T. Brady

Stoquastic Hamiltonians play a role in the computational complexity of the local Hamiltonian problem as well as the study of classical simulability. In particular, stoquastic Hamiltonians can be straightforwardly simulated using Monte Carlo techniques. We address the question of whether two or more Hamiltonians may be made simultaneously stoquastic via a unitary transformation. This question has important implications for the complexity of simulating quantum annealing where quantum advantage is related to the stoquasticity of the Hamiltonians involved in the anneal. We find that for almost all problems no such unitary exists and show that the problem of determining the existence of such a unitary is equivalent to identifying if there is a solution to a system of polynomial (in)equalities in the matrix elements of the initial and transformed Hamiltonians. Solving such a system of equations is NP-hard. We highlight a geometric understanding of this problem in terms of a collection of generalized Bloch vectors.Stoquastic Hamiltonians play a role in the computational complexity of the local Hamiltonian problem as well as the study of classical simulability. In particular, stoquastic Hamiltonians can be straightforwardly simulated using Monte Carlo techniques. We address the question of whether two or more Hamiltonians may be made simultaneously stoquastic via a unitary transformation. This question has important implications for the complexity of simulating quantum annealing where quantum advantage is related to the stoquasticity of the Hamiltonians involved in the anneal. We find that for almost all problems no such unitary exists and show that the problem of determining the existence of such a unitary is equivalent to identifying if there is a solution to a system of polynomial (in)equalities in the matrix elements of the initial and transformed Hamiltonians. Solving such a system of equations is NP-hard. We highlight a geometric understanding of this problem in terms of a collection of generalized Bloch vectors.

arXiv:2202.08863Physical Review AJun 9, 20222 citations

Permutation matrix representation quantum Monte Carlo

Lalit Gupta, Tameem Albash, Itay Hen

Abstract We present a quantum Monte Carlo algorithm for the simulation of general quantum and classical many-body models within a single unifying framework. The algorithm builds on a power series expansion of the quantum partition function in its off-diagonal terms and is both parameter-free and Trotter error-free. In our approach, the quantum dimension consists of products of elements of a permutation group. As such, it allows for the study of a very wide variety of models on an equal footing. To demonstrate the utility of our technique, we use it to clarify the emergence of the sign problem in the simulations of non-stoquastic physical models. We showcase the flexibility of our algorithm and the advantages it offers over existing state-of-the-art by simulating transverse-field Ising model Hamiltonians and comparing the performance of our technique against that of the stochastic series expansion algorithm. We also study a transverse-field Ising model augmented with randomly chosen two-body transverse-field interactions.Abstract We present a quantum Monte Carlo algorithm for the simulation of general quantum and classical many-body models within a single unifying framework. The algorithm builds on a power series expansion of the quantum partition function in its off-diagonal terms and is both parameter-free and Trotter error-free. In our approach, the quantum dimension consists of products of elements of a permutation group. As such, it allows for the study of a very wide variety of models on an equal footing. To demonstrate the utility of our technique, we use it to clarify the emergence of the sign problem in the simulations of non-stoquastic physical models. We showcase the flexibility of our algorithm and the advantages it offers over existing state-of-the-art by simulating transverse-field Ising model Hamiltonians and comparing the performance of our technique against that of the stochastic series expansion algorithm. We also study a transverse-field Ising model augmented with randomly chosen two-body transverse-field interactions.

arXiv:1908.03740Journal of Statistical Mechanics Theory and ExperimentJul 1, 202015 citations

H

with a promise that the ground state of

H

has a non-negligible correlation with some `guiding' state that admits a concise classical description. A formalized version of this problem called Guided Stoquastic Hamiltonian is shown to be complete for the complexity class $\MA$ (a probabilistic analogue of $\NP$). To prove this result we employ the Projection Monte Carlo algorithm with a variable number of walkers. Secondly, we show that the ground state and thermal equilibrium properties of the ferromagnetic TIM can be simulated in polynomial time on a classical probabilistic computer. This result is based on the approximation algorithm for the classical ferromagnetic Ising model due to Jerrum and Sinclair (1993).

H

with a promise that the ground state of

H

has a non-negligible correlation with some `guiding' state that admits a concise classical description. A formalized version of this problem called Guided Stoquastic Hamiltonian is shown to be complete for the complexity class MA (a probabilistic analogue of NP). To prove this result we employ the Projection Monte Carlo algorithm with a variable number of walkers. Secondly, we show that the ground state and thermal equilibrium properties of the ferromagnetic TIM can be simulated in polynomial time on a classical probabilistic computer. This result is based on the approximation algorithm for the classical ferromagnetic Ising model due to Jerrrum and Sinclair (1993).