一回投稿していたのですが，少し恥ずかしくなり削除しました．再投稿です．
はじめに
こんにちは，初投稿です．
現在学部3年の情報学部生です．
今回 研究室配属の課題で，まず読むことになった
「An Introduction to Quantum Algorithms」
の論文の4章の内容を一通り理解できたので記事にしたいと思いました．
解釈が間違ったところもあると思いますので，ご指摘お願いします．
課題で使ったスライドはこれです↓．
量子アルゴリズム入門
こちらの記事を参考にさせていただきました．本当にお世話になりました．
量子コンピュータ
最近なんだか熱いですね！！！
googleの量子超越の話だったりIBMの量子コンピュータだったり．アニーリングの方も勉強したいと思います．
4章 Simon's Algorithm
問題
f:{0,1}^n -> {0,1}^nの神託マシン（オラクルマシン）
が与えられたとき，f(x) = f(y)となるようなx，yにおいて
（ x ⊕ a ) = yを満たすようなaを見つける．
- 神託マシン（オラクルマシン）... 入力値に対応する返り値がO(1)で得られるブラックボックス関数
- ⊕ ... XOR
ではこの神託マシンのはどのように生成されるかというと，
aの値が与えられること初めて生成できます．具体例で見てみます．
| x | f(x) |
|---|---|
| 000 | 101 |
| 001 | 010 |
| 010 | 000 |
| 011 | 110 |
| 100 | 000 |
| 101 | 110 |
| 110 | 101 |
| 111 | 010 |
今回は論文に倣いこの神託マシンを例に見ていきます．見方はわかると思いますがxの値を突っ込むとそれに対応するf(x)が返ってきます．
この表よりaを求めるには
排他的論理和の演算において，x⊕a＝y ⇔ x⊕y＝a が成り立つ．
ので，f(000) = 101 = f(110) より x＝000，y＝110．
a = 000 ⊕ 110 ＝ 110 がこの神託マシンのaになります．
（この神託マシンはこの110を元にx⊕110＝yが成り立つように作成されました）
サイモンのアルゴリズムは量子コンピュータを使って古典アルゴリズムよりも効率的にaを解く為のアルゴリズムです．古典コンピュタではO(2^(n/2)）以上かかる計算が量子コンピュータを使うとO(n)で解けます．
サイモンのアルゴリズム
サイモンのアルゴリズムについて説明する前に量子ビットと量子ゲートの説明が必要です．
今回それらの説明は，上部に載せているスライドを見てください．量子アルゴリズム入門
（書くのが大変そうでした．そのままスライド載せれるようになったら楽なんですが．．．）
量子回路
「An Introduction to Quantum Algorithms」のp29 より図をいただきサイモンのアルゴリズムにおける回路を示します．
- |0>...量子ビット
-
... アダマールゲート -
...神託マシン（オラクルマシン） -
... 量子ビットの観測
手順
サイモンのアルゴリズムは以下手順で量子レジスタに対して操作を行います．
- n bitの量子レジスタ2つを|0>にセット
- 2つのレジスタをアダマール変換
- 第1レジスタを神託マシンに入れ，結果を第2レジスタに入れる．
- 第2レジスタを観測する．
- 第1レジスタをもう一度アダマール変換
- 第1レジスタを観測
- n-1通りの結果が出るまで繰り返す．
- 出てきた結果よりaについての連立方程式を作成し解く．
説明
ここからは各手順 順を追って説明していきます．
1. n bitの量子レジスタ2つを |0> にセット
求めたいビット数（n）の量子レジスタを用意し，ともに基底状態の|000>にセットします．
量子レジスタ|000>の状態とは，このレジスタを観測すると確率 1（100％）で000が観測される状態です．
量子レジスタの状態の表し方は色々あります．
例えば 1bit量子レジスタの状態をΨとすると
と表すことができます．ちなみにこのΨの状態は基底状態|0>と|1>が等確率で観測される量子状態となります．
2. 2つのレジスタをアダマール変換
1．で用意した2つのn bitレジスタのうち第1レジスタにアダマール変換を行います．
アダマール変換は，量子の重ね合わせを作り出す為の非常に重要な変換になります．
アダマール変換を行う量子ゲートのことを，そのままアダマールゲートと呼びます．
量子状態の変換を表現するために行列が使われます．
アダマール変換を行うアダマール行列は次のような形をしています．
アダマール変換は各基底状態の重ね合わせ状態を作るため，第1レジスタにアダマール 変換を行った後の量子レジスタの状態は
になります．（基底状態｜x＞の係数の2乗が観測した時の確率になる．）
（※今回一応計算式も交えながら説明しようと思います．しかし，まずは数学的なことは置いておき，後に書く具体例を確認していただいた方が全体像が掴めると思います．）
3. 第1レジスタを神託マシンに入れ，結果を第2レジスタに入れる．
第1レジスタを入力，第2レジスタを出力として神託マシンに入れます．
それにより，『量子のもつれ』と呼ばれる状態にします．
私のイメージとしては，第1レジスタと第2レジスタを神託マシンの結果を元に紐付けている感じです．
（正確には違うという意見しか出てこないと思いますがとりあえず説明を続けます．）
第1レジスタと第2レジスタの状態は以下のようになります．
4. 第2レジスタを観測する．
(2)状態の量子レジスタのの第2レジスタ（ |f(x)> ）を観測します．
すると少し不思議な感じはしますが，観測した結果と矛盾がない状態に第1レジスタの状態は制限されます．
具体的な例で説明すると
| x | f(x) |
|---|---|
| 000 | 101 |
| 001 | 010 |
| 010 | 000 |
| 011 | 110 |
| 100 | 000 |
| 101 | 110 |
| 110 | 101 |
| 111 | 010 |
第2レジスタの値に|010＞を観測した時，第1レジスタの状態は
になります．
これを数式で表すと
になります．
第2レジスタを観測することで第1レジスタはこの状態になります．
（以降第2レジスタンスは不要に）
5. 第1レジスタをもう一度アダマール変換
(4)の状態の量子レジスタにもう一度アダマール変換を行います．
計算式は載せますが，無視して最後の結果に注目してください．
計算によって出てきた式を考えてみます．
n=3の時,yは 000から111までの8通りあります．それらの観測確率はそれぞれの係数の2乗によって決定します．
つまり，係数が0になると絶対に観測されないということです．
|y>の係数は
です．
今重要になるのは係数の後半
の部分です．
場合分けをして考える．
-
case 1: a*y = 1 のとき
となり|y>の係数が0になる．（＝＞ |y>は観測されない） -
case 2: a*y = 0 のとき
となる．（＝＞ |y>は観測される候補）
6. 第1レジスタを観測
5．より y*a＝0 を満たす|y>が等確率で第1レジスタを観測することで得られる．
7. n-1通りの結果が出るまで繰り返す．
1．〜 6．までの操作を|y>がn-1種類得られるまで繰り返す．
8. 出てきた結果よりaについての連立方程式を作成し解く．
（ただし，mod2であることに注意）
以上の操作を持って神託マシンにおける a をサイモンのアルゴリズムを使うことで求めることができます．
では次に具体的な例を使用して一つずつ手順を追ってみます．
具体例で解いてみる．
スライドの画像を載せてます．
まず上記の操作1，〜 3．が終わり，第2レジスタを観測するところから見てみます．その制限された
第2レジスタを観測することで第1レジスタの状態が制限されます．
その制限されたレジスタにアダマール変換を行います．
（アダマール変換はレジスタの状態全体にかかるので分配則が適用されます．）
アダマール変換って具体的にどんな操作なのでしょう？
量子のレジスタの操作は行列の計算で表すことができます．アダマール変換と対応する行列はアダマール行列と呼ばれるものです．この行列を第1レジスタの状態を表す行列に左からかけてあげます．どのように|000>や|110>が行列に対応するのかは，スライドのp11，p12などを見てください．
※(|000> ＝|0>⊗|0>⊗|0>，|110> ＝|1>⊗|1>⊗|0>の意味です)
アダマール変換の計算がこれになります．行列の積なので右のベクトル（行列）の1の位置によってアダマール行列のどの列が取り出されるかが決まります．今回取り出されるのは赤で囲った列．
計算すると
続けて
続けて
という形に計算されます．これは第1レジスタの状態の計算結果でした．この式が一体何を表しているかというと，この状態の第1レジスタを観測すると，等確率（1／4）でそれぞれ|000>,|001>,|110>,|111>が観測されるということを表しています．
では，それぞれが観測された場合，aとなる候補は何が残るでしょうか？
アダマール変換を2回目行ったときに，y * a = 1 となる観測は絶対にされないという条件がありました．よって観測された値が|y>とするとy * a = 0となる候補はスライドの通りになります．(注意としてはmod 2です)
見たらわかるように|000>,|001>,|110>,|111>のどれを観測しても候補となりうるのはa=000とa=110です．a＝000の場合オラクルマシンを作ることができないため，今回求めたかったaは110に定まります．
（実はy＝|000>が観測されたとき1つも絞り込みができてないです．情報量0．
運がなかった．もう一回繰り返そう！！）
なぜこれがO(n)なのかについては，一回の一連の観測で3／10ほどの確率で情報量のある観測結果が得られ，観測結果の候補として2^n個ある中から，情報量を持つn-1個の要素（基底状態）を観測することでaを求めることができるため，O(n)で問題を解くことができます．
(説明下手ですみません．)
以上がサイモンのアルゴリズムの全体になります．
最後に
皆様，最後まで読んでいただきありがとうございます．
初投稿の記事で文章が幼稚な部分（誤字・脱字・間違い）が多々あります．
これからの様々なご指摘により，問題のない文章に改善していこうと思います．
皆様，ご指摘よろしくお願いします．
（間違った表現があればすぐに修正します）