{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T20:37:35Z","timestamp":1778099855878,"version":"3.51.4"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,11,26]],"date-time":"2014-11-26T00:00:00Z","timestamp":1416960000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2015,1]]},"DOI":"10.1007\/s11128-014-0877-9","type":"journal-article","created":{"date-parts":[[2014,12,2]],"date-time":"2014-12-02T14:33:07Z","timestamp":1417530787000},"page":"83-101","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["The commuting local Hamiltonian problem on locally expanding graphs is approximable in $$\\mathsf{{NP}}$$ NP"],"prefix":"10.1007","volume":"14","author":[{"given":"Dorit","family":"Aharonov","sequence":"first","affiliation":[]},{"given":"Lior","family":"Eldar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,11,26]]},"reference":[{"key":"877_CR1","unstructured":"Aaronson, S.: The quantum $${\\sf PCP}$$ PCP manifesto (2006). http:\/\/www.scottaaronson.com\/blog\/?p=139"},{"key":"877_CR2","doi-asserted-by":"crossref","unstructured":"Aharonov, D., Arad, I., Landau, Z., Vazirani, U.: The Detectability Lemma and Quantum Gap Amplification. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing. ACM, New York, NY, USA, pp. 417426 (2009)","DOI":"10.1145\/1536414.1536472"},{"issue":"2","key":"877_CR3","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1145\/2491533.2491549","volume":"44","author":"D Aharonov","year":"2013","unstructured":"Aharonov, D., Arad, I., Vidick, T.: The Quantum $${\\sf PCP}$$ PCP Conjecture Guest column: the quantum PCP conjecture. SIGACT News 44(2), 47\u201379 (2013)","journal-title":"SIGACT News"},{"key":"877_CR4","doi-asserted-by":"crossref","unstructured":"Aharonov, D., Eldar, L.: On the complexity of commuting local Hamiltonians, and tight conditions for topological order in such systems. In: IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pp. 334\u2013343 (2011)","DOI":"10.1109\/FOCS.2011.58"},{"key":"877_CR5","unstructured":"Aharonov, D., van Dam, W., Kempe, J., Landau, Z., Lloyd, S., Regev, O.: Adiabatic quantum computation is equivalent to standard quantum computation. SIAM J. Comput. 37(1), 166\u2013194 (2007). Conference version in Proc. 45th FOCS, pp. 42\u201351 (2004)"},{"issue":"1","key":"877_CR6","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/s00220-008-0710-3","volume":"287","author":"D Aharonov","year":"2009","unstructured":"Aharonov, D., Gottesman, D., Irani, S., Kempe, J.: The power of quantum systems on a line Comm. Math. Phys. 287(1), 41\u201365 (2009)","journal-title":"Math. Phys."},{"key":"877_CR7","unstructured":"Aharonov, D., Naveh, T.: Quantum NP\u2014A Survey arXiv:quant-ph\/0210077"},{"key":"877_CR8","first-page":"1019","volume":"11","author":"I Arad","year":"2011","unstructured":"Arad, I.: A note about a partial no-go theorem for quantum $${\\sf PCP}$$ PCP . Quantum Inf. Comput. 11, 1019 (2011)","journal-title":"Quantum Inf. Comput."},{"issue":"3","key":"877_CR9","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and intractability of Approximation problems. J. ACM 45(3), 501\u2013555 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"877_CR10","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of $${\\sf NP}$$ NP . J. ACM 45(1), 70\u2013122 (1998)","journal-title":"J. ACM"},{"key":"877_CR11","doi-asserted-by":"crossref","unstructured":"Arora, S., Barak, B., Steurer, D.: Subexponential algorithms for unique games and related problems. In: FOCS, pp. 563\u2013572 (2010)","DOI":"10.1109\/FOCS.2010.59"},{"key":"877_CR12","doi-asserted-by":"crossref","unstructured":"Arora, S., Khot, S., Kolla, A., Steurer, D., Tulsiani, M., Vishnoi, N.K.: Unique games on expanding constraint graphs are easy. In: STOC, pp. 21\u201328 (2008)","DOI":"10.1145\/1374376.1374380"},{"key":"877_CR13","unstructured":"Brand\u00e3o, F., Harrow, A.: Approximation Guarantees for the Quantum Local Hamiltonian Problem and Limitations for Quantum $${\\sf PCP}$$ PCP s Pre-Print"},{"key":"877_CR14","unstructured":"Bravyi, S.: Efficient algorithm for a quantum analogue of 2-SAT (2006). arXiv:quant-ph\/0602108v1"},{"issue":"3","key":"877_CR15","first-page":"187","volume":"5","author":"S Bravyi","year":"2005","unstructured":"Bravyi, S., Vyalyi, M.: Commutative version of the k-local Hamiltonian problem and common eigenspace problem. Quantum Inf. Comput. 5(3), 187\u2013215 (2005)","journal-title":"Quantum Inf. Comput."},{"key":"877_CR16","doi-asserted-by":"crossref","first-page":"070503","DOI":"10.1103\/PhysRevLett.101.070503","volume":"101","author":"S Bravyi","year":"2008","unstructured":"Bravyi, S., DiVincenzo, D.P., Loss, D., Terhal, B.M.: Simulation of many-body Hamiltonians using perturbation theory with bounded-strength interactions. Phys. Rev. Lett. 101, 070503 (2008)","journal-title":"Phys. Rev. Lett."},{"key":"877_CR17","doi-asserted-by":"crossref","unstructured":"Capalbo, M.R., Reingold, O., Vadhan, S., Wigderson, A.: Randomness conductors and constant-degree lossless expanders. In: Proceedings of the ACM Symposium on Theory of Computing (STOC), pp. 659\u2013668 (2002)","DOI":"10.1145\/510002.510003"},{"key":"877_CR18","doi-asserted-by":"crossref","unstructured":"Dinur, I.: The $${\\sf PCP}$$ PCP theorem by gap amplification. In: STOC, pp. 241\u2013250 (2006)","DOI":"10.1145\/1132516.1132553"},{"key":"877_CR19","unstructured":"Dinur, I., Kaufman, T.: Locally Testable Codes and Expanders Pre-Print"},{"key":"877_CR20","unstructured":"Freedman, M.H., Hastings, M.B.: Quantum systems on non-k-hyperfinite complexes: a generalization of classical statistical mechanics on expander graphs. arXiv: 1301.1363"},{"issue":"4","key":"877_CR21","doi-asserted-by":"crossref","first-page":"1028","DOI":"10.1137\/110842272","volume":"41","author":"S Gharibian","year":"2012","unstructured":"Gharibian, S., Kempe, J.: Approximation algorithms for QMA complete problems. SIAM J. Comput. 41(4), 1028\u20131050 (2012)","journal-title":"SIAM J. Comput."},{"key":"877_CR22","doi-asserted-by":"crossref","unstructured":"Gharibian, S., Kempe, J.: Hardness of approximation for quantum problems. In: ICALP (1), pp. 387\u2013398 (2012)","DOI":"10.1007\/978-3-642-31594-7_33"},{"key":"877_CR23","doi-asserted-by":"crossref","unstructured":"Gottesman, D., Irani, S.: The quantum and classical complexity of translationally invariant tiling and Hamiltonian problems. In: 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS \u201909, pp. 95\u2013104 (2009)","DOI":"10.1109\/FOCS.2009.22"},{"key":"877_CR24","doi-asserted-by":"crossref","first-page":"798","DOI":"10.1145\/502090.502098","volume":"48","author":"J H\u00e5stad","year":"2001","unstructured":"H\u00e5stad, J.: Some optimal inapproximability results. J. ACM 48, 798\u2013859 (2001)","journal-title":"J. ACM"},{"issue":"5\u20136","key":"877_CR25","first-page":"393","volume":"13","author":"MB Hastings","year":"2013","unstructured":"Hastings, M.B.: Trivial low energy states for commuting Hamiltonians, and the quantum $${\\sf PCP}$$ PCP conjecture. Quantum Inf. Comput. 13(5\u20136), 393\u2013429 (2013)","journal-title":"Quantum Inf. Comput."},{"key":"877_CR26","doi-asserted-by":"crossref","unstructured":"Khot, S.: On the power of unique 2-prover 1-round games. In: Proceedings of the 17th Annual IEEE Conference on Computational Complexity, pp. 25 (2002)","DOI":"10.1109\/CCC.2002.1004334"},{"key":"877_CR27","doi-asserted-by":"crossref","unstructured":"Kitaev, A.Yu., Shen, A.H., Vyalyi, M.N.: Classical and Quantum Computation, vol. 47, Graduate Studies in Mathematics. AMS (2002)","DOI":"10.1090\/gsm\/047"},{"issue":"1","key":"877_CR28","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1016\/S0003-4916(02)00018-0","volume":"303","author":"AYu Kitaev","year":"2003","unstructured":"Kitaev, AYu.: Fault-tolerant quantum computation by anyons. Ann. Phys. 303(1), 2\u201330 (2003)","journal-title":"Ann. Phys."},{"key":"877_CR29","unstructured":"Kempe, J., Kitaev, A., Regev, O.: The complexity of the local Hamiltonian problem. SIAM J. Comput. 35(5), 1070\u20131097 (2006). Conference version in Proc. 24th FSTTCS, p. 372\u2013383 (2004)"},{"key":"877_CR30","doi-asserted-by":"crossref","first-page":"045110","DOI":"10.1103\/PhysRevB.71.045110","volume":"B71","author":"Michael A Levin","year":"2005","unstructured":"Levin, Michael A., Wen, Xiao-Gang: String-net condensation: a physical mechanism for topological phases. Phys. Rev. B71, 045110 (2005)","journal-title":"Phys. Rev."},{"issue":"10","key":"877_CR31","first-page":"900","volume":"8","author":"R Oliveira","year":"2008","unstructured":"Oliveira, R., Terhal, B.M.: The complexity of quantum spin systems on a two-dimensional square lattice. Quant. Inf. Comput. 8(10), 900\u2013924 (2008)","journal-title":"Quant. Inf. Comput."},{"key":"877_CR32","doi-asserted-by":"crossref","first-page":"022001","DOI":"10.1088\/0034-4885\/75\/2\/022001","volume":"75","author":"T Osborne","year":"2012","unstructured":"Osborne, T.: Hamiltonian complexity. Rep. Prog. Phys. 75, 022001 (2012)","journal-title":"Rep. Prog. Phys."},{"key":"877_CR33","volume-title":"Computational Complexity","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley, Reading (1994)"},{"key":"877_CR34","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D.: Graph expansion and the unique games conjecture. In: Proceedings of the 42nd ACM symposium on Theory of computing, STOC, pp. 755\u2013764 (2010)","DOI":"10.1145\/1806689.1806792"},{"key":"877_CR35","doi-asserted-by":"crossref","unstructured":"Raghavendra, P., Steurer, D., Tulsiani, M.: Reductions between expansion problems. In: IEEE Conference on Computational Complexity, pp. 64\u201373 (2012)","DOI":"10.1109\/CCC.2012.43"},{"key":"877_CR36","first-page":"901","volume":"11","author":"N Schuch","year":"2011","unstructured":"Schuch, N.: Complexity of commuting Hamiltonians on a square lattice of qubits. Quantum Inf. Comput. 11, 901 (2011)","journal-title":"Quantum Inf. Comput."},{"key":"877_CR37","doi-asserted-by":"crossref","first-page":"732","DOI":"10.1038\/nphys1370","volume":"5","author":"N Schuch","year":"2009","unstructured":"Schuch, N., Verstraete, F.: Computational complexity of interacting electrons and fundamental limitations of density functional theory. Nat. Phys. 5, 732\u2013735 (2009)","journal-title":"Nat. Phys."},{"issue":"6","key":"877_CR38","doi-asserted-by":"crossref","first-page":"1710","DOI":"10.1109\/18.556667","volume":"42","author":"M Sipser","year":"1996","unstructured":"Sipser, M., Spielman, D.: Expander codes. IEEE Trans. Inf. Theory 42(6), 1710\u20131722 (1996)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"877_CR39","doi-asserted-by":"crossref","unstructured":"Trevisan, L.: Approximation algorithms for unique games. In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 197\u2013205 (2005)","DOI":"10.1109\/SFCS.2005.22"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-014-0877-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11128-014-0877-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-014-0877-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,18]],"date-time":"2019-08-18T02:05:33Z","timestamp":1566093933000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11128-014-0877-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,26]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["877"],"URL":"https:\/\/doi.org\/10.1007\/s11128-014-0877-9","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"value":"1570-0755","type":"print"},{"value":"1573-1332","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11,26]]}}}