{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,12,9]],"date-time":"2022-12-09T16:14:55Z","timestamp":1670602495297},"reference-count":0,"publisher":"Rinton Press","issue":"11&12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["QIC"],"published-print":{"date-parts":[[2017,9]]},"abstract":"<jats:p>We study how complexity classes above BQP, such as postBQP, postBQPFP, and SBQP, change if we \u201cMerlinize\u201d them, i.e., if we allow an extra input quantum state (or classical bit string) given by Merlin as witness. Our main results are the following: First, the Merlinized version of postBQP is equal to PSPACE. Second, if the Merlinized postBQP is restricted in such a way that the postselection probability is equal for all witness states, then the class is equal to PP. Finally, the Merlinization does not change the class SBQP.<\/jats:p>","DOI":"10.26421\/qic17.11-12-3","type":"journal-article","created":{"date-parts":[[2021,2,23]],"date-time":"2021-02-23T04:41:31Z","timestamp":1614055291000},"page":"959-972","source":"Crossref","is-referenced-by-count":3,"title":["Merlinization of complexity classes above BQP"],"prefix":"10.26421","volume":"17","author":[{"given":"Tomoyuki","family":"Morimae","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Harumichi","family":"Nishimura","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"10955","published-online":{"date-parts":[[2017,9]]},"container-title":["Quantum Information and Computation"],"original-title":[],"deposited":{"date-parts":[[2021,2,23]],"date-time":"2021-02-23T04:41:35Z","timestamp":1614055295000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.rintonpress.com\/journals\/doi\/QIC17.11-12-3.html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9]]},"references-count":0,"journal-issue":{"issue":"11&12","published-online":{"date-parts":[[2017,9]]},"published-print":{"date-parts":[[2017,9]]}},"URL":"https:\/\/doi.org\/10.26421\/qic17.11-12-3","relation":{},"ISSN":["1533-7146","1533-7146"],"issn-type":[{"value":"1533-7146","type":"print"},{"value":"1533-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9]]}}}