論文の概要: Quantum state isomorphism problems for groups

• arxiv url: http://arxiv.org/abs/2605.12615v1
• Date: Tue, 12 May 2026 18:05:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-14 23:30:27.604819
• Title: Quantum state isomorphism problems for groups
• Title（参考訳）: 群に対する量子状態同型問題
• Authors: Alexandru Gheorghiu, Dale Jacobs, Saeed Mehraban, Arsalan Motamedi,
• Abstract要約: 群作用下での量子状態同型問題の計算複雑性について検討する。 純粋状態バージョンの場合、問題はすべての非自明な群に対して BQP-hard であることが示される。 混合状態バージョンの場合、非自明で有限で効率的な表現可能な群に対して、問題はQSZK完全である。
• 参考スコア（独自算出の注目度）: 41.49556721904551
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the computational complexity of quantum state isomorphism problems under group actions: given two quantum circuits that prepare pure or mixed states, decide whether the two states are related by a group action. This can be seen as a quantum state version of the Hidden Shift Problem, in much the same way that the State Hidden Subgroup Problem is a quantum version of the ordinary Hidden Subgroup Problem. We prove several results for this computational problem: - For the pure-state version, we show that the problem is BQP-hard for all nontrivial groups, and contained in QCMA $\cap$ QCSZK. We further obtain refined results for specific groups of interest: for abelian groups we show that the problem reduces to the state hidden subgroup problem over the generalized dihedral group; for the Clifford group, the problem is at least as hard as Graph Isomorphism under polynomial-time reductions; for the Pauli group it is BQP-complete. - For the mixed-state version, for nontrivial, finite and efficiently representable groups, the problem is QSZK-complete. - We also study a variant of this problem over an infinite group, in particular, the bosonic linear optical unitaries. We show that in the setting where the classical description of the quantum state is given in a suitable wave function representation known as the stellar representation, the problem is at least as hard as Graph Isomorphism, and is contained in NP $\cap$ SZK. Prior to our work, state isomorphism problems had only been studied for the symmetric group [LG17]. As a consequence of our results, we resolve an open question posed in [HEC25] about the existence of a quantum algorithm for the abelian state hidden subgroup problem on mixed states. We show that this problem is QSZK-hard in the worst case, thereby ruling out an efficient quantum algorithm unless QSZK = BQP.
• Abstract（参考訳）: 我々は、群作用下での量子状態同型問題の計算複雑性について研究し、純状態または混合状態を作成する2つの量子回路が与えられたとき、その2つの状態が群作用によって関連しているかどうかを決定する。 これは、状態隠れ部分群問題(State Hidden Subgroup Problem)が通常の隠れ部分群問題(Hidden Subgroup Problem)の量子バージョンであるのと同じように、隠れシフト問題(Hidden Shift Problem)の量子状態バージョンと見なすことができる。 純粋状態版では、問題はすべての非自明な群に対して BQP-hard であり、QCMA $\cap$ QCSZK に含まれることを示す。 アーベル群に対しては、問題は一般化二面体群上の状態隠れ部分群問題に還元されることを示し、クリフォード群に対しては、多項式時間還元の下でグラフ同型(英語版)(Graph Isomorphism)と同じくらい難しいことを示し、パウリ群ではBQP完全である。 -混合状態バージョンの場合、非自明で有限かつ効率的な表現可能な群に対して、問題はQSZK完全である。 また、この問題の変種を無限群、特にボソニック線型光学ユニタリ上で研究する。 恒星表現として知られる適切な波動関数表現において量子状態の古典的記述が与えられるような場合、問題はグラフ同型と同様に困難であり、NP$\cap$SZKに含まれる。 我々の研究以前には、状態同型問題は対称群 [LG17] に対してのみ研究されていた。 その結果、混合状態上のアーベル状態隠蔽部分群問題に対する量子アルゴリズムの存在について、[HEC25]で提起されたオープンな疑問を解決した。 その結果、QSZK = BQPでない限り、効率的な量子アルゴリズムを除外できることがわかった。

関連論文リスト

• Two Problems on Quantum Computing in Finite Abelian Groups [0.0]
  有限アーベル群の文脈では、2つの問題が量子コンピューティング技術を用いて提示され、解決される。 1つはよく知られた隠れた部分群問題であり、元々はサイモンが解いた。 2つ目は、著者が最初に導入したフルバランス画像問題である。
  論文  参考訳（メタデータ） (2026-04-01T14:07:38Z)
• Average-case quantum complexity from glassiness [45.57609001239456]
  グラスネス(Glassiness)は、物理学において、不安定な自由エネルギーの風景を特徴とする現象であり、安定な古典的アルゴリズムの難しさを意味する。 レプリカ対称性の破れに基づく標準的な量子ガラス性の概念は、ギブスサンプリングのための安定な量子アルゴリズムを妨げていることを証明している。
  論文  参考訳（メタデータ） (2025-10-09T17:37:33Z)
• Topological control of quantum speed limits [55.2480439325792]
  量子状態が完全に分散していないとしても、この状態のQFIは運動量分解される。 我々は、(分散のない)位相位相相において$sqrt|C|$としてスケールする量子速度制限上の境界を見つける。
  論文  参考訳（メタデータ） (2025-07-21T18:00:07Z)
• Group Order is in QCMA [0.5188841610098435]
  ブラックボックスとして与えられる有限群の順序を検証することは、複雑性クラス QCMA にあることを示す。 我々の手法は、ブラックボックス群における群同型のような他の多くの群理論問題の複雑さに関する量子上界も改善する。
  論文  参考訳（メタデータ） (2025-04-07T22:54:09Z)
• Quantum channels, complex Stiefel manifolds, and optimization [45.9982965995401]
  我々は、量子チャネルの位相空間と複素スティーフェル多様体の商の間の連続性関係を確立する。 確立された関係は、様々な量子最適化問題に適用できる。
  論文  参考訳（メタデータ） (2024-08-19T09:15:54Z)
• 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)
• Clique Homology is QMA1-hard [0.0]
  simplicial complex のホモロジー群を決定する決定問題は QMA1-hard である。 これは、古典的と思われる問題は、実際には量子力学である可能性を示唆している。 本稿では、トポロジカルデータ解析における量子優位性の問題への潜在的な影響について論じる。
  論文  参考訳（メタデータ） (2022-09-23T18:14:16Z)
• The dihedral hidden subgroup problem [0.0]
  有限群に対する標準部分群量子アルゴリズムの観点から、二面体群に対する隠れた問題の例を示す。 二面体コセット問題と量子状態のクローンとの新たな接続について説明する。
  論文  参考訳（メタデータ） (2021-06-18T04:19:10Z)
• Verification of Group Non-membership by Shallow Quantum Circuits [6.611344035597144]
  群要素の群非メンバーシップ(GNM)を決定する問題は、$mathsfQMA$である。 本稿では,GNM問題を効率よく検証し,回路深さを$O(1)$に減らし,キュービット数を半減する手法を提案する。
  論文  参考訳（メタデータ） (2020-10-07T14:53:15Z)

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

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