隠れたサブグループ問題

Very general problem in computer science

隠れ部分群問題（HSP ）は、数学および理論計算機科学における研究テーマです。この枠組みは、因数分解、離散対数、グラフ同型性、最短ベクトル問題といった問題を捉えています。量子計算における因数分解と離散対数を求めるショアのアルゴリズムは有限アーベル群の隠れ部分群問題の例であり、その他の問題はアーベル群ではない有限群に対応するため、 HSPは量子計算理論において特に重要です。

問題の説明

群 、部分群、集合が与えられたとき、がすべての に対して であり、かつ の場合に限り、関数 が部分群を隠蔽するという。同様に、はHの各剰余類上で定数であるが、 Hの異なる剰余類間では異なる。 ${\displaystyle G}$ ${\displaystyle H\leq G}$ ${\displaystyle X}$ ${\displaystyle f:G\to X}$ ${\displaystyle H}$ ${\displaystyle g_{1},g_{2}\in G,f(g_{1})=f(g_{2})}$ ${\displaystyle g_{1}H=g_{2}H}$ ${\displaystyle f}$

隠れ部分群問題：を群 、を有限集合 、 を部分群 を隠す関数とします。この関数は、ビットを用いるオラクルを介して与えられます。オラクル を介して を評価することで得られる情報を用いて、の生成集合を求めます。 ${\displaystyle G}$ ${\displaystyle X}$ ${\displaystyle f:G\to X}$ ${\displaystyle H\leq G}$ ${\displaystyle f}$ ${\displaystyle O(\log |G|+\log |X|)}$ ${\displaystyle f}$ ${\displaystyle H}$

特殊なケースとして、が群であり が群準同型である場合が挙げられます。この場合はの核に対応します。 ${\displaystyle X}$ ${\displaystyle f}$ ${\displaystyle H}$ ${\displaystyle f}$

モチベーション

隠れた部分群問題は、以下の理由から量子コンピューティングの理論において特に重要です。

• 因数分解と離散対数を求めるショアのアルゴリズム（およびその拡張のいくつか）は、有限アーベル群の HSP を解く量子コンピュータの能力に依存しています。
• 特定の非可換群に対するHSPに対する効率的な量子アルゴリズムの存在は、2つの主要な問題、すなわちグラフ同型問題と格子における特定の最短ベクトル問題（SVP）に対する効率的な量子アルゴリズムを意味する。より正確には、対称群に対するHSPに対する効率的な量子アルゴリズムは、グラフ同型問題に対する量子アルゴリズムを与える^{[1] 。}二面体群に対するHSPに対する効率的な量子アルゴリズムは、唯一のSVPに対する量子アルゴリズムを与える^[2]。 ${\displaystyle \operatorname {poly} (n)}$

量子アルゴリズム

有限アーベル群上のHSPを の多項式時間で解く効率的な量子アルゴリズムが存在する。任意の群に対して、隠れた部分群問題はオラクルの評価を多項式回数行うことで解けることが知られている。^[3]しかし、これを実装する回路は において指数関数的になる可能性があり、アルゴリズム全体としては効率的ではない。効率的なアルゴリズムは、オラクルの評価回数と実行時間に関して多項式でなければならない。任意の群に対してこのようなアルゴリズムが存在するかどうかは未知数である。量子多項式時間アルゴリズムは、一部のアーベル群の半直積など、群の特定のサブクラスに対して存在する。 ${\displaystyle \log |G|}$ ${\displaystyle \log |G|}$

アーベル群のアルゴリズム

アーベル群のアルゴリズムは、複素数上の一般線型群からへの準同型写像 といった表現を用いる。表現がの2つ以上の表現の直積として表せない場合、それは既約表現である。アーベル群の場合、すべての既約表現はの指標であり、これらは1次元の表現である。アーベル群には、それより大きい次元の既約表現は存在しない。 ${\displaystyle G}$ ${\displaystyle \mathrm {GL} _{k}(\mathbb {C} )}$ ${\displaystyle G}$

量子フーリエ変換の定義

量子フーリエ変換は、位数 の加法巡回群を用いて定義できます。 という特性を導入すると、量子フーリエ変換は という定義を持ちます。さらに、 と定義します。任意の有限アーベル群は、複数の巡回群 の直積として表すことができます。量子コンピュータでは、これはそれぞれ 次元の複数のレジスタのテンソル積として表され、全体の量子フーリエ変換は となります。 ${\displaystyle \mathrm {Z} _{N}}$ ${\displaystyle N}$ $${\displaystyle \chi _{j}(k)=\omega _{N}^{jk}=e^{2\pi i{\frac {jk}{N}}},}$$ $${\displaystyle F_{N}|j\rangle ={\frac {1}{\sqrt {N}}}\sum _{k=0}^{N}\chi _{j}(k)|k\rangle .}$$ ${\displaystyle |\chi _{j}\rangle =F_{N}|j\rangle }$ ${\displaystyle \mathrm {Z} _{N_{1}}\times \mathrm {Z} _{N_{2}}\times \ldots \times \mathrm {Z} _{N_{m}}}$ ${\displaystyle N_{1},N_{2},\ldots ,N_{m}}$ ${\displaystyle F_{N_{1}}\otimes F_{N_{2}}\otimes \ldots \otimes F_{N_{m}}}$

手順

の文字の集合は、の双対群と呼ばれる群を形成します。また、によって定義されるサイズの の部分群も存在します。アルゴリズムの各反復において、量子回路は文字 に対応する要素を出力します。また、すべての に対してとなるため、 が何であるかを特定するのに役立ちます。 ${\displaystyle G}$ ${\displaystyle {\widehat {G}}}$ ${\displaystyle G}$ ${\displaystyle H^{\perp }\leq {\widehat {G}}}$ ${\displaystyle |G|/|H|}$ $${\displaystyle H^{\perp }=\{\chi _{g}:\chi _{g}(h)=1{\text{ for all }}h\in H\}}$$ ${\displaystyle g\in G}$ ${\displaystyle \chi _{g}\in H^{\perp }}$ ${\displaystyle \chi _{g}(h)={1}}$ ${\displaystyle h\in H}$ ${\displaystyle H}$

アルゴリズムは次のとおりです。

1. 状態 から開始します。ここで、左レジスタの基底状態は の各要素であり、右レジスタの基底状態は の各要素です。 ${\displaystyle |0\rangle |0\rangle }$ ${\displaystyle G}$ ${\displaystyle X}$
2. 左レジスタのの基底状態間の重ね合わせを作成し、状態 を残します。 ${\displaystyle G}$ ${\textstyle {\frac {1}{\sqrt {|G|}}}\sum _{g\in G}|g\rangle |0\rangle }$
3. 関数 をクエリします。その後の状態は です。 ${\displaystyle f}$ ${\textstyle {\frac {1}{\sqrt {|G|}}}\sum _{g\in G}|g\rangle |f(g)\rangle }$
4. 出力レジスタを測定する。これにより、ある に対して が得られ、 は剰余類 の各要素に対して同じ値を持つため、状態は に収束する。出力レジスタを破棄して を得る。 ${\displaystyle f(s)}$ ${\displaystyle s\in G}$ ${\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|s+h\rangle |f(s)\rangle }$ ${\displaystyle f}$ ${\displaystyle s+{H}}$ ${\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|s+h\rangle }$
5. 量子フーリエ変換を実行して、状態を取得します。 ${\textstyle {\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|\chi _{s+h}\rangle }$
6. この状態は に等しく、これを測定することで に関する情報を得ることができます。 ${\textstyle {\sqrt {\frac {|H|}{|G|}}}\sum _{\chi _{g}\in H^{\perp }}\chi _{g}(s)|g\rangle }$ ${\displaystyle H}$
7. （または の生成セット）が決定されるまで繰り返します。 ${\displaystyle H}$ ${\displaystyle H}$

ステップ 5 の状態は、次の理由により、ステップ 6 の状態と等しくなります。最後の等式については、次の恒等式を使用します。 $${\displaystyle {\begin{aligned}{\frac {1}{\sqrt {|H|}}}\sum _{h\in H}|\chi _{s+h}\rangle &={\frac {1}{\sqrt {|H||G|}}}\sum _{h\in H}\sum _{g\in G}\chi _{s+h}(g)|g\rangle \\&={\frac {1}{\sqrt {|H||G|}}}\sum _{g\in G}\chi _{s}(g)\sum _{h\in H}\chi _{h}(g)|g\rangle \\&={\frac {1}{\sqrt {|H||G|}}}\sum _{g\in G}\chi _{g}(s)\left(\sum _{h\in H}\chi _{g}(h)\right)|g\rangle \\&={\sqrt {\frac {|H|}{|G|}}}\sum _{\chi _{g}\in H^{\perp }}\chi _{g}(s)|g\rangle \end{aligned}}}$$

定理— $${\displaystyle \sum _{h\in H}\chi _{g}(h)={\begin{cases}|H|&\chi _{g}\in H^{\perp }\\0&\chi _{g}\notin H^{\perp }\end{cases}}}$$

証拠

これは指標の直交性から導かれます。 の指標は直交基底を形成します。 を自明な表現とし、すべての入力を に写像すると、 が得られます。の上で総和を求めるので、が自明であることは 上で自明な場合にのみ、つまり の場合にのみ問題になります。したがって、の場合には総和は となり、の場合には となることがわかります。 ${\displaystyle G}$ $${\displaystyle {\frac {1}{\vert H\vert }}\sum _{h\in H}\chi _{g}(h)\chi _{g'}(h)={\begin{cases}1&g=g'\\0&g\neq g'\end{cases}}}$$ ${\displaystyle \chi _{g'}}$ ${\displaystyle 1}$ $${\displaystyle \sum _{h\in H}\chi _{g}(h)={\begin{cases}\vert H\vert &g{\text{ is trivial}}\\0&g{\text{ is not trivial}}\end{cases}}}$$ ${\displaystyle H}$ ${\displaystyle \chi _{g}}$ ${\displaystyle H}$ ${\displaystyle \chi _{g}\in H^{\perp }}$ ${\displaystyle \vert H\vert }$ ${\displaystyle \chi _{g}\in H^{\perp }}$ ${\displaystyle 0}$ ${\displaystyle \chi _{g}\notin H^{\perp }}$

最終状態の各測定により、 について何らかの情報が得られます。なぜなら、すべての についてであることがわかっているからです。、または の生成セットは、多項式回の測定の後に見つかります。 生成セットのサイズは、 のサイズに比べて対数的に小さくなります。を の生成セット、つまりを表すことにします。 によって生成される部分群のサイズは、新しい要素が追加されると少なくとも 2 倍になります。これは、と が互いに素であり であるためです。したがって、生成セットのサイズはを満たします。したがって、 の生成セットは、が指数関数的なサイズであっても、多項式時間で取得できます。 ${\displaystyle H}$ ${\displaystyle \chi _{g}(h)=1}$ ${\displaystyle h\in H}$ ${\displaystyle H}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle T}$ ${\displaystyle H}$ ${\displaystyle \langle T\rangle =H}$ ${\displaystyle T}$ ${\displaystyle t\notin T}$ ${\displaystyle H}$ ${\displaystyle t+H}$ ${\displaystyle H\cup t+H\subseteq \langle \{t\}\cup T\rangle }$ ${\displaystyle |T|}$ $${\displaystyle |T|\leq \log |H|\leq \log |G|}$$ ${\displaystyle H}$ ${\displaystyle G}$

インスタンス

量子コンピューティングにおいて量子的な高速化を実現するアルゴリズムの多くは、隠れ部分群問題（HSP）の例です。以下のリストは、HSPの重要な例と、それらが解けるかどうかを概説しています。

問題	量子アルゴリズム	アーベル？	多項式時間で解決できますか?
ドイチュの問題	ドイチュのアルゴリズム。 Deutsch-Jozsa アルゴリズム	はい	はい
サイモンの問題	サイモンのアルゴリズム	はい	はい
注文の検索	ショアの順序発見アルゴリズム	はい	はい
離散対数	ショアのアルゴリズム § 離散対数に対するショアのアルゴリズム	はい	はい
周期の発見	ショアのアルゴリズム	はい	はい
アーベル安定子	キタエフのアルゴリズム[4]	はい	はい
グラフ同型性	なし	いいえ	いいえ
最短ベクトル問題	なし	いいえ	いいえ

参照

• 隠れたシフト問題
• ポンチャギンの二重性

参考文献

1. Mark Ettinger; Peter Høyer (1999). 「グラフ同型性問題のための量子観測可能量」. arXiv : quant-ph/9901029 .
2. Oded Regev (2003). 「量子計算と格子問題」. arXiv : cs/0304005 .
3. Mark Ettinger、Peter Hoyer、Emanuel Knill (2004). 「隠れ部分群問題の量子クエリ複雑度は多項式である」. Information Processing Letters . 91 : 43–48 . arXiv : quant-ph/0401083 . Bibcode :2004quant.ph..1083E. doi :10.1016/j.ipl.2004.01.024. S2CID  5520617.
4. キタエフ, アレクセイ (1995年11月20日). 「量子測定とアーベル安定問題」. arXiv : quant-ph/9511026 .

外部リンク

• リチャード・ジョザ：量子因数分解、離散対数、隠れた部分群問題
• クリス・ロモント：隠れた部分群問題 - レビューと未解決問題
• arxiv.org における隠れたサブグループ問題
• 離散対数を求めるためのショアのアルゴリズムをClassiqで完全に実装

Retrieved from "https://en.wikipedia.org/w/index.php?title=Hidden_subgroup_problem&oldid=1309628979"