Physics – Quantum Physics
Scientific paper
2011-02-03
Physics
Quantum Physics
A revised version with a few changes: Title and abstract changed to highlight the transition from local to global entanglement
Scientific paper
The local Hamiltonian problem plays the equivalent role of SAT in quantum complexity theory. Understanding the complexity of the intermediate case in which the constraints are quantum but all local terms in the Hamiltonian commute, is of importance for conceptual, physical and computational complexity reasons. Bravyi and Vyalyi showed in 2003, using a clever application of the representation theory of C*-algebras, that if the terms in the Hamiltonian are all two-local, the problem is in NP, and the entanglement in the ground states is local. The general case remained open since then. In this paper we extend the results of Bravyi and Vyalyi beyond the two-local case, to the case of three-qubit interactions. We then extend our results even further, and show that NP verification is possible for three-wise interaction between qutrits as well, as long as the interaction graph is embedded on a planar lattice, or more generally, "Nearly Euclidean" (NE). The proofs imply that in all such systems, the entanglement in the ground states is local. These extensions imply an intriguing sharp transition phenomenon in commuting Hamiltonian systems: 3-local NE systems based on qubits and qutrits cannot be used to construct Topological order, as their entanglement is local, whereas for higher dimensional qudits, or for interactions of at least 4 qudits, Topological Order is already possible, via Kitaev's Toric Code construction. We thus conclude that Kitaev's Toric Code construction is optimal for deriving topological order based on commuting Hamiltonians.
Aharonov Dorit
Eldar Lior
No associations
LandOfFree
On the complexity of Commuting Local Hamiltonians, and tight conditions for Topological Order in such systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On the complexity of Commuting Local Hamiltonians, and tight conditions for Topological Order in such systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the complexity of Commuting Local Hamiltonians, and tight conditions for Topological Order in such systems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-490738