論文の概要: Tight Bounds on the Spooky Pebble Game: Recycling Qubits with Measurements
- arxiv url: http://arxiv.org/abs/2110.08973v3
- Date: Thu, 06 Feb 2025 22:33:36 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-10 14:53:05.367281
- Title: Tight Bounds on the Spooky Pebble Game: Recycling Qubits with Measurements
- Title（参考訳）: おしゃれなPebbleゲーム「Tight Bounds」(動画あり)
- Authors: Niels Kornerup, Jonathan Sadun, David Soloveichik,
- Abstract要約: 我々は,この不気味な小石ゲームが,可逆的アプローチが達成できる範囲を超えて,キュービット数を減少させることを示す。
任意のDAGに対して、スポッキーな小石ゲームに必要な小石の数はPSPACEハードであることが示される。
最小数の小石を使用する二分木を編み出すための時間効率の戦略を構築することができる。
- 参考スコア（独自算出の注目度）: 0.6144680854063939
- License:
- 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. We show that for an arbitrary DAG even approximating the number of required pebbles in the spooky pebble game is PSPACE-hard. Despite this, we are able to construct a time-efficient strategy for pebbling binary trees that uses the minimum number of pebbles.
- Abstract（参考訳）: 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)上でのスポーキーな小石ゲームも検討し、計算におけるきめ細かいデータ依存を捉える。
任意のDAGに対して、スポッキーな小石ゲームに必要な小石の数を近似してもPSPACEハードであることが示される。
それにもかかわらず、最小数の小石を使用する二分木を編み出すための時間効率の戦略を構築することができる。
関連論文リスト
- 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) - SQUWALS: A Szegedy QUantum WALks Simulator [0.0]
私たちのシミュレータは、時間とメモリリソースの両方で$mathcalO(N2)$にスケールします。
このパッケージは、Szegedyの量子ウォークに基づくアルゴリズムの高レベルなアプリケーションを提供している。
論文 参考訳（メタデータ） (2023-07-26T17:24:10Z) - Classical and Quantum Elliptical Billiards: Mixed Phase Space and Short
Correlations in Singlets and Doublets [0.0]
ビリヤードの2つの双パラメトリック族における古典的および量子的性質に関する数値的な結果を示す。
数値計算により楕円族が混合古典位相空間を提示できることを示す。
rho_textc$が減少するにつれて、$p(s)$'sはGOE(シングルレット)とGUE(ダブルレット)のディストリビューションから同時に離れる傾向にある。
論文 参考訳（メタデータ） (2023-01-11T20:56:55Z) - 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) - Solving Random Parity Games in Polynomial Time [4.715993310546794]
パリティゲームは高い確率で時間$O(cal V|)$で解けることを示す。
また、非スパースゲームは高い確率で時間$O(cal V|)$で解けることを示し、$d=2$の場合の硬さに関する予想を出力する。
論文 参考訳（メタデータ） (2020-07-16T15:05:51Z) - Near-Optimal Reinforcement Learning with Self-Play [50.29853537456737]
我々は,直接の監督なしに自己対決で最適な政策を学習するセルフプレイアルゴリズムに焦点をあてる。
本稿では,サンプル複雑性を$tildemathcalO(SAB)$,サンプル複雑性を$tildemathcalO(S(A+B)$とする新しいemphNash Vラーニングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-22T05:00:13Z) - Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
NISQとフォールトトレラントの両方の設定で格子シュウィンガーモデルをシミュレートするために、スケーラブルで明示的なデジタル量子アルゴリズムを提供する。
格子単位において、結合定数$x-1/2$と電場カットオフ$x-1/2Lambda$を持つ$N/2$物理サイト上のシュウィンガーモデルを求める。
NISQと耐故障性の両方でコストがかかるオブザーバブルを、単純なオブザーバブルとして推定し、平均ペア密度を推定する。
論文 参考訳（メタデータ） (2020-02-25T19:18:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。