Gharibian, Sevag ;
Rudolph, Dorian
On Polynomially Many Queries to NP or QMA Oracles
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}
}
25.01.2022
Keywords: 

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

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

Issue date: 

2022 
Date of publication: 

25.01.2022 