論文の概要: Revisiting finite Abelian hidden subgroup problem and its distributed exact quantum algorithm

• arxiv url: http://arxiv.org/abs/2512.22959v1
• Date: Sun, 28 Dec 2025 15:00:50 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-30 22:37:30.299837
• Title: Revisiting finite Abelian hidden subgroup problem and its distributed exact quantum algorithm
• Title（参考訳）: 有限アベリア隠れ部分群問題の再検討とその分散完全量子アルゴリズム
• Authors: Ziyuan Dong, Xiang Fan, Tengxun Zhong, Daowen Qiu,
• Abstract要約: 我々は数学的な観点から有限アベリア隠れ部分群問題(AHSP)を再考する。 有限 AHSP に対して正確な量子アルゴリズムを提案するが、これは以前の正確なアルゴリズムよりも簡潔である。 本稿では,有限量子AHSPのための分散完全量子アルゴリズムを提案し,量子キューディットを少なくし,量子クエリの複雑性を低くし,量子通信を不要とした。
• 参考スコア（独自算出の注目度）: 4.250782756734906
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We revisit the finite Abelian hidden subgroup problem (AHSP) from a mathematical perspective and make the following contributions. First, by employing amplitude amplification, we present an exact quantum algorithm for the finite AHSP, our algorithm is more concise than the previous exact algorithm and applies to any finite Abelian group. Second, utilizing the Chinese Remainder Theorem, we propose a distributed exact quantum algorithm for finite AHSP, which requires fewer qudits, lower quantum query complexity, and no quantum communication. We further show that our distributed approach can be extended to certain classes of non-Abelian groups. Finally, we develop a parallel exact classical algorithm for finite AHSP with reduced query complexity; even without parallel execution, the total number of queries across all nodes does not exceed that of the original centralized algorithm under mild conditions.
• Abstract（参考訳）: 我々は数学的な観点から有限アベリア隠れ部分群問題(AHSP)を再検討し、以下の貢献を行う。 まず、振幅増幅を用いて、有限 AHSP に対して正確な量子アルゴリズムを提示することにより、我々のアルゴリズムは以前の正確なアルゴリズムよりも簡潔になり、任意の有限アベリア群に適用できる。 第二に、中国語のRemainder Theoremを用いて、有限 AHSP に対する分散完全量子アルゴリズムを提案する。 さらに、我々の分散アプローチは非アベリア群のある種のクラスに拡張可能であることを示す。 並列実行がなくても、全てのノードにまたがるクエリの総数は、穏やかな条件下での元の集中型アルゴリズムの総数を超えない。

関連論文リスト

• The hidden subgroup problem for infinite groups [0.0]
  HSP は有理数の加法群と非アーベル自由群の正規部分群に対して NP-ハードであることを示す。 HSPのShorKitevアルゴリズムを標準クエリコストで$mathbbZk$で一般化する。 したがって、任意の有限生成アーベル群の HSP もまた指数時間アルゴリズムを拡張している。
  論文  参考訳（メタデータ） (2025-07-24T15:16:20Z)
• An Initialization-free Quantum Algorithm for General Abelian Hidden Subgroup Problem [0.0]
  我々のアルゴリズムは、任意の未知混合状態を補助レジスタとして適用することができる。 また,計算終了後に補助レジスタの状態を元の形式に復元する。
  論文  参考訳（メタデータ） (2025-07-24T04:50:28Z)
• Quantum Complexity for Discrete Logarithms and Related Problems [7.077306859247421]
  我々は、群理論問題に対する量子計算の一般モデルを構築し、これを量子ジェネリックグループモデルと呼ぶ。 このモデルでは、量子複雑性の低い境界と、DLのほぼ一致するアルゴリズムと関連する問題を示す。 Shorのアルゴリズムのバリエーションは、量子群演算の数を減らすために古典的な計算を利用することができる。
  論文  参考訳（メタデータ） (2023-07-06T15:32:50Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  最適なヘッセン依存型サンプルの複雑さを, 初めて厳密に評価した。 ヘシアン非依存のアルゴリズムは、すべてのヘシアンインスタンスに対して最適なサンプル複雑さを普遍的に達成する。 本アルゴリズムにより得られたサンプルの最適複雑さは,重み付き雑音分布においても有効である。
  論文  参考訳（メタデータ） (2023-06-21T17:03:22Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Polynomial-time quantum algorithm for solving the hidden subgroup problem [0.0]
  隠れ部分群問題(HSP)は量子計算における最も重要な問題の一つである。 我々は,HSPを,マルチステップ量子アルゴリズムによる量子アルゴリズムを用いて効率よく解けるネスト型構造化探索問題に還元できることを見出した。
  論文  参考訳（メタデータ） (2022-04-07T08:50:50Z)
• First-Order Algorithms for Nonlinear Generalized Nash Equilibrium Problems [88.58409977434269]
  非線形一般化ナッシュ均衡問題(NGNEP)における平衡計算の問題を考える。 我々の貢献は、2次ペナルティ法と拡張ラグランジアン法に基づく2つの単純な一階アルゴリズムフレームワークを提供することである。 これらのアルゴリズムに対する漸近的理論的保証を提供する。
  論文  参考訳（メタデータ） (2022-04-07T00:11:05Z)
• An efficient quantum algorithm for lattice problems achieving subexponential approximation factor [2.3351527694849574]
  整数格子のクラスに対する指数近似係数を用いて,境界距離復号法(BDD)問題を解く量子アルゴリズムを提案する。 量子アルゴリズムの実行時間は、近似因子の1つの範囲と、第2の範囲の近似因子のサブ指数時間である。 この見解は、有限アーベル群の観点からクリーンな量子アルゴリズムを定め、格子理論から相対的にほとんど使用せず、次元以外のパラメータの格子問題に対する近似アルゴリズムを探求することを提案している。
  論文  参考訳（メタデータ） (2022-01-31T18:58:33Z)
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization [76.57464214864756]
  この研究は、未知の報酬関数が非可逆であるようなバンドイット問題の大群を考察する。 我々のアルゴリズムは、非常に一般化されたゼロ階最適化のパラダイムに基づいている。 標準的な楽観的アルゴリズムは次元因子によって準最適であることを示す。
  論文  参考訳（メタデータ） (2021-07-09T16:04:24Z)

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

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