On the Computational Complexity of Curing the Sign Problem

Abstract

Quantum many-body systems whose Hamiltonians are non-stoquastic, i.e., have positive off-diagonal matrix elements in a given basis, are known to pose severe limitations on the efficiency of Quantum Monte Carlo algorithms designed to simulate them, due to the infamous sign problem. We study the computational complexity associated with `curing' non-stoquastic Hamiltonians, i.e., transforming them into sign-problem-free ones. We prove that if such transformations are limited to single-qubit Clifford group elements or general single-qubit orthogonal matrices, finding the curing transformation is NP-complete. We discuss the implications of this result.

6+6 pages, Comments welcome

References in corpus (2)

• Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations
• From Near to Eternity: Spin-glass planting, tiling puzzles, and constraint satisfaction problems

Cited by in corpus (41)

• Perspectives of quantum annealing: Methods and implementations
• Quantum Annealing for Industry Applications: Introduction and Review
• Prospects for Quantum Enhancement with Diabatic Quantum Annealing
• Easing the Monte Carlo sign problem
• Demonstration of nonstoquastic Hamiltonian in coupled superconducting flux qubits
• Symmetry-protected sign problem and magic in quantum phases of matter
• Dynamical structure factors of dynamical quantum simulators
• Wavefunction positivization via automatic differentiation
• Intrinsic sign problem in fermionic and bosonic chiral topological matter
• Universality and Critical Exponents of the Fermion Sign Problem
• Fermion sign bounds theory in quantum Monte Carlo simulation
• Two-local qubit Hamiltonians: when are they stoquastic?
• De-Signing Hamiltonians for Quantum Adiabatic Optimization
• Intrinsic sign problems in topological quantum field theories
• Sign Problem in Quantum Monte Carlo Simulation
• Determining QMC simulability with geometric phases
• Assessing and Advancing the Potential of Quantum Computing: A NASA Case Study
• A Quantum N-Queens Solver
• Mitigating the fermion sign problem by automatic differentiation
• Permutation Matrix Representation Quantum Monte Carlo
• Superconducting qubit circuit emulation of a vector spin-1/2
• Stoquasticity in circuit QED
• Emulating Quantum Interference with Generalized Ising Machines
• Phase transitions in the frustrated Ising ladder with stoquastic and nonstoquastic catalysts
• Locally Suppressed Transverse-Field Protocol for Diabatic Quantum Annealing
• Defining a universal sign to strictly probe a phase transition
• Lefschetz Thimble Quantum Monte Carlo for Spin Systems
• Improving nonstoquastic quantum annealing with spin-reversal transformations
• Quantum computing quantum Monte Carlo algorithm
• Emergent magnetic order in the antiferromagnetic Kitaev model with a [111] field
• Disentanglement Approach to Quantum Spin Ground States: Field Theory and Stochastic Simulation
• Variational Quantum Simulation of Valence-Bond Solids
• The 7 faces of quantum NP
• Validating a Two Qubit Non-Stoquastic Hamiltonian in Quantum Annealing
• Real-time Sign-Problem-Suppressed Quantum Monte Carlo Algorithm For Noisy Quantum Circuit Simulations
• Simultaneous Stoquasticity
• Pinned QMA: The power of fixing a few qubits in proofs
• Most two-dimensional bosonic topological orders forbid sign-problem-free quantum Monte Carlo: Nonpositive Gauss sum as an indicator
• Classical Simulation of High Temperature Quantum Ising Models
• Essentiality of the Non-stoquastic Hamiltonians and Driver Graph Design in Quantum Optimization Annealing
• Circuit connectivity boosts by quantum-classical-quantum interfaces