@yuichirominato 2019.01.04更新 255views

Simon(サイモン)のアルゴリズム

shor サイモン 周期性 暗号 量子ゲート 量子コンピュータ

周期性を求めるアルゴリズムとして有名なサイモンのアルゴリズムについて簡単に確認したいと思います。

はじめに

計算複雑性理論および量子計算において、サイモンの問題は、古典的なコンピュータよりも量子コンピュータの方が指数関数的に早く解くことができる計算問題です。問題自体は実用的な価値はほとんどありませんが、量子アルゴリズムがこの問題を従来のどの古典的アルゴリズムよりも指数関数的に速く解くことができることを証明することができます。 この問題はデシジョンツリーの複雑度またはクエリの複雑度のモデルに設定されており、1994年にDaniel Simonによって考案されました。これは、決定論的または確率論的な古典的アルゴリズムよりも指数関数的に速く問題を解決し、最善の古典的確率論的アルゴリズムよりも指数関数的に短い計算時間を必要とします。 Simonのアルゴリズムは、Shorのアルゴリズムのヒントにもなっています。

https://en.wikipedia.org/wiki/Simon%27s_problem

概要

$f:\{0,1\}^n \rightarrow \{0,1\}^n$のような関数$f$と0でない$s\in\{0,1\}^n$があるとき、全ての$x\in\{0,1\}^n$に対して、$f(x)=f(x+s)$となる周期を持つとき、0でない周期sを探すアルゴリズム。

参考:https://www.ipa.go.jp/security/enc/quantumcomputers/contents/doc/chap4_2.pdf

例題

3量子ビットの例題を見てみます。

xf(x)
000 101
001 010
010 000
011 110
100 000
101 110
110 101
111 010

この周期性を求めるのは簡単で、8つの入力に対して出力が4種類となっている。例えば010と100は等しく000の出力を得るので、$010\oplus100$のXORをとることで、sが求まる。s=110となる。f(x)=f(x+s)。他の数で確認すると、f(000)=f(000+110)=f(110)=101となっている。

参考:https://en.wikipedia.org/wiki/Simon%27s_problem

XORの参考:https://ja.wikipedia.org/wiki/%E6%8E%92%E4%BB%96%E7%9A%84%E8%AB%96%E7%90%86%E5%92%8C

量子回路

1、すべて|0>の量子状態を最初に準備します。

2、そして半分は、アダマール変換を使用して重ね合わせを作成。結果はそれからfに対応するオラクルを適用します。

3、その後、オラクルによって生成された出力の一部をアダマール変換を使用して変換。

4、最後に量子状態の測定となります。

https://en.wikipedia.org/wiki/Simon%27s_problem

上記のステップでサイモンのアルゴリズムが実行できます。実際にはオラクルと呼ばれる関数部分を自分で作る必要があります。

例題

ちょっと例題を考えてみます。3量子ビットの問題をいきなりやるのはきついので、まずは2量子ビットで下記のような解にうつされるような周期性を探します。

xf(x)
00 10
01 11
10 10
11 11

こちらの回路は、オラクル部分はCXをつかって下記のように表せされます。

|0> ---H-----------H--- x
|0> ---H---*-------H--- x
|0> -------|---X------- f(x)
|0> -------X----------- f(x)

上記はxの値によらずf(x)の左の位は1となるので、Xゲートをかけて準備します。右の位は元のxの位と同じになってるのでCXで写します。Blueqatコードでは、

from blueqat import Circuit 
Circuit().h[:2].x[2].cx[1,3].h[:2].m[:].run(shots=100)                                                                 

Counter({'0111': 26, '0110': 21, '0011': 27, '0010': 26})

f(x)がきちんと10と11になっていて、元のxは01の場合か、00となっています。00は今回捨ててしまっていいので、50%の確率で、01を選びます。答えは10になるはずなので、なぜか逆ですが、、、s=10が答えです。

念の為他のもやってみます。

x >> f(x)が
00 >> 10
01 >> 10
10 >> 11
11 >> 11

回路としては、0番目の量子ビットの値を3番目に写します。

---H-------*---H---
---H-------|---H---
-------X---|-------
-----------X-------

Blueqatコードは、

Circuit().h[:2].x[2].cx[0,3].h[:2].m[:].run(shots=100)                                                                 

Counter({'0011': 21, '1010': 26, '0010': 30, '1011': 23})

この場合も10がでたのでなぜか逆ですが、s=01が答えです。

続いてあと1つだけ、

x >> f(x)が
00 >> 00
01 >> 11
10 >> 11
11 >> 00

この場合には回路は、

---H-------*-----*--H---
---H----*--|--*--|--H---
--------X--X--|--|------
--------------X--X------

Blueqatコードで、

Circuit().h[:2].cx[1,2].cx[0,2].cx[1,3].cx[0,3].h[:2].m[:].run(shots=100)                                              

Counter({'1100': 22, '0011': 25, '1111': 31, '0000': 22})

11がでてきているのでs=11となりました。

まとめ

Blueqatでサイモンのアルゴリズムが実装できました。f(x)を実現するアルゴリズムはf(x)に応じて自分で考えて作ってみてください。

Recommended


CONTACT

info@mdrft.com

ブログトップへ Wikiへ移動

量子コンピュータ一般

量子ゲートアルゴリズム

量子アニーリング一般

量子アニーリングアルゴリズム

BlueqatSDKの使い方