情報セキュリティ第14回

(1)

情報セキュリティ第14回

大久保誠也静岡県立大学経営情報学部

2/54

はじめに

 量子計算機は、古典計算機（従来の計算機）に量子力学の原理を取り入れたもの。

 量子計算機の物理的実現に関する研究が盛んに。

 量子計算機の実現方法

量子デジタル計算機

量子アナログ計算機

 そのまま使えば幸せになれるわけではない。

量子計算機とその特徴を古典と比較して説明

3/54

目次とキーワード

 はじめに

 登場人物紹介

古典計算機

量子デジタル計算機

量子アナログ計算機

 対戦ルール

ステップと時間

 対戦結果

 おわりに

4/54

登場人物紹介 1 古典計算機

そもそも「計算」とは？

 「数学的に測る」として、定義は何？

 計算機（コンピュータ）は「計算」するもの。

 そもそも、「計算」ってなに？

Church-Turing の提唱

 Turing機械とは。

計算機の数学的モデルの一つ。

実際の計算機よりも、相当に単純化・理想化されている。

今の計算機でできることは、原理的にはTuring機械でもできる！

計算可能なものとは、Turing機械で実行できるもの

(2)

7/54

Turing 機械

p

1 0 0 1 0 

有限制御部

（CPUに相当）

ヘッド

テープ

（メモリに相当）

現在の計算機の数学的モデルは，Turing機械

状態遷移関数（プログラムに相当）にしたがって、テープの値の書き換え、

状態の変更、ヘッドの移動を行う。

8/54

Turing 機械の動作

0 0 0 0 0

0 0 0 1 0 0 0

ヘッド

有限制御部テープ

p q

テープの値を書き換える

ヘッドの位置が動く

動作

状態が変わる

9/54

古典計算機のまとめ

 現在、世界に普及している計算機。

高い汎用性と量産性を持って、さまざまなところで大活躍中。

 モデルはTuring機械。

さまざまなアルゴリズムが研究されたり、評価されています。

 古典計算機では、歯が立たない、時間がかかる問題がある（と強く信じられている）。

10/54

登場人物紹介2 量子（デジタル）計算機

11/54

量子って何か

 古典力学

マクロな現象の力学。

古来から伝わる、由緒正しき力学。

例：手を離したらリンゴが落ちる

例：天体の運動

 一方、原子や分子ぐらいミクロな世界になると、これらの古典力学では説明できない現象が発生。

こういう現象を説明できるのが量子力学

12/54

例：偏光板実験 (1)

 偏光板には向きがあります。

 1枚の偏光板を

縦向きのときには、光を（）。

横向きのときには、光を（）。

縦-縦の順番に並べたときは、光を（）。

縦-横の順番に並べたときは、光を（）。

光？

(3)

13/54

例：偏光板実験 (2)

 偏光板には向きがあります。

縦-縦-横のときには、光を（）。

縦-横-横のときには、光を（）。

縦-横-斜のときには、光を（）。

縦-斜-横のときには、光を（）。

量子力学で説明可能

14/54

量子デジタル計算機の発想

 量子力学の世界では...

メモリは重ね合わせ状態をもてる

つまり、0と1のどちらかではなく、複数の状態を同時に保持できる。

重ね合わせ状態に対して、演算を行うことができる

量子並列計算が可能。

通常の計算機では実現できない並列度。

量子並列計算だと、問題が高速に解けるのでは？

15/54

世界は分裂している？

多世界解釈と量子重ね合わせ

「シュレーディンガーの猫」で検索をかけてみよう。

世界は常に分裂し、

重ね合わさっている！

自分が認識しているのは、

その世界のうちの一つ

16/54

任意の重ね合わせ状態を記憶

量子ビット (qubit)

1

0 

 

 とはを満たす複素数である.

 とはヒルベルト空間内の状態ベクトル

 ( )  は，状態 ( )の確率振幅と呼ばれる.



 _ ²_ _ ²_₁

 ⁰ ¹

0 1

^or

0 1

重ね合わせ

Turing機械の場合量子Turing機械の場合

0 または1 を記憶テープの1つの区画に

1bit 1qubit

1 0

and

量子 Turing 機械

 1985年にDavid Deutsch が提案。

 通常のTuring機械に、量子並列計算機能を取り入れたもの。

p

1 0 0 1 0 

有限制御部

（CPUに相当）

ヘッド

テープ

（メモリに相当）

状態遷移関数（プログラムに相当）にしたがって、テープの値の書き換え、

状態の変更、ヘッドの移動を行う。

量子計算機

 量子計算機は、量子並列計算を行う

0 0 0 0

量子計算機入力

0 0 0 0 0 0 0 00 0 0 1 1 0^ ¹ 0

量子並列計算

出力

0 0 0 ¹

並列計算をするけど、

出力されるのは1つだけ！

(4)

19/54

Shor のアルゴリズム

 1994年のPeter Shor

量子計算機は、因数分解を任意に小さい誤り確率で多項式時間で実行可能であることを示す．

 通常の計算機は、整数の因数分解を多項式時間で解くことが難しいと信じられている．

量子計算機は通常の計算機より強力かもしれない！

量子計算機が完成すると，

RSA暗号が解けてしまう！

20/54

Grover のアルゴリズム

 1996年のL.K.Grover

量子探索アルゴリズムを発表。

鍵の総当たりに必要な時間が、に。

指数時間ではあるが、時間の桁数は半分になる！

量子計算機が完成すると，

鍵の総当たり攻撃も高速に可能

2n

21/54

量子デジタル計算機のまとめ

 量子力学の原理を用いて、量子重ね合わせを用いた計算が可能。

量子並列計算。

通常の計算機では実現不能なサイズの並列度が実現可能。

 ただし、人間は量子重ね合わせ状態を直に観測する能力を持っていない！

単に動かしただけでは、意味がない

工夫（アルゴリズム）が必要

 汎用性は高い。が、物理実現はまだ先か。

22/54

登場人物紹介3 量子（アナログ）計算機

23/54

アナログ計算とは

 自然界の物理現象等には、見ようによっては、人間が解きたい問題を解いてしまっているものがある。

 それを使って問題を解こう！

 例：釘とシャボン 1) 板に釘を2本挿します 2) シャボン液につけます

2点間の最短経路に

膜が！

24/54

量子アナログ計算機の発想

 量子力学の原理に基づいて、物体の状態を変化させると、何か問題が解けるのでは？

初期設定時間発展最後の状態を答えと解釈！

(5)

25/54

時間発展

 物理系を発展させることにより、問題を解く

 初期状態H₀、最終状態H₁

 全体の状態を表すハミルトニアンは

最初はA(0)=1かつB(0)=0、つまり初期状態

時間発展後A(t)=0 かつB(t)=T。つまり、最終状態

 ゆっくり変化させると、最終状態が解を示す

0 1

( ) ( )

A t H B t H

26/54

3 彩色問題を解くハミルトニアン

 以下がLucas によって示されている。

 ここで、v, u はノード、E はエッジの集合

 各x は0,1のどちらかの値を取る。

 ノードvに対してx_v,1, x_v,2, x_v,3の3ビットを使い、各ビットが立っているか否かで、どの色かを表現。

3 2 3

, , ,

1 ( , ) E 1

1 _{v t} _{v t u t}

v t u v t

H A x A x x

  

 





 



 

 

曰く「物理系に乗せる方法を考える必要がある」

27/54

D-Waveの

量子アニーリング機械

 ユニットが平面上に格子状に並ぶ

 隣のユニットとは4ビットのみが結線されている

問題を埋め込む工夫が

必要

28/54

量子アナログ計算機のまとめ

 量子力学の原理に基づき、時間発展させることで、問題を解く

 どのような問題が解けるかは、使用する物理系に依存

デジタルコンピュータのように、

“プログラムすると何でも解ける”

ような汎用性はない。専用機。

 いろいろな問題を解くには、解きたい問題を解ける問題に変換するくふうが必要。

難しい問題簡単な問題

現代暗号の安全性の根拠

 基本的に、どんな暗号でも、時間をかければ、いずれ必ず解ける。

 安全であるとは『実時間で解くのは難しい』ということ。

 数学的な難しさに、安全性の根拠を求めることが多い

 本当に簡単に解けないかは、証明されていない（方法と、今の人類が知らないだけの可能性も）

この数学の問題は難しそうだ！

これ元にして暗号を作れば、きっと安全だ！

(6)

31/54

問題の難しさ

 『実時間で解くのは難しい』とは、どういうこと？

問題を解くのに必要な時間は、計算機の速度によって違うんじゃないの？

15と129813472では、因数分解するのに必要な時間は違ってくるんじゃない？

結局のところ、

『問題を解くのに必要な時間』を測るためのの尺度は何？

32/54

尺度

 物事を測るためには、何事にも尺度が必要。

重さ：単位はキログラム重等。

基本的にその物体に働く重力。

場所により秤の目は異なる。

質量：単位はキログラム等。

物体固有の値。

場所により秤の目は変化しない。

他にも、長さや明るさ、速度等、色々ある。

33/54

問題の難しさの尺度

 問題を解くのに必要な時間を測る尺度。

実時間で測る：

ある問題を解くのに、現在の計算機では、どれだけ時間が必要かを測る。

数学的に測る：

その種の問題を解くのに、ある動作が何回必要かを評価する。

ステップ数や主な動作を数えたりする。

理屈なので、物理的実現が不要。

34/54

問題とインスタンス

 因数分解問題

整数Xが与えられる。因数を1つ求めなさい

 具体的な因数分解問題

整数123456が与えられる。因数を1つ求めなさい。

この形の問題を解くには、

これだけの計算量が必要だ

この設定の問題を解くには、

これだけの計算量が必要だ

35/54

計算量の例 [1/2]

 nビットの長さの鍵で暗号化された暗号文ある。

 総当たりで正解の鍵を発見するには、何回ぐらい、『鍵を入力し復号しようとする』動作を試みればよい？

 入力：暗号化アルゴリズム

nビットの長さの鍵を利用するのだから、長さはn ビットぐらいはある。

 出力：正しい鍵

何回試みるか、n の関数として表現する

36/54

計算量の例 [2/2]

 nビットの長さの鍵だと、候補数は全部で2ⁿ個ある。

 総当たりするとなると、2ⁿ回程度、試す必要がある。

 nの指数時間ぐらいの手間がかかる。

→ こういうのを、『非常に時間がかかる問題』と言う

 1ビット鍵の長さが伸びると、

必要になる時間は2倍に！

 一方、多項式なら

『時間がかからない問題』

2ⁿは難しい n²は簡単

ビット数回数

(7)

37/54

各計算機の比較

38/54

物理的な実現の話 (1)

 古典計算機：

一家に一台を超えて広く普及。

さまざまなところでさまざまな用途で活躍中。

 量子デジタル計算機：

現在進行形で開発中。

数十ビットぐらい。実用的な問題を解くには不十分

 量子アナログ計算機：

D-Waveをはじめとして、実装が盛んに。

幾つかの企業は問題を解いている。

39/54

物理的な実現の話(2)

D-Wave

カナダのベンチャー企業

2007年2月に16qubit の実現を主張。

現在は512qubitと主張している。

本当に実現しているのか、評価は分かれている。

汎用量子計算機ではなく、特定の問題を解く専用機らしい。量子アニーリング専用機。

2013年、NASAやGoogle等が、量子人工知能研究所の設立を発表。D-Waveの機械を使用中。

40/54

物理的な実現の話(3)

 この数年で、急激に進んだ。

Intelが量子計算のチップを出荷（49量子ビット）

IBMがクラウドで使用できるにサービス開始

 D-waveの量子アニーリングの機械は大規模化

量子的なアナログ計算機

特定の用途向け。

最適化問題が解けるので、応用先は多い。

2000ビットぐらいある

（が、無条件で使える訳ではない）

因数分解問題

整数Xが与えられる。因数を1つ求めなさい

時間がかかると信じられている。

公開鍵暗号のRSAの安全性の根拠。

 量子デジタルコンピュータ：

フルスペックで完成すれば、一瞬で解く。

Shorのアルゴリズム。

ようするに、完成したら現在の公開鍵暗号はヤバイ。

データベース検索

時間がかかると信じられている。

 量子デジタルコンピュータ：

フルスペックで完成すれば、桁数半分ぐらいのステップ数で解く。Groverのアルゴリズム。

 量子アニーリング

理想的にできていれば、半分ぐらいの時間で解く。

関数f が与えられる。

f(x)=1 となる x を1つ発見せよ

(8)

43/54

その他

 『D-Waveの計算機を使ったら、xx倍高速に解けた！』

あるインスタンスに対して問題を解いているため、その形の問題すべてに早いかは示せていない。

早い可能性の証拠にはなる。

最適化問題として、いろいろ発表されています。

44/54

総評

 日常的な多くの用途や問題

コストや規模、速度を考えると

･･････古典計算機の圧勝

 一部の問題に対して

古典計算機では手に負えない一部の問題

･･････量子計算機の勝利

これからもお役に立ちます

因数分解データベース検索重要な問題も最適化

含まれている

45/54

量子通信

46/54

重ね合わせ状態の崩壊

日本でも、量子計算に関する研究は行われている。

「量子ビット開発」で検索してみよう。

47/54

重ね合わせ状態の崩壊

 人は、重ね合わせ状態を直に見ることはできない。

 観測という行為を行って、状態を知る。

 量子重ね合わせ状態は、観測すると崩壊してしまう。

…

量子重ね合わせ

ci

観測すると、

重ね合わせが壊れる。

48/54

量子通信

量子状態を通信するのが、量子通信。

さまざまな実験が行われている。

「量子通信プレスリリース」で検索してみよう。

Alice

Bob

あｓｄふぁｓｄＪｌｋｊぇｗｋｆ

量子状態をやりとりする

(9)

49/54

量子通信の実現

 さまざまな実験が行われている。

光子を用いた通信を利用する方式が有名。

1980 年代には数十センチの距離

2002 年には三菱電機により87km

2004 年には三菱電機により96km

2007 年にはロス・アラモス研究所により107km，

2006 年にはウィーン大学などにより144km，

2007 年にはNTT により200km

50/54

量子鍵配送

量子通信を利用して、通常の（古典的な）秘密鍵を共有するのが、量子鍵配送。

Alice

Bob

量子通信も利用して、

秘密鍵を共有

51/54

盗聴者が居た場合

 間に盗聴者が居た場合、重ね合わせ状態が壊れてしまい、正確に送られない。

 盗聴されているかを検知できる！

 盗聴されていたら通信をやめる。

Alice

Bob

送信

盗聴だ！

あれ？

おかしいぞ。

盗聴されてる？

52/54

その他の量子情報処理

 量子もつれ合い状態を利用した情報のやりとり

光子を飛ばさないで行うデータのやりとり

 量子ゲーム理論

人間が量子的な動作をするなら（つまり、人と人が量子力学的に繋がってるなら）何が起きるか。

 量子不正行為

量子計算の考え方や、量子ビットを用いて、ゲーム等でイカサマ行為をしよう。

演習：

課題と課題の提出

 感想文を書いて出すこと。

 未来の暗号と情報セキュリティはどうあるべきかを考えて書くこと。

 ファイル名は学籍番号の末尾にnをつけたもの。

情報セキュリティ 第14回