論文の概要: The Hidden Subgroup Problem for Universal Algebras

• arxiv url: http://arxiv.org/abs/2001.11298v2
• Date: Fri, 1 May 2020 20:14:21 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-05 04:54:36.763510
• Title: The Hidden Subgroup Problem for Universal Algebras
• Title（参考訳）: 普遍代数に対する隠れ部分群問題
• Authors: Matthew Moore, Taylor Walenczyk
• Abstract要約: 隠れ部分群問題(英: Hidden Subgroup Problem、HSP)は、特殊の場合の整数分解、離散離散問題、グラフ同型、最短ベクトル問題を含む計算問題である。
• 参考スコア（独自算出の注目度）: 0.7832189413179361
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Hidden Subgroup Problem (HSP) is a computational problem which includes as special cases integer factorization, the discrete logarithm problem, graph isomorphism, and the shortest vector problem. The celebrated polynomial-time quantum algorithms for factorization and the discrete logarithm are restricted versions of a generic polynomial-time quantum solution to the HSP for abelian groups, but despite focused research no full solution has yet been found. We propose a generalization of the HSP to include arbitrary algebraic structures and analyze this new problem on powers of 2-element algebras. We prove a complete classification of every such power as quantum tractable (i.e. polynomial-time), classically tractable, quantum intractable, and classically intractable. In particular, we identify a class of algebras for which the generalized HSP exhibits super-polynomial speedup on a quantum computer compared to a classical one.
• Abstract（参考訳）: 隠れ部分群問題(英: Hidden Subgroup Problem、HSP)は、特殊の場合の整数分解、離散対数問題、グラフ同型、最短ベクトル問題を含む計算問題である。 分解と離散対数に対する有名な多項式時間量子アルゴリズムは、アーベル群に対するhspに対する多項式時間量子解の制限バージョンであるが、集中した研究にもかかわらず、完全な解は見つかっていない。 我々は、任意の代数構造を含む HSP の一般化を提案し、この新たな問題を2要素代数のパワーで解析する。 量子トラクタブル(多項式時間)、古典的トラクタブル、量子的トラクタブル、古典的トラクタブルといったすべてのパワーの完全な分類を証明する。 特に、一般化されたHSPが量子コンピュータ上の超多項式スピードアップを示す代数のクラスを古典的なものと比較する。

関連論文リスト

• Bosonic Quantum Computational Complexity [0.0]
  私たちはそのような研究計画の基礎をつくった。 本稿では,BQPのボゾン一般化に基づく自然複雑性クラスと問題を紹介する。 ボソニックハミルトニアンのスペクトルの有界性を決定する問題はコ-NPハードであることを示す。
  論文  参考訳（メタデータ） (2024-10-05T19:43:41Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• On the quantum time complexity of divide and conquer [42.7410400783548]
  量子分割の時間的複雑さと古典的問題に対するアルゴリズムの克服について検討する。 これらの定理を、弦、整数、幾何学的対象を含む一連の問題に適用する。
  論文  参考訳（メタデータ） (2023-11-28T01:06:03Z)
• A hybrid quantum-classical algorithm for multichannel quantum scattering of atoms and molecules [62.997667081978825]
  原子と分子の衝突に対するシュリンガー方程式を解くためのハイブリッド量子古典アルゴリズムを提案する。 このアルゴリズムはコーン変分原理の$S$-matrixバージョンに基づいており、基本散乱$S$-matrixを計算する。 大規模多原子分子の衝突をシミュレートするために,アルゴリズムをどのようにスケールアップするかを示す。
  論文  参考訳（メタデータ） (2023-04-12T18:10:47Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  本稿では,部分関数に対する完全次数と近似量子クエリの指数関数的分離を実証する。 アルファベットのサイズについては、定値対分離の複雑さがある。
  論文  参考訳（メタデータ） (2023-01-22T22:08:28Z)
• Quantum Worst-Case to Average-Case Reductions for All Linear Problems [66.65497337069792]
  量子アルゴリズムにおける最悪のケースと平均ケースの削減を設計する問題について検討する。 量子アルゴリズムの明示的で効率的な変換は、入力のごく一部でのみ正し、全ての入力で正しくなる。
  論文  参考訳（メタデータ） (2022-12-06T22:01:49Z)
• Unitary property testing lower bounds by polynomials [0.15229257192293197]
  我々は、量子アルゴリズムにブラックボックスのユニタリへのクエリアクセスを与えるユニタリプロパティテストについて研究する。 これらの問題の複雑さを特徴づけるには、新しいアルゴリズム技術と低いバウンド法が必要である。 我々は、$mathsfQMA$と$mathsfQMA(2)$の間のオラクル分離に対するユニタリなプロパティテストベースのアプローチを示す。
  論文  参考訳（メタデータ） (2022-10-12T03:01:00Z)
• 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)
• An efficient quantum algorithm for lattice problems achieving subexponential approximation factor [2.3351527694849574]
  整数格子のクラスに対する指数近似係数を用いて,境界距離復号法(BDD)問題を解く量子アルゴリズムを提案する。 量子アルゴリズムの実行時間は、近似因子の1つの範囲と、第2の範囲の近似因子のサブ指数時間である。 この見解は、有限アーベル群の観点からクリーンな量子アルゴリズムを定め、格子理論から相対的にほとんど使用せず、次元以外のパラメータの格子問題に対する近似アルゴリズムを探求することを提案している。
  論文  参考訳（メタデータ） (2022-01-31T18:58:33Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  任意の$d$値論理関数を符号化する有限関数符号化(FFE)を導入する。 それらの構造的特性について検討する。
  論文  参考訳（メタデータ） (2020-12-01T13:53:23Z)

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

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