論文の概要: 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ハードであることを意味する。

関連論文リスト

• 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)

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

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