論文の概要: 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 の構成よりも改善が見られた。
さらに,本論文はバリントンの定理と組み合わさって,一定数のアンシラ量子ビットを用いて量子入力のログ深さ回路を効率的に計算する一般的な方法を提案する。
また、ペブブリングアルゴリズムの最適構造と動的プログラミングからのバックトラックとの関係についても検討する。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。