論文の概要: Tight Bounds on the Spooky Pebble Game: Recycling Qubits with
Measurements
- arxiv url: http://arxiv.org/abs/2110.08973v2
- Date: Tue, 6 Feb 2024 05:31:26 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-07 21:39:55.399167
- Title: Tight Bounds on the Spooky Pebble Game: Recycling Qubits with
Measurements
- Title（参考訳）: spooky pebbleゲームにおける厳密な境界: 測定値によるクビットのリサイクル
- Authors: Niels Kornerup, Jonathan Sadun, David Soloveichik
- Abstract要約: 我々は,この不気味な小石ゲームが,可逆的アプローチが達成できる範囲を超えて,キュービット数を減少させることを示す。
また、より汎用的な非巡回グラフ(DAG)上のスポーキー小石ゲームも検討し、このゲームが木上の可逆小石ゲームより優れていることを示す。
- 参考スコア（独自算出の注目度）: 0.6906005491572401
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Pebble games are popular models for analyzing time-space trade-offs. In
particular, the reversible pebble game is often applied in quantum algorithms
like Grover's search to efficiently simulate classical computation on inputs in
superposition. However, the reversible pebble game cannot harness the
additional computational power granted by irreversible intermediate
measurements. The spooky pebble game, which models interleaved measurements and
adaptive phase corrections, reduces the number of qubits beyond what reversible
approaches can achieve. While the spooky pebble game does not reduce the total
space (bits plus qubits) complexity of the simulation, it reduces the amount of
space that must be stored in qubits. We prove asymptotically tight trade-offs
for the spooky pebble game on a line with any pebble bound, giving a tight
time-qubit tradeoff for simulating arbitrary classical sequential computation
with the spooky pebble game. For example, for all $\epsilon \in (0,1]$, any
classical computation requiring time $T$ and space $S$ can be implemented on a
quantum computer using only $O(T/ \epsilon)$ gates and
$O(T^{\epsilon}S^{1-\epsilon})$ qubits. This improves on the best known bound
for the reversible pebble game with that number of qubits, which uses
$O(2^{1/\epsilon} T)$ gates.
We also consider the spooky pebble game on more general directed acyclic
graphs (DAGs), capturing fine-grained data dependency in computation and show
that this game can outperform the reversible pebble game on trees. Additionally
any DAG can be pebbled with at most one more pebble than is needed in the
irreversible pebble game, implying that finding the minimum number of pebbles
necessary to play the spooky pebble game on a DAG with maximum in-degree two is
PSPACE-hard to approximate.
- Abstract（参考訳）: Pebbleゲームは、時間空間のトレードオフを分析する一般的なモデルである。
特に可逆小石ゲームは、グロバー探索のような量子アルゴリズムで重ね合わせの入力の古典計算を効率的にシミュレートするためによく用いられる。
しかし、可逆小石ゲームは、可逆中間測度によって与えられる余分な計算力を利用することはできない。
測定と適応位相補正をモデル化したスポーキーな小石ゲームは、可逆的なアプローチが達成できる範囲を超えて、キュービットの数を減らす。
スパーキー小石ゲームはシミュレーションの総空間(ビット+キュービット)の複雑さを減少させるわけではないが、キュービットに格納しなければならない空間の量を減少させる。
あらゆるpebbleバウンドのライン上に、spooky pebbleゲームに対する漸近的に厳しいトレードオフがあることを証明し、sooky pebbleゲームと任意の古典的なシーケンシャルな計算をシミュレートするための、厳密な時間的トレードオフを与えました。
例えば、すべての$\epsilon \in (0,1]$に対して、時間$T$とスペース$S$を必要とする古典的な計算は、量子コンピュータ上で$O(T/ \epsilon)$ gatesと$O(T^{\epsilon}S^{1-\epsilon})$ qubitsで実装できる。
これにより、その数で可逆小石ゲームに最もよく知られた境界が改善され、これは$O(2^{1/\epsilon} T)$ gates を使用する。
さらに,より一般的な有向非循環グラフ(dag)上では,細粒度データ依存性をキャプチャし,このゲームが木上で可逆的なpebbleゲームに勝ることを示す。
さらに、任意のDAGは、不可逆小石ゲームで必要とされる以上の1つ以上の小石で小石化することができ、最大2度のDAG上でスポッキー小石ゲームをプレイするのに必要となる最小の小石を見つけることは、PSPACEハードであることを意味する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。