論文の概要: Streaming Regev's Quantum Factoring Algorithm

• arxiv url: http://arxiv.org/abs/2610.06733v1
• Date: Mon, 05 Oct 2026 17:18:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-08 23:18:49.860504
• Title: Streaming Regev's Quantum Factoring Algorithm
• Title（参考訳）: Streaming Regev's Quantum Factoring Algorithm
• Abstract要約: Regevのファクタリングアルゴリズムは「量子リサイクル」とは相容れない Regevのアルゴリズムは、$4n+O(sqrtn)$ qubitsを使って$n$-bit整数を分解できる。 Regevのアルゴリズムは、$4n+O(sqrtn)$ qubitsを使って$n$-bit整数を分解できる。
• 参考スコア（独自算出の注目度）: 0.5973037224935535
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A major practical obstacle to Regev's factoring algorithm is its large space usage. In particular, the algorithm was believed to be incompatible with "qubit recycling," which streams the control qubits in phase estimation rather than storing them all simultaneously. We show how to fix this streaming problem. We build on the construction of Ragavan and Vaikuntanathan, which used Fibonacci accumulators to reduce the qubit count from $O(n^{1.5})$ to $11.32n$. We make two key improvements. First, we use superposition masking to prevent unwanted information from entering the accumulators, removing the need for uncomputation. Second, we show how to perform phase estimation using Fibonacci powers of a unitary operation rather than powers of two. This avoids various encoding conversions required by the construction of Ragavan and Vaikuntanathan. After these improvements, the phase-estimation qubits are used only once in the circuit, allowing them to be streamed. Our improvements reduce the space usage of Regev's factoring algorithm to $n+M(n)+O(\sqrt{n})$, where $M(n)$ is the space required for an in-place multiplication. For example, using the in-place multiplier of Luo et al. (2026), Regev's algorithm can factor an $n$-bit integer using $4n+O(\sqrt{n})$ qubits. Although our construction still falls short of the $n/2+εn$ qubits sufficient for leading implementations of Shor's algorithm, it is the lowest-space instantiation of Regev's algorithm to date and suggests that Regev's algorithm is still far from fully optimized.
• Abstract（参考訳）: リーゼフの因数分解アルゴリズムの大きな現実的な障害は、その空間使用量が大きいことである。 特に、このアルゴリズムは、すべてを同時に保存するのではなく、位相推定で制御量子ビットをストリームする「量子リサイクル」と互換性がないと考えられていた。 このストリーミング問題の解決方法を示します。 我々は、フィボナッチのアキュミュレータを用いて、キュービット数を$O(n^{1.5}) から $111.32n$ に減らしたラガバンとヴァイクンタナサンの構築の上に構築する。 重要な改善が2つあります。 まず、重畳マスキングを用いて、不要な情報がアキュムレータに入るのを防ぎ、計算不要な情報を除去する。 第二に、2の力ではなく、単位演算のフィボナッチ力を用いて位相推定を行う方法を示す。 これにより、ラガヴァンとヴァイクンタナンの建設に必要な様々なエンコード変換が回避される。 これらの改良の後、位相推定キュービットは回路内で1回だけ使用され、ストリーム化が可能である。 我々の改良は、Regevの分解アルゴリズムの空間使用量を$n+M(n)+O(\sqrt{n})$に減らした。 例えば、Luo et al (2026) の in-place multiplier を用いて、Regev のアルゴリズムは 4n+O(\sqrt{n})$ qubits を用いて$n$-bit 整数を分解できる。 我々の構成はいまだにショアのアルゴリズムの先導実装に十分な$n/2+εn$ qubitsには達していないが、これはレゼフのアルゴリズムの現在までの最低空間のインスタンス化であり、レゼフのアルゴリズムがまだ完全に最適化されていないことを示唆している。

関連論文リスト

• Arbitrary state creation via controlled measurement [49.494595696663524]
  このアルゴリズムは任意の$n$-qubit純量子重ね合わせ状態を生成し、精度は$m$-decimalsである。 このアルゴリズムは、1キュービット回転、アダマール変換、マルチキュービット制御によるC-NOT演算を使用する。
  論文  参考訳（メタデータ） (2025-04-13T07:23:50Z)
• 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)
• Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
  我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。 本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T14:37:21Z)
• 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)
• Gaussian Process Bandit Optimization with Few Batches [49.896920704012395]
  有限腕バンディットアルゴリズムにインスパイアされたバッチアルゴリズムを導入する。 O(log T)$ batches in time horizon $T$.sqrtTgamma_T)$ using $O(log T)$ batches in time horizon。 さらに,アルゴリズムの修正版を提案し,バッチ数によって後悔がどう影響するかを特徴付ける。
  論文  参考訳（メタデータ） (2021-10-15T00:54:04Z)
• Online Sub-Sampling for Reinforcement Learning with General Function Approximation [111.01990889581243]
  本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。 複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。 少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
  論文  参考訳（メタデータ） (2021-06-14T07:36:25Z)

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

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