Easing the Monte Carlo sign problem

Abstract

Quantum Monte Carlo (QMC) methods are the gold standard for studying equilibrium properties of quantum many-body systems -- their phase transitions, ground and thermal state properties. However, in many interesting situations QMC methods are faced with a sign problem, causing the severe limitation of an exponential increase in the sampling complexity and hence the run-time of the QMC algorithm. In this work, we develop a systematic, generally applicable, and practically feasible methodology for easing the sign problem by efficiently computable basis changes and use it to rigorously assess the sign problem. Our framework introduces measures of non-stoquasticity that -- as we demonstrate analytically and numerically -- at the same time provide a practically relevant and efficiently computable figure of merit for the severity of the sign problem. We show that those measures can practically be brought to a good use to ease the sign problem. To do so, we use geometric algorithms for optimization over the orthogonal group and ease the sign problem of frustrated Heisenberg ladders. Complementing this pragmatic mindset, we prove that easing the sign problem in terms of those measures is in general an NP-complete task for nearest-neighbour Hamiltonians and simple basis choices by a polynomial reduction to the MAXCUT-problem. Intriguingly, easing remains hard even in cases in which we can efficiently assert that no exact solution exists.

20+7 pages, 8 figures. Comments welcome. v2: added Theorem 6 on efficiently computing the non-stoquasticity. v3: minor clarifications

References in corpus (44)

• Surprises on the Way from 1D to 2D Quantum Magnets: the Novel Ladder Materials
• String-net condensation: A physical mechanism for topological phases
• Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations
• Computational Studies of Quantum Spin Systems
• Exact SO(5) Symmetry in spin 3/2 fermionic system
• Meron-Cluster Solution of Fermion Sign Problems
• Estimating outcome probabilities of quantum circuits using quasiprobabilities
• Suppression of the critical temperature for superfluidity near the Mott transition: validating a quantum simulator
• Solving fermion sign problem in quantum Monte Carlo by Majorana representation
• One-Dimensional Magnetism
• The sign problem in Monte Carlo simulations of frustrated quantum spin systems
• Matrix Product Unitaries: Structure, Symmetries, and Topological Invariants
• Majorana-time-reversal symmetries: a fundamental principle for sign-problem-free quantum Monte Carlo simulations
• Recent developments in Quantum Monte-Carlo simulations with applications for cold gases
• A new approach to the complex-action problem and its application to a nonperturbative study of superstring theory
• Geometry Dependence of the Sign Problem
• The sign problem and population dynamics in the full configuration interaction quantum Monte Carlo method
• Meron-Cluster Simulation of the $\theta$-Vacuum in the 2-d $O(3)$-Model
• Universal Quantum Hamiltonians
• Coupled wire construction of chiral spin liquids
• Compact numerical solutions to the two-dimensional repulsive Hubbard model obtained via non-unitary similarity transformations
• On the Computational Complexity of Curing the Sign Problem
• Sign-problem-free Monte Carlo simulation of certain frustrated quantum magnets
• Vanishing of the negative-sign problem of quantum Monte Carlo simulations in one-dimensional frustrated spin systems
• Thermodynamic properties of highly frustrated quantum spin ladders: influence of many-particle bound states
• Matrix Product Representation of Locality Preserving Unitaries
• Efficient Quantum Monte Carlo simulations of highly frustrated magnets: the frustrated spin-1/2 ladder
• Quantum Kagome Ice
• QMA-complete problems for stoquastic Hamiltonians and Markov matrices
• How Quantum Are Non-Negative Wavefunctions?
• Negative sign problem in continuous-time quantum Monte Carlo: optimal choice of single-particle basis for impurity problems
• Wavefunction positivization via automatic differentiation
• Mitigating the Sign Problem Through Basis Rotations
• Non-local updates for quantum Monte Carlo simulations
• Alleviating the Sign Problem in Quantum Monte Carlo Simulations of Spin-Orbit-Coupled Multi-Orbital Hubbard Models
• Nested Cluster Algorithm for Frustrated Quantum Antiferromagnets
• Two-local qubit Hamiltonians: when are they stoquastic?
• Symmetry-protected topological order and negative-sign problem for SO(N) bilinear-biquadratic chains
• Clock Quantum Monte Carlo: an imaginary-time method for real-time quantum dynamics
• Solution to sign problems in models of interacting fermions and quantum spins
• Resolution of the Sign Problem for a Frustrated Triplet of Spins
• Coupled spin-1/2 ladders as microscopic models for non-Abelian chiral spin liquids
• Solution to the sign problem in a frustrated quantum impurity model
• Composite symmetry protected topological order and effective models

Cited by in corpus (54)

• A full-stack view of probabilistic computing with p-bits: devices, architectures and algorithms
• Quantum Critical Points and the Sign Problem
• Variational Quantum Boltzmann Machines
• Symmetry-protected sign problem and magic in quantum phases of matter
• Perturbative quantum Monte Carlo method for nuclear physics
• Accelerated quantum Monte Carlo with mitigated error on noisy quantum computer
• Dynamical structure factors of dynamical quantum simulators
• A perspective on machine learning and data science for strongly correlated electron problems
• Wavefunction positivization via automatic differentiation
• Quantum Monte Carlo simulations in the trimer basis: first-order transitions and thermal critical points in frustrated trilayer magnets
• Mitigating the Sign Problem Through Basis Rotations
• Compressive gate set tomography
• Intrinsic sign problem in fermionic and bosonic chiral topological matter
• Correlation-Enhanced Neural Networks as Interpretable Variational Quantum States
• Fermion sign bounds theory in quantum Monte Carlo simulation
• Universality and Critical Exponents of the Fermion Sign Problem
• Automatic Differentiable Monte Carlo: Theory and Application
• Intrinsic sign problems in topological quantum field theories
• Sign Problem in Quantum Monte Carlo Simulation
• Quantum Monte Carlo Simulation of Generalized Kitaev Models
• Determining QMC simulability with geometric phases
• An Amelioration for the Sign Problem: Adiabatic Quantum Monte Carlo
• Mitigating the fermion sign problem by automatic differentiation
• Phases of the spin-1/2 Heisenberg antiferromagnet on the diamond-decorated square lattice in a magnetic field
• Robustly learning the Hamiltonian dynamics of a superconducting quantum processor
• Stoquasticity in circuit QED
• Variational Quantum Eigensolver Ansatz for the $J_1$-$J_2$-model
• Emulating Quantum Interference with Generalized Ising Machines
• Sign problem in tensor network contraction
• Lefschetz Thimble Quantum Monte Carlo for Spin Systems
• The Green's function Monte Carlo combined with projected entangled pair state approach to the frustrated $J_1$-$J_2$ Heisenberg model
• Imaginary-time Mpemba effect in quantum many-body systems
• Boosting quantum Monte Carlo and alleviating sign problem by Gutzwiller projection
• Defining a universal sign to strictly probe a phase transition
• All you need is spin: SU(2) equivariant variational quantum circuits based on spin networks
• Preempting Fermion Sign Problem: Unveiling Quantum Criticality through Nonequilibrium Dynamics in Imaginary Time
• Thermodynamic properties of the macroscopically degenerate tetramer-dimer phase of the spin-1/2 Heisenberg model on the diamond-decorated square lattice
• The ALF (Algorithms for Lattice Fermions) project release 2.4. Documentation for the auxiliary-field quantum Monte Carlo code
• Quantum computing quantum Monte Carlo algorithm
• Quantum subspace expansion approach for simulating dynamical response functions of Kitaev spin liquids
• Quantum Monte Carlo simulations of highly frustrated magnets in a cluster basis: The two-dimensional Shastry-Sutherland model
• Learning topological states from randomized measurements using variational tensor network tomography
• Neural Quantum State Study of Fracton Models
• Quantum Convolutional Neural Network for Phase Recognition in Two Dimensions
• Identification of the transport regimes of the one-dimensional Holstein model
• Geometric and computational aspects of chiral topological quantum matter
• Simultaneous Stoquasticity
• Phase transitions in the spin-1/2 Heisenberg antiferromagnet on the dimerized diamond lattice
• Sampling and the complexity of nature
• Pinned QMA: The power of fixing a few qubits in proofs
• Autoencoder-based analytic continuation method for strongly correlated quantum systems
• Magnetization plateaus, spin-canted orders and field-induced transitions in a spin-1/2 Heisenberg antiferromagnet on a distorted diamond-decorated honeycomb lattice
• Negative sign free formulations of generalized Kitaev models with higher symmetries
• Circuit connectivity boosts by quantum-classical-quantum interfaces