Simultaneous Stoquasticity

Abstract

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 comment11 pages, 1 figure; (v2) updated to match Physical Review A version

References in corpus (20)

• Quantum Annealing in the Transverse Ising Model
• Computational complexity and fundamental limitations to fermionic quantum Monte Carlo simulations
• The Bloch Vector for N-Level Systems
• Bloch vectors for qudits
• Characterization of the Positivity of the Density Matrix in Terms of the Coherence Vector Representation
• Solving fermion sign problem in quantum Monte Carlo by Majorana representation
• Easing the Monte Carlo sign problem
• On the Computational Complexity of Curing the Sign Problem
• Scaling analysis and instantons for thermally-assisted tunneling and Quantum Monte Carlo simulations
• The Power of Adiabatic Quantum Computation with No Sign Problem
• Quantum Monte Carlo Simulations of Tunneling in Quantum Adiabatic Optimization
• Two-local qubit Hamiltonians: when are they stoquastic?
• Determining QMC simulability with geometric phases
• Resolution of the Sign Problem for a Frustrated Triplet of Spins
• Unitary and orthogonal equivalence of sets of matrices
• Rapid mixing of path integral Monte Carlo for 1D stoquastic Hamiltonians
• Local unitary equivalence of quantum states and simultaneous orthogonal equivalence
• Effective gaps are not effective: quasipolynomial classical simulation of obstructed stoquastic Hamiltonians
• Simultaneous unitary equivalences
• The quantum separability problem is a simultaneous hollowisation matrix analysis problem