文章基本信息

标题：The Acrobatics of BQ
本地全文：下载
作者：Scott Aaronson ; DeVon Ingram ; William Kretschmer 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We show that, in the black-box setting, the behavior of quantum polynomial-time (BQP) can be remarkably decoupled from that of classical complexity classes like NP. Specifically: -There exists an oracle relative to which NPBQPBQPPH , resolving a 2005 problem of Fortnow. Interpreted another way, we show that AC0 circuits cannot perform useful homomorphic encryption on instances of the Forrelation problem. As a corollary, there exists an oracle relative to which P=NP but BQP=QCMA . -Conversely, there exists an oracle relative to which BQPNPPHBQP . -Relative to a random oracle, PP=PostBQP is not contained in the "QMA hierarchy" QMAQMAQMA, and more generally PP(MIP)(MIP)(MIP) (!), despite the fact that MIP=RE in the unrelativized world. This result shows that there is no black-box quantum analogue of Stockmeyer's approximate counting algorithm. -Relative to a random oracle, Pk+1BQPPk for every k. -There exists an oracle relative to which BQP=P#P and yet PH is infinite. (By contrast, if NPBPP , then PH collapses relative to all oracles.) -There exists an oracle relative to which P=NP=BQP=P#P . To achieve these results, we build on the 2018 achievement by Raz and Tal of an oracle relative to which BQPPH , and associated results about the Forrelation problem. We also introduce new tools that might be of independent interest. These include a "quantum-aware" version of the random restriction method, a concentration theorem for the block sensitivity of AC0 circuits, and a (provable) analogue of the Aaronson-Ambainis Conjecture for sparse oracles.
关键词：BQP;Forrelation;oracle separations;Polynomial Hierachy;query complexity