{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,23]],"date-time":"2026-02-23T23:35:14Z","timestamp":1771889714803,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540240587","type":"print"},{"value":"9783540305385","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-30538-5_31","type":"book-chapter","created":{"date-parts":[[2010,3,12]],"date-time":"2010-03-12T13:40:30Z","timestamp":1268401230000},"page":"372-383","source":"Crossref","is-referenced-by-count":23,"title":["The Complexity of the Local Hamiltonian Problem"],"prefix":"10.1007","author":[{"given":"Julia","family":"Kempe","sequence":"first","affiliation":[]},{"given":"Alexei","family":"Kitaev","sequence":"additional","affiliation":[]},{"given":"Oded","family":"Regev","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"31_CR1","volume-title":"Computational Complexity","author":"C. Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.: Computational Complexity. Addison Wesley, Reading (1994)"},{"key":"31_CR2","unstructured":"Knill, E.: Quantum randomness and nondeterminism, quant-ph\/9610012 (1996)"},{"key":"31_CR3","series-title":"Graduate Studies in Mathematics","doi-asserted-by":"crossref","DOI":"10.1090\/gsm\/047","volume-title":"Classical and quantum computation","author":"A.Y.. Kitaev","year":"2002","unstructured":"Kitaev, A.Y., Shen, A.H., Vyalyi, M.N.: Classical and quantum computation. Graduate Studies in Mathematics, vol.\u00a047. AMS, Providence, RI (2002)"},{"key":"31_CR4","doi-asserted-by":"crossref","unstructured":"Watrous, J.: Succinct quantum proofs for properties of finite groups. In: Proc. 41st FOCS, 537\u2013546 (2000)","DOI":"10.1109\/SFCS.2000.892141"},{"key":"31_CR5","unstructured":"Janzing, D., Wocjan, P., Beth, T.: Identity check is QMA-complete, quant-ph\/0305050 (2003)"},{"key":"31_CR6","unstructured":"Aharonov, D., Naveh, T.: Quantum NP - a survey, quant-ph\/0210077 (2002)"},{"key":"31_CR7","first-page":"258","volume":"3","author":"J. Kempe","year":"2003","unstructured":"Kempe, J., Regev, O.: 3-local Hamiltonian is QMA-complete. Quantum Inf. Comput.\u00a03, 258\u2013264 (2003)","journal-title":"Quantum Inf. Comput."},{"key":"31_CR8","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1142\/S021974990300022X","volume":"1","author":"P. Wocjan","year":"2003","unstructured":"Wocjan, P., Beth, T.: The 2-local Hamiltonian problem encompasses NP. International J. of Quantum Info.\u00a01, 349\u2013357 (2003)","journal-title":"International J. of Quantum Info."},{"key":"31_CR9","unstructured":"Bravyi, S., Vyalyi, M.: Commutative version of the k-local Hamiltonian problem and non-triviality check for quantum codes, quant-ph\/0308021 (2003)"},{"key":"31_CR10","unstructured":"Aharonov, D., van Dam, W., Kempe, J., Landau, Z., Lloyd, S., Regev, O.: Adiabatic quantum computation is equivalent to standard quantum computation. In: Proc. 45th FOCS, quant-ph\/0405098 (2004)"},{"key":"31_CR11","doi-asserted-by":"crossref","unstructured":"Marriott, C., Watrous, J.: Quantum Arthur-Merlin games. In: Proc. of 19th IEEE Annual Conference on Computational Complexity, CCC (2004)","DOI":"10.1109\/CCC.2004.1313850"},{"key":"31_CR12","series-title":"International Series in Pure and Applied Mathematics","volume-title":"Functional analysis","author":"W. Rudin","year":"1991","unstructured":"Rudin, W.: Functional analysis. International Series in Pure and Applied Mathematics, vol.\u00a02. McGraw-Hill Inc, New York (1991)"},{"key":"31_CR13","volume-title":"Methods of quantum field theory in statistical physics","author":"A.A. Abrikosov","year":"1975","unstructured":"Abrikosov, A.A., Gorkov, L.P., Dzyaloshinski, I.E.: Methods of quantum field theory in statistical physics. Dover Publications Inc., New York (1975)"}],"container-title":["Lecture Notes in Computer Science","FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-30538-5_31.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T04:58:52Z","timestamp":1605761932000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-30538-5_31"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540240587","9783540305385"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-30538-5_31","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}