{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:04Z","timestamp":1787337484049,"version":"build-2736575974"},"reference-count":32,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>We prove the following surprising result: given any quantum state $\\rho$ on $n$ qubits, there exists a local Hamiltonian $H$ on $\\operatorname*{poly}(n)$ qubits (e.g., a sum of two-qubit interactions), such that any ground state of $H$ can be used to simulate $\\rho$ on all quantum circuits of fixed polynomial size. In terms of complexity classes, this implies that ${BQP\/qpoly}\\subseteq{QMA\/poly}$, which supersedes the previous result of Aaronson that ${BQP\/qpoly}\\subseteq {PP\/poly}$. Indeed, we can exactly characterize quantum advice as equivalent in power to untrusted quantum advice combined with trusted classical advice. Proving our main result requires combining a large number of previous tools---including a result of Alon et al. on learning of real-valued concept classes, a result of Aaronson on the learnability of quantum states, and a result of Aharonov and Regev on \u201c${QMA}_{{+}}$ super-verifiers''---and also creating some new ones. The main new tool is a so-called majority-certificates lemma, which is closely related to boosting in machine learning, and which seems likely to find independent applications. In its simplest version, this lemma says the following. Given any set $S$ of Boolean functions on $n$ variables, any function $f\\in S$ can be expressed as the pointwise majority of $m=O(n)$ functions $f_{1},\\ldots,f_{m}\\in S$, such that each $f_{i}$ is the unique function in $S$ compatible with $O(\\log\\vert S\\vert)$ input\/output constraints.<\/jats:p>","DOI":"10.1137\/110856939","type":"journal-article","created":{"date-parts":[[2014,5,15]],"date-time":"2014-05-15T13:23:42Z","timestamp":1400160222000},"page":"1131-1183","source":"Crossref","is-referenced-by-count":7,"title":["A Full Characterization of Quantum Advice"],"prefix":"10.1137","volume":"43","author":[{"given":"Scott","family":"Aaronson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew","family":"Drucker","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,5,15]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1145\/1007352.1007378","author":"Aaronson S.","year":"2004","journal-title":"Proceedings of ACM STOC"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2005.v001a001"},{"key":"atypb3","first-page":"340","author":"Aaronson S.","year":"2006","journal-title":"Proceedings of the IEEE Conference on Computational Complexity"},{"key":"atypb4","first-page":"261","author":"Aaronson S.","year":"2006","journal-title":"Proceedings of the IEEE Conference on Computational Complexity"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2007.0113"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2007.v003a007"},{"key":"atypb7","unstructured":"D. Aharonov and T. Naveh,\n                      Quantum NP-a survey\n                      , arXiv:quant-ph\/0210077, 2002."},{"key":"atypb8","first-page":"210","author":"Aharonov D.","year":"2003","journal-title":"Proceedings of IEEE FOCS"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1145\/1089023.1089025"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263927"},{"key":"atypb11","doi-asserted-by":"crossref","first-page":"376","DOI":"10.1145\/301250.301347","author":"Ambainis A.","year":"1999","journal-title":"Proceedings of ACM STOC"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/581771.581773"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1557"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1996.0032"},{"key":"atypb15","doi-asserted-by":"crossref","unstructured":"H. Buhrman and L. Fortnow,\n                      One-sided versus two-sided error in probabilistic computation\n                      , in Proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS), 1999, pp. 100-109.","DOI":"10.1007\/3-540-49116-3_9"},{"key":"atypb16","doi-asserted-by":"crossref","unstructured":"V. Chakaravarthy and S. Roy,\n                      Oblivious symmetric alternation\n                      , in Proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS), 2006, pp. 230-241.","DOI":"10.1007\/11672142_18"},{"key":"atypb17","first-page":"19","author":"Fortnow L.","year":"2009","journal-title":"Proceedings of the IEEE Conference on Computational Complexity"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1504"},{"key":"atypb19","first-page":"2385","volume":"41","author":"Hausladen P.","year":"1994","journal-title":"measurement for distinguishing quantum states, J. Modern Opt."},{"key":"atypb20","first-page":"177","volume":"9","author":"Holevo A. S.","year":"1973","journal-title":"Prob. Inf. Transm."},{"key":"atypb21","first-page":"538","author":"Impagliazzo R.","year":"1995","journal-title":"Proceedings of IEEE FOCS"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.77.062329"},{"key":"atypb23","unstructured":"S. Kakade and A. Tewari,\n                      Learning Theory Lecture Notes\n                      , http:\/\/www.ttic.uchicago.edu\/ \u02dctewari\/LT_SP2008.html (2008)."},{"key":"atypb24","first-page":"191","volume":"28","author":"Karp R. M.","year":"1982","journal-title":"Enseign. Math."},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704445226"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"A. Kitaev, A. Shen, and M. N. Vyalyi,\n                      Classical and Quantum Computation\n                      , AMS, Providence, RI, 2002.","DOI":"10.1090\/gsm\/047"},{"key":"atypb27","first-page":"369","author":"Nayak A.","year":"1999","journal-title":"Proceedings of IEEE FOCS"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2004.02.005"},{"key":"atypb29","first-page":"900","volume":"8","author":"Oliveira R.","year":"2010","journal-title":"Quantum Inf. Comput."},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116037"},{"key":"atypb31","first-page":"91","author":"Vidal G.","year":"2003","journal-title":"Phys. Rev. Lett."},{"key":"atypb32","first-page":"537","author":"Watrous J.","year":"2000","journal-title":"Proceedings of IEEE FOCS"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/110856939","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:13:14Z","timestamp":1787335994000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/110856939"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/110856939"],"URL":"https:\/\/doi.org\/10.1137\/110856939","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}