論文の概要: Improved Quantum Algorithms for Black-Box Abelian Group Decomposition
- arxiv url: http://arxiv.org/abs/2609.36480v2
- Date: Sun, 04 Oct 2026 20:04:38 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-07 04:43:28.4131
- Title: Improved Quantum Algorithms for Black-Box Abelian Group Decomposition
- Title（参考訳）: ブラックボックスアベリア群分解のための量子アルゴリズムの改良
- Abstract要約: 有限アベリアブラックボックス群を分解するための量子アルゴリズムを与える。
我々はRegevの因数分解アルゴリズムの量子サンプリングと古典的格子還元法に適応する。
- 参考スコア（独自算出の注目度）: 6.739725742809849
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Decomposing finite Abelian black-box groups into cyclic factors is a basic problem in quantum computation. We give a quantum algorithm for decomposing finite Abelian black-box groups by adapting the quantum sampling and classical lattice-reduction method of Regev's factoring algorithm. The algorithm computes an invariant-factor decomposition and corresponding cyclic generators with high probability. For a group G of order at most 2^n with unique encodings and reversible group-operation cost T_op = Omega(sqrt(n)), our algorithm uses O(sqrt(n)) quantum circuits, each with O~(n T_op) gates and executed at most O(n) times. For comparison, we consider the Cheung-Mosca algorithm, which decomposes the Sylow p-subgroups separately. We also consider the common-modulus implementation of the extended Cheung-Mosca algorithm. Our algorithm reduces the sum of the circuit gate counts from O~(n^2 T_op) to O~(n^(3/2) T_op). The total quantum time bound reduces from O~(n^3 T_op) to O~(n^(5/2) T_op), and the quantum space bound reduces from O(n^2) to O(n) qubits. The classical computation uses polynomially many bit operations and group-operation queries. These improvements rely on two technical ingredients. We prove that the integer relation lattices used in our algorithm admit, with high probability, integral bases whose vectors have Euclidean norm at most exp(O(sqrt(n))). We preserve the circuit-size advantage of Regev's algorithm for group decomposition by incorporating all O(n) sampled generators while keeping the lattice-reduction dimension at O(sqrt(n)).
- Abstract（参考訳）: 有限アベリアブラックボックス群を巡回因子に分解することは、量子計算の基本的な問題である。
本稿では、Regevの因数分解アルゴリズムの量子サンプリングと古典的格子還元法を適用することにより、有限アベリアブラックボックス群を分解する量子アルゴリズムを提案する。
アルゴリズムは不変要素分解と対応する巡回発生器を高い確率で計算する。
T_op = Omega(sqrt(n)) は O(sqrt(n)) 量子回路であり、O~(n T_op) ゲートを持つ。
比較のために、Sylow p-部分群を別々に分解するCheung-Moscaアルゴリズムを考える。
また、拡張されたCheung-Moscaアルゴリズムの共通モジュラー実装についても検討する。
本アルゴリズムは,回路ゲート数の和を O~(n^2 T_op) から O~(n^(3/2) T_op) に還元する。
全量子時間境界は O~(n^3 T_op) から O~(n^(5/2) T_op) に減少し、量子空間境界は O(n^2) から O(n) キュービットに減少する。
古典計算は多項式的に多くのビット演算とグループ演算クエリを使用する。
これらの改良は2つの技術要素に依存している。
アルゴリズムで用いられる整数関係格子は、高い確率で、ベクトルがユークリッドノルムを持つ積分基底が少なくともexp(O(sqrt(n)))であることを示す。
我々は、O(sqrt(n)) における格子誘引次元を維持しながら、すべての O(n) サンプルジェネレータを組み込むことで、グループ分解に対する Regev のアルゴリズムの回路サイズ優位性を保っている。
関連論文リスト
- The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem [18.167418729752068]
本研究では、未知の量子状態の対称性を特定することを目的とする状態隠蔽部分群問題(State hidden subgroup problem, StateHSP)について検討する。
我々は、$O(log(|G/H|)/sqrt)$forward and inverse query を用いて時間効率の量子アルゴリズムを与え、一致する $(log(|G/H|)/sqrt)$ lower bound を証明する。
応用として、安定化群を学習し、絡み合いを突き止め、隠れた翻訳対称性を同定するための高速なアルゴリズムを得る。
論文 参考訳（メタデータ） (2026-09-28T17:21:41Z) - Improved quantum circuits for division [42.76841620787673]
様々な整数分割アルゴリズムのための新しいフォールトトレラント量子回路を開発した。
回路は最大76.08%、68.35%のT数とCNOT数を実現している。
論文 参考訳（メタデータ） (2026-03-18T13:41:43Z) - Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
周期的な対角構造を持つスパース行列を符号化するための明示的な量子回路を提供する。
本手法の様々な応用は, 微分問題を解く文脈で論じる。
論文 参考訳（メタデータ） (2026-02-11T07:24:33Z) - Space-Efficient Quantum Error Reduction without log Factors [50.10645865330582]
本稿では,多数決のランダムウォーク解釈に類似したライン上の重み付けウォークとして理解可能な,新たに単純化された浄化器の構成を提案する。
我々の浄化器は、前者よりも指数関数的に空間の複雑さが良く、精製されるアルゴリズムの音質-完全性ギャップに四分法的に依存している。
論文 参考訳（メタデータ） (2025-02-13T12:04:39Z) - Do you know what q-means? [42.96240569413475]
古典的な$varepsilon$-$k$-meansアルゴリズムは、ロイドのアルゴリズムの1つの反復の近似バージョンを時間的複雑さで実行する。
また,時間的複雑さを考慮した$q$-means量子アルゴリズムも提案する。
論文 参考訳（メタデータ） (2023-08-18T17:52:12Z) - Quantum Complexity for Discrete Logarithms and Related Problems [7.077306859247421]
我々は、群理論問題に対する量子計算の一般モデルを構築し、これを量子ジェネリックグループモデルと呼ぶ。
このモデルでは、量子複雑性の低い境界と、DLのほぼ一致するアルゴリズムと関連する問題を示す。
Shorのアルゴリズムのバリエーションは、量子群演算の数を減らすために古典的な計算を利用することができる。
論文 参考訳（メタデータ） (2023-07-06T15:32:50Z) - Efficient application of the factorized form of the unitary
coupled-cluster ansatz for the variational quantum eigensolver algorithm by
using linear combination of unitaries [0.0]
変分量子固有解法は、短期量子コンピュータにとって最も有望なアルゴリズムの1つである。
強い相関電子を含む量子化学問題を解くことができる。
論文 参考訳（メタデータ） (2023-02-17T04:03:06Z) - An exact quantum hidden subgroup algorithm and applications to solvable
groups [2.5204420653245245]
隠れた部分群問題に対する時間正確な量子アルゴリズムを、Z_mkn$で示す。
また、位数が m と同じ(おそらく未知の)素因子を持つアーベル群と可解群の構造を計算するための応用も提示する。
論文 参考訳（メタデータ） (2022-02-08T18:22:35Z) - An efficient quantum algorithm for lattice problems achieving
subexponential approximation factor [2.3351527694849574]
整数格子のクラスに対する指数近似係数を用いて,境界距離復号法(BDD)問題を解く量子アルゴリズムを提案する。
量子アルゴリズムの実行時間は、近似因子の1つの範囲と、第2の範囲の近似因子のサブ指数時間である。
この見解は、有限アーベル群の観点からクリーンな量子アルゴリズムを定め、格子理論から相対的にほとんど使用せず、次元以外のパラメータの格子問題に対する近似アルゴリズムを探求することを提案している。
論文 参考訳（メタデータ） (2022-01-31T18:58:33Z) - Quantum algorithms for spectral sums [50.045011844765185]
正半定値行列(PSD)のスペクトル和を推定するための新しい量子アルゴリズムを提案する。
本稿では, スペクトルグラフ理論における3つの問題に対して, アルゴリズムと手法が適用可能であることを示す。
論文 参考訳（メタデータ） (2020-11-12T16:29:45Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。