論文の概要: The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem

• arxiv url: http://arxiv.org/abs/2609.35656v1
• Date: Mon, 28 Sep 2026 17:21:41 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-01 19:52:38.097304
• Title: The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem
• Title（参考訳）: オラクルアクセスのパワー:アーベル状態隠れ部分群問題の最適サンプルとクエリ複雑性
• Abstract要約: 本研究では、未知の量子状態の対称性を特定することを目的とする状態隠蔽部分群問題(State hidden subgroup problem, StateHSP)について検討する。 我々は、$O(log(|G/H|)/sqrt)$forward and inverse query を用いて時間効率の量子アルゴリズムを与え、一致する $(log(|G/H|)/sqrt)$ lower bound を証明する。 応用として、安定化群を学習し、絡み合いを突き止め、隠れた翻訳対称性を同定するための高速なアルゴリズムを得る。
• 参考スコア（独自算出の注目度）: 18.167418729752068
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In the quest to identify further quantum algorithms exhibiting superpolynomial speed-ups, a recurring theme is that the complexity of a problem is largely shaped by the input access model. Here, we study this phenomenon for the state hidden subgroup problem (StateHSP), a quantum generalization of the hidden subgroup problem in which the goal is to identify the symmetries of an unknown quantum state. For finite abelian groups, existing Fourier-sampling algorithms use $O(\log(|G|)/ε)$ copies of the state, but whether this scaling is optimal has remained open. We settle the complexity of the abelian StateHSP in both the previously studied sample model and a new query model, which is a stronger and operationally natural generalization that provides access to the state-preparation unitary and its inverse. In the query model, we give a time-efficient quantum algorithm using $O(\log(|G/H|)/\sqrtε)$ forward and inverse queries, and prove a matching $Ω(\log(|G/H|)/\sqrtε)$ lower bound which holds even in the stronger conjugate-query and controlled-query settings. By contrast, we show that in the sample model, $Θ(\log(|G/H|)/ε)$ copies are both sufficient and information-theoretically necessary, even if one allows for arbitrary collective measurements. Thus, the quadratic improvement in $ε$ genuinely arises from coherent access to the preparation circuit. As applications, we obtain faster algorithms for learning stabilizer groups, locating unentanglement, and identifying hidden translation symmetries.
• Abstract（参考訳）: 超ポリノミカルなスピードアップを示すさらなる量子アルゴリズムの探索において、問題の複雑さは入力アクセスモデルによって大きく形作られる。 本稿では、この現象を、未知の量子状態の対称性を特定することを目的とした隠蔽部分群問題の量子一般化である状態隠蔽部分群問題(StateHSP)について研究する。 有限アーベル群に対しては、既存のフーリエサンプリングアルゴリズムは状態のコピーを$O(\log(|G|)/ε)$使うが、このスケーリングが最適かどうかはまだ未定である。 我々は,前述したサンプルモデルと新しいクエリモデルの両方において,アーベル状態HSPの複雑さを解決した。 問合せモデルでは、$O(\log(|G/H|)/\sqrtε)$forward and inverse query を用いて時間効率の量子アルゴリズムを与え、より強い共役クエリや制御クエリの設定でも保持できる $Ω(\log(|G/H|)/\sqrtε)$ lower bound を証明する。 対照的に、サンプルモデルでは、任意の集合的測定を許すとしても、$(\log(|G/H|)/ε)$コピーは十分かつ情報理論的に必要である。 したがって、$ε$の二次的な改善は、実際に準備回路へのコヒーレントアクセスによって生じる。 応用として、安定化群を学習し、絡み合いを突き止め、隠れた翻訳対称性を同定するための高速なアルゴリズムを得る。

関連論文リスト

• Towards Optimal Quantum Estimators for State Frame Potential [12.326210204717336]
  本稿では, 3 つのより弱いアクセスモデルの下で, 次数 $t$ の状態フレームポテンシャルを付加誤差 $varepsilon$ に推定する問題について検討する。 クエリモデルでは、$widetilde(sqrtt/varepsilon)$のほぼ最適クエリ複雑性を確立します。 一般的なサンプルモデルでは、最適なサンプル複雑性を$(t/varepsilon2)$とする。
  論文  参考訳（メタデータ） (2026-08-25T15:29:24Z)
• Optimal quantum simulation of linear non-unitary dynamics [0.31439717339537293]
  有界時間依存演算子$-A$によって生成される時間進化をシミュレートする量子アルゴリズムを提案する。 本稿では,最近のLinear-Combination-of-Hamiltonian-Simulation (LCHS)フレームワークを一般化する。
  論文  参考訳（メタデータ） (2025-08-26T17:58:27Z)
• Quantum Complexity for Discrete Logarithms and Related Problems [7.077306859247421]
  我々は、群理論問題に対する量子計算の一般モデルを構築し、これを量子ジェネリックグループモデルと呼ぶ。 このモデルでは、量子複雑性の低い境界と、DLのほぼ一致するアルゴリズムと関連する問題を示す。 Shorのアルゴリズムのバリエーションは、量子群演算の数を減らすために古典的な計算を利用することができる。
  論文  参考訳（メタデータ） (2023-07-06T15:32:50Z)
• Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model [85.51611950757643]
  IAC (Instance-Adaptive Clustering, インスタンス適応クラスタリング) を提案する。 IACは$ MathcalO(n, textpolylog(n) $の計算複雑性を維持しており、大規模問題に対してスケーラブルで実用的なものである。
  論文  参考訳（メタデータ） (2023-06-18T08:46:06Z)
• Learning Hidden Markov Models Using Conditional Samples [72.20944611510198]
  本稿では,隠れマルコフモデル(HMM)の学習における計算複雑性について述べる。 本稿では,HMMの条件分布からサンプルを問合せする対話型アクセスモデルを提案する。 具体的には、正確な条件付き確率に対するクエリアクセスが可能な設定において、HMMを学習するための効率的なアルゴリズムを得る。
  論文  参考訳（メタデータ） (2023-02-28T16:53:41Z)
• Complexity-Theoretic Limitations on Quantum Algorithms for Topological Data Analysis [59.545114016224254]
  トポロジカルデータ解析のための量子アルゴリズムは、古典的手法よりも指数関数的に有利である。 我々は、量子コンピュータにおいても、TDA(ベッチ数の推定)の中心的なタスクが難解であることを示します。 我々は、入力データが単純さの仕様として与えられると、指数的量子優位性を取り戻すことができると論じる。
  論文  参考訳（メタデータ） (2022-09-28T17:53:25Z)
• Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs [45.87981728307819]
  異種空間に居住する関連するデータセットを比較して整列する能力は、機械学習においてますます重要な役割を担っている。 グロモフ・ワッサーシュタイン (Gromov-Wasserstein, GW) 形式主義はこの問題に対処するのに役立つ。
  論文  参考訳（メタデータ） (2021-06-02T12:50:56Z)

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

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