論文の概要: Coherent Rollout Oracles for Finite-Horizon Sequential Decision Problems

• arxiv url: http://arxiv.org/abs/2604.25962v1
• Date: Tue, 28 Apr 2026 00:46:37 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-30 15:59:36.105941
• Title: Coherent Rollout Oracles for Finite-Horizon Sequential Decision Problems
• Title（参考訳）: 有限水平列決定問題に対するコヒーレントロールアウトオラクル
• Authors: Nishant Shukla,
• Abstract要約: 逐次決定問題に対するコヒーレント量子ロールアウトには、ユニタリシミュレータが必要である。 枝依存の有効作用では、この写像は、絡み合った$N-bitマスク上のコヒーレントなランク選択である。 このプリミティブの最初の可逆・可逆的複雑性解析を行う。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Coherent quantum rollout for sequential decision problems requires a unitary simulator: randomness must live in explicit quantum registers, and basis-state selectors must be mapped to actions reversibly. With branch-dependent valid actions, this mapping is totalized coherent rank-select over an entangled $N$-bit validity mask: return the position of the $r$-th valid bit, or a sentinel if $r$ is out of range. We give the first reversible-circuit complexity analysis of this primitive. For selector width $w = \lceil \log_2(N+1) \rceil$, rank-select admits an $O(Nw)$-gate low-ancilla bounded-span scan, proved gate-optimal in its model, and an $O(N\log w)$-gate low-ancilla blocked construction when long-range gates are available; across all bounded-fan-in layouts, the unconditional gate lower bound is $Ω(N)$. Composing rank-select with reversible transition and predicate-evaluation circuits gives an explicit polynomial-size coherent rollout oracle for finite-horizon planning problems satisfying these primitive assumptions. The resulting oracle satisfies the access model of the best-arm pipeline of Wang et al., yielding $\widetilde{O}(\sqrt{k}/\varepsilon)$ coherent oracle calls against the standard classical $Ω(k/\varepsilon^2)$ arm-pull lower bound. We give a bounded-influence lifting theorem that extends this lower-bound construction from a base configuration to an exponential family of configurations. We instantiate the construction on SIR epidemic intervention, with a stochastic placement-game sanity check, and machine-check the main results in Lean 4. Code and proofs: https://github.com/BinRoot/b01t/tree/main/demos/rollout.
• Abstract（参考訳）: 連続的な決定問題に対するコヒーレントな量子ロールアウトは、ユニタリシミュレータを必要とする: ランダム性は明示的な量子レジスタで生きなければならず、基底状態セレクタは可逆的にアクションにマッピングされなければならない。 ブランチ依存のバリデーションアクションでは、このマッピングは、絡み合った$N$-bitバリデーションマスク上のコヒーレントなランク選択を総括する:$r$-thバリデーションビットの位置を返すか、$r$が範囲外であればセンチネルを返す。 このプリミティブの最初の可逆・回路的複雑性解析を行う。 セレクタ幅$w = \lceil \log_2(N+1) \rceil$に対して、 rank-select は$O(Nw)$-gate low-ancilla bounded-span scan を許容し、そのモデルでゲート最適化を証明し、$O(N\log w)$-gate low-ancilla block construction when long-range gates are available; all bounded-fan-in layouts, in the unconditional gate lower bound is $Ω(N)$. 可逆遷移と述語評価回路を持つランク選択を構成することは、これらの原始仮定を満たす有限水平計画問題に対して、明らかに多項式サイズのコヒーレントなロールアウトオラクルを与える。 結果として得られるオラクルは、Wang et al のベストアームパイプラインのアクセスモデルを満たすもので、$\widetilde{O}(\sqrt{k}/\varepsilon)$ coherent oracle call against the standard classical $Ω(k/\varepsilon^2)$ arm-pull lower boundである。 我々は、この下界構造を基本構成から指数的な構成の族へと拡張する有界影響持ち上げ定理を与える。 我々は、SIR感染対策の構築を、確率的配置ゲーム衛生チェックでインスタンス化し、Lean 4の主な成果をマシンチェックする。 コードと証明:https://github.com/BinRoot/b01t/tree/main/demos/rollout

関連論文リスト

• Nonvariational quantum optimisation approaches to pangenome-guided sequence assembly [0.42970700836450487]
  ゲノム組立問題に対する短期量子最適化手法を開発した。 固定された線形ランプQAOAスケジュールと反復的ウォームスタートバイアス更新を組み合わせたIterative-QAOAフレームワークを使用する。 カスタム回路コンパイル戦略は、標準ツールと比較してハードウェアゲートのオーバーヘッドを最大67%削減する。
  論文  参考訳（メタデータ） (2026-04-07T17:17:34Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  我々は、最大半空間離散性問題に対する次元下界の新たな指数関数を確立する。 どちらも計算幾何学と機械学習の基本的問題であり、その正確で近似的な形式である。
  論文  参考訳（メタデータ） (2026-03-19T15:53:41Z)
• Universal Hirschberg for Width Bounded Dynamic Programs [0.0]
  ヒルシュベルクのアルゴリズムは、格子動的プログラム(DP)上の中点二項による$O(N2)$から$O(N)$へ、最も長い共通部分列問題の空間複雑性を減少させる。 我々は、その基礎となるアイデアが、有向非巡回グラフ(DP DAG)に局所的依存を持つ広範な動的プログラムのクラスに一般化されることを示す。 前方シングルパスモデルでは$()$空間項は避けられないことを示し、ストリーミング設定における推測される$sqrtT$-type障壁について議論する。
  論文  参考訳（メタデータ） (2025-12-10T22:26:22Z)
• Optimal quantum simulation of linear non-unitary dynamics [0.31439717339537293]
  有界時間依存演算子$-A$によって生成される時間進化をシミュレートする量子アルゴリズムを提案する。 本稿では,最近のLinear-Combination-of-Hamiltonian-Simulation (LCHS)フレームワークを一般化する。
  論文  参考訳（メタデータ） (2025-08-26T17:58:27Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  近年の研究では、再生カーネルヒルベルト空間(RKHS)がニューラルネットワークによる関数のモデル化に適した空間ではないことが示されている。 本稿では,有界ノルムを持つオーバーパラメータ化された2層ニューラルネットワークに適した関数空間について検討する。
  論文  参考訳（メタデータ） (2024-04-29T15:04:07Z)
• Efficient Quantum State Synthesis with One Query [0.0]
  本稿では,古典的オラクルへの単一クエリ(重ね合わせ)を実現する時間類似量子アルゴリズムを提案する。 我々は、すべての$n$-qubit状態が、適切な有限ゲート集合上の$On/n)$-size回路によって0.01エラー内に構築可能であることを証明した。
  論文  参考訳（メタデータ） (2023-06-02T17:49:35Z)
• Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies [68.93512627479197]
  量子順序付き二項決定図($OBDD$)モデルについて検討する。 入力変数の任意の順序で、OBDDの下位境界と上位境界を証明します。 read$k$-times Ordered Binary Decision Diagrams (k$-OBDD$)の幅の階層を拡張します。
  論文  参考訳（メタデータ） (2022-04-22T12:37:56Z)
• 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)
• Second-Order Information in Non-Convex Stochastic Optimization: Power and Limitations [54.42518331209581]
  私たちは発見するアルゴリズムを見つけます。 epsilon$-approximate stationary point ($|nabla F(x)|le epsilon$) using $(epsilon,gamma)$surimateランダムランダムポイント。 ここでの私たちの下限は、ノイズのないケースでも新規です。
  論文  参考訳（メタデータ） (2020-06-24T04:41:43Z)

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

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