Fugu-MT 論文翻訳(概要): Group Order is in QCMA

論文の概要: Group Order is in QCMA

arxiv url: http://arxiv.org/abs/2504.05547v1
Date: Mon, 07 Apr 2025 22:54:09 GMT
ステータス: 翻訳完了
システム内更新日: 2025-04-17 03:23:35.880813
Title: Group Order is in QCMA
Title（参考訳）: グループオーダーはQCMAにあります
Authors: François Le Gall, Harumichi Nishimura, Dhara Thakkar,
Abstract要約: ブラックボックスとして与えられる有限群の順序を検証することは、複雑性クラス QCMA にあることを示す。我々の手法は、ブラックボックス群における群同型のような他の多くの群理論問題の複雑さに関する量子上界も改善する。
参考スコア（独自算出の注目度）: 0.5188841610098435
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In this work, we show that verifying the order of a finite group given as a black-box is in the complexity class QCMA. This solves an open problem asked by Watrous in 2000 in his seminal paper on quantum proofs and directly implies that the Group Non-Membership problem is also in the class QCMA, which further proves a conjecture proposed by Aaronson and Kuperberg in 2006. Our techniques also give improved quantum upper bounds on the complexity of many other group-theoretical problems, such as group isomorphism in black-box groups.
Abstract（参考訳）: 本研究では、ブラックボックスとして与えられる有限群の順序を検証することは、複雑性クラス QCMA に含まれることを示す。これは2000年にWatrousが量子証明に関するセミナー論文で求めたオープンな問題を解き、グループ非メンバーシップ問題はクラス QCMA にも含まれており、2006年にアーロンソンとクパーバーグが提唱した予想をさらに証明している。我々の手法は、ブラックボックス群における群同型のような他の多くの群理論問題の複雑さに関する量子上界も改善する。

関連論文リスト

A quantum algorithm for Khovanov homology [42.6618666851542]
ホバノフホモロジー(Khovanov homology)は、ジョーンズ位相不変量を分類し、カンノットを認識する結び目であり、4D$超対称ヤン・ミルズ理論において観測可能であると推測されている。リッチな数学的および物理的重要性にもかかわらず、ホバノフホモロジーの計算複雑性はほとんど不明である。
論文参考訳（メタデータ） (2025-01-21T18:54:59Z)
A QUBO Formulation for the Generalized LinkedIn Queens and Takuzu/Tango Game [49.1574468325115]
本稿では、LinkedIn Queens ゲームの一連の一般化を解決するために設計された QUBO の定式化について述べる。この定式化は、テンツ・アンド・ツリー (Tents & Trees) のような、問題のいくつかの特定のケースに適応する。また,カラーチェスピース問題 (Coloured Chess Piece Problem) とマックスチェスピース問題 (Max Chess Pieces Problem) という2種類の新しい問題を,対応するQUBOの定式化とともに提示する。
論文参考訳（メタデータ） (2024-10-08T23:54:54Z)
Constructive quantum mechanics based on finite groups [0.0]
一般ユニタリ群を有限群で置き換える量子力学の定式化を考える。この定式化の文脈で生じる問題を解決するために、計算機代数と計算群理論法を用いる。
論文参考訳（メタデータ） (2024-09-26T14:04:37Z)
Contracting Self-similar Groups in Group-Based Cryptography [0.0]
我々は,同時共役探索問題(SCSP)に基づく暗号スキームのプラットフォームとして,自己相似契約群を提案する。これらの群のクラスは、非線型であることが知られているグリゴルチャック群のような特別な例を含む。グループベースの暗号においてこれらのグループを使用することの利点と欠点について議論し、SCSPに対する長さベースの攻撃の変種を計算解析する。
論文参考訳（メタデータ） (2024-08-26T15:30:11Z)
Quantum channels, complex Stiefel manifolds, and optimization [45.9982965995401]
我々は、量子チャネルの位相空間と複素スティーフェル多様体の商の間の連続性関係を確立する。確立された関係は、様々な量子最適化問題に適用できる。
論文参考訳（メタデータ） (2024-08-19T09:15:54Z)
A perturbative approach to the solution of the Thirring quantum cellular automaton [42.205102271729665]
Thirring Quantum Cellular Automaton (QCA) は、ディラックセルオートマトンの一段階に従って進化する局所フェルミオンモードの離散時間ダイナミクスと、最も一般的なオンサイト数保存相互作用を記述し、量子場理論におけるTirrringモデルのQCAとして機能する。
論文参考訳（メタデータ） (2024-06-28T13:44:10Z)
Clique Homology is QMA1-hard [0.0]
simplicial complex のホモロジー群を決定する決定問題は QMA1-hard である。これは、古典的と思われる問題は、実際には量子力学である可能性を示唆している。本稿では、トポロジカルデータ解析における量子優位性の問題への潜在的な影響について論じる。
論文参考訳（メタデータ） (2022-09-23T18:14:16Z)
Max-Min Grouped Bandits [48.62520520818357]
マルチアームバンディット問題であるmax-min grouped banditsを導入する。ゴールは、最悪の腕が最高の平均報酬を持つグループを見つけることです。この問題はレコメンデーションシステムのようなアプリケーションには関心がある。
論文参考訳（メタデータ） (2021-11-17T01:59:15Z)
On the Universality and Membership problems for quantum gates [0.0]
有限個の量子ゲートからなるゲート集合に対する普遍性と会員問題について検討する。我々のアプローチはコンパクトリー群論の技法に依存している。
論文参考訳（メタデータ） (2021-10-08T15:53:09Z)
The dihedral hidden subgroup problem [0.0]
有限群に対する標準部分群量子アルゴリズムの観点から、二面体群に対する隠れた問題の例を示す。二面体コセット問題と量子状態のクローンとの新たな接続について説明する。
論文参考訳（メタデータ） (2021-06-18T04:19:10Z)
Constraints on Maximal Entanglement Under Groups of Permutations [73.21730086814223]
絡み合いの集合は本質的に等しく、群作用の下で同じ軌道上にある。物理対称性群の正規化子および正規化部分群を利用することにより、これらの絡み合いの最大値に対する新しい一般化された関係を導入する。
論文参考訳（メタデータ） (2020-11-30T02:21:22Z)
A Unified Approach to Synchronization Problems over Subgroups of the Orthogonal Group [29.714239628405515]
群が閉部分群である同期問題のクラスを考える。このような問題を解くための統一的なアプローチを提案する。私たちのアプローチは既存のアプローチよりも優れています。
論文参考訳（メタデータ） (2020-09-16T07:25:50Z)
Continuous LWE [32.345218864470446]
CLWEと呼ばれるLearning with Errors(LWE)問題の連続的な類似点を紹介する。最短ケース格子問題の量子化をCLWEに与え、CLWEがLWEと同じような硬さの保証を享受していることを示す。
論文参考訳（メタデータ） (2020-05-19T17:16:12Z)

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