{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T11:27:11Z","timestamp":1740137231740,"version":"3.37.3"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"12","license":[{"start":{"date-parts":[[2021,11,23]],"date-time":"2021-11-23T00:00:00Z","timestamp":1637625600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,11,23]],"date-time":"2021-11-23T00:00:00Z","timestamp":1637625600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Quantum Inf Process"],"published-print":{"date-parts":[[2021,12]]},"DOI":"10.1007\/s11128-021-03326-3","type":"journal-article","created":{"date-parts":[[2021,11,23]],"date-time":"2021-11-23T09:03:02Z","timestamp":1637658182000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Characterising the intersection of QMA and coQMA"],"prefix":"10.1007","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4381-2485","authenticated-orcid":false,"given":"Serge","family":"Massar","sequence":"first","affiliation":[]},{"given":"Miklos","family":"Santha","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,11,23]]},"reference":[{"key":"3326_CR1","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0304-3975(91)90200-L","volume":"81","author":"N Megiddo","year":"1991","unstructured":"Megiddo, N., Papadimitriou, C.H.: On total functions, existence theorems and computational complexity. Theor. Comput. Sci. 81, 317\u2013324 (1991)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"3326_CR2","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0022-0000(88)90046-3","volume":"37","author":"DS Johnson","year":"1988","unstructured":"Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: How easy is local search? J. Comput. Syst. Sci. 37(1), 79\u2013100 (1988)","journal-title":"J. Comput. Syst. Sci."},{"key":"3326_CR3","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Schaeffer, A.A., Yannakakis, M.: On the complexity of local search. In: Proceedings of the ACM 22nd Annual Symposium on Theory of Computing, pp. 438\u2013445 (1990)","DOI":"10.1145\/100216.100274"},{"key":"3326_CR4","doi-asserted-by":"crossref","unstructured":"Krentel, M.W.: Structure in locally optimal solutions. In: Proceedings of the IEEE 30th Annual Symposium on Foundations of Computer Science, pp. 216\u2013221 (1989)","DOI":"10.1109\/SFCS.1989.63481"},{"issue":"3","key":"3326_CR5","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1016\/S0022-0000(05)80063-7","volume":"48","author":"CH Papadimitriou","year":"1994","unstructured":"Papadimitriou, C.H.: On the complexity of the parity argument and other inefficient proofs of existence. J. Comput. Syst. Sci. 48(3), 498\u2013532 (1994)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"3326_CR6","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1137\/070699652","volume":"39","author":"C Daskalakis","year":"2009","unstructured":"Daskalakis, C., Goldberg, P.W., Papadimitriou, C.H.: The complexity of computing a Nash equilibrium. SIAM J. Comput. 39(1), 195\u2013259 (2009)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"3326_CR7","doi-asserted-by":"publisher","first-page":"14","DOI":"10.1145\/1516512.1516516","volume":"56","author":"X Chen","year":"2009","unstructured":"Chen, X., Deng, X., Teng, S.H.: Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3), 14\u201357 (2009)","journal-title":"J. ACM"},{"key":"3326_CR8","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/j.jcss.2017.12.003","volume":"94","author":"PW Goldberg","year":"2018","unstructured":"Goldberg, P.W., Papadimitriou, C.: Towards a unified complexity theory of total functions. J. Comput. Syst. Sci. 94, 167\u2013192 (2018)","journal-title":"J. Comput. Syst. Sci."},{"key":"3326_CR9","doi-asserted-by":"crossref","unstructured":"Kitaev, A.Y., Shen, A.H., Vyalyi, M.N.: Classical and quantum computation. Graduate Studies in Mathematics, vol. 47 (AMS, Providence, RI) (2002)","DOI":"10.1090\/gsm\/047"},{"key":"3326_CR10","doi-asserted-by":"crossref","unstructured":"Bookatz, A.D.: QMA-complete problems. Quantum Information and Computation, vol. 14, pp. 361\u2013383. arXiv preprint arXiv:1212.6312 (2014)","DOI":"10.26421\/QIC14.5-6-1"},{"key":"3326_CR11","doi-asserted-by":"crossref","unstructured":"Janzing, D., Wocjan, P., Beth, T.: Cooling and low energy state preparation for 3-local Hamiltonians are FQMA-complete. arXiv preprint arXiv:quant-ph\/0303186 (2003)","DOI":"10.26421\/QIC3.6-7"},{"key":"3326_CR12","doi-asserted-by":"crossref","unstructured":"Massar, S., Santha, M.: Total functions in QMA. Quantum Information Processing, vol. 20, pp. 35. arXiv preprint arXiv:1805.00670 (2021)","DOI":"10.1007\/s11128-020-02959-0"},{"issue":"2","key":"3326_CR13","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/s00037-005-0194-x","volume":"14","author":"C Marriott","year":"2005","unstructured":"Marriott, C., Watrous, J.: Quantum Arthur\u2013Merlin games. Comput. Complex. 14(2), 122\u2013152 (2005)","journal-title":"Comput. Complex."},{"issue":"11","key":"3326_CR14","first-page":"1053","volume":"9","author":"D Nagaj","year":"2009","unstructured":"Nagaj, D., Wocjan, P., Zhang, Y.: Fast amplification of QMA. Quantum Inf. Comput. 9(11), 1053\u20131068 (2009)","journal-title":"Quantum Inf. Comput."},{"key":"3326_CR15","unstructured":"Aharonov, D., Ben-Or, M., Brand\u00e3o, F.G.S.L., Sattath, O.: The pursuit for uniqueness: extending Valiant-Vazirani theorem to the probabilistic and quantum settings. arXiv preprint arXiv:0810.4840 (2008)"},{"key":"3326_CR16","unstructured":"Deshpande, A., Gorshkov, A.V., Fefferman, B.: The importance of the spectral gap in estimating ground-state energies. arXiv preprint arXiv:2007.11582 (2020)"},{"key":"3326_CR17","unstructured":"F\u00fcrer, M., Goldreich, O., Mansour, Y., Sipser, M., Zachos, S.: On completeness and soundness in interactive proof systems. In: Micali, S. (ed.) Advances in Computing Research: A Research Annual (Randomness and Computation), vol.\u00a05, pp. 429\u2013442 (1989)"}],"container-title":["Quantum Information Processing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03326-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11128-021-03326-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11128-021-03326-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,12,2]],"date-time":"2021-12-02T07:18:17Z","timestamp":1638429497000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11128-021-03326-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,11,23]]},"references-count":17,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2021,12]]}},"alternative-id":["3326"],"URL":"https:\/\/doi.org\/10.1007\/s11128-021-03326-3","relation":{},"ISSN":["1570-0755","1573-1332"],"issn-type":[{"type":"print","value":"1570-0755"},{"type":"electronic","value":"1573-1332"}],"subject":[],"published":{"date-parts":[[2021,11,23]]},"assertion":[{"value":"8 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 October 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 November 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"396"}}