Abstract
We study the complexity of problems solvable in deterministic polynomial time with access to an NP or Quantum MerlinArthur (QMA)oracle, such as P^NP and P^QMA, respectively. The former allows one to classify problems more finely than the PolynomialTime Hierarchy (PH), whereas the latter characterizes physically motivated problems such as Approximate Simulation (APXSIM) [Ambainis, CCC 2014]. In this area, a central role has been played by the classes P^NP[log] and P^QMA[log], defined identically to P^NP and P^QMA, except that only logarithmically many oracle queries are allowed. Here, [Gottlob, FOCS 1993] showed that if the adaptive queries made by a P^NP machine have a "query graph" which is a tree, then this computation can be simulated in P^NP[log].
In this work, we first show that for any verification class C ∈ {NP, MA, QCMA, QMA, QMA(2), NEXP, QMA_exp}, any P^C machine with a query graph of "separator number" s can be simulated using deterministic time exp(slog n) and slog n queries to a Coracle. When s ∈ O(1) (which includes the case of O(1)treewidth, and thus also of trees), this gives an upper bound of P^C[log], and when s ∈ O(log^k(n)), this yields bound QP^{C[log^{k+1}]} (QP meaning quasipolynomial time). We next show how to combine Gottlob’s "admissibleweighting function" framework with the "flagqubit" framework of [Watson, Bausch, Gharibian, 2020], obtaining a unified approach for embedding P^C computations directly into APXSIM instances in a blackbox fashion. Finally, we formalize a simple nogo statement about polynomials (c.f. [Krentel, STOC 1986]): Given a multilinear polynomial p specified via an arithmetic circuit, if one can "weakly compress" p so that its optimal value requires m bits to represent, then P^NP can be decided with only m queries to an NPoracle.
BibTeX  Entry
@InProceedings{gharibian_et_al:LIPIcs.ITCS.2022.75,
author = {Gharibian, Sevag and Rudolph, Dorian},
title = {{On Polynomially Many Queries to NP or QMA Oracles}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {75:175:27},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772174},
ISSN = {18688969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15671},
URN = {urn:nbn:de:0030drops156717},
doi = {10.4230/LIPIcs.ITCS.2022.75},
annote = {Keywords: admissible weighting function, oracle complexity class, quantum complexity theory, Quantum Merlin Arthur (QMA), simulation of local measurement}
}
Keywords: 

admissible weighting function, oracle complexity class, quantum complexity theory, Quantum Merlin Arthur (QMA), simulation of local measurement 
Collection: 

13th Innovations in Theoretical Computer Science Conference (ITCS 2022) 
Issue Date: 

2022 
Date of publication: 

25.01.2022 