On the Computational Complexity of Curing the Sign Problem
read the original 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.
This paper has not been read by Pith yet.
Forward citations
Cited by 3 Pith papers
-
RFOX (Rotated-Field Oscillatory eXchange) quantum algorithm: Towards Parameter-Free Quantum Optimizers
RFOX keeps the instantaneous spectral gap flat across interpolation and disorder by using a constant XX catalyst plus derived ZX counter-diabatic drive, yielding faster ground-state convergence on small RFIM instances.
-
RFOX (Rotated-Field Oscillatory eXchange) quantum algorithm: Towards Parameter-Free Quantum Optimizers
RFOX maintains a flat spectral gap via non-stoquastic XX catalyst plus analytic counter-diabatic ZX driving, yielding near-optimal solutions on random-field Ising models with up to 10x fewer Trotter steps.
-
Separability and entanglement of resonating valence-bond states
Proves exact separability for disconnected subsystems in dimer RK states and exponentially suppressed entanglement for RVB states on arbitrary lattices, with negativity expressed via partition functions.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.