論文の概要: One-Query Quantum Algorithms for the Index-$q$ Hidden Subgroup Problem
- arxiv url: http://arxiv.org/abs/2510.10538v1
- Date: Sun, 12 Oct 2025 10:42:50 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-10-14 18:06:29.997104
- Title: One-Query Quantum Algorithms for the Index-$q$ Hidden Subgroup Problem
- Title（参考訳）: 指数-$q$隠れ部分群問題に対する1クエリ量子アルゴリズム
- Authors: Amit Te'eni, Yaron Oz, Eliahu Cohen,
- Abstract要約: ベルンシュタイン・ヴァジラニ問題(Bernstein-Vazirani problem)は、隠れ部分群問題(HSP)の例である。
インデックス-$q$ HSP: 隠された部分群 $H le G$ がインデックス 1$ または $q$ を持つかどうかを判定し、可能であれば$H$ を識別する。
- 参考スコア（独自算出の注目度）: 1.4146420810689422
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The quantum Fourier transform (QFT) is central to many quantum algorithms, yet its necessity is not always well understood. We re-examine its role in canonical query problems. The Deutsch-Jozsa algorithm requires neither a QFT nor a domain group structure. In contrast, the Bernstein-Vazirani problem is an instance of the hidden subgroup problem (HSP), where the hidden subgroup has either index $1$ or $2$; and the Bernstein-Vazirani algorithm exploits this promise to solve the problem with a single query. Motivated by these insights, we introduce the index-$q$ HSP: determine whether a hidden subgroup $H \le G$ has index $1$ or $q$, and, when possible, identify $H$. We present a single-query algorithm that always distinguishes index $1$ from $q$, for any choice of abelian structure on the oracle's codomain. Moreover, with suitable pre- and post-oracle unitaries (inverse-QFT/QFT over $G$), the same query exactly identifies $H$ under explicit minimal conditions: $G/H$ is cyclic of order $q$, and the output alphabet admits a faithful, compatible group structure. These conditions hold automatically for $q \in \left\{ 2,3 \right\}$, giving unconditional single-query identification in these cases. In contrast, the Shor-Kitaev sampling approach cannot guarantee exact recovery from a single sample. Our results sharpen the landscape of one-query quantum solvability for abelian HSPs.
- Abstract（参考訳）: 量子フーリエ変換(QFT)は多くの量子アルゴリズムの中心であるが、その必要性は必ずしもよく理解されていない。
標準クエリ問題におけるその役割を再検討する。
Deutsch-JozsaアルゴリズムはQFTもドメイン群構造も必要としない。
対照的に、ベルンシュタイン・ヴァジラニ問題(Bernstein-Vazirani problem)は隠れた部分群問題(HSP)の例であり、隠れた部分群はインデックスが1ドルか2ドルである。
隠れた部分群$H \le G$がインデックスを持つかどうかを判定し、可能であれば$H$を識別する。
オラクルのコドメイン上のアーベル構造の任意の選択に対して、インデックスを$q$から$q$と常に区別するシングルクエリアルゴリズムを提案する。
さらに、適切な事前および後のユニタリ($G$よりも逆QFT/QFT)で、同じクエリは、明示的な最小条件下で$H$を正確に識別する:$G/H$は$q$の巡回であり、出力アルファベットは忠実で互換性のあるグループ構造を認める。
これらの条件は、$q \in \left\{ 2,3 \right\}$に対して自動的に成立し、これらの場合において無条件の単一クエリ識別を与える。
対照的に、Shor-Kitaevサンプリングアプローチでは、単一のサンプルから正確なリカバリを保証できない。
我々の結果は、アーベル HSP に対する一列量子可解性の展望を鮮明にする。
関連論文リスト
- Near-Optimal Clustering in Mixture of Markov Chains [74.3828414695655]
我々は、長さ$H$の軌跡を、大きさ$S$の有限状態空間上の未知のエルゴードマルコフ鎖の1つによって生成される、$T$ trajectories of length $H$の問題を研究する。
我々は、連鎖の遷移核間の重み付きKL分散によって支配されるクラスタリングエラー率に基づいて、インスタンス依存で高い確率の低い境界を導出する。
次に,新しい2段階クラスタリングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2025-06-02T05:10:40Z) - Quantum phase discrimination with applications to quantum search on graphs [0.0]
本稿では,この課題に対して量子位相判別(QPD)という量子アルゴリズムを提案する。
QPDを用いることで、Li と Zur が提案するパスフィニングアルゴリズムのクエリ複雑性を低減できる。
グラフ上の量子探索に2つの応用を提案する。
論文 参考訳（メタデータ） (2025-04-21T16:06:43Z) - A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - On the exact quantum query complexity of $\text{MOD}_m^n$ and $\text{EXACT}_{k,l}^n$ [4.956977275061968]
我々は、$textMOD_mn$を計算するための正確な量子アルゴリズムを示す。
我々は、0,1n$ を有限集合 $X$ が$n$ 未満であるような対称関数の広いクラスの正確な量子クエリ複雑性を示す。
論文 参考訳（メタデータ） (2023-03-20T08:17:32Z) - Mind the gap: Achieving a super-Grover quantum speedup by jumping to the
end [114.3957763744719]
本稿では,数種類のバイナリ最適化問題に対して,厳密な実行保証を有する量子アルゴリズムを提案する。
このアルゴリズムは、$n$非依存定数$c$に対して、時間で$O*(2(0.5-c)n)$の最適解を求める。
また、$k$-spinモデルからのランダムなインスタンスの多数と、完全に満足あるいはわずかにフラストレーションされた$k$-CSP式に対して、文 (a) がそうであることを示す。
論文 参考訳（メタデータ） (2022-12-03T02:45:23Z) - Quantum security of subset cover problems [1.4072904523937533]
多くのハッシュベースのシグネチャスキームのセキュリティは、サブセットカバー問題やこの問題の変種に依存する。
我々は、任意の量子アルゴリズムが、基礎となるハッシュ関数に対する$Omegaleft(k+1)-frac2k+1-1cdot Nfrac2k-12k+1-1right)$クエリを作成する必要があることを証明した。
また、一般的な$(r,k)$-subsetカバー問題のセキュリティも解析する。
論文 参考訳（メタデータ） (2022-10-27T12:58:27Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - Tight Quantum Lower Bound for Approximate Counting with Quantum States [49.6558487240078]
Aaronson, Kothari, Kretschmer, Thaler (2020) が考える数え上げ問題の次の変種に対する厳密な下界を証明する。
このタスクは、入力セット$xsubseteq [n]$が$k$か$k'=(1+varepsilon)k$であるかどうかを識別する。
論文 参考訳（メタデータ） (2020-02-17T10:53:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。