論文の概要: Space-Optimized and Experimental Implementations of Regev's Quantum Factoring Algorithm

• arxiv url: http://arxiv.org/abs/2511.18198v1
• Date: Sat, 22 Nov 2025 21:57:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-25 18:34:24.6875
• Title: Space-Optimized and Experimental Implementations of Regev's Quantum Factoring Algorithm
• Title（参考訳）: Regevの量子ファクタリングアルゴリズムの空間最適化と実験的実装
• Authors: Wentao Yang, Bao Yan, Muxi Zheng, Quanfeng Lu, Shijie Wei, Gui-Lu Long,
• Abstract要約: 整数分解問題(IFP)はRSAのセキュリティを支えるが、ショアのアルゴリズムによって量子コンピュータ上で効率的に解ける。 本稿では、Regevアルゴリズムの空間複雑性を著しく低減する中間計算によるクォービット再利用法を提案する。
• 参考スコア（独自算出の注目度）: 4.0106855695925585
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The integer factorization problem (IFP) underpins the security of RSA, yet becomes efficiently solvable on a quantum computer through Shor's algorithm. Regev's recent high-dimensional variant reduces the circuit size through lattice-based post-processing, but introduces substantial space overhead and lacks practical implementations. Here, we propose a qubit reuse method by intermediate-uncomputation that significantly reduces the space complexity of Regev's algorithm, inspired by reversible computing. Our basic strategy lowers the cost from \( O(n^{3/2}) \) to \( O(n^{5/4}) \), and refined strategies achieve \( O(n \log n) \)which is a space lower bound within this model. Simulations demonstrate the resulting time-space trade-offs and resource scaling. Moreover, we construct and compile quantum circuits that factor \( N = 35 \), verifying the effectiveness of our method through noisy simulations. A more simplified experimental circuit for Regev's algorithm is executed on a superconducting quantum computer, with lattice-based post-processing successfully retrieving the factors. These results advance the practical feasibility of Regev-style quantum factoring and provide guidance for future theoretical and experimental developments.
• Abstract（参考訳）: 整数分解問題(IFP)はRSAのセキュリティを支えるが、ショアのアルゴリズムによって量子コンピュータ上で効率的に解ける。 Regevの最近の高次元変種は格子ベースの後処理によって回路サイズを小さくするが、空間オーバーヘッドが大きくなり、実用的な実装が欠如している。 本稿では、Regevのアルゴリズムの空間的複雑さを著しく低減し、可逆計算にインスパイアされた、中間計算による量子ビット再利用法を提案する。 我々の基本的な戦略は、コストを \(O(n^{3/2}) \) から \(O(n^{5/4}) \) に下げ、洗練された戦略は、このモデル内の空間の下限である \(O(n \log n) \) を達成する。 シミュレーションは、結果として生じる時間空間のトレードオフとリソースのスケーリングを示しています。 さらに,本手法の有効性をノイズシミュレーションにより検証し,その妥当性を検証した。 より単純化されたRegevのアルゴリズムの実験回路は超伝導量子コンピュータ上で実行され、格子ベースの後処理がそれらの因子の検索に成功している。 これらの結果は、Regevスタイルの量子ファクタリングの実現可能性を促進し、将来の理論的および実験的発展のためのガイダンスを提供する。

関連論文リスト

• Fast Expectation Value Calculation Speedup of Quantum Approximate Optimization Algorithm: HoLCUs QAOA [55.2480439325792]
  本稿では,LCU演算子の線形結合として表現できる演算子の期待値を計算するための新しい手法を提案する。 この方法は任意の量子アルゴリズムに対して一般的であり、変分量子アルゴリズムの加速に特に関心がある。
  論文  参考訳（メタデータ） (2025-03-03T17:15:23Z)
• Implementation and Analysis of Regev's Quantum Factorization Algorithm [0.2874893537471256]
  本稿では,合成数を分解するRegevのアルゴリズムの実装について述べる。 Regevの理論的優位性にもかかわらず、我々の実装は小さな整数因数分解のためのShorのアルゴリズムよりも長い実行時間を示した。
  論文  参考訳（メタデータ） (2025-02-13T21:02:15Z)
• Quantum Circuit Optimization with AlphaTensor [47.9303833600197]
  我々は,所定の回路を実装するために必要なTゲート数を最小化する手法であるAlphaTensor-Quantumを開発した。 Tカウント最適化の既存の方法とは異なり、AlphaTensor-Quantumは量子計算に関するドメイン固有の知識を取り入れ、ガジェットを活用することができる。 注目すべきは、有限体における乗法であるカラツバの手法に似た効率的なアルゴリズムを発見することである。
  論文  参考訳（メタデータ） (2024-02-22T09:20:54Z)
• Forward and Backward Constrained Bisimulations for Quantum Circuits using Decision Diagrams [3.788308836856851]
  我々は,古典コンピュータ上での量子回路のシミュレーションを効率的に行う手法を開発した。 特に,制約バイシミュレーションにより,決定図に基づく量子回路シミュレーションを桁違いに高速化できることを示す。
  論文  参考訳（メタデータ） (2023-08-18T12:40:47Z)
• Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
  テンソルネットワーク(TN)アルゴリズムは、パラメタライズド量子回路(PQC)にマッピングできる 本稿では,現実的な量子回路を用いてTN状態を近似する新しいプロトコルを提案する。 その結果、量子回路の逐次的な成長と最適化を含む1つの特定のプロトコルが、他の全ての手法より優れていることが明らかとなった。
  論文  参考訳（メタデータ） (2022-09-01T17:08:41Z)
• Variational Quantum Optimization with Multi-Basis Encodings [62.72309460291971]
  マルチバスグラフ複雑性と非線形活性化関数の2つの革新の恩恵を受ける新しい変分量子アルゴリズムを導入する。 その結果,最適化性能が向上し,有効景観が2つ向上し,測定の進歩が減少した。
  論文  参考訳（メタデータ） (2021-06-24T20:16:02Z)
• Investigating the Scalability and Biological Plausibility of the Activation Relaxation Algorithm [62.997667081978825]
  アクティベーション・リラクシエーション(AR)アルゴリズムは、誤りアルゴリズムのバックプロパゲーションを近似するためのシンプルでロバストなアプローチを提供する。 このアルゴリズムは、学習可能な後方重みセットを導入することにより、さらに単純化され、生物学的に検証可能であることを示す。 また、元のARアルゴリズム(凍結フィードフォワードパス)の別の生物学的に信じられない仮定が、パフォーマンスを損なうことなく緩和できるかどうかについても検討する。
  論文  参考訳（メタデータ） (2020-10-13T08:02:38Z)
• ACSS-q: Algorithmic complexity for short strings via quantum accelerated approach [1.4873907857806357]
  符号化定理法を用いて,アルゴリズムの複雑性を推定する量子回路を提案する。 ユースケースとして,アルゴリズムの複雑さに基づくタンパク質-タンパク質相互作用の応用フレームワークを提案する。
  論文  参考訳（メタデータ） (2020-09-18T14:41:41Z)
• Activation Relaxation: A Local Dynamical Approximation to Backpropagation in the Brain [62.997667081978825]
  活性化緩和(AR)は、バックプロパゲーション勾配を力学系の平衡点として構成することで動機付けられる。 我々のアルゴリズムは、正しいバックプロパゲーション勾配に迅速かつ堅牢に収束し、単一のタイプの計算単位しか必要とせず、任意の計算グラフで操作できる。
  論文  参考訳（メタデータ） (2020-09-11T11:56:34Z)

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

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