Complexity of Stoquastic Frustration-Free Hamiltonians

DOI10.1137/08072689XzbMath1206.68121arXiv0806.1746WikidataQ62168082 ScholiaQ62168082MaRDI QIDQ3586188

Barbara M. Terhal, Sergey Bravyi

Publication date: 6 September 2010

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0806.1746

zbMATH Keywords

nonnegative matricesrandomized algorithmsadiabatic quantum computingMerlin-Arthur games

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Quantum computation (81P68) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Randomized algorithms (68W20) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (10)

Convergence condition of simulated quantum annealing with a non-stoquastic catalyst ⋮ The gap of the area-weighted Motzkin spin chain is exponentially small ⋮ A practitioner’s guide to quantum algorithms for optimisation problems ⋮ Unnamed Item ⋮ A monomial matrix formalism to describe quantum many-body states ⋮ Quantum Annealing with Anneal Path Control: Application to 2-SAT Problems with Known Energy Landscapes ⋮ ON THE GAP OF HAMILTONIANS FOR THE ADIABATIC SIMULATION OF QUANTUM CIRCUITS ⋮ Hardness and Ease of Curing the Sign Problem for Two-Local Qubit Hamiltonians ⋮ Entangling problem Hamiltonian for adiabatic quantum computation ⋮ Ground-state spaces of frustration-free Hamiltonians

This page was built for publication: Complexity of Stoquastic Frustration-Free Hamiltonians