Paper Info
Title
Complexity of commuting Hamiltonians on a square lattice of qubits
Abstract
We consider the computational complexity of Hamiltonians which are sums of commuting terms acting on plaquettes in a square lattice of qubits, and we show that deciding whether the ground state minimizes the energy of each local term individually is in the complexity class NP. That is, if the ground states has this property, this can be proven using a classical certificate which can be efficiently verified on a classical computer. Different to previous results on commuting Hamiltonians, our certificate proves the existence of such a state without giving instructions on how to prepare it.
Year
Venue
Keywords
2011
Quantum Information & Computation
classical computer,square lattice,ground state,previous result,computational complexity,complexity class np,classical certificate,local term,quantum physics,complexity class
Field
DocType
Volume
Complexity class,Quantum complexity theory,Discrete mathematics,Ground state,Square lattice,Quantum mechanics,Qubit,Mathematics,Certificate,Computational complexity theory
Journal
11
Issue
ISSN
Citations 
11-12
Quantum Inf. Comput. 11, 901 (2011)
10
PageRank 
References 
Authors
0.80
5
1
Name
Order
Citations
PageRank
Norbert Schuch1212.35