Hidden Subgroup Problem

【 Hidden Subgroup Problem 】

Shorのアルゴリズムから、Hidden Subgroup Problem を説明してみよう。　

素因数分解のアルゴリズムとしてShorのアルゴリズムは、素数 n, a について a^(n-1) ≡ 1 (mod n) というフェルマーの小定理を素数判定に繰り返し利用している。フェルマーの小定理がなりたつことは、次のような例で確かめてみればいい。

2^3=8=3x2+2 ≡ 2 (mod 3)
2^5=32=5x6+2 ≡ 2 (mod 5)
2^7=128=7x18+2 ≡ 2 (mod 7)
2^11=2048 =11x186+2 ≡ 2 (mod 11)

a^r ≡ 1 (mod n) なるrが存在する時、この最小のrを（nについての）aの周期（あるいは位数）という。

例えば、n = 15, a = 7 とすると、周期は4である。

        7^0 = 1 (mod 15) 7^1 = 7 (mod 15)
7^2 = 4 (mod 15) 7^3 = 13 (mod 15)
   7^4 = 1 (mod 15) 7^5 = 7 (mod 15)
7^6 = 4 (mod 15) 7^7 = 13 (mod 15)
7^8 = 1 (mod 15) 7^9 = 7 (mod 15)

Shorのアルゴリズムでは、aの周期を求める時、量子コンピューターが呼び出されている。逆に言えば、Shorのアルゴリズムで量子コンピュータが使われているのは、その部分だけである。

足し算が定義されている整数の全体をGとする。Gは、足し算について群になる。今度は、Gの部分群（Gの部分集合で足し算について群になるもの）Kを考える。

このKについて、Gから有限集合Xの関数fを、次のように定義する。
Gの二つの要素g1,g2について、f(g1)=f(g2)となるのは、g1K=g2K となるものに限るものとする。Kは足し算についての部分群なので、g1K=g2K という条件は、g1+k1=g2+k2 というKの要素 k1, k2があるという条件に等しい。

Shorのアルゴリズムの量子コンピューター担当パートでの、「aの周期を求めよ」という問題なら、a^j ≡ 1 ( mod n) となる整数の全体( mod n で考える）をXとして、GからXの関数fを、f(x) = a^x で定義する。この時、f(x+r) = a^(x+r) = a^x ・a^r = a^x・1 = a^x = f(x) となる。この時、Kは、K = { 0, r, 2r, 3r, ... }という形をしていることがわかる。

Gの要素xとxにfを適用したXの要素 f(x) が与えられた時、この二つの情報の集まりから、部分群Kの形を求めよというのが、Hidden Subgroup Problem である。

なぜHidden Subgroupというかだが、Kは確かに部分群なのだが、関数 f: G -> XのもとではKの剰余類上では、それは定数にしか見えない。Kの情報はfによって隠されているのである。

さらに、Hidden Subgroup Problemでは、fの情報は、関数fの定義として明示的に与えられる必要はない。我々は、f(x)を吐き出すブラックボックスから情報をサンプリングすればいいのだ。

量子コンピューターの研究者は、多くの量子アルゴリズムを、( G, X, K, f ) の四つ組のHidden Subgroup Problem として捉え返そうとしている。次の表は、NielsenとChuang からのもの。

これらの大部分は「有限アーベル群のHidden Subgroup Problem」であることに注意が必要である。

問題の整理は、次の問題の発見につながる。

そうでない群に対するHidden Subgroup Problemと、それを実装した量子コンピューターの振る舞いは、どういうものになるのか？

次の投稿は、こうした問題をめぐる状況について触れたいと思う。

------------

セミナーの申し込み受付始めました。申し込みはこちらからお願いします。https://cipher3.peatix.com/view

「ラティス暗号入門」のまとめページはこちらです。この間の投稿は、こちらからもまとめて読めます。https://www.marulabo.net/docs/cipher3/