ap museum 理論冊子
東京大学工学部物理工学科・計数工学科4年有志
2014年度工学博覧会
i
まえがき
この冊子を手にとっていただき、ありがとうございます。
本年度より始まった ap museum では、私たちが専門的な内容をわかりやすく紹介しようという趣旨のもと、物理
工学、計数工学に関するトピックを学部生の手によって解説することを試みています。
量子情報科学とは、量子力学の原理を本質的に用いた情報処理に関する科学です。20 世紀初頭にかけて発見され
た量子力学は、主に原子スケールの極微の世界を記述する物理の分野で、今では物理学全体の最も重要な基礎になっ
ています。量子力学は Newton が発見した古典力学とは大きく異なる特徴を有しています。粒子の位置は一意的に
確定しない。測定によって状態が変化する。複数の状態の重ね合わせが取れる。このような奇妙な特性は、今まで情
報処理のあり方を大きく変えるポテンシャルを持っていることが次第に明らかになってきました。ただ、量子情報処
理を物理的に実現することは非常にチャレンジングな課題で、当物理工学科でも多くの研究室が日夜奮闘を重ねてい
ます。
本稿では量子力学と量子情報の一端を紹介いたします。最初に量子力学の基礎に解説し、続いて、量子回路の基本
的構成要素である量子ゲートについて説明します。そののち、量子情報の分野で最も目を引くトピックである Shor
のアルゴリズムと量子テレポーテーションを紹介します。
この冊子を読んでいただくことでこの分野に少しでも興味を持っていただけたなら幸いです。
紺野雄介
ii
目次
まえがき
第1章
i
量子力学の公理 (岡田将典)
1
1.1
キーワード . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
状態 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.3
具体例 1:偏光量子ビット . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.4
ブラケット表示 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.5
観測について . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2
1.6
量子計算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
1.7
具体例 2:スピン量子ビット . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
量子ゲートと測定 (山崎雄司)
4
2.1
キーワード . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.2
はじめに . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.3
量子ゲートと測定
4
第2章
第3章
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Shor のアルゴリズム (紺野雄介)
8
3.1
キーワード . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
3.2
はじめに . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8
3.3
Shor のアルゴリズム . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
3.4
おわりに . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
量子テレポーテーション (村本和也)
13
4.1
キーワード . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
4.2
はじめに . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
4.3
量子エンタングルメント . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
4.4
EPR パラドックス . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
4.5
量子ビットテレポーテーション . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
4.6
おわりに . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
第4章
参考文献
18
1
第1章
量子力学の公理 (岡田将典)
1.1 キーワード
量子、古典、状態、ブラケット表示、測定、偏光、電子スピン
1.2 状態
量子情報や量子コンピュータは、古典的な物理とは全く異なる (古典的な物理ではありえない) 方法を使います。
まず、量子力学的な「状態」のお話をしましょう。
1.2.1 古典論
量子論と古典論の決定的な違いは、我々人間が「測定」をすることによって、自然界の情報をいくらでも詳しく調
べられると考えているところです。野球のピッチャーのボールの球速は 150m/s のように正確に測定されています
し、あなたが今見ているこのポスターも、ちゃんと見たところにあると思うのが普通です。自分たちが「見た」もの
は、いくらでも信じられる。これが古典論の世界でした。しかし 20 世紀に入り、我々が「見る」ことが自然界に及
ぼす影響を無視できない世界にたどり着いたのです。
1.2.2 量子論
「見る」ことが自然界に及ぼすとはどういうことでしょう？これが最初に顕著に見えたのは、電子のようなとても
小さいものを見ようとしたときのことです。そもそも電子が見えるのは、光が電子にぶつかり、返ってきた光が目に
飛び込んできたときです。野球のボールやこの冊子ほど大きいものは、光がぶつかったところでびくともしません。
ですから、見たものは確かにそこにあると信じるのも妥当なことです。しかし、電子ほど小さいものになると光がぶ
つかることは一大事で、光がぶつかった勢いで、電子は吹き飛ばされてしまいます。そのため、電子がある場所を
通ったことは分かっても、電子を見た影響によって他のことは分からなくなってしまいます。上手い調べ方をすれ
ば、電子の様子をよく調べられるのではないか……と思いたいところかもしれません。しかし、このような小さな世
界を説明することに成功したのは、そもそも電子の位置を完璧に予測するのをあきらめ、この範囲にある確率が高
い、ということだけを予測する「量子力学」でした。20 世紀最高の物理学者と呼ばれる Einstein も、小さいものの
世界の動きを完璧に予測できる理論があるはず考え、一生をかけて量子力学を超えた理論を探しましたが、見つける
ことはできませんでした。量子力学のポピュラーな考え方では、電子はある特定の場所に存在しているのではなく、
広い範囲で測定される確率があり、それは人間が見るまで分からない、ということになります。なかなか直観に合わ
ず納得できないかもしれませんが、この考え方で自然界のことがとてもうまく説明できているのが事実です。古典的
第1章
2
量子力学の公理 (岡田将典)
な考え方では、うまくいかなかったのです。そして、この量子力学の気味の悪い考え方を利用してしまおう、という
のが量子情報の世界です。
1.3 具体例 1:偏光量子ビット
レーザーの光を偏光板に通してみます。偏光板はレーザーの光の向き (偏光) が偏光板と同じ向きなら全て通し、
直行する向きなら全く通さない、という性質を持っています。斜めを向いた光はどうなるかと言うと、ベクトルの考
え方で、斜めの光を縦と横に分け考えれば良いのです。偏光板の方向から θ だけずれているときには、同じ向きの成
分だけが通るので、電場の大きさは cos θ 倍、光の強度が cos2 θ 倍になります。
レーザーの光は十分強いので、偏光板の性質にとくに不思議なことはありません。光の偏光状態は決まっていて、
偏光板を通れる光だけ通り、通れない光は完全にシャットアウトします。
ここで、レーザーの光をだんだん弱くし光子一個が飛んでくる状況を考えると、どうでしょうか? 光子一個でもあ
る偏光状態が決まっているとして、偏光状態と平行か、垂直な光を考えたときには、あまり問題はありません。平行
ならば光は通りますし、垂直ならば光は通ることはできません。
ところが、ある角度 θ だけ傾いた光では、よくわからなくなってしまいます。光は一個しかないので、cos2 θ 分だ
け通るということはできません。実際にどうなるかと言うと、cos2 θ の確率で光子が通り、1 − cos2 θ の確率で光子
は通らないのです。この確率でしか予測できない状態は、先ほどの量子力学の解釈とよくマッチしています。量子力
学では、そもそも光子一個の状態は、縦の偏光と横の偏光が重ね合わせられているものだとして理解できます。
1.4 ブラケット表示
コンピュータでは、0 と 1 の二つを用いてあらゆる計算が行われています。量子コンピュータのビットに当たる、
量子ビット”qubit”の書き方を紹介します。
偏光を例にすると、水平偏光に 0, 垂直偏光に 1 を割り当てると、二つの状態を表現することができます。特に、
量子力学的な状態であることを強調して、普通は
横の偏光状態 : |0⟩ , 縦の偏光状態 : |1⟩
と書きます。縦か横か決まっていない状態は、
a |0⟩ + b |1⟩ (|a|2 + |b|2 = 1)
と書くことができます。係数 a や b の絶対値の二乗が、偏光板を通る確率になります。そのため θ だけ傾いた偏光
板で測定するときには、a = cos θ, b = sin θ となります。ちなみに、45 度だけ傾いていて、通る確率も通らない確率
も 1/2 となる偏光状態は、
1
√ (|0⟩ + |1⟩)
2
です。
このように、縦と横が同時に存在している状態を扱うのが、古典的な考え方と違うところです。
1.5 観測について
冒頭で、人間が「見る」ことが自然界に影響を及ぼす、と書いていました。このことについて、少し詳しく説明し
ましょう。偏光の例では、偏光板を通るまで状態が縦か横か決まっていない、
1
√ (|0⟩ + |1⟩)
2
1.6 量子計算
3
という状態が実現していました。ここで、偏光板を通すと、確率 1/2 で |0⟩ か |1⟩ になるのでしたね。このように、
偏光板を通ることで、量子力学でしかありえなかった重ね合わせの状態から、古典論の世界でも説明できる「普通」
の状態になります。
このように、状態を確かめられる (大きな) ものを使って、何があったか確認することを「測定」と呼んでいます。
私たち人間は、量子状態が見えるようなものと比べればとても大きなものです。そんな私たちが認識できるような情
報を得るためには、量子にとってはかなり大きいものと相互作用することが避けられません。そして、大きいものと
相互作用した量子状態は、必ず古典的な (重ね合わせではない) 状態になってしまいます。
従って、もう少し測定をはっきりと定義しておくと、量子状態がマクロな物体と相互作用すること、と言えます。
このとき、重ね合わせ状態が、ひとつの決まった状態に収縮してしまうことは、波束の収縮とも言われています。
ところで、なぜ波束の収縮が起きてしまうのか、なぜ大きなものでは量子状態が観測できないのか、ということ
は今日でも答えは得られていません。この問題は、デコヒーレンスの問題とも呼ばれ、今日でも研究がなされてい
ます。
1.6 量子計算
重ね合わせ状態を理解できると、量子計算の概念に触れることができます。今のコンピュータは、古典的な状態、
すなわち波束が収縮していて確定した状態を用いて計算しています。電圧の高低を、1 と 0 に対応させ、あらゆる計
算を行っているということは、あまりに有名ですね。ここで、一つの素子は 1 か 0 の一つの状態しか持っていませ
ん。1 と 0 の間の「0.5」のような状態は、古典的な (と言っても今も使われている普通の) 計算機ではありません。
鋭い方はピンときているでしょう。この 1 と 0 に、量子状態を利用することはどうでしょうか？古典的には、1 つの
素子では 1 つの情報しか表現できませんでした。2 つ素子があったときには、二つの情報です。しかし、量子的に
は、それぞれの素子で
1
√ (|0⟩ + |1⟩)
2
のように二つの状態の重ね合わせが実現すれば、2 × 2=4 で、4 個の状態をとり得るはずです。このような状態は、
1
1
1
√ (|0⟩ + |1⟩) ⊗ √ (|0⟩ + |1⟩) = (|00⟩ + |01⟩ + |10⟩ + |11⟩)
2
2
2
と表現することにしています。5 個の素子では、2 × 2 × 2 × 2 × 2=32 個、10 個の素子では 1024 個……N 個の素
子では、2N 個の状態を取り得るので、素子の数が増えると、量子状態の数は爆発的に大きくなります。
2N 個の状態があれば 2N 倍速く計算できる、と簡単に結論できるほどことは単純ではありませんが、それにして
も大きな可能性を秘めていることは間違いありません。この重ね合わせを利用した計算が、量子コンピュータが従来
のコンピュータと決定的に違う点なのです。
1.7 具体例 2:スピン量子ビット
他の量子状態として、電子のスピンも利用されています。スピンは、くるくる回ることのできる磁石のような性質
をもつものと考えてください。例えば、スピンが上向きのときに |0⟩、下向きのときには |1⟩ と書くことにすれば、量
子状態を表現することができます。上や下向きから傾いたスピンの場合には、重ね合わせた、
a |1⟩ + b |0⟩ (|a|2 + |b|2 = 1)
の状態になります。
4
第2章
量子ゲートと測定 (山崎雄司)
2.1 キーワード
Pauli gate、Hadamard gate、CNOT gate、エンタングル状態
2.2 はじめに
ここまでで量子力学の公理や量子ビットについて学んだ。この章では、それらを元に実際の量子回路を考えていく
際に必要な知識を身に付けることを目標とする。
2.3 量子ゲートと測定
2.3.1 概要
量子回路とは量子ビットを操作するモデルのひとつである [8]。以下では量子系としてはひとつまたは複数の量子
ビットのみを考える。 量子ゲートとは入力された量子ビットに対しなんらかの演算を施し、入力されたものに対応
した量子ビットを生成するものである。測定とは、得られた量子ビットに対し ⟨0|,⟨1| を作用させることでひとつの
値を得ることである。
2.3.2 量子ゲート
実際の量子回路で頻繁に用いられる量子ゲートには以下のものがあり、それぞれは 2 × 2 正方行列である。
なお、以下の本文で出てくる量子ビットは
( )
( )
1
0
|0⟩ =
|1⟩ =
0
1
であるとする。
1. Pauli gate(パウリゲート)：
σx =
(
0
1
)
(
1
0
σy =
0
i
)
(
)
−i
1 0
σz =
0
0 −1
(2.1)
の形で表される量子ゲートのことを Pauli gate と呼ぶ。最も基本的な量子ゲートで、後述する Hadamard
gate や CNOT gate を理解する上でも重要になってくる。これが出てくるたびに量子ビットに行列をかけた
計算をするのは面倒なので、上記の変換による量子ビットの変換をまとめると以下のようになる。
σx |0⟩ = |1⟩ σx |1⟩ = |0⟩ σy |0⟩ = i|1⟩ σy |1⟩ = −i|0⟩ σz |0⟩ = |0⟩ σz |1⟩ = −|1⟩ (2.2)
2.3 量子ゲートと測定
5
2. Hadamard gate(アダマールゲート)：
1
H=√
2
(
)
1 1
1 −1
(2.3)
の形で表される量子ゲートのことを Hadamard gate と呼ぶ。量子回路において頻繁に現れる変換である。回
路図は図 2.1 であらわされる。
図 2.1 Hadamard gate
この行列をよく見てみると Pauli gate を用いて書き直すことが可能なことがわかる。実際に書き直すと
1
H = √ (σx + σz )
2
(2.4)
となる。この形と前述の Pauli gate による変換の式から次のようなことがわかる
1
H|0⟩ = √ (σx + σz )|0⟩
2
1
= √ (σx |0⟩ + σz |0⟩)
2
1
= √ (|1⟩ + |0⟩)
2
1
1
= √ |0⟩ + √ |1⟩
2
2
1
H|1⟩ = √ (σx + σz )|1⟩
2
1
= √ (σx |1⟩ + σz |1⟩)
2
1
= √ (|0⟩ − |1⟩)
2
1
1
= √ |0⟩ − √ |1⟩
2
2
(2.5)
(2.6)
第2章
6
量子ゲートと測定 (山崎雄司)
3. CNOT gate(シーノットゲート,Controlled NOT gate )：ここまでに紹介した gate は 1 量子ビットに作用す
るものであったが、2 量子ビット以上に作用する重要なものもある。それが CNOT gate である [8]。2 量子
ビットにおける CNOT gate の行列表示は
1
0
CNOT =
0
0
0
1
0
0
0
0
0
1
0
0
1
0
(2.7)
がある。2 量子ビットの基底は |00⟩ , |01⟩ , |10⟩ , |11⟩ と取っている。これの回路図は図 2.2 のようになる。こ
図 2.2 CNOT gate
れだけだとなかなか意味がわかりにくいと思われるので、これを 2 量子ビット |00⟩, |01⟩, |10⟩, |11⟩ に作用さ
せることを考える。なお、上記の 2 量子ビットとは、ひとつを例に挙げて説明すると
( ) ( )
1
1
|00⟩ =
⊗
0
0
(
)
1 × |0⟩
=
0 × |0⟩
1
0
=
0 0
のように計算される。|01⟩, |10⟩, |11⟩ も同様にして計算される。これに (7) を作用させると、
CNOT|00⟩ = |00⟩
CNOT|01⟩ = |01⟩
CNOT|10⟩ = |11⟩
CNOT|11⟩ = |10⟩
のようになり、1 ビット目 (制御ビット) が 0 のときは CNOT による変換で 2 ビット目 (標的ビット) が変化
せず、1 ビット目が 1 のときは CNOT による変換で 2 ビット目が反転することがわかる。このような CNOT
は CNOT12 と書くこともある。CNOT13 や CNOT32 などといったような変換も存在している。
量子エンタングルメント
量子エンタングルメントとは、2 量子ビット系において
|α⟩ ⊗ |β⟩
2.3 量子ゲートと測定
7
の形で表すことのできない状態のことを言う [8]。
これまでに紹介した gate を用いることで、この状態を簡単に作ることができる。そのための回路図の一例を図 2.3
に挙げる。
図 2.3
量子エンタングルメント生成のための回路
この回路の 1 ビット目に |0⟩、2 ビット目に |0⟩ を入力することを考えると、まず 1 ビット目が Hadamard gate に
より
1
1
H|0⟩ = √ |0⟩ + √ |1⟩
2
2
と変換される。
次に 2 量子ビット状態
1
1
√ |00⟩ + √ |10⟩
2
2
に対し CNOT12 を作用させると
1
1
1
1
CNOT12( √ |00⟩ + √ |10⟩) = √ |00⟩ + √ |11⟩
2
2
2
2
となる。この状態は、1 量子ビット状態の積で書き表すことは決してできない。つまり、量子エンタングル状態が生
成していることになる。
8
第3章
Shor のアルゴリズム (紺野雄介)
3.1 キーワード
量子計算、量子アルゴリズム、素因数分解、計算量、暗号、セキュリティ、量子 Fourier 変換
3.2 はじめに
1994 年、米国のコンピュータ科学者 Peter Shor は素因数分解を多項式時間で行う量子アルゴリズムを提唱した
[2]。これは現在 Shor のアルゴリズムと呼ばれ、量子計算の威力を端的に示す例としてきわめて有名である*1 。本稿
では Shor のアルゴリズムの基礎を紹介する。
42211453675801 = 9775879 × 4317919
上記のように自然数 N は N = pq のように 2 つの素数 p, q の積に分解できる数だとする。2 進数で表わした時の N
の桁数を n とする。 N のみが与えられたとき、未知数 p, q を求めるのにどれくらいの計算量が必要だろうか。もっ
とも素朴なアルゴリズムとしては、N を 2 から N − 1 までのすべての自然数で割ってみて、割り切れるか調べるこ
とである。割り算の回数で計算量を見積もると計算量は 2n のオーダーであり、n に指数関数的に依存する。もう少
し考えると、割り算は
√
N 以下の整数のみについて行えば良いことがわかるので計算量は 2N/2 のオーダーにまで
削減できる。一般に計算量（の上界）が入力長 n の多項式で与えられるような問題は多項式時間で解けると呼ばれ、
効率よく解ける問題だとみなされる (これは理論上の話で、実用上は同じ多項式時間で解ける問題でも n2 と n100 で
は大きく異なるが)。多項式時間で解けない問題は、入力長 n が長くなるにつれて計算量が急激に増大するため、一
般に解くのが困難である。素因数分解の問題を（量子的でない）古典計算によって多項式時間で解く方法は見つかっ
ていない [7]。
素因数分解の困難性を逆手にとって、暗号に応用することが行われている。RSA 暗号*2 と呼ばれる公開鍵暗号
で、その安全性の根拠は素因数分解の計算量がきわめて大きいことにおかれている。もし量子計算によって素因数分
解が素早く行われるようになったら、この安全性は原理上は揺らぐことになる [1]。このような意味でも Shor のア
ルゴリズムは世界に大きなインパクトを与えた。
*1
そういえば、細田守監督の映画「サマーウォーズ」で、主人公が電車の中で Shor のアルゴリズムを勉強しているシーンが出てくる。後半
への伏線でもあるのだろう。
*2 N = pq は巨大な素数 p, q の積とする。(p, q) は受信者のみが知っている。適当な正整数 e を設定し、(N, e) を公開する。送信者は平文
M を M e mod N と暗号化して受信者に送る。受信者はまず ed ≡ 1 mod (p − 1)(q − 1) となる d を (p, q を知っていることにより)
計算する。Fermat の小定理から M ed ≡ M mod N となることが示せるので、これを利用して M を復元できる [7]。
3.3 Shor のアルゴリズム
9
3.3 Shor のアルゴリズム
3.3.1 概要
素因数分解問題と Shor のアルゴリズムの定式化にはいくつか種類があるが、ここでは主に文献 [8] に従って述べ
る。以下、x と y が N を法として合同である (x と y を N で割った余りが等しい) ことを x ≡ y mod N と書き、
x の N による剰余を x mod N と書く。また、GCD(x, y) は x と y の最大公約数をあらわすものとする。最大公
約数は Euclid の互除法で効率的に計算できる。
素因数分解問題
N = pq (p, q は素数) となる n 桁の自然数 N が与えられたとき、p, q を求めよ。
Shor のアルゴリズム
(1) x ∈ {1, ..., N − 1} を一様ランダムに選ぶ。
(2) x が N を割り切るならば x を出力して終了する。
(3) xr ≡ 1 mod N となる最小の自然数 r を量子計算によって見つける。
(4) r が偶数かつ ̸≡ ±1 mod N ならば、GCD(xr/2 − 1, N ) と GCD(xr/2 + 1, N ) が N を割り切るかどうか検査
し、割り切るならばそれを出力して終了する。そうでなければ (1) に戻る。
Shor のアルゴリズムは大きく分けて 2 つの部分からなる。ひとつは古典計算部分であり、純粋に数学的なテク
ニックによって素因数分解問題を位数計算という問題に変換させる部分である (1),(2),(4)。もうひとつが位数計算問
題を量子計算によって解く部分 (3) であり、Shor のアルゴリズムの核心となる部分である。
3.3.2 古典計算部分―素因数分解を位数計算に帰着させること
自然数 x に対し、xr ≡ 1 mod N を満たす最小の自然数 r を x の位数という。位数 r が偶数であり、しかも
xr/2 ̸≡ ±1 mod N ならば、(xr/2 + 1)(xr/2 − 1) ≡ 0 mod N となり、GCD(xr/2 − 1, N ),GCD(xr/2 + 1, N ) が
p, q を与える。x をランダムに選ぶとき、位数 r が上記の条件を満たす確率は 1/2 以上であることが知られている。
このことを利用し、Shor のアルゴリズムでは次のような手順を踏む。(1) で x をランダムに選ぶ。(2) で選んだ x
が (ものすごく低い確率だが)N の素因数でないか確認する。(3) において後述の方法で位数 r を計算する。(4) で r
が適切な条件を満たしていれば上記の原理で素因数を手に入れることができる。さもなければ (1) からやりなおす。
よって、素因数分解問題は位数 r を計算する問題に帰着される。次に位数を量子計算を駆使して求める。
3.3.3 量子計算部分―周期発見問題と量子 Fourier 変換
f (a) = xa mod N としよう。このとき、f (a) は位数 r を周期とする周期関数となることがわかる (位数の定義
より、f (a + r) = xa xr mod N = xa mod N = f (a))。よってより一般的な次の周期発見問題を解けばよいこと
が分かる。以下で、ZM = {0, 1, ..., M − 1} とする。
周期発見問題
関数 f : ZM → N は未知の周期 s ∈ N(ただし M は s で割り切れるとする) を持ち、
f (a) = f (a + s mod M ) を満たしている。このとき s を求めよ。
この問題を量子計算によって以下のように解決する。ポイントは (iv) の量子 Fourier 変換 (Quantum Fourier
第3章
10
Shor のアルゴリズム (紺野雄介)
Transformation, QFT) である。QFT は通常の (離散)Fourier 変換の量子バージョンでありユニタリ変換である。
通常の Fourier 変換がそうであるように、QFT も関数の周期性に密接に関連していて、周期性を抜きだすような役
割を持つ。*3
周期発見量子アルゴリズム
(i) 2 つの量子ビット列を用意する。第 1 の列は ZM の値を格納するためのもので、M の桁数分のビットを持つ。
第 2 の列は f (a) の値を格納するためのもので、それに十分な数のビットを持つとする。これら 2 つの量子ビッ
ト列に以下の重ね合わせ状態を生成する。
1 ∑
√
|a⟩|0⟩
M a∈ZM
(ii) f の出力を第 2 量子ビット列に書き込む。
1 ∑
√
|a⟩|f (a)⟩
M a∈ZM
(iii) 第 2 量子ビット列を計算基底で測定する。測定値を z とする。測定によって状態は
∑
1
√
|a⟩|z⟩
M/s a|f (a)=z
へと変化する。和は f (a) = z を満たすすべての a について取られている。
(iv) 第 1 量子ビット列に以下で定義される QFT を作用させる。
M −1
1 ∑ 2πiak/M
F |a⟩ = √
e
|k⟩
M k=0
QFT によって状態は
√ M
−1
s ∑
M
∑
e2πiak/M |k⟩|z⟩
k=0 a|f (a)=z
となる。f (a) = z を満たす a の集合を {a0 , a0 + s, ..., a0 + (M/s − 1)s} とし、等比数列の和の公式をつかっ
て a についての和を計算すると*4
√ M
−1
s ∑
M
∑
k=0 a|f (a)=z
e
2πiak/M
√ M
−1 M/s−1
s ∑ ∑ 2πi(a0 +ls)k/M
|k⟩|z⟩ =
e
|k⟩|z⟩
M
k=0
1
=√
s
l=0
∑
e2πia0 k/M |k⟩|z⟩
k|k は M/s の倍数
となり、k が M/s の倍数の成分のみ振幅が残る。したがって、第 1 量子ビット列を測定すると、M/s の倍数
がいずれか 1 つ得られる。
*3
*4
なお、細かい注意だが、そもそも s を知らないのに M を s の倍数にとることはできない。しかし、M を s に比べて十分大きくとれば、
M が s の倍数でなくても高い確率で正しい答えを得ることができる。
k が M/s の倍数の時のみ公比が 1 になることに注意すると、
∑
M 2πia0 k/M
M/s−1
e
|k⟩ (k は M/s の倍数)
l e2πia0 k/M |k⟩ =
∑
2πi(a0 +ls)k/M
e
|k⟩ = e2πia0 k/M (1 − e2πik )s
|k⟩ = 0
(k は M/s の倍数でない)
l=0
1 − e2πisk/M
3.3 Shor のアルゴリズム
11
(v) (i) から (iv) を適切な回数繰り返し、得られた M/s の倍数から正しい s を得る。
上記のアルゴリズムは多項式時間で実行できる (n の多項式程度の個数の量子ゲート数で実装できる) ことが知られ
ている。
3.3.4 例：N = 15 の素因数分解
上記の説明（特に量子計算部分）は抽象的だと思われるので、しばしば例として引き合いに出される N = 15 の場
合に Shor のアルゴリズムがどのように働くか見てみよう。これは文献 [4] でも解説されている。
まず、Shor のアルゴリズム (1) で例えば x = 13 と選ばれたとする。(2) で 13 は明らかに 15 を割り切らな
いことをチェックしたのち、(3) の位数計算に進む。すなわち、13r ≡ 1 mod 15 となる r を探す。そのために、
f (a) = 13a , M = 16 として、周期発見問題を解く (M の選び方は自由だが、こう選ぶと話が簡単になる)。以下で
その量子計算部分をみてみよう。
まず、4 個の量子ビットを持つ量子ビット列を 2 つ用意し、それぞれ第 1, 第 2 量子ビット列とする。全てのビッ
トを 0 に初期化する。(i) 第 1 量子ビット列の各ビットに Hadamard ゲートを作用させると、状態は
(i)
|0⟩|0⟩ −→
1 ∑
|a⟩|0⟩
4
a∈Z15
へと変化する。(ii) 次に、f (a) の出力を第 2 量子ビット列に書き込む。この操作は、ユニタリ変換 Uf |a⟩|0⟩ =
|a⟩|f (a)⟩ として実現されている。この操作を終えた後の状態をあらわに書くと、
(ii)
−−→
1
(|0⟩|1⟩ + |1⟩|13⟩ + |2⟩|4⟩ + |3⟩|7⟩ + |4⟩|1⟩ + |5⟩|13⟩ + |6⟩|4⟩ + |7⟩|7⟩
4
+ |8⟩|1⟩ + |9⟩|13⟩ + |10⟩|4⟩ + |11⟩|7⟩ + |12⟩|1⟩ + |13⟩|13⟩ + |14⟩|4⟩ + |15⟩|7⟩)
となる。(iii) 第 2 量子ビット列を測定する。今の場合、第 2 量子ビット列には |1⟩, |13⟩, |4⟩, |7⟩ の 4 種類があるの
で、測定によってこれらのいずれかひとつが確率 1/4 で得られる。なお、どれを得るかをコントロールすることはで
きない。測定によって例えば |4⟩ を得たとしよう。このとき、状態は
1
(|2⟩ + |6⟩ + |10⟩ + |14⟩)|4⟩
2
(iii)
−−→
へと変化する。(iv) 第 1 量子ビット列に QFT
1 ∑ 2πiak
e 16 |k⟩
4
15
F |a⟩ =
k=0
を作用させると、状態は (直接計算は面倒だが)
(iv)
−−→
1
(|0⟩ − |4⟩ + |8⟩ − |12⟩)|4⟩
2
となる。第 1 量子ビット列を測定すると、|0⟩, |4⟩, |8⟩, |12⟩ のいずれかが得られる。必要ならば同じ測定を何回か繰
り返して、M/s = 4 すなわち s = 4 がわかる。よって位数が r = 4 と求まった。
(4) GCD(13r/2 − 1, 15) = GCD(168, 15) = 3, GCD(13r/2 + 1, 15) = GCD(170, 15) = 5 より、15=3×5 と素因
数分解できた。x の選び方によってはうまくいかないときがあるので、その場合は新たな x を選んで最初からやり
直す。
第3章
12
Shor のアルゴリズム (紺野雄介)
3.4 おわりに
上でも例示した 15 の因数分解は物理的な実装に成功している [3]。一方、古典コンピュータでは解けないような巨
大な数の因数分解を行えるような量子回路を物理的に実現するのは、今もって非常に困難な課題である*5 。その主た
る原因は、量子系の状態の壊れやすさと制御の難しさにある。何らかのブレークスルーにより古典コンピュータを凌
駕する文字通りの量子コンピュータが誕生するかどうかは定かではないが、Shor のアルゴリズムをはじめとする量
子アルゴリズムが、量子系の制御技術の発達を刺激するとともに、古典力学にはなかった量子力学の不思議な特性を
浮き彫りにし、新たな光を当てた点についてはいずれにせよ大きな意義があるといえるだろう。
Shor のアルゴリズムのほかによく知られている量子アルゴリズムとしては、Grover の探索アルゴリズム (f (a) = 1
となるような未知数 a を探すアルゴリズム) などがある。これらについては、文献 [1] に詳しい。
図 3.1 周期発見を行う量子回路。後半部分が QFT に対応するが、細かい説明は省略する。図は [1] を参考にした。
*5
ここで述べたのとは異なる方法で量子力学を計算に取り入れたものとして、”D-Wave”と呼ばれる量子コンピュータが話題になっている。
(参考：http://itpro.nikkeibp.co.jp/article/NCD/20140407/548765/)
13
第4章
量子テレポーテーション (村本和也)
4.1 キーワード
量子ビット、量子エンタングルメント、EPR 状態、EPR パラドックス、Bell 不等式、量子ビットテレポーテー
ション
4.2 はじめに
量子テレポーテーションとはなんだろうか?初めてこの単語を聞く人は SF 小説の宇宙船のワープのような事をイ
メージするかもしれない。しかしこの量子テレポーテーションは、Newton の力学にも Einstein の相対性理論にも
矛盾しないごく普通の物理現象である。
おおざっぱに言うと量子テレポーテーションとは、情報の伝達手段の一種であり、これまでの古典的な情報伝達と
は一線を画した革命的な技術である（今の通信技術も最先端のものが使われているが区別するためにあえて古典的と
書いた）。量子テレポーテーションが完全に実用化されれば、通信速度は今よりも格段に上昇し、量子コンピュータ
を作ることができるようにもなる。
この革新的な技術を 1993 年に初めて提案したのは Charles Bennett という物理学者である。その後 1997 年に
Anton Zeilinger が条件付きの量子テレポーテーションに成功した。Zeilinger 教授は 1980 年代に物理工学科で放射
線に関する共同研究をしていたそうだ。当時物理工学科は放射線に関する研究で世界をリードしていた。しかし翌年
の 1998 年、当物理工学科の教授である古澤明教授が、無条件の量子テレポーテーションに成功した。（当時はカリ
フォルニア工科大学の客員研究員）
そして去年の 8 月、古澤教授の率いるグループが世界で初めて光量子ビットの決定論的なテレポーテーションに成
功した。従来のテレポーテーションでは確率的な方式であったが、この方式では決定論的、つまり光量子ビットが必
ずテレポートされる。つまり完全に新しいタイプの量子テレポーテーションなのだ。
今回はあまり深入りはせず、Bennett の考案した量子ビットテレポーテーションまでの説明にとどめるが、興味の
ある方はぜひ古澤先生の著書を読まれるといいだろう。
4.3 量子エンタングルメント
「エンタングルメント」とは日本語に直せば、
「もつれ」という意味であり量子テレポーテーションの仕組みを理解
するにあたってもっとも重要となる概念である。このもつれとは量子がある物理的な相関関係を持つことを意味して
いる。
一般的な話をしてもわかりにくいので具体的な話をしようと思う。まず二次元空間にある量子が x 方向に一定の
第 4 章 量子テレポーテーション (村本和也)
14
速度で移動していたとする（原子核でも光子でもいい）、そしてこの量子が何らかの作用を受けて二つの量子 A と B
に分裂したとする。このとき量子 A と B の間には運動量保存則が成り立っているので以下の関係式が成り立つ
xA − xB = 0
(4.1)
pA + pB = 0
(4.2)
これは量子エンタングルメントのもっとも単純な例なので特別な名前がついており、EPR（Einstein-Podolsky-
Rosen）状態と呼ばれている。
このエンタングル状態で重要なのは、一方の量子の物理量を測定すると他方の量子の物理量が自動的に確定すると
いうことである。つまり量子 A の位置を測定すると量子 B についての測定をせずとも量子 B の位置を決めることが
できるのである。しかしここで注意しておきたいのは、量子 A の位置を測定した瞬間に不確定性原理により量子 A
の運動量が不確定になってしまい、量子エンタングルメントがなくなってしまうことである。
またこの量子エンタングルメントは二つの量子間の距離がいくら離れていても成立しうるが、A の測定結果を B
に伝えるためには古典通信を用いるほかないので、量子 A の測定をするとその情報が一瞬で量子 B に伝わる（つま
り情報が光速を超えて伝わる）などという相対性理論に矛盾した物理現象は起こらないのだ。
なおこの量子エンタングルメントは三つ以上の量子に対してももちろん成立させることができ、古澤研究室では世
界で初めて 9 個の光子間の量子エンタングル状態の生成に成功した。
4.4 EPR パラドックス
この量子エンタングルメントに関して Einstein などの過去の物理学の大家を悩ませた問題がある。それがこの
EPR パラドックスと呼ばれる問題である。量子論において、物理量の測定は波束の収縮として理解されるが、量子
エンタングルメントにおいて一方の何らかの物理量を測定した時に波束の収縮が光速を超えて、文字通り一瞬で伝わ
ると考える人が多くいた。しかし光速を超える相互作用は相対論では否定されており、この点で長い間パラドックス
とされてきた。Einstein もこの点がなかなか腑に落ちなかったらしく、量子エンタングルメントのことを「気持ち悪
い」と表現していたそうだ。
このことを決定論的、つまり古典論的に説明するために考えられたのが実験者は決して観測できない「隠れた変
数」が存在するという考えである。この考えはアインシュタインなどの決定論の支持者に多く支持されていた。つま
り「隠れた変数」を観測することができないがために一見情報が光速を超えて伝わっているように見えるが、実際は
そうではないという考えである。
Bell 不等式と呼ばれる不等式がある。この不等式の詳しい説明をするとメインテーマから外れてしまうので割愛さ
せていただく。もし上述の「隠れた変数」が存在するならば必ず成立するという不等式なのであるが、Alain Aspect
は光子対を用いた実験でベル不等式の破れを観測した。つまり「隠れた変数」は存在しないことが証明されたのだ。
この量子論において成り立つ相関関係は EPR 相関と呼ばれている。ただし古典論と矛盾しているというわけでも
ない。
この一見これまでの物理学と矛盾しているようにも見える不思議な相関関係をうまく利用する事で量子テレポー
テーションを実現できるのだ。
4.5 量子ビットテレポーテーション
これから Bennett の考案した量子ビットテレポーテーションの話に入ることにしよう。現実的にどう実現するか
の話の前に原理的な説明からはじめていこうと思う。
4.5 量子ビットテレポーテーション
15
量子ビット |ψ⟩ とは直交したふたつの状態 |0⟩ と |1⟩ を用いて、
|ψ⟩ = c0 |0⟩ + c1 |1⟩
(4.3)
と表される。ただし、c0 、c1 は |c0 |2 + |c1 |2 = 1 を満たす複素数である。この二つの状態には、前述したように原子
のスピンや光の偏光方向などが用いられる。
まず、以下にもっとも基本的なエンタングル状態を量子ビットで表した 4 つの Bell 基底を紹介する。
|ϕ+ ⟩ =
|0⟩A |0⟩B + |1⟩A |1⟩B
√
2
(4.4)
|ϕ− ⟩ =
|0⟩A |0⟩B − |1⟩A |1⟩B
√
2
(4.5)
|ψ + ⟩ =
|0⟩A |1⟩B + |1⟩A |0⟩B
√
2
(4.6)
|ψ − ⟩ =
|0⟩A |1⟩B − |1⟩A |0⟩B
√
2
(4.7)
添え字の A、B はそれぞれ量子 A、B の量子ビットであることを表している。つまり上記の Bell 基底は量子 A、B
の量子エンタングルメントを数学的に表したものであり、4 つの基底は |00⟩AA , |01⟩AB , |10⟩AB , |11⟩AB で張られる
空間の正規直交基底になっている。これらを用いて量子ビットテレポーテーションを数式で説明する前に、まず言葉
で概要を説明することにしよう。
エンタングルしている量子ビット A、B があるとする。情報の送信者を Alice、受信者を Bob と名付ける（量子情報
の世界ではこのように名づける風習がある）
。量子ビット A は Alice の手元に、量子ビット B は Bob の手元にある。
また Alice が Bob に送ろうとしている量子ビット X（つまりアリスがボブに送りたい情報）を |ψ⟩X = a |0⟩X +b |1⟩X
とする。ただし a, b はともに複素数であり規格化されている。
一番大切なことなのだが、量子テレポーテーションとは Alice が Bob に量子ビット X「そのもの」を送信するこ
とではなく、量子ビット AB 間のエンタングルメントを用いて量子ビット X の状態をボブの手元にある量子ビット
B で「再現」することなのだ。手順としては、量子ビット X を量子ビット A と何らかの方法で相互作用させ X と
A を強制的にエンタングルさせ、その後 X と A のエンタングル状態を測定することにより A とエンタングルして
いる B の状態を割り出すことができる。そして B の状態に対してに適切なユニタリ変換を施すことにより X の状態
を B で再現することができるのである。これは量子ビット X そのものは送信せずに、Alice から Bob に実質的に量
子ビット X の情報を伝達できたことになっている。ここで Alice が Bob に情報を送ったと言えるようになるために
は、Bob が量子ビット X の係数 a, b を知ることができればいい、ということを確認しておこう。
なお、Alice が測定した X と A のエンタングル状態がなんなのかを Bob に伝えるためには古典通信を用いなけれ
ばならない。量子テレポーテーションとは量子エンタングルメントと古典通信を組み合わせた技術なのである。
このような話をしても初めてこの話を聞いた人は何が何だかわからないと思うが、これから詳しく述べていこうと
思う。そのあとでもう一度ここを読み返してみると最初よりもイメージがつきやすくなっているはずだ。
具体的に数式で追ってみよう。量子ビット A と B のエンタングル状態は式 (4) で表される |ϕ+ ⟩ の状態にあると
する。まず量子ビット A と X をアリスが強制的にエンタングルさせたとすると、量子ビット A、B、X はある相関
関係を持つことになるので三つの量子ビットの状態は以下のように書き換えることができる。（なお、実際にどう実
現させるかについての話を始めるとかなり複雑になってしまい今回のページ数では説明しきれないのでここではおい
第 4 章 量子テレポーテーション (村本和也)
16
ておくことにしよう。）
(a |0⟩X + b |1⟩X ) ⊗
[
|0⟩A |0⟩B + |1⟩A |1⟩B 1 |0⟩X |0⟩A + |1⟩X |1⟩A
√
√
=
⊗ (a |0⟩B + b |1⟩B )
2
2
2
|0⟩X |0⟩A − |1⟩X |1⟩A
√
+
⊗ (a |0⟩B − b |1⟩B )
2
|0⟩X |1⟩A + |1⟩X |0⟩A
√
+
⊗ (a |1⟩B + b |0⟩B )
2
]
|0⟩X |1⟩A − |1⟩X |0⟩A
√
+
⊗ (a |1⟩B − b |0⟩B )
2
[
1
=
|ϕ+ ⟩XA ⊗ (a |0⟩B + b |1⟩B ) + |ϕ− ⟩XA ⊗ (a |0⟩B − b |1⟩B )
2
]
+
−
+ |ψ ⟩XA ⊗ (a |1⟩B + b |0⟩B ) + |ψ ⟩XA ⊗ (a |1⟩B − b |0⟩B )
この最後の式をよく見ていただきたい。量子ビット A と X のエンタングル状態が 4 つの Bell 基底のいずれかで
表され、さらにもともとは量子ビット X の持っていた情報である係数 a、b がいつの間にか量子ビット B の持つ情
報へと変化しているのだ。語弊を恐れずに言うと Alice の持ってた情報が Bob に移っていることになるのだ。この
言い方では多くの人が誤解してしまうと思うのでもう一つ大切なことを補足しておくと、この段階では Bob はまだ
何の情報を得ることもできない。係数 a, b がどちらのビットの係数なのか、係数 b についている符号はプラスかマイ
ナスかが全く分からないからである。なお、量子ビット X の初めの状態 |ψ⟩ は X と A を強制的にエンタングルさせ
た段階で変化してしまっておりもはや X から情報を引き出すことはできない。
それでは Bob が情報を得るためにはどうしたらいいのだろうか、それにはいくつかの操作が必要になってくる。
まず一番初めに必要になるのは A と X が 4 つの Bell 基底のうちどのエンタングル状態にあるのかを知ることで
ある。この測定には、先ほどの Bell 不等式を考案した John Stewart Bell にちなんで Bell 測定と呼ばれている。量
子テレポーテーションにはこの測定が無くてはならないのだが、残念なことにこの測定の実現は困難である。
次に必要なのは Alice が Bob に Bell 測定の測定結果を伝えることであるが、これに関しては Bob がエベレスト
の頂上やマリアナ海溝の奥底にいるといった稀な事態でなければ技術的な制約はないと言っていいだろう。
そしてこの情報を受け取った Bob は量子ビット B がどの状態にあるのかを知ることができる。その量子ビットに
たいしてあらかじめ決められたユニタリ変換を施せば、量子ビット X の初めの状態 |ψ⟩ を量子ビット B を使って
再構成することができる。あらかじめ決められたユニタリ変換とは今回の場合は次の四種類である。[1]:何もしない
(恒等変換)[2]:位相反転 (+ と-の入れ替え)[3]:ビット反転 (|0⟩ と |1⟩ の入れ替え)[4]:[2] と [3] 両方を行う。ユニタリ
変換とは数学的には異なる Hilbert 空間の間の同型写像として定義されるがここではユニタリ変換とは何かとは考え
る必要はない。
この 4 種類のうちの適切な操作を施すことで |ψ⟩ を再現することができるのだ。たとえば A と X のエンタングル
状態が |ϕ− ⟩ にあるという測定結果を Alice が得てそれをボブに伝えたとき、Bob は手元にある量子ビット B の状態
が a |0⟩B − b |1⟩B にあるのだと知ることができる (この段階では Bob はまだ a, b の具体的な値は知らない)。そして
この状態に対しては [2] の位相反転を施せば Alice が Bob に伝えたかった |ψ⟩ を再現できる。
中には X を直接 Bob に送ればいいと考える人もいるだろうが、量子ビットそのものを送ろうとすると伝送途中で
外界との何らかの相互作用により量子状態が容易に崩壊してしまうため Bob に |ψ⟩ の情報を伝えるのはほとんど不
可能なのだ。
4.6 おわりに
17
4.6 おわりに
量子テレポーテーションを用いることにより情報伝達の効率がどれほど上がるのか、Zeilinger 教授の量子テレ
ポーテーションと古澤教授のそれの違いはなんなのか、決定論的なテレポーテーションとは何なのか、などといった
疑問がたくさん浮かんできていることであろうがすべてを書き尽くすのはページの制約上不可能なので、省かせてい
ただくことにする。量子テレポーテーションに関しては多くの本 [5, 6] が出版されているのでそれらを参考にしても
らいたい。
この記事を読んで量子テレポーテーションや物理工学科の研究に少しでも興味を持ってもらう事ができたならばこ
れに勝る喜びはない。
18
参考文献
[1] I. L.Chuang M. A. Nielsen. Quantum Computation and Quantum Information. Cambridge, 2010.
[2] P.W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. pp. 124–134, 1994.
[3] Lieven M. K. Vandersypen, Matthias Steffen, Gregory Breyta, Costantino S. Yannoni, Mark H. Sherwood,
and Isaac L. Chuang. Experimental realization of shor’s quantum factoring algorithm using nuclear magnetic
resonance. Nature, Vol. 414, No. 6866, pp. 883–887, 2001.
[4] 宮野健次郎, 古澤明. 量子コンピュータ入門. 日本評論社, 2008.
[5] 古澤明. 量子テレポーテーション. 講談社, 2009.
[6] 古澤明. 量子光学の基礎. 内田老鶴圃, 2013.
[7] 細谷暁夫. 量子コンピュータの基礎. サイエンス社, 第 2 版, 2009.
[8] 石坂智他. 量子情報科学入門. 共立出版, 2012.
© Copyright 2024 ExpyDoc
