



01457nas a2200157   4500008004100000245003100041210003100072260001500103490000800118520103500126653002701161653003101188100002201219700002101241856003701262       2022                        eng d00aSimultaneous Stoquasticity0 aSimultaneous Stoquasticity  c06/09/20220 v1053 a<p>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.</p>10aFOS: Physical sciences10aQuantum Physics (quant-ph)1 aBringewatt, Jacob1 aBrady, Lucas, T.  uhttps://arxiv.org/abs/2202.08863