論文の概要: The Spooky Pebble Game
- arxiv url: http://arxiv.org/abs/2110.08973v1
- Date: Mon, 18 Oct 2021 01:57:46 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-11 04:32:49.428231
- Title: The Spooky Pebble Game
- Title（参考訳）: スポークなPebbleゲーム
- Authors: Niels Kornerup, Jonathan Sadun, David Soloveichik
- Abstract要約: Pebbleゲームは一般に、計算における時空のトレードオフを研究するために使用される。
非古典的な入力に対する任意の古典回路の量子シミュレーションにおいて、このトレードオフを探求する小石ゲームを提案する。
- 参考スコア（独自算出の注目度）: 1.2891210250935146
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Pebble games are commonly used to study space-time trade-offs in computation.
We present a pebble game that explores this trade-off in quantum simulation of
arbitrary classical circuits on non-classical inputs. Many quantum algorithms,
such as Shor's algorithm and Grover's search, include subroutines that require
simulation of classical functions on inputs in superposition. The current state
of the art uses generic reversible simulation through Bennett's pebble game and
universal reversible gate sets such as the Toffoli. Using measurement-based
uncomputation, we replace many of the ancilla qubits used by existing
constructions with classical control bits, which are cheaper. Our pebble game
forms a natural framework for reasoning about measurement-based uncomputation,
and we prove tight bounds on the time complexity of all algorithms that use our
pebble game. For any $\epsilon \in (0,1)$, we present an algorithm that can
simulate irreversible classical computation that uses $\mathcal{T}$ time and
$\mathcal{S}$ space in
$O(\frac{1}{\epsilon}\frac{\mathcal{T}^{1+\epsilon}}{\mathcal{S}^\epsilon})$
time with $O(\frac{1}{\epsilon}\mathcal{S})$ qubits. With access to more qubits
we present algorithms that run in $O(\frac{1}{\epsilon}\mathcal{T})$ time with
$O(\mathcal{S}^{1-\epsilon}\mathcal{T}^\epsilon)$ qubits. Both of these results
show an improvement over Bennett's construction, which requires
$O(\frac{\mathcal{T}^{1+\epsilon}}{\mathcal{S}^\epsilon})$ time when using
$O(\epsilon2^{1/\epsilon} \mathcal{S} (1+\log
\frac{\mathcal{T}}{\mathcal{S}}))$ qubits. Additionally the results in our
paper combine with Barrington's theorem to provide a general method to
efficiently compute any log-depth circuit on quantum inputs using a constant
number of ancilla qubits. We also explore a connection between the optimal
structure of our pebbling algorithms and backtracking from dynamic programming.
- Abstract（参考訳）: pebbleゲームは、計算の時間的トレードオフを研究するためによく使われる。
我々は、非古典的入力に対する任意の古典回路の量子シミュレーションにおけるこのトレードオフを探求するpebbleゲームを提案する。
ショアのアルゴリズムやグローバーの探索のような多くの量子アルゴリズムは、重ね合わせの入力に対する古典関数のシミュレーションを必要とするサブルーチンを含む。
この芸術の現在の状態は、ベネットの小石ゲームとトフォリのような普遍的可逆ゲートセットによる一般的な可逆シミュレーションを用いている。
既存の構成で使用されるアンシラ量子ビットの多くを、測定に基づくアン計算を用いて、より安価な古典的な制御ビットに置き換える。
私たちのpebbleゲームは、測定に基づく計算を推論するための自然なフレームワークを形成しており、pebbleゲームを使用するすべてのアルゴリズムの時間的複雑さの厳密な境界を証明します。
任意の$\epsilon \in (0,1)$に対して、$\mathcal{T}$ time と $\mathcal{S}$ space in $O(\frac{1}{\epsilon}\frac{\mathcal{T}^{1+\epsilon}}{\mathcal{S}^\epsilon})$time with $O(\frac{1}{\epsilon}\mathcal{S})$ qubits を用いる可逆な古典計算をシミュレートできるアルゴリズムを提案する。
より多くの量子ビットにアクセスすることで、$O(\frac{1}{\epsilon}\mathcal{T})$O(\mathcal{S}^{1-\epsilon}\mathcal{T}^\epsilon)$ qubitsで実行されるアルゴリズムを提示する。
これらの結果から,$o(\epsilon2^{1/\epsilon} \mathcal{s} (1+\log \frac{\mathcal{t}}{\mathcal{s}})$ qubits を使用する場合,$o(\frac{\mathcal{t}^{1+\epsilon}}{\mathcal{s}^\epsilon})$ time を必要とする bennett の構成よりも改善が見られた。
さらに,本論文はバリントンの定理と組み合わさって,一定数のアンシラ量子ビットを用いて量子入力のログ深さ回路を効率的に計算する一般的な方法を提案する。
また、ペブブリングアルゴリズムの最適構造と動的プログラミングからのバックトラックとの関係についても検討する。
関連論文リスト
- Computational Lower Bounds for Regret Minimization in Normal-Form Games [68.66209476382213]
乗算重み更新などの既存の学習アルゴリズムが最適に近いことを示す。
結果はKothari と Mehta が提案したアルゴリズムの枠組みで得られた。
論文 参考訳（メタデータ） (2024-11-04T00:39:52Z) - Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms [71.73971094342349]
オンライン学習によるセルフプレイは、大規模な2人プレイのゼロサムゲームを解くための重要な方法の1つだ。
我々は,OMWUが支払行列のサイズに対数依存するなど,いくつかの利点があることを示した。
我々は、過去のことをすぐに忘れない幅広い種類のアルゴリズムが、すべて同じ問題に悩まされていることを証明している。
論文 参考訳（メタデータ） (2024-06-15T13:26:17Z) - Trade-offs between classical and quantum space using spooky pebbling [0.0]
Pebbleゲームは、空間/時間のトレードオフを研究するために使用されます。
本稿では,一般的な回路に対して,スポーキーな小石ゲームフレームワークを初めて適用する。
制限されたランタイム内では、古典的な空間を考慮すると量子空間を減らす戦略を見つけることができる。
論文 参考訳（メタデータ） (2024-01-19T09:41:47Z) - Provably Efficient High-Dimensional Bandit Learning with Batched
Feedbacks [93.00280593719513]
本稿では,オンラインインタラクションのT$ステップをバッチに分割したバッチフィードバックによる高次元マルチアームコンテキストバンドレットについて検討する。
具体的には、各バッチは以前のバッチに依存するポリシーに従ってデータを収集し、その報酬はバッチの最後にのみ明らかにする。
我々のアルゴリズムは,$mathcalO( log T)$ バッチで完全に逐次的に設定されたものに匹敵する後悔の限界を達成している。
論文 参考訳（メタデータ） (2023-11-22T06:06:54Z) - Learning in Multi-Player Stochastic Games [1.0878040851638]
有限ホライズン設定において、多くのプレイヤーとゲームにおける同時学習の問題を考える。
ゲームの典型的な対象解はナッシュ均衡であるが、これは多くのプレイヤーにとって難解である。
我々は異なるターゲットに目を向ける:全てのプレイヤーが使用するときの平衡を生成するアルゴリズム。
論文 参考訳（メタデータ） (2022-10-25T19:02:03Z) - Near-Optimal No-Regret Learning for General Convex Games [121.50979258049135]
一般凸およびコンパクト戦略集合に対して後悔が得られることを示す。
我々の力学は、適度にエンハンリフトされた空間上の楽観的な従順化バウンドのインスタンス化にある。
先行結果が適用される特殊な場合であっても、我々のアルゴリズムは最先端の後悔よりも改善される。
論文 参考訳（メタデータ） (2022-06-17T12:58:58Z) - 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) - The Parallel Reversible Pebbling Game: Analyzing the Post-Quantum
Security of iMHFs [6.305950347749109]
本稿では,量子コンピューティングにおけるNo-Deletion Theoremによる追加制約を捉える並列可逆ペブブリングゲームを提案する。
我々は、いくつかの重要なグラフの可逆空間時間複雑性を解析するために、新しい可逆ペブブリングゲームを適用した。
論文 参考訳（メタデータ） (2021-10-08T15:24:31Z) - Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov
Games with Perfect Recall [34.73929457960903]
本研究では,不完全情報ゲーム(IIG)におけるナッシュ均衡(NE)学習の問題について,自己学習を通して検討する。
Inlicit Exploration Online Mirror Descent (IXOMD)アルゴリズムを提案する。
IXOMD は 1/sqrtT$ の NE への収束率に縛られる確率の高いモデルのないアルゴリズムである。
論文 参考訳（メタデータ） (2021-06-11T09:51:29Z) - EigenGame Unloaded: When playing games is better than optimizing [19.522120239876486]
EigenGameは、Eigen Decompositionを競争ゲームと見なしている。
我々は、最近提案されたEigenGameに基づいて、固有分解を競争ゲームとみなす。
論文 参考訳（メタデータ） (2021-02-08T12:04:59Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-22T05:00:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。