License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.75
URN: urn:nbn:de:0030-drops-156717
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15671/
Go to the corresponding LIPIcs Volume Portal

Gharibian, Sevag ; Rudolph, Dorian

On Polynomially Many Queries to NP or QMA Oracles

pdf-format:
LIPIcs-ITCS-2022-75.pdf (1 MB)

Abstract

We study the complexity of problems solvable in deterministic polynomial time with access to an NP or Quantum Merlin-Arthur (QMA)-oracle, such as P^NP and P^QMA, 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 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 C-oracle. 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 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 P^C 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 P^NP can be decided with only m queries to an NP-oracle.

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:1--75:27},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/15671},
  URN =		{urn:nbn:de:0030-drops-156717},
  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

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI