論文の概要: On polynomially many queries to NP or QMA oracles

• arxiv url: http://arxiv.org/abs/2111.02296v1
• Date: Wed, 3 Nov 2021 15:29:01 GMT
• ステータス: 処理完了
• システム内更新日: 2023-03-09 06:50:23.131923
• Title: On polynomially many queries to NP or QMA oracles
• Title（参考訳）: NPまたはQMAオーラクルに対する多項式的な多くのクエリについて
• Authors: Sevag Gharibian and Dorian Rudolph
• Abstract要約: 本稿では,NPやQuantum Merlin-Arthur-oracle(QMA)にアクセスして,決定論的時間で解ける問題の複雑性について検討する。 まず、検証クラス$CinNP,MA,QMA,QMA(2),NEXP,QMA_exp$に対して、「セパレータ番号」$s$のクエリグラフを持つ任意の$PC$マシンをシミュレートできることを示す。 次に、Gottlobの"許容重み付け関数"フレームワークと"フラグキュービット"フレームワークを組み合わせる方法について説明する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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\in\{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(s\log n)$ and $s\log n$ queries to a $C$-oracle. When $s\in 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\in 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.
• Abstract（参考訳）: P^{NP}$や$P^{QMA}$といったNPやQuantum Merlin-Arthur-oracle(QMA)へのアクセスを伴う決定論的多項式時間で解ける問題の複雑性について検討する。 前者はPolynomial-Time Hierarchy (PH)よりも細かな分類が可能であり、後者は Approximate Simulation (APX-SIM) [Ambainis, CCC 2014] のような物理的動機付けの問題を特徴付ける。 この領域では、中心的な役割は$P^{NP[\log]}$と$P^{QMA[\log]}$によって演じられ、これは$P^{NP}$と$P^{QMA}$と同一に定義される。 ここで [Gottlob, FOCS 1993] は、$P^{NP}$マシンで作られた適応的なクエリが木である「クエリグラフ」を持つなら、この計算は$P^{NP[\log]}$でシミュレートできることを示した。 この研究において、まず、検証クラス$C\in\{NP,MA,QCMA,QMA(2),NEXP,QMA_{\exp}\}$に対して、"セパレータ番号"のクエリグラフを持つ任意の$P^C$マシンに対して、$s$は決定論的時間$\exp(s\log n)$と$s\log n$クエリを$C$-oracleにシミュレートできることを示す。 もし$s\in o(1)$(これは$o(1)$-treewidthの場合を含み、したがって木も含む)の場合、これは$p^{c[\log]}$の上限を与え、$s\in o(\log^k(n))$のとき、バウンド$qp^{c[\log^{k+1}]}$(qpは準多項時間を意味する)となる。 次に、Gottlobの"許容重み付け関数"フレームワークと[Watson, Bausch, Gharibian, 2020]の"フラグキュービット"フレームワークを組み合わせる方法を示し、ブラックボックス方式でAPX-SIMインスタンスに直接$P^C$計算を埋め込む統一的なアプローチを得る。 最後に、多項式に関する単純なno-go文を形式化する(c.f. [Krentel, STOC 1986]): 算術回路で指定された多重線型多項式$p$が与えられたとき、その最適値が表現するのに$m$ビットを必要とするように$p$を「弱圧縮」できるなら、$P^{NP}$はNP-オラクルへのクエリだけで決定できる。

関連論文リスト

• Data subsampling for Poisson regression with pth-root-link [53.63838219437508]
  ポアソン回帰のためのデータサブサンプリング手法を開発し解析する。 特に,ポアソン一般化線形モデルと ID-および平方根リンク関数について考察する。
  論文  参考訳（メタデータ） (2024-10-30T10:09:05Z)
• A shortcut to an optimal quantum linear system solver [55.2480439325792]
  複雑で解析困難な手法を用いない、概念的にシンプルな量子線形システム解法(QLSS)を提案する。 ソリューションノルム$lVertboldsymbolxrVert$が正確に知られているなら、私たちのQLSSはカーネルの1つのアプリケーションだけを必要とします。 あるいは、断熱経路追従法から概念を再導入することにより、標準推定に$O(kappa)$複雑さを実現できることを示す。
  論文  参考訳（メタデータ） (2024-06-17T20:54:11Z)
• BQP, meet NP: Search-to-decision reductions and approximate counting [0.0]
  本稿では,探索-決定還元と近似カウントという,ブール充足可能性(SAT)問題の研究の2つの基本的な課題に焦点をあてる。 まず、ポリ時間チューリングマシンがNPオラクルに対して$Theta(n)$クエリを必要とする古典的な設定とは対照的に、量子的には$Theta(log n)$クエリが十分であることを示す。 近似カウンティングに移行し、探索-決定還元と近似カウンティングの量子リンクを利用して、既存の古典的近似カウンティングアルゴリズムが最適であることを示す。
  論文  参考訳（メタデータ） (2024-01-08T14:59:48Z)
• Efficient Quantum State Synthesis with One Query [0.0]
  本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。 我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
  論文  参考訳（メタデータ） (2023-06-02T17:49:35Z)
• Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning [54.806166861456035]
  本研究では,有限水平マルコフ決定過程(MDP)によってモデル化されたエピソディック強化学習(RL)問題をバッチ数に制約を加えて検討する。 我々は,$tildeO(sqrtSAH3Kln (1/delta))$tildeO(cdot)をほぼ最適に後悔するアルゴリズムを設計し,$(S,A,H,K)$の対数項を$K$で隠蔽する。 技術的貢献は2つある: 1) 探索のためのほぼ最適設計スキーム
  論文  参考訳（メタデータ） (2022-10-15T09:22:22Z)
• The Approximate Degree of DNF and CNF Formulas [95.94432031144716]
  すべての$delta>0に対して、$はCNFと近似次数$Omega(n1-delta)の式を構築し、基本的には$nの自明な上限に一致する。 すべての$delta>0$に対して、これらのモデルは$Omega(n1-delta)$、$Omega(n/4kk2)1-delta$、$Omega(n/4kk2)1-delta$が必要です。
  論文  参考訳（メタデータ） (2022-09-04T10:01:39Z)
• Pseudo Polynomial-Time Top-k Algorithms for d-DNNF Circuits [0.0]
  我々は,最大値w.r.$$$の内,$C$のモデルを計算するアルゴリズムを提案する。 また、d-DNNF回路に$C$を変換する擬似時間アルゴリズムを、上位の$k$に値を持つ$C$のモデルによって正確に満たされる。
  論文  参考訳（メタデータ） (2022-02-11T23:53:43Z)
• An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
  すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
  論文  参考訳（メタデータ） (2020-08-24T06:50:57Z)
• An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications [28.54236118020831]
  本稿では,最適な$O(n log (kappa))$オアラーク評価を用いた新しい切削平面アルゴリズムを提案する。 また、評価毎に$n2$の時間を改善できないため、実行時間が最適であることを示す。
  論文  参考訳（メタデータ） (2020-04-08T20:56:40Z)
• Agnostic Q-learning with Function Approximation in Deterministic Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
  本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。 もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
  論文  参考訳（メタデータ） (2020-02-17T18:41:49Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。