{"id":6237,"date":"2012-04-03T23:34:20","date_gmt":"2012-04-04T06:34:20","guid":{"rendered":"http:\/\/dabacon.org\/pontiff\/?p=6237"},"modified":"2012-04-03T23:34:20","modified_gmt":"2012-04-04T06:34:20","slug":"ghost-paper-dance","status":"publish","type":"post","link":"https:\/\/dabacon.org\/pontiff\/2012\/04\/03\/ghost-paper-dance\/","title":{"rendered":"Ghost Paper Dance!"},"content":{"rendered":"

In a belated revival of the Ghost Pontiff’s “Happy Paper Dance” ritual, I’d like to talk about the recent paper The k-local Pauli Commuting Hamiltonians Problem is in P<\/a> by my student Jijiang (Johnny) Yan and his former advisor, Dave Bacon. The abstract is:<\/p>\n

\nGiven a Hamiltonian that is a sum of commuting few-body terms, the commuting Hamiltonian problem is to determine if there exists a quantum state that is the simultaneous eigenstate of all of these terms that minimizes each term individually. This problem is known to be in the complexity class quantum Merlin-Arthur, but is widely thought to not be complete for this class. Here we show that a limited form of this problem when the individual terms are all made up of tensor products of Pauli matrices is efficiently solvable on a classical computer and thus in the complexity class P. The problem can be thought of as the classical XOR-SAT problem over a symplectic vector space. This class of problems includes instance Hamiltonians whose ground states possess topological entanglement, thus showing that such entanglement is not always a barrier for the more general problem.\n<\/p><\/blockquote>\n

This result follows a long string of papers that discuss the complexity of finding the ground state energy of k-local Hamiltonians, usually modified by various adjectives like “commuting” or “frustration-free” or “Pauli” or “in d dimensions.” Typically, these problems are shown to be somewhere between NP and QMA, and the subtle differences between these relate to issues such as topological order<\/a> and the quantum PCP conjecture<\/a>. In fact, one specific inspiration for this paper was 1102.0770<\/a>, which showed that 3-qubit (or even 3-qutrit) commuting Hamiltonians could not have topologically-ordered ground states, while 4-qubit commuting Hamiltonians include the toric code, and 2-qubit non<\/i>-commuting Hamiltonians include things that look like the toric code<\/a>.
\nThis paper shows that, in the case of commuting Pauli Hamiltonians, the difference between 3-local and 4-local is not important from a complexity point of view; indeed, it is possible to efficiently find the ground state of even $latex O(n)$-local Hamiltonians.
\nAt first this is shocking, but to see why it’s reasonable to expect this result, consider classical (commuting, Pauli) Hamiltonians. Determining whether these terms has a simultaneous ground state is equivalent to solving a linear system of equations over $latex mathbb{F}_2$, which of course can be done in poly-time. This paper extends that to general Paulis, but the algorithm still involves solving linear systems of equations–this time over $latex mathbb{F}_4$. It is one of my favorite examples of the power and simplicity of the Pauli matrices, tied perhaps with the elegant Wehner-Winter uncertainty relations<\/a> for anti-commuting observables.<\/p>\n","protected":false},"excerpt":{"rendered":"

In a belated revival of the Ghost Pontiff’s “Happy Paper Dance” ritual, I’d like to talk about the recent paper The k-local Pauli Commuting Hamiltonians Problem is in P by my student Jijiang (Johnny) Yan and his former advisor, Dave Bacon. The abstract is: Given a Hamiltonian that is a sum of commuting few-body terms, … <\/p>\n

Continue reading “Ghost Paper Dance!”<\/span><\/a><\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[32],"tags":[],"class_list":["post-6237","post","type-post","status-publish","format-standard","hentry","category-general"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/6237","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/comments?post=6237"}],"version-history":[{"count":0,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/posts\/6237\/revisions"}],"wp:attachment":[{"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/media?parent=6237"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/categories?post=6237"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dabacon.org\/pontiff\/wp-json\/wp\/v2\/tags?post=6237"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}