文章基本信息

标题：On polynomially many queries to NP or QMA oracle
本地全文：下载
作者：Sevag Gharibian ; Dorian Rudolph
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2021
卷号：21
语种：English
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We study the complexity of problems solvable in deterministic polynomial time with access to an NP or Quantum Merlin-Arthur (QMA)-oracle, such as PNP and PQMA, respectively. The former allows one to classify problems more finely than the Polynomial-Time Hierarchy (PH), whereas the latter characterizes physically motivated problems such as Approximate Simulation (APX-SIM) [Ambainis, CCC 2014]. In this area, a central role has been played by the classes PNP[log] and PQMA[log], defined identically to PNP and PQMA, except that only logarithmically many oracle queries are allowed. Here, [Gottlob, FOCS 1993] showed that if the adaptive queries made by a PNP machine have a "query graph" which is a tree, then this computation can be simulated in PNP[log]. In this work, we first show that for any verification class CNPMAQCMAQMAQMA(2)NEXPQMAexp , any PC machine with a query graph of "separator number" s can be simulated using deterministic time exp(slogn) and slogn queries to a C-oracle. When sO(1) (which includes the case of O(1)-treewidth, and thus also of trees), this gives an upper bound of PC[log], and when sO(logk(n)), this yields bound QPC[logk+1] (QP meaning quasi-polynomial time). We next show how to combine Gottlob's "admissible-weighting function" framework with the "flag-qubit" framework of [Watson, Bausch, Gharibian, 2020], obtaining a unified approach for embedding PC computations directly into APX-SIM instances in a black-box fashion. Finally, we formalize a simple no-go statement about polynomials (c.f. [Krentel, STOC 1986]): Given a multi-linear polynomial p specified via an arithmetic circuit, if one can "weakly compress" p so that its optimal value requires m bits to represent, then PNP can be decided with only m queries to an NP-oracle.
关键词：admissible weighting function;oracle complexity class;quantum complexity theory;Quantum Merlin Arthur (QMA);simulation of local measurement