{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,11,25]],"date-time":"2022-11-25T05:53:59Z","timestamp":1669355639058},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,9,20]],"date-time":"2022-09-20T00:00:00Z","timestamp":1663632000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,9,20]],"date-time":"2022-09-20T00:00:00Z","timestamp":1663632000000},"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":["comput. complex."],"published-print":{"date-parts":[[2022,12]]},"DOI":"10.1007\/s00037-022-00231-8","type":"journal-article","created":{"date-parts":[[2022,9,20]],"date-time":"2022-09-20T03:33:47Z","timestamp":1663644827000},"update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Quantum generalizations of the polynomial hierarchy with applications to QMA(2)"],"prefix":"10.1007","volume":"31","author":[{"given":"Sevag","family":"Gharibian","sequence":"first","affiliation":[]},{"given":"Miklos","family":"Santha","sequence":"additional","affiliation":[]},{"given":"Jamie","family":"Sikora","sequence":"additional","affiliation":[]},{"given":"Aarthi","family":"Sundaram","sequence":"additional","affiliation":[]},{"given":"Justin","family":"Yirka","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,9,20]]},"reference":[{"key":"231_CR1","doi-asserted-by":"crossref","unstructured":"S. Aaronson, S. Beigi, A. Drucker, B. Fefferman & P. Shor (2009). The Power of Unentanglement. Theory of Computing 5(1), 1\u201342.","DOI":"10.4086\/toc.2009.v005a001"},{"key":"231_CR2","unstructured":"S. Aaronson, A. Cojocaru, A. Gheorghiu & E. Kashefi (2019). Complexity-theoretic limitations on blind delegated quantum computation. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), C. Baier, I. Chatzigiannakis, P. Flocchini & S. Leonardi, editors, volume 132 of Leibniz International Proceedings in Informatics (LIPIcs), 6:1\u20136:13. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany."},{"key":"231_CR3","doi-asserted-by":"crossref","unstructured":"S. Aaronson & A. Drucker (2014). A full characterization of quantum advice. SIAM Journal on Computing 43(3), 1131\u20131183.","DOI":"10.1137\/110856939"},{"key":"231_CR4","unstructured":"D. Aharonov (2003). A simple proof that Toffoli and Hadamard are quantum universal. Available at arXiv:quant-ph\/0301040v1."},{"key":"231_CR5","doi-asserted-by":"crossref","unstructured":"D. Aharonov, M. Ben-Or, F. Brand\u00e3o & O. Sattath (2022). The pursuit of uniqueness: Extending Valiant-Vazirani Theorem to the probabilistic and quantum Settings. Quantum 6, 668.","DOI":"10.22331\/q-2022-03-17-668"},{"key":"231_CR6","doi-asserted-by":"crossref","unstructured":"D. Aharonov, A. Kitaev & N. Nisan (1998). Quantum circuits with mixed states. In Proceedings of 13th ACM Symposium on Theory of Computing (STOC 1998), 20\u201330.","DOI":"10.1145\/276698.276708"},{"key":"231_CR7","unstructured":"D. Aharonov & T. Naveh (2002). Quantum NP\u2014A survey. Available at arXiv:quant-ph\/0210077v1."},{"key":"231_CR8","doi-asserted-by":"crossref","unstructured":"E. W. Allender & K. W. Wagner (1993). Counting hierarchies: Polynomial time and constant depth circuits. In Current Trends in Theoretical Computer Science, 469\u2013483. World Scientific.","DOI":"10.1142\/9789812794499_0035"},{"key":"231_CR9","doi-asserted-by":"crossref","unstructured":"A. Ambainis (2014). On physical problems that are slightly more difficult than QMA. In Proceedings of 29th IEEE Conference on Computational Complexity (CCC 2014), 32\u201343.","DOI":"10.1109\/CCC.2014.12"},{"key":"231_CR10","doi-asserted-by":"crossref","unstructured":"S. Beigi (2010). NP vs QMA $$_{\\rm log}(2)$$. Quantum Information and Computation (QIC) 10(1\u20132), 141\u2013151.","DOI":"10.26421\/QIC10.1-2-10"},{"key":"231_CR11","doi-asserted-by":"crossref","unstructured":"H. Blier & A. Tapp (2009). All languages in NP have very short quantum proofs. In Proceedings of the 3rd International Conference on Quantum, Nano and Micro Technologies, 34\u201337.","DOI":"10.1109\/ICQNM.2009.21"},{"key":"231_CR12","doi-asserted-by":"crossref","unstructured":"S. Boyd & L. Vandenberghe (2004). Convex Optimization. Cambridge University Press. ISBN 9780521833783.","DOI":"10.1017\/CBO9780511804441"},{"key":"231_CR13","doi-asserted-by":"crossref","unstructured":"C. M. Dawson & M. A. Nielsen (2006). The Solovay-Kitaev algorithm. Quantum Information and Computation (QIC) 6(1).","DOI":"10.26421\/QIC6.1-6"},{"key":"231_CR14","unstructured":"A. Deshpande, A. V. Gorshkov & B. Fefferman (2022). The importance of the spectral gap in estimating ground-state energies. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), M. Braverman, editor, volume 215 of Leibniz International Proceedings in Informatics (LIPIcs), 54:1\u201354:6. Schloss Dagstuhl\u2014Leibniz- Zentrum f\u00fcr Informatik, Dagstuhl, Germany."},{"key":"231_CR15","doi-asserted-by":"crossref","unstructured":"S. Fenner, L. Fortnow, S. A. Kurtz & L. Li (2003). An oracle builder\u2019s toolkit. Information and Computation 182(2), 95\u2013136.","DOI":"10.1016\/S0890-5401(03)00018-X"},{"key":"231_CR16","unstructured":"L. Fortnow (1994). The Role of Relativization in Complexity Theory. Bulletin of the European Association for Theoretical Computer Science 52, 52\u2013229."},{"key":"231_CR17","doi-asserted-by":"crossref","unstructured":"L. Fortnow & J. Rogers (1999). Complexity limitations on quantum computation. Journal of Computer and System Sciences 59(2), 240\u2013252.","DOI":"10.1006\/jcss.1999.1651"},{"key":"231_CR18","doi-asserted-by":"crossref","unstructured":"S. Gharibian & J. Kempe (2012). Hardness of approximation for quantum problems. In Automata, Languages, and Programming (ICALP 2012), A. Czumaj, K. Mehlhorn, A. Pitts & R. Wattenhofer, editors, 387\u2013398. Springer, Berlin, Heidelberg.","DOI":"10.1007\/978-3-642-31594-7_33"},{"key":"231_CR19","unstructured":"S. Gharibian, M. Santha, J. Sikora, A. Sundaram & J. Yirka (2018). Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2). In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), I. Potapov, P. Spirakis & J. Worrell, editors, volume 117 of Leibniz International Proceedings in Informatics (LIPIcs), 58:1\u201358:16. Schloss Dagstuhl\u2014Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany."},{"key":"231_CR20","doi-asserted-by":"crossref","unstructured":"S. Gharibian & J. Yirka (2019). The complexity of simulating local measurements on quantum systems. Quantum 3, 189.","DOI":"10.22331\/q-2019-09-30-189"},{"key":"231_CR21","doi-asserted-by":"crossref","unstructured":"O. Goldreich (2006). On promise problems: A survey. In Theoretical Computer Science: Essays in Memory of Shimon Even, O. Goldreich, A.L. Rosenberg & A.L. Selman, editors, 254-290. Springer-Verlag, Berlin, Heidelberg.","DOI":"10.1007\/11685654_12"},{"key":"231_CR22","doi-asserted-by":"crossref","unstructured":"A. B. Grilo, I. Kerenidis & J. Sikora (2016). QMA with subset state witnesses. Chicago Journal of Theoretical Computer Science 2016(4).","DOI":"10.4086\/cjtcs.2016.004"},{"key":"231_CR23","doi-asserted-by":"crossref","unstructured":"M. Gr\u00f6tschel, L. Lov\u00e1sz & A. Schrijver (1993). Geometric Algorithms and Combinatorial Optimization. Springer-Verlag. ISBN 9783642782404.","DOI":"10.1007\/978-3-642-78240-4"},{"key":"231_CR24","unstructured":"R. A. Horn & C. H. Johnson (1990). Matrix Analysis. Cambridge University Press. ISBN 9780521548236."},{"key":"231_CR25","doi-asserted-by":"crossref","unstructured":"R. Jain & J. Watrous (2009). Parallel approximation of noninteractive zero-sum quantum games. In 24th Annual IEEE Conference on Computational Complexity (CCC), 243\u2013253.","DOI":"10.1109\/CCC.2009.26"},{"key":"231_CR26","doi-asserted-by":"crossref","unstructured":"S. P. Jordan, H. Kobayashi, D. Nagaj & H. Nishimura (2012). Achieving perfect completeness in classical-witness quantum Merlin- Arthur proof systems. Quantum Information and Computation (QIC) 12(5\u20136), 461\u2013471.","DOI":"10.26421\/QIC12.5-6-7"},{"key":"231_CR27","doi-asserted-by":"crossref","unstructured":"R. M. Karp & R. J. Lipton (1980). Some connections between nonuniform and uniform complexity classes. In Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing (STOC 1980), 302\u2013309. ACM, New York, NY, USA.","DOI":"10.1145\/800141.804678"},{"key":"231_CR28","doi-asserted-by":"crossref","unstructured":"A. Kitaev, A. Shen & M. Vyalyi (2002). Classical and Quantum Computation. American Mathematical Society. ISBN 082182161X.","DOI":"10.1090\/gsm\/047"},{"key":"231_CR29","doi-asserted-by":"crossref","unstructured":"A. Kitaev & J. Watrous (2000). Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. In Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC 2000), 608\u2013617.","DOI":"10.1145\/335305.335387"},{"key":"231_CR30","doi-asserted-by":"crossref","unstructured":"H. Kobayashi, F. le Gall & H. Nishimura (2015). Stronger methods of making quantum interactive proofs perfectly complete. SIAM Journal on Computing 44(2), 243\u2013289.","DOI":"10.1137\/140971944"},{"key":"231_CR31","doi-asserted-by":"crossref","unstructured":"Y.-K. Liu, M. Christandl & F. Verstraete (2007). Quantum Computational complexity of the N-representability problem: QMA complete. Phys. Rev. Lett. 98, 110 503.","DOI":"10.1103\/PhysRevLett.98.110503"},{"key":"231_CR32","unstructured":"J. Lockhart & C. E. Gonz\u00e1lez-Guill\u00e9n (2017). Quantum state isomorphism. Available at arXiv:1709.09622v1 [quant-ph]."},{"key":"231_CR33","doi-asserted-by":"crossref","unstructured":"C. Lund, L. Fortnow, H. Karloff & N. Nisan (1992). Algebraic methods for interactive proof systems. Journal of the ACM 39(4), 859\u2013868.","DOI":"10.1145\/146585.146605"},{"key":"231_CR34","doi-asserted-by":"crossref","unstructured":"C. Marriott & J. Watrous (2005). Quantum Arthur-Merlin games. Computational Complexity 14(2), 122\u2013152.","DOI":"10.1007\/s00037-005-0194-x"},{"key":"231_CR35","doi-asserted-by":"crossref","unstructured":"A. Meyer & L. Stockmeyer (1972). The equivalence problem for regular expressions with squaring requires exponential space. In 13th Annual Symposium on Switching and Automata Theory, 125\u2013129.","DOI":"10.1109\/SWAT.1972.29"},{"key":"231_CR36","doi-asserted-by":"crossref","unstructured":"A. Molina & J. Watrous (2019). Revisiting the simulation of quantum Turing machines by quantum circuits. Proceedings of the Royal Society A 475(2226), 20180 767.","DOI":"10.1098\/rspa.2018.0767"},{"key":"231_CR37","doi-asserted-by":"crossref","unstructured":"J. von Neumann (1928). Zur Theorie der Gesellschaftspiele. Mathematische Annalen 100(1), 295\u2013320.","DOI":"10.1007\/BF01448847"},{"key":"231_CR38","unstructured":"A. Pereszl\u00e9nyi (2012). Multi-prover quantum Merlin-Arthur proof systems with small gap. Available at arXiv:1205.2761v1 [quant-ph]."},{"key":"231_CR39","doi-asserted-by":"crossref","unstructured":"Y. Shi (2003). Both Toffoli and controlled-NOT need little help to do universal quantum computing. Quantum Information and Computation 3(1), 84\u201392.","DOI":"10.26421\/QIC3.1-7"},{"key":"231_CR40","doi-asserted-by":"crossref","unstructured":"S. Toda (1991). PP is as hard as the Polynomial-Time Hierarchy. SIAM Journal on Computing 20, 865\u2013877.","DOI":"10.1137\/0220053"},{"key":"231_CR41","doi-asserted-by":"crossref","unstructured":"J. Tor\u00e1n (1991). Complexity classes defined by counting quantifiers. Journal of the ACM 38(3), 752-773.","DOI":"10.1145\/116825.116858"},{"key":"231_CR42","doi-asserted-by":"crossref","unstructured":"L. G. Valiant & V. V. Vazirani (1986). NP is as easy as detecting unique solutions. Theoretical Computer Science 47, 85\u201393.","DOI":"10.1016\/0304-3975(86)90135-0"},{"key":"231_CR43","unstructured":"L. Vinkhuijzen (2018). A quantum polynomial hierarchy and a simple proof of Vyalyi\u2019s Theorem. Master\u2019s thesis, Leiden University."},{"key":"231_CR44","doi-asserted-by":"crossref","unstructured":"N. V. Vinodchandran (2005). A note on the circuit complexity of PP. Theoretical Computer Science 347(1-2), 415\u2013418.","DOI":"10.1016\/j.tcs.2005.07.032"},{"key":"231_CR45","unstructured":"M. Vyalyi (2003). QMA=PP implies that PP contains PH. Technical Report TR03-021, Electronic Colloquium on Computational Complexity."},{"key":"231_CR46","doi-asserted-by":"crossref","unstructured":"J. Watrous (2009a). Quantum computational complexity. In Encyclopedia of Complexity and Systems Science, R. A. Meyers, editor, 7174\u20137201. Springer, New York, NY.","DOI":"10.1007\/978-0-387-30440-3_428"},{"key":"231_CR47","doi-asserted-by":"crossref","unstructured":"J. Watrous (2009b). Semidefinite programs for completely bounded norms. Theory of Computation 5, 217\u2013238.","DOI":"10.4086\/toc.2009.v005a011"},{"key":"231_CR48","doi-asserted-by":"crossref","unstructured":"J. Watrous (2009c). Zero-knowledge against quantum attacks. SIAM Journal of Computing 39(1), 25\u201358.","DOI":"10.1137\/060670997"},{"key":"231_CR49","doi-asserted-by":"crossref","unstructured":"C. Wrathall (1976). Complete sets and the Polynomial-Time Hierarchy. Theoretical Computer Science 3(1), 23 \u2013 33.","DOI":"10.1016\/0304-3975(76)90062-1"},{"key":"231_CR50","doi-asserted-by":"crossref","unstructured":"T. Yamakami (2002). Quantum NP and a quantum hierarchy. In Foundations of Information Technology in the Era of Network and Mobile Computing (TCS 2002), R. Baeza-Yates, U. Montanari & N. Santoro, editors, 323\u2013336. Springer, Boston, MA.","DOI":"10.1007\/978-0-387-35608-2_27"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-022-00231-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-022-00231-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-022-00231-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,24]],"date-time":"2022-11-24T15:28:15Z","timestamp":1669303695000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-022-00231-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,20]]},"references-count":50,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["231"],"URL":"https:\/\/doi.org\/10.1007\/s00037-022-00231-8","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"value":"1016-3328","type":"print"},{"value":"1420-8954","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,20]]},"assertion":[{"value":"4 February 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 September 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 October 2022","order":3,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":4,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"``Missed-out author corrections updated in XML''.","order":5,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"13"}}