論文の概要: How fast can a parent estimate the value of their children? A quantum algorithm for stochastic games

• arxiv url: http://arxiv.org/abs/2609.35511v1
• Date: Mon, 28 Sep 2026 16:06:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 21:15:53.934363
• Title: How fast can a parent estimate the value of their children? A quantum algorithm for stochastic games
• Title（参考訳）: 親は子どもの価値をどのくらいの速さで推定できるのか?確率ゲームのための量子アルゴリズム
• Abstract要約: 2ドルのゲームに量子アルゴリズムを与える。 アルゴリズムは、ゲームの値をルート平均2乗誤差$に推定し、[O!left(KD, degfracD4, fracN, D4D logleft( fracdeg N right), qquad D = 2m ] クエリを葉の値に変換する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We give a quantum algorithm for stochastic $2$-player games. Their game trees are the expectiminimax trees of classical game search: $m$ adversarial layers alternate with $m$ chance layers, every node has $deg$ children, and the leaf values lie in an interval of length $N$. The algorithm estimates the value of the game to root mean square error $ε$ with \[ O\!\left( K^{D}\, deg^{\frac{D}{4}} \, \frac{N}ε \, D^{4D} \log\left( \frac{deg N}ε \right)^{4D} \right), \qquad D = 2m \] queries to the leaf values, where $K$ is an absolute constant. If we treat the depth $D$ as a constant as is sometimes done in the literature, the bound is $\widetilde O(deg^{m/2}ε^{-1})$ against the classical $\widetilde O(deg^{m}ε^{-2})$. So the quadratic speedup in the branching factor known for adversarial trees and the quadratic speedup in the accuracy known for a single expectation both survive when we nest one inside the other. We use a derandomised multilevel Monte Carlo estimator for chance layers and a coherent binary search for adversarial layers. The composition is done by introducing a conversion between root-mean-square and uniform error guarantees, and a composition to nest it with quantum mean estimation. We state the algorithm for stochastic games, but it is valid for the following conditions: the value of a parent is a Lipschitz function of the values of its children and the value at a chance vertex is linear in its children, however the speedup is preserved only if the deterministic step has a quantum subroutine with sublinear query complexity.
• Abstract（参考訳）: 確率的2ドルプレイヤゲームに対する量子アルゴリズムを提案する。 それらのゲームツリーは、古典的なゲーム検索の予測ミニマックスツリーである:$m$ 敵層は$m$ チャンス層と交互に、各ノードは$deg$ 子供を持ち、葉の値は長さ$N$の間隔にある。 アルゴリズムは、ゲームの価値をルート平均二乗誤差$ε$ with \[O\! K^{D}\, deg^{\frac{D}{4}} \, \frac{N}ε \, D^{4D} \log\left( \frac{deg N}ε \right)^{4D} \right), \qquad D = 2m \] を葉の値に問い合わせる。 文献でしばしば行われるように、深さ$D$を定数として扱うなら、境界は$\widetilde O(deg^{m/2}ε^{-1})$であり、古典的な$\widetilde O(deg^{m}ε^{-2})$に対してである。 したがって、枝分かれ係数の二次的スピードアップは、逆木で知られ、また、単一の期待で知られている精度の二次的スピードアップは、どちらも、一方を他方の中に入れた時に生き残る。 我々は、確率層に対するデランドマイズされたマルチレベルモンテカルロ推定器と、対向層に対するコヒーレントな二項探索を行う。 この合成は、ルート平均二乗と均一な誤差保証の間の変換を導入し、量子平均推定でネストする合成を行う。 親の値は子供の値のリプシッツ関数であり、チャンス頂点の値は子供に線形であるが、決定論的ステップがサブ線形クエリの複雑さを持つ量子サブルーチンを持つ場合に限り、スピードアップは保存される。

関連論文リスト

• Exponential lower bounds for low-degree strategies in position-based quantum cryptography [0.764671395172401]
  非局所量子計算 (NLQC) は、2つの遠隔操作者による2部単位のU_AB$の実装に基づいている。 ユニタリな$U_AB$が存在するかどうかを知ることは、大きなオープンな問題である。 このような指数的下界は、位置ベースの量子暗号のセキュリティに不可欠である。
  論文  参考訳（メタデータ） (2026-09-28T16:43:48Z)
• Quantum Query Complexity of Persistence Statistics in Graph Zigzags [2.895030292351388]
  本研究では、スナップショット・アジャシエンスビットからジグザグバー寿命のスカラーサマリーを推定するクエリ複雑性について検討した。 ランクがグラフの回路ランクであるグラフの場合、非線形バーコード関数はエッジと成分数の平均となる。 すべての固定パワーウェイトに対して$xr$,$rge2$、均一ウィンドウ平均では、最悪のケースの複雑さは$widetilde(nsqrt m/varepsilon)$ Quantumと$(n2m)$ classicalである。
  論文  参考訳（メタデータ） (2026-09-05T02:16:28Z)
• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  AxiotisとSviridenkoは[AS21]において、凸最適化における制限条件数への線形依存はスパース時間アルゴリズムでは改善できないと推測した。 我々は、最小二乗目的に対する予想下界を確立し、ランダム化された完全体積小セット展開仮説に基づく条件付けを行う。
  論文  参考訳（メタデータ） (2026-08-03T17:57:01Z)
• High-Dimensional Procrustes Matching via Tree Counts [5.464035038606368]
  Procrustes matching problem(英語版)は、2つの集合を整列する$[n]$の未知の置換を復元するように要求する。 gtrsim maxlog n/d,sqrtlog n/n$ のとき、正確な回復が可能であることを示す。 また,木数計算アルゴリズムには条件2 > sqrt$ が必要であることを示唆する低次優位計算を行う。
  論文  参考訳（メタデータ） (2026-07-09T14:33:47Z)
• Online Newton Method for Bandit Convex Optimisation [28.66596225688161]
  ゼロ階帯域幅の最適化のための計算効率の良いアルゴリズムを提案する。 逆条件では、その後悔は少なくとも$d3.5 sqrtn Mathrmpolylog(n, d)$であり、d$が時間的地平線である確率が高いことを証明している。 設定において、バウンダリは$M d2 sqrtn Mathrmpolylog(n, d)$に改善され、[d-1/2, d-1 / 4]$は$Mとなる。
  論文  参考訳（メタデータ） (2024-06-10T17:44:11Z)
• Can We Find Nash Equilibria at a Linear Rate in Markov Games? [95.10091348976779]
  マルチプレイヤーゼロサム割引マルコフゲームにおける分散学習について検討した。 目標は、2つの特性を満たすエージェントのポリシー最適化アルゴリズムを設計することである。
  論文  参考訳（メタデータ） (2023-03-03T02:40:26Z)
• Superpolynomial Lower Bounds for Decision Tree Learning and Testing [5.117810469621253]
  ランダム化されたETHの下では、2つの基本的な問題に対して超ポリノミカルな下界が証明される。 その結果, 分散自由なPAC学習と決定木の試験において, 新たな下位境界が示唆された。 学習決定木の境界の低さを$nOmega(log s)$に改善できることを示します。
  論文  参考訳（メタデータ） (2022-10-12T16:25:48Z)
• Near-Optimal Learning of Extensive-Form Games with Imperfect Information [54.55092907312749]
  本稿では,2プレイヤーゼロサムゲームにおいて,$widetildemathcalO((XA+YB)/varepsilon2)$プレイのエピソードのみを必要とするアルゴリズムの最初の行を,$varepsilon$-approximate Nash平衡を求める。 これにより$widetildemathcalO((X2A+Y2B)/varepsilon2)$が$widetildemathcalO(maxX,
  論文  参考訳（メタデータ） (2022-02-03T18:18:28Z)
• Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
  我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。 本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-22T05:00:13Z)

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

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