The local hamiltonian problem on a line with eight states is QMA-complete

Sean Hallgren; Daniel Nagaj; Sandeep Narayanaswami

The local hamiltonian problem on a line with eight states is QMA-complete

Sean Hallgren, Daniel Nagaj, Sandeep Narayanaswami

Computer Science and Engineering

Research output: Contribution to journal › Article › peer-review

30 Scopus citations

Abstract

The Local Hamiltonian problem is the problem of estimating the least eigenvalue of a local Hamiltonian, and is complete for the class QMA. The 1D problem on a chain of qubits has heuristics which work well, while the 13-state qudit case has been shown to be QMA-complete. We show that this problem remains QMA-complete when the dimensionality of the qudits is brought down to 8.

Original language	English (US)
Pages (from-to)	721-750
Number of pages	30
Journal	Quantum Information and Computation
Volume	13
Issue number	9-10
State	Published - Jul 23 2013

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Statistical and Nonlinear Physics
Nuclear and High Energy Physics
Mathematical Physics
General Physics and Astronomy
Computational Theory and Mathematics

Cite this

@article{b57fc1f3ce7d41b2b16ed969904032f3,

title = "The local hamiltonian problem on a line with eight states is QMA-complete",

abstract = "The Local Hamiltonian problem is the problem of estimating the least eigenvalue of a local Hamiltonian, and is complete for the class QMA. The 1D problem on a chain of qubits has heuristics which work well, while the 13-state qudit case has been shown to be QMA-complete. We show that this problem remains QMA-complete when the dimensionality of the qudits is brought down to 8.",

author = "Sean Hallgren and Daniel Nagaj and Sandeep Narayanaswami",

year = "2013",

month = jul,

day = "23",

language = "English (US)",

volume = "13",

pages = "721--750",

journal = "Quantum Information and Computation",

issn = "1533-7146",

publisher = "Sciendo",

number = "9-10",

}

TY - JOUR

T1 - The local hamiltonian problem on a line with eight states is QMA-complete

AU - Hallgren, Sean

AU - Nagaj, Daniel

AU - Narayanaswami, Sandeep

PY - 2013/7/23

Y1 - 2013/7/23

N2 - The Local Hamiltonian problem is the problem of estimating the least eigenvalue of a local Hamiltonian, and is complete for the class QMA. The 1D problem on a chain of qubits has heuristics which work well, while the 13-state qudit case has been shown to be QMA-complete. We show that this problem remains QMA-complete when the dimensionality of the qudits is brought down to 8.

AB - The Local Hamiltonian problem is the problem of estimating the least eigenvalue of a local Hamiltonian, and is complete for the class QMA. The 1D problem on a chain of qubits has heuristics which work well, while the 13-state qudit case has been shown to be QMA-complete. We show that this problem remains QMA-complete when the dimensionality of the qudits is brought down to 8.

UR - http://www.scopus.com/inward/record.url?scp=84880254341&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84880254341&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:84880254341

SN - 1533-7146

VL - 13

SP - 721

EP - 750

JO - Quantum Information and Computation

JF - Quantum Information and Computation

IS - 9-10

ER -

The local hamiltonian problem on a line with eight states is QMA-complete

Abstract

All Science Journal Classification (ASJC) codes

Other files and links

Fingerprint

Cite this