{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T11:26:57Z","timestamp":1740137217391,"version":"3.37.3"},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2018,6,8]],"date-time":"2018-06-08T00:00:00Z","timestamp":1528416000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100011264","name":"FP7 People: Marie-Curie Actions","doi-asserted-by":"publisher","award":["609427"],"award-info":[{"award-number":["609427"]}],"id":[{"id":"10.13039\/100011264","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100005357","name":"Agent\u00fara na Podporu V\u00fdskumu a V\u00fdvoja","doi-asserted-by":"publisher","award":["QETWORK APVV-14-0878"],"award-info":[{"award-number":["QETWORK APVV-14-0878"]}],"id":[{"id":"10.13039\/501100005357","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100010783","name":"Slovensk\u00e1 Akad\u00e9mia Vied","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100010783","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100005156","name":"Alexander von Humboldt-Stiftung","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005156","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2018,7]]},"DOI":"10.1007\/s11128-018-1944-4","type":"journal-article","created":{"date-parts":[[2018,6,8]],"date-time":"2018-06-08T00:50:16Z","timestamp":1528419016000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Shorter unentangled proofs for ground state connectivity"],"prefix":"10.1007","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7401-8076","authenticated-orcid":false,"given":"Libor","family":"Caha","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Nagaj","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Martin","family":"Schwarz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,6,8]]},"reference":[{"issue":"1","key":"1944_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2009.v005a001","volume":"5","author":"S Aaronson","year":"2009","unstructured":"Aaronson, S., Beigi, S., Drucker, A., Fefferman, B., Shor, P.: The power of unentanglement. Theory Comput. 5(1), 1\u201342 (2009)","journal-title":"Theory Comput."},{"issue":"1&2","key":"1944_CR2","first-page":"2","volume":"10","author":"S Beigi","year":"2010","unstructured":"Beigi, S.: NP vs QMA\n                           \n                    \n                      \n                    \n                    $$_{{\\rm log}}(2)$$\n                    \n                      \n                        \n                          \n                            \n                            log\n                          \n                          \n                            (\n                            2\n                            )\n                          \n                        \n                      \n                    \n                  . Quantum Inf. Comput. 10(1&2), 2 (2010)","journal-title":"Quantum Inf. Comput."},{"issue":"3","key":"1944_CR3","doi-asserted-by":"publisher","first-page":"499","DOI":"10.1007\/s00037-011-0016-2","volume":"21","author":"H Blier","year":"2012","unstructured":"Blier, H., Tapp, A.: A quantum characterization of NP. Comput. Complex. 21(3), 499\u2013510 (2012)","journal-title":"Comput. Complex."},{"key":"1944_CR4","doi-asserted-by":"publisher","first-page":"805","DOI":"10.1007\/s00220-011-1302-1","volume":"306","author":"FGSL Brand\u00e3o","year":"2011","unstructured":"Brand\u00e3o, F.G.S.L., Christandl, M., Yard, J.: Faithful squashed entanglement. Commun. Math. Phys. 306, 805\u2013830 (2011)","journal-title":"Commun. Math. Phys."},{"key":"1944_CR5","doi-asserted-by":"publisher","first-page":"167902","DOI":"10.1103\/PhysRevLett.87.167902","volume":"87","author":"H Buhrman","year":"2001","unstructured":"Buhrman, H., Cleve, R., Watrous, J., de Wolf, R.: Quantum fingerprinting. Phys. Rev. Lett. 87, 167902 (2001)","journal-title":"Phys. Rev. Lett."},{"key":"1944_CR6","unstructured":"Chen, J., Drucker, A.: Short multi-prover quantum proofs for SAT without entangled measurements. arXiv e-print: \n                    arXiv:1011.0716\n                    \n                   (2010)"},{"key":"1944_CR7","first-page":"1","volume":"2013","author":"A Chiesa","year":"2013","unstructured":"Chiesa, A., Forbes, M.A.: Improved soundness for QMA with multiple provers. Chic. J. Theor. Comput. Sci. 2013, 1 (2013)","journal-title":"Chic. J. Theor. Comput. Sci."},{"key":"1944_CR8","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1145\/1236457.1236459","volume":"54","author":"I Dinur","year":"2007","unstructured":"Dinur, I.: The PCP theorem by gap amplification. J. ACM 54, 3 (2007)","journal-title":"J. ACM"},{"issue":"7\u20138","key":"1944_CR9","first-page":"589","volume":"12","author":"FL Gall","year":"2012","unstructured":"Gall, F.L., Nakagawa, S., Nishimura, H.: On QMA protocols with two short quantum proofs. Quantum Inf. Comput. 12(7\u20138), 589\u2013600 (2012)","journal-title":"Quantum Inf. Comput."},{"issue":"3&4","key":"1944_CR10","first-page":"343","volume":"10","author":"S Gharibian","year":"2010","unstructured":"Gharibian, S.: Strong NP-hardness of the quantum separability problem. Quantum Inf. Comput. 10(3&4), 343\u2013360 (2010)","journal-title":"Quantum Inf. Comput."},{"key":"1944_CR11","doi-asserted-by":"crossref","unstructured":"Gharibian, S., Sikora, J.: Ground state connectivity of local Hamiltonians. In: Automata, Languages, and Programming: 42nd International Colloquium, ICALP: Kyoto, Japan, July 6\u201310, 2015, Proceedings, Part I, pp. 617\u2013628. Springer, Berlin (2015)","DOI":"10.1007\/978-3-662-47672-7_50"},{"key":"1944_CR12","doi-asserted-by":"crossref","unstructured":"Gurvits, L.: Classical deterministic complexity of Edmonds\u2019 problem and quantum entanglement. In: Proceedings of 35th Annual ACM Symposium on Theory of Computing, STOC \u201903, pp. 10\u201319. ACM, New York (2003)","DOI":"10.1145\/780543.780545"},{"key":"1944_CR13","doi-asserted-by":"crossref","unstructured":"Harrow, A.W., Montanaro, A.: An efficient test for product states with applications to quantum Merlin\u2013Arthur games. In: Proceedings of 51st Annual Symposium on Foundations of Computer Science, pp.\u00a0633\u2013642 (2010)","DOI":"10.1109\/FOCS.2010.66"},{"issue":"5\u20136","key":"1944_CR14","first-page":"461","volume":"12","author":"SP Jordan","year":"2012","unstructured":"Jordan, S.P., Kobayashi, H., Nagaj, D., Nishimura, H.: Achieving perfect completeness in classical-witness quantum Merlin\u2013Arthur proof systems. Quantum Inf. Comput. 12(5\u20136), 461\u2013471 (2012)","journal-title":"Quantum Inf. Comput."},{"key":"1944_CR15","series-title":"Graduate studies in mathematics","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/047","volume-title":"Classical and Quantum Computation","author":"A Kitaev","year":"2002","unstructured":"Kitaev, A., Shen, A., Vyalyi, M.: Classical and Quantum Computation. Graduate studies in mathematics. American Mathematical Society, Providence (2002)"},{"key":"1944_CR16","unstructured":"Liu, Y.: The complexity of the consistency and N-representability problems for quantum states. PhD thesis, University of California, San Diego (2007)"},{"key":"1944_CR17","unstructured":"Nakagawa, S., Nishimura, H.: On the soundness of the Blier\u2013Tapp QMA protocol. In: 23rd quantum information technology symposium (QIT23), pp.\u00a0132\u2013135. \n                    http:\/\/www.math.cm.is.nagoya-u.ac.jp\/~hnishimura\/NN10.pdf\n                    \n                   (2010). Accessed 1 Oct 2017 (in Japanese)"},{"key":"1944_CR18","doi-asserted-by":"publisher","first-page":"7174","DOI":"10.1007\/978-0-387-30440-3_428","volume-title":"Encyclopedia of Complexity and Systems Science","author":"J Watrous","year":"2009","unstructured":"Watrous, J.: Quantum computational complexity. In: Meyers, R.A. (ed.) Encyclopedia of Complexity and Systems Science, pp. 7174\u20137201. Springer, New York (2009)"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11128-018-1944-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-018-1944-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-018-1944-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,7]],"date-time":"2019-06-07T19:14:04Z","timestamp":1559934844000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11128-018-1944-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,8]]},"references-count":18,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["1944"],"URL":"https:\/\/doi.org\/10.1007\/s11128-018-1944-4","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"type":"print","value":"1570-0755"},{"type":"electronic","value":"1573-1332"}],"subject":[],"published":{"date-parts":[[2018,6,8]]},"assertion":[{"value":"22 February 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 May 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 June 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"174"}}