情報セキュリティ第14回

(1)

情報セキュリティ第14回

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

はじめに

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

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

 量子計算機の実現方法

量子デジタル計算機

量子アナログ計算機

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

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

目次とキーワード

 はじめに

 登場人物紹介

古典計算機

量子デジタル計算機

量子アナログ計算機

 対戦ルール

ステップと時間

 対戦結果

 おわりに

本日の結論

量子計算機は、特定の問題に対してのみ、

高速に解を求める可能性がある

そのためには工夫も必要

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

 はじめに

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

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

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

 対戦ルール

 対戦結果

 おわりに

そもそも「計算」とは？

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

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

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

(2)

Church-Turing の提唱

 Turing機械とは。

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

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

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

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

Turing 機械

p

1 0 0 1 0 

有限制御部

（CPUに相当）

ヘッド

テープ

（メモリに相当）

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

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

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

Turing 機械の動作

0 0 0 0 0

0 0 0 1 0 0 0

ヘッド

有限制御部テープ

p q

テープの値を書き換える

ヘッドの位置が動く

動作

状態が変わる

古典計算機のまとめ

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

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

 モデルはTuring機械。

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

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

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

 はじめに

 対戦ルール

 対戦結果

 おわりに

量子って何か

 古典力学

マクロな現象の力学。

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

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

例：天体の運動

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

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

(3)

例：偏光板実験 (1)

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

 1枚の偏光板を

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

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

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

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

光？

例：偏光板実験 (2)

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

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

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

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

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

量子力学で説明可能

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

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

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

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

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

量子並列計算が可能。

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

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

世界は分裂している？

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

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

世界は常に分裂し、

重ね合わさっている！

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

その世界のうちの一つ

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

量子ビット (qubit)

1

0 

 

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

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

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



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

 0 1

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に相当）

ヘッド

テープ

（メモリに相当）

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

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

(4)

量子 Turing 機械の動作

0

0 0 0 0

0 0 0 1 0 0 0

c2

遷移確率

ヘッド

有限制御部

p,0,1,q,Rc



テープ

p q

状態pであり，ヘッドが0 を読んでいる時に

1 を書き込み，状態 q にして, ヘッドを右に動かす

c2

その遷移を行う確率は，

量子計算機

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

0 0 0 0

量子計算機入力

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

量子並列計算

出力

0 0 0 ¹

並列計算をするけど、

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

工夫が必要！

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

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

量子並列計算。

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

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

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

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

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

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

 はじめに

 対戦ルール

 対戦結果

 おわりに

アナログ計算とは

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

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

 例：釘とシャボン

1) 板と板の間に釘を2本通します 2) シャボン液につけます

2点間の最短経路に

膜が！

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

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

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

(5)

時間発展

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

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

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

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

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

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

0 1

( ) ( )

A t H B t H

問題例： 3 彩色問題

 地図が与えられます。

隣り合う国が同じ色にならないように、3色で塗り分けなさい。

 4色あれば、必ず塗り分けられる。3色だと、地図による。

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

  

 





 



 

 

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

色を塗る隣り合うなら違う色

D-Waveの

量子アニーリング機械

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

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

問題を埋め込む工夫が

必要

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

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

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

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

“プログラムすると何でも解ける” ような汎用性はない。専用機。

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

対戦ルール

 はじめに

 対戦ルール

 対戦結果

 おわりに

(6)

問題とインスタンス

因数分解問題

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

具体的な因数分解問題

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

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

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

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

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

尺度

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

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

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

場所により秤の目が変化する

（ので、条件が必要）

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

物体固有の値。

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

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

問題の難しさの尺度

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

実時間で測る：

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

数学的に測る：

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

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

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

難しいと簡単

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

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

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

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

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

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

 一方、多項式なら

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

2ⁿは難しい

n²は簡単

ビット数回数

対戦結果

 はじめに

 対戦ルール

 対戦結果

 おわりに

物理的な実現の話

 古典計算機：

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

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

 量子デジタル計算機：

現在進行形で開発中。

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

 量子アナログ計算機：

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

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

(7)

因数分解問題

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

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

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

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

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

Shorのアルゴリズム。

ようするに、完成したら現在の公開鍵暗号は不味い。

データベース検索

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

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

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

 量子アニーリング

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

関数f が与えられる。

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

その他

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

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

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

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

総評

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

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

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

 一部の問題に対して

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

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

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

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

含まれている

おわりに

 はじめに

 対戦ルール

 対戦結果

 おわりに

おわりに

 量子計算機とはどういうものかについて、ざっくりと説明をしました。

量子力学を用いて（特定の問題を）高速に解く。

 量子計算機は、どんな計算でも高速化してくれる夢の計算機では（恐らく）ありません。

 ただし、ある程度高速に解ける問題には、汎用性の高い問題が含まれています。

 今後の発展に期待。

(8)

43/44

量子通信

重ね合わせ状態の崩壊

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

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

重ね合わせ状態の崩壊

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

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

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

…

量子重ね合わせ

ci

観測すると、

重ね合わせが壊れる。

量子通信

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

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

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

Alice

Bob

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

量子状態をやりとりする

量子通信の実現

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

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

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

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

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

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

，

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

2007 年にはNTT により200km

量子鍵配送

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

Alice

Bob

量子通信も利用して、

秘密鍵を共有

(9)

盗聴者が居た場合

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

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

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

Alice

Bob

送信

盗聴だ！

あれ？

おかしいぞ。

盗聴されてる？

その他の量子情報処理

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

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

 量子ゲーム理論

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

 量子不正行為

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

51/44

演習：

52/44

課題と課題の提出

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

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

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

53/44

13 回目について

 先週の告知

【詳細は、経情グループウェアのお知らせ欄に、

7/21ごろを目処に掲載します】

 実態

20日午前に前半を公開。締め切りは7月30日夜

その後、後半を公開しました。締め切りは8月5日夜

54/44

試験について

 「学内で実施してはダメ」ということになりましたので、

以下のようになります。

全員が、Webによる試験

 安定したネットワーク回線と、パソコンとブラウザが必要です。

 アクセス方法とかは、今後、説明します。

来週、ログイン方法とか負荷テストとかしたい。

情報セキュリティ 第14回