論文の概要: Parallel Spooky Pebbling Makes Regev Factoring More Practical

• arxiv url: http://arxiv.org/abs/2510.08432v1
• Date: Thu, 09 Oct 2025 16:45:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-10 17:54:15.21064
• Title: Parallel Spooky Pebbling Makes Regev Factoring More Practical
• Title（参考訳）: パラレルなスポークなペブリングは、レグレブファクタリングをより実用的なものにする
• Authors: Gregory D. Kahanamoku-Meyer, Seyoon Ragavan, Katherine Van Kirk,
• Abstract要約: 古典コンピューティングの抽象化である"Pebble Games"は、本質的にシーケンシャルなタスクに量子回路の設計に使われている。 本稿では,これらの手法をRegevの分解アルゴリズムに適用することにより,演算のコストを大幅に削減できることを示す。 我々は、整数分解以外の量子暗号解析にも応用できると信じている。
• 参考スコア（独自算出の注目度）: 1.733255162390776
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: "Pebble games," an abstraction from classical reversible computing, have found use in the design of quantum circuits for inherently sequential tasks. Gidney showed that allowing Hadamard basis measurements during pebble games can dramatically improve costs -- an extension termed "spooky pebble games" because the measurements leave temporary phase errors called ghosts. In this work, we define and study parallel spooky pebble games. Previous work by Blocki, Holman, and Lee (TCC 2022) and Gidney studied the benefits offered by either parallelism or spookiness individually; here we show that these resources can yield impressive gains when used together. First, we show by construction that a line graph of length $\ell$ can be pebbled in depth $2\ell$ (which is exactly optimal) using space $\leq 2.47\log \ell$. Then, to explore pebbling schemes using even less space, we use a highly optimized $A^*$ search implemented in Julia to find the lowest-depth parallel spooky pebbling possible for a range of concrete line graph lengths $\ell$ given a constant number of pebbles $s$. We show that these techniques can be applied to Regev's factoring algorithm (Journal of the ACM 2025) to significantly reduce the cost of its arithmetic. For example, we find that 4096-bit integers $N$ can be factored in multiplication depth 193, which outperforms the 680 required of previous variants of Regev and the 444 reported by Eker{\aa} and G\"artner for Shor's algorithm (IACR Communications in Cryptology 2025). While space-optimized implementations of Shor's algorithm remain likely the best candidates for first quantum factorization of large integers, our results show that Regev's algorithm may have practical importance in the future, especially given the possibility of further optimization. Finally, we believe our pebbling techniques will find applications in quantum cryptanalysis beyond integer factorization.
• Abstract（参考訳）: 古典的可逆計算の抽象化である"Pebble Games"は、本質的にシーケンシャルなタスクに量子回路の設計に使われている。 ギドニー氏は、小石ゲーム中のアダマール基底測定を可能にすることで、コストが劇的に向上することを示した。 本研究では,並列小石ゲームを定義し,研究する。 Blocki氏、Holman氏、Lee氏(TCC 2022)とGidney氏による以前の研究は、並列性またはスポーク性の両方によって提供されるメリットを個別に研究した。 まず、長さ $\ell$ の直線グラフを、空間 $\leq 2.47\log \ell$ を用いて深さ $2\ell$ (正確には最適) で絞り込むことができることを示す。 さらに、より少ない空間を用いてペブブリングスキームを探索するために、Juliaで実装された高度に最適化された$A^*$サーチを用いて、コンクリートの線グラフの長さの幅に対して最小の深さの並列スポッキーペブリングを求める。 これらの手法はRegevの分解アルゴリズム(ACM 2025のジャーナル)に適用でき、演算のコストを大幅に削減できることを示す。 例えば 4096-bit 整数 $N$ は乗算深さ 193 で分解でき、これは以前の Regev の変種と Eker{\aa} と G\"artner for Shor's Algorithm (IACR Communications in Cryptology 2025) によって報告された 444 の 680 よりも優れている。 Shorのアルゴリズムの空間最適化実装は、大きな整数の最初の量子因数分解の最適候補である可能性が高いが、我々の結果は、特にさらなる最適化の可能性を考えると、Regevのアルゴリズムが将来、実用的な重要性を持つことを示している。 最後に、我々はペブブリング技術が整数分解以外の量子暗号解析に応用できると考えている。

関連論文リスト

• Space-Efficient and Noise-Robust Quantum Factoring [10.974556218898435]
  Regevの最近の量子ファクタリングアルゴリズムに2つの改善がある。 レゲフの回路は$O(n3/2)$ qubitsと$O(n3/2 log n)$ gatesを必要とする。 Regev氏の古典的な後処理手順の分析は、すべての$approx sqrtn$の実行を成功させる必要がある。
  論文  参考訳（メタデータ） (2023-10-02T04:31:21Z)
• Simulation of IBM's kicked Ising experiment with Projected Entangled Pair Operator [71.10376783074766]
  我々は最近,誤りを軽減した量子回路を用いてエミュレートされた127量子ビットキックド・イジングモデルの古典的シミュレーションを行った。 提案手法はハイゼンベルク図の射影的絡み合ったペア作用素(PEPO)に基づいている。 我々はクリフォード展開理論を開発し、正確な期待値を計算し、それらをアルゴリズムの評価に利用する。
  論文  参考訳（メタデータ） (2023-08-06T10:24:23Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。 補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。 各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
  論文  参考訳（メタデータ） (2022-06-30T03:15:23Z)
• Private Frequency Estimation via Projective Geometry [47.112770141205864]
  そこで本研究では,局所微分型(LDP)周波数推定のための新しいアルゴリズムであるProjectiveGeometryResponse (PGR)を提案する。 私たちの$varepsilon$-LDPアルゴリズムは、プライベートコイン設定で$lceillogkrceilビット、パブリックコイン設定で$varepsilonlog e + O(1)$の通信コストを持っています。 実際に使用される多くのパラメータ設定では、これは最近のPIによって達成されるO(n+k2)$Optimalコストよりも大幅に改善されている。
  論文  参考訳（メタデータ） (2022-03-01T02:49:55Z)
• Tight Bounds on the Spooky Pebble Game: Recycling Qubits with Measurements [0.6144680854063939]
  我々は,この不気味な小石ゲームが,可逆的アプローチが達成できる範囲を超えて,キュービット数を減少させることを示す。 任意のDAGに対して、スポッキーな小石ゲームに必要な小石の数はPSPACEハードであることが示される。 最小数の小石を使用する二分木を編み出すための時間効率の戦略を構築することができる。
  論文  参考訳（メタデータ） (2021-10-18T01:57:46Z)
• Bayesian Optimistic Optimisation with Exponentially Decaying Regret [58.02542541410322]
  現在の実用的なBOアルゴリズムは、$mathcalO(fraclogNsqrtN)$から$mathcalO(e-sqrtN)$まで、$N$は評価の数である。 本稿では,boと木に基づく楽観的楽観化の概念を絡み合うことにより,無音環境における後悔を改善できる可能性について検討する。 次数$mathcal O(N-sqrt)で指数的再帰を達成できる最初の実践的手法であるBOOアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-05-10T13:07:44Z)
• On Effective Parallelization of Monte Carlo Tree Search [51.15940034629022]
  モンテカルロ木探索(MCTS)は、探索木を構築するためにかなりの数のロールアウトを必要とするため、計算コストがかかる。 効果的な並列MCTSアルゴリズムを設計する方法は、体系的に研究されておらず、まだよく分かっていない。 我々は,より効率的な並列MCTSアルゴリズムの設計に,提案する必要条件をどのように適用できるかを実証する。
  論文  参考訳（メタデータ） (2020-06-15T21:36:00Z)

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

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