目次。
- 目次。
- はじめに。
- インターネットと暗号。
- 量子コンピュータの強み：状態の重ね合わせ。
- 量子コンピュータの弱み：状態の重ね合わせ。
- 救世主：ショアの因数分解アルゴリズム。
- ショアの因数分解アルゴリズム。
- まとめると…。
- ちゃんと勉強したい人向け。
この文章を読んで、面白い！役に立った！...と思った分だけ、投げ銭していただけると嬉しいです。
【宣伝】ギターも歌も下手だけど、弾き語りをやっているので、よければ聴いてください。
はじめに。
前に量子アルゴリズムである「ショアのアルゴリズム」を疑似実装したという文章を書いた。
そして、これは、「ショアのアルゴリズム」を一般の人向けに分かりやすく書いてみたつもりの文章である。1万5千字以上あるので、ご注意を。修論の半分くらい。
僕は海外大学院の物理学専攻の量子情報に進みたいと思っている。ショアのアルゴリズムを疑似実装した理由は、海外大学院出願において、生物系出身の僕でも、量子情報の分野でやっていけるということを示すためであった。その時は知らなかったが「ショアのアルゴリズム」を考案したピーター・ショア博士は、僕の第一志望の海外大学院の教授をされているらしい。ピーター・ショア博士は、数学専攻であって、物理学専攻ではないので、願書を読まれることはないと思うが...。
量子コンピュータができると、世界中の暗号が破られるとか、ブロックチェーン技術を基盤にしている暗号通貨（仮想通貨）が大暴落するとか…そんな話を聞いたことがあるかもしれない。（この文章では、ブロックチェーン技術の基盤になっている楕円曲線暗号の話はしない）
けれども多くの人は、「暗号通貨（仮想通貨）なんて持っていないし、暗号だなんて、よく分からないものは触ったことがないから、私には関係ない話」だと思っているかもしれない。
しかし、この話は、ほとんどの人に関係のある大問題である。仮に量子コンピュータで暗号が解読されるようになると、今の社会は崩壊する。そして、それだとむちゃくちゃヤバいので、量子コンピュータで破られない「耐量子暗号」が研究されている。
といってもピンとこないと思うので、まずはインターネットと暗号の話から。
インターネットと暗号。
日本の中で、インターネットと一切、関わりを持っていない人を探すのは困難だろう。お年寄りの中には、インターネットを使ったことがないという人がいると思うが、少なくとも、その人の周りにいる人やサービスは、インターネットと関わっている。
スマホやパソコンで、インターネットを使うと、YouTubeで動画が見れたり、Instagramでインスタ映えする写真を投稿できたり、Twitterでしょうもないことをツイートしたりできる。電子メールも、Amazonとか楽天といったオンラインショッピングもインターネットを利用したサービスである。インターネットは、現代の生活にはなくてはならないものである。
インターネットとは、「世界中のコンピュータ（スマホ・パソコンを含む）が相互接続された状態」を指す。世界中の人が繋がっていることによって、生活は便利になったが、新たな問題も生まれた。端的に言うと、繋がっている人の中には、あなたの個人情報を盗もうとしている人もいるわけである。
Amazonをはじめとしたオンラインショッピングで何か買い物をする状況を考える。買い物をするには、クレジットカードの情報をオンラインショッピング側に送らなければいけない。クレジットカードの情報は、家のパソコンとオンラインショッピングをつないでいる回線を使って送る。
さて、情報を送る回線は、誰のものだろうか。実は、あなたのものでも、オンラインショッピングのものでもない。第三者のものなのである。実は、オンラインショッピングの買い物をするときには、クレジットカードの情報を見ず知らずの第三者が用意した回線を使って送っている。
Wi-Fiの話をすると、もっと分かりやすいかもしれない。スマホをWi-Fiにつないだことがある人なら分かると思うが、特に東京とかは、W-Fiの電波が飛びまくっている。「通信料節約のため」と言って、「Wi-Fiの電波を出しているのは誰なのか」気に留めることなく、自身のスマホと接続している人が結構いるような気がするが、まさしくそれが見ず知らずの第三者の回路を使って、情報を送る行為である。
インターネットは、「“見ず知らずの人たち”が“見ず知らずの人たちが作った回線”によって相互接続された状態」である。
僕だって、渋谷のど真ん中で、Wi-Fiの名前（SSID）に「Tokyo Public Wi-Fi」なんて、それらしい名前をつけて、電波を飛ばすことができる。きっと何も知らない人たちは、僕のWi-Fiにスマホをつないで、情報を送るだろう。そして、情報が向こうから送られてくるのだから、盗むなんて簡単なことである。
インターネットで情報が盗まれるのは当然のこと。なぜなら、通信をするために見知らぬ人に情報を送っているから。それでも、インターネットを使いたいのであれば、たとえ盗まれても、中身が読まれないように情報に鍵（暗号）をつける必要がある。
インターネットには、暗号が必要不可欠なのである。
共通鍵暗号方式。
オンラインショッピングで買い物をするとき、オンラインショッピング側から「この鍵を使って、クレジットカードの情報に鍵をつけてください（暗号化）」と鍵を渡されるのが共通鍵暗号方式。渡された鍵のことを共通鍵という。客は、渡された共通鍵を使って、クレジットカードの情報に鍵をかけて送り、オンラインショッピング側は、送られてきた情報を先ほど渡した共通鍵を使って開け、クレジットカードの情報を得る。万が一、途中で悪い人に情報が盗まれてしまっても、鍵がかかっているので、解読ができない。
共通鍵暗号方式は、「鍵を閉める」鍵と「鍵を開ける」鍵が同一という特徴がある。これは、僕らが一般的に使っている鍵と一緒である。家の鍵だって、車の鍵だって、倉庫の鍵だって、扉を閉める鍵と開ける鍵は一緒のはずである。
しかし、この共通鍵暗号方式には、大きな弱点がある。それは、クレジットカードの情報を送る前に共通鍵を渡さないといけないことである。そして、この共通鍵の情報には、鍵がかかっていない（暗号化されていない）。もし途中で、悪い人に共通鍵の情報が渡ってしまったら、クレジットカードの情報に鍵をかけたとしても、中身を見られてしまう。「それでは、「共通鍵の情報」に鍵をかければいいのでは？（暗号化）」と思うかもしれないが、「共通鍵の情報に鍵をかける」共通鍵の情報には、鍵がかかっていないのである。「共通鍵の情報」に鍵をかける共通鍵の情報」に鍵をかけるにしても、「共通鍵の情報」に鍵をかける共通鍵の情報」に鍵をかける共通鍵の情報には鍵がかかっていないので、中身が見られてしまう。
友達同士だったら、どこかで会ってこそっと共通鍵の情報を渡せば、安全に通信できるが、オンラインショッピングは、数百万、数千万の客に対して、安全に鍵を渡さなければ、安全な通信ができないのである。そして、数千万の客すべてに決して盗まれることなく鍵を渡すのは不可能である。
秘密鍵暗号方式。
先ほど、共通鍵暗号方式は、家の鍵や車の鍵と一緒で、「鍵を閉める」鍵と「鍵を開ける」鍵が一緒であると言った（共通鍵）。
一方、「鍵を閉める」鍵（公開鍵）と「鍵を開ける」鍵（秘密鍵）を別にすることによって、公開鍵暗号方式の「公開鍵をどうやって安全に客に渡すか問題」を全く別の視点で解決したのが秘密鍵暗号方式。
まず、オンラインショッピング側は、「鍵を閉める」鍵（公開鍵）を全世界に公開する。「公開した鍵を使って、クレジットカードの情報に鍵をつけてください（暗号化）」と言うわけである。一方で、「鍵を開ける」鍵（秘密鍵）は誰にも見られないように隠しておく。客は、公開鍵を使って、鍵をかけて情報を送る。万が一、情報が盗まれても、悪い人が知っているのは「鍵を閉める」鍵（公開鍵）であって、「鍵を開ける」鍵（秘密鍵）ではないので、中身を見ることはできない。
「閉める鍵」と「開ける鍵」別々にしたことによって、「どうやって鍵をこそっと渡すか問題」は解決した。そもそも「鍵を閉める鍵」で鍵を開けることはできないので、堂々と渡せばいいである。
「とは言うものの「閉める鍵」と「開ける鍵」を別々にすることってできるの？」って思っている人もいるかもしれない。
それを可能にしたのが「RSA暗号」である。
RSA暗号。
この暗号は、考案者の頭文字をとって名付けられたらしい。ブラウザのアドレスバーを見れば、あなたがRSA暗号を使っているか知ることができる。アドレスバーが「http://」じゃなくて「https://」で始まれば、あなたはRSA暗号を使っている。ちなみに僕のブログは、「https://」で始まるので、この文章を読んでいるのであれば、あなたはRSA暗号を使っている。ちなみに「http://」で始まるRSA暗号を使っていないサイトはどんどん減っており、もうそんなサイトを見つけるのはちょっと難しいような気がする。
RSA暗号に必要なのは、数百桁の素数aとbである。このaとbからcとdという数字をつくり、aとbを掛け算する（）。そして、abとcという2つの数字を公開鍵として、全世界に公開するのである。客は、公開されたabとcという2つの数字を使って、クレジットカードの情報に鍵をかけ、オンラインショッピング側に送る。オンラインショッピング側は、abと公開していないd（2つ合わせて秘密鍵）の2つの数字を使って、鍵を開けて、情報を得る。
閉める鍵（abとc）と開ける鍵（abとd）が違うので、悪い人が情報を盗んだとしても、数字dが分からない限り、中身を見ることができない。
ここで勘のいい人は気づいたと思うが、RSA暗号は、絶対に破ることができる暗号である。公開鍵は、abとcという2つの数字である。そして、秘密鍵の1つであるdという数字は、aとbという2つの数字から作られている。つまり、公開されたabという数字をa×bの形に因数分解することができたら、秘密鍵の1つであるdを手に入れることができるのである。
しかし、RSA暗号は、絶対に破ることができるが、実は安全な暗号である。abという数字をa×bに因数分解するだけで、RSA暗号を破ることができるが、実は「数百桁の素数aとbを掛け合わして得られるabという数字をaとbの2つに因数分解する」のはめちゃくちゃ難しいのである。15を3×5に因数分解するのは、簡単であるが、RSA暗号に使われる素数は1桁ではなく、数百桁である。巨大な数を2つの巨大な素数に因数分解するアルゴリズム（問題の解き方）は知られていない。愚直に2、3、5、7、…といった具合に素数で割っていって、余りが0のものを探すしかないのである。
RNA暗号は、必ず破ることができるが、スーパーコンピュータを使っても数千万年とか数億年かけないと破ることができない。そのため、安全な暗号なのである。
しかし、それを脅かすのが量子コンピュータ…。
量子コンピュータの強み：状態の重ね合わせ。
現在のコンピュータ（古典コンピュータ）は、0か1かの「どちらか」の状態を取るビットを使って計算するのに対し、量子コンピュータは、0と1の状態を「同時」にとる（重ね合わせ）量子ビットを使って計算するので、現在のスーパーコンピュータを使うと数万年かかるような問題でも、数分で解けてしまうことがある。
「状態の重ね合わせ」と言ってもピンと来ないと思うので、たとえ話をする。「Aさんが歩きながら音楽を聴く」は、状態の重ね合わせだろうか？…一見、「歩く状態」と「音楽を聴く状態」の重ね合わせのように思えるが、実は違う。Aさんの足とAさんの耳が別々のことをやっているので、これは重ね合わせとは言わない。スーパーコンピュータは、並列処理を用いて、高速に計算を行うことができるが、それは膨大な数の計算するための回路を並列につないでいるからである。回路一つ一つは、一度に一つの計算しか行えない。つまり、同時に色々なことをやっているように見えて、その一つ一つの要素は、「ある一つの計算をする状態」しか取れないのである。
一方で、「Aさんは、南方向に歩きながら、北方向に歩く」というのが、量子力学で言うところの重ね合わせである。現実世界では、そんなことはできないが、不気味な量子の世界では、そのようなことが当たり前のように起こっている。そして、その不気味な世界の法則を使ったコンピュータが量子コンピュータである。量子コンピュータは、ざっくり言うならば、「を計算している状態」と「
を計算している状態」を同時にとることができる。スーパーコンピュータみたいに2つの計算回路が「
」と「
」を並列して行うのではない。一つの計算回路の上に「
を計算している状態」と「
を計算している状態」が幽霊のように重なり合っているのである。
RSA暗号は、絶対に破ることができるが、破るためには「巨大な数を2つの素数に因数分解する」というめちゃくちゃ計算時間がかかる問題を解かないといけない。これを解くには、愚直に2、3、5、7、…と地道に一つ一つ素数で割っていって余りが0になる素数を探さないといけない。これは素数の桁数が多くなるにつれて、計算時間がものすごく長くなる。スーパーコンピュータでも数千万年かけなければ、解けない問題である。
ここで登場するのが、量子コンピュータ。量子コンピュータは、一つの計算回路の上に「を計算している状態」と「
を計算している状態」が幽霊のように重なりあっているのだった。となれば、「巨大な数を2で割っている状態」と「巨大な数を3で割っている状態」と「巨大な数を5で割っている状態」と「巨大な数を7で割っている状態」と…が一つの量子計算回路の上に幽霊のように重なりあうことだって可能である。スーパーコンピュータを使って、RSA暗号に使われている巨大な数ab を1000兆個の異なる素数で割るためには、1000兆回の計算が必要であるが、量子コンピュータを使えば、巨大な数abを「1000兆個の異なる素数が重なりあった状態」で一気に割ることができるので、計算は1回で済む。
（と言っても、1000兆回の演算は、スーパーコンピュータにとって、大変な仕事ではない。神戸にあるスーパーコンピュータ「京」は、1秒間に難しい演算を1000兆の10倍、1京回行うとことができる。1京は巨大な数のように思えるが、桁数はたったの16桁で、RSA暗号に使われる素数の桁数、300桁に比べると、ものすごく小さい数である。ついでに言うと、この宇宙の原子の数を数え上げると90桁ぐらいの数になるらしいが、RSA暗号に使われる素数の桁数は、宇宙に存在するすべての原子の数と比べても圧倒的に大きい）
けれども、そんなことは関係ない。宇宙に存在するすべての原子よりも圧倒的に多い数の演算が必要だったとしても、量子コンピュータを使えば、あらゆる状態を重ね合わせて、一発で計算できてしまうのである。
量子コンピュータの弱み：状態の重ね合わせ。
RSA暗号に使われる素数は、300桁以上あるが、300桁ある数をどのように呼んだらいいのか分からないので、分かりやすい1000兆回の演算のたとえ話に戻る。
量子コンピュータを使って、「1000兆個の異なる素数が重なりあった状態」でRSA暗号に使われる巨大な数abを割って余りを求める計算を行うと、もちろん計算結果が出てくる。さて、計算結果はどうなっているだろうか？
ここで嫌な予感がした人は、その予感が的中する。1000兆個の状態の重ね合わせで計算を行うと、当然出てくる答えも1000兆個の状態の重ね合わせなのである。
今ここで、欲しいのは「1000兆個の異なる素数で巨大な数を割った時の余り」が重なりあった状態ではない。「余りが0」という1つの状態である。実は、1000兆個の状態の重ね合わせから1つの状態を取り出すのは、とても簡単である。1000兆個の状態が重なりあった状態を観測すれば、重ね合わせは自然と壊れてしまい1つの状態になってしまう。問題は、重ね合わせの状態が壊れて、出てきた1つの状態が「余りが0」という欲しい答えになっているか否かである。1000兆個の素数の中にabの因数が含まれているとしても、せいぜい2個である。つまり1000兆個の計算の内、欲しい答えが得られる計算は多くて2個しかない。「1000兆個の余り」が重なりあった状態から「余りが0」という状態を取り出せる確率は、大体500兆分の1。宇宙一運のいい人であれば、量子コンピュータで1回計算して、出力の重ね合わせを1回測定すれば、欲しい答えが得られるだろうが、運が普通の人であれば、「量子コンピュータで計算→出力の重ね合わせを測定」という過程を大体500兆回ぐらい繰り返さないと欲しい答えは得られない。
スーパーコンピュータが1000兆回計算しなければいけない問題であっても、量子コンピュータを使えば、1回の計算で済む。しかし量子コンピュータの出力は、1000兆個の答の重ね合わせになっていて、測定するとランダムに1つの状態になるので、欲しい状態を得るためには、量子コンピュータを1000兆回ぐらい動かさないといけない。
量子コンピュータの能力って、スーパーコンピュータと変わらなくない…？
救世主：ショアの因数分解アルゴリズム。
「RSA暗号に使われる巨大な数abを素数で一つ一つ割っていき、余りが0になるものを見つける」というアルゴリズムでは、量子コンピュータは、スーパーコンピュータと対して性能が変わらない箱である（問題の解き方のことをアルゴリズムという）。
この状況を解決し、量子コンピュータの利点を最大限に活かす救世主が「ショアの因数分解アルゴリズム」である。
ざっくり言うと、「因数分解の問題」を「周期性を求める問題」に上手いこと変換し、1000兆個の重ね合わせの状態から「欲しくない答えを取っている状態」を消滅させて、「欲しい答えを取っている状態」だけの重ね合わせ状態を得るという方法である。
重ね合わせの状態のちょっとだけ真面目な話。
まずは、0と1の重ね合わせから。これを数式で表すと以下のようになる。
AとBは、0と1がどれくらいの割合で重なりあっているかを示している（この説明は正しくないけども）。単に0の1の重ね合わせと言っても、1 : 1で重なりあっている場合もあれば、10 : 1で重なりあっている場合もある。もちろん1 : 10の時もある。例えば、Aが3、Bが1の時は、この重ね合わせの状態を測定すれば、90%の確率で0が得られ、10%の確率で1が得られる。袋に赤玉（0）が9個、青玉（1）が1個入っていて、袋に手を突っ込んで、1個取り出すという話にとても似ている。けれども、量子の世界の玉は、「赤色の状態」と「青色の状態」を同時に取っていて、誰かに観測された瞬間に、90％の確率で「赤色の状態」になって、10%の確率で「青色の状態」になる。
今までのアルゴリズムで得られる答の重ね合わせは、こんな感じ。
これをどうにかこうにか…
こんな感じにするのが、「ショアの因数分解アルゴリズム」である。
ショアの因数分解アルゴリズム。
僕が参考にした本は、前回も紹介した通り、佐川弘幸著『量子情報理論 第3版』（培風館）である。
後は、以下の記事も分かりやすかった。ただし、この文章は一般向けではない。
「因数分解の問題」をどうにかこうにか「周期性を求める問題」に変換する。
まずは、「指数」の話をする。高校の数学で文系の人であっても勉強するはずだが、きっと忘れている人も多いと思うので。
xのR乗（）とは、xをR回、掛け合わせた数を表している。2の3乗（
）ならば、（
）。Rは、分数でもよくて、
は、（
）を表してる。
もう一つ、思い出していただきたいのが、の因数分解である。確かこれは、中学校の頃にやったと思う。
の因数分解は、
である。これは、別にRが2でなくとも、こんな感じで因数分解できる。
これで下準備が整った。
をRSA暗号に使われている巨大な数abで割ると1余る。これを式で書くと以下のようになる。
1余るということは、から1を引いておけば、割り切れる。
両辺にabをかけると、
となる。そして、先ほどの因数分解の式を使うと、
となる。である。つまり
と
を掛け合わしたものは、aの整数倍とbの整数倍を掛け合わしたものになる。じゃあ、xとrを求めれば、aとbが求まるんじゃないかっていうのがショアのアルゴリズム。と言っても、xはほぼ適当な値（xはabと互いに素じゃないとダメ）を代入しておくので、実際はrだけを求めればいい。aとbは、もう忘れているかもしれないが、RSA暗号で使用する2つの巨大な素数である。aとbが分かれば、秘密鍵の1つであるdを作ることができ、RSA暗号は破られる。
「因数分解の問題」を「周期性を探す問題」へ改変。
ショアのアルゴリズムによって因数分解は、単純に巨大な数abを手当たり次第、素数で割っていくのではなく、rを求める問題へと改変された。
例えば、35という数字をに因数分解する場合を考える。もちろんRSA暗号に5と7なんて1桁の素数を使うと、一瞬で破られてしまうので、絶対にこんな数を暗号鍵生成に使ってはダメである。
xの値は、ほぼ適当に決めてもいいので3とする。を35で割ると、余りは3。
を35で割ると余りは9。
を35で割ると、余りは27。…といった感じで続けていくと、
の時に35で割ると余りが1になる。ちなみに
は、1であり、35で割ると、これも余りが1となる。
なので、rは12である。
3^12の次に余りが1になる数は何だろうか？その次は？…実は、
である。24、36、どちらもr(=12)の倍数である。つまり
、
、
、
、
…を35で割っていくと余りが1になる数は、12回ごとに現れる。これが周期性である。
さっきまで余りが1になる数に固執していたが、余りが3の場合も12回ごとに35で割ると余りが3の数が現れるし、9の場合も同様である。「3をr回かけたものを35で割ると余りが1になる」と言っていたが、実は「35で割って、余りが3になる、9になる数はそれぞれr回ごとに現れる」のである。もう一度言うと、これが周期性。
ショアのアルゴリズムには、2つの量子ビット列（レジスタ）を用いる。一つ目の量子ビット列は、0、1、2、3、4、5、…の重ね合わせの状態を取っている。2つ目の量子ビット列は、、
、
、
、
…を35で割ったときの余りの重ね合わせの状態を取っている。これを数式で書いてみると
この段階では、すべての状態が同じ割合くらい混ざりあっている。Cは無視してもらって大丈夫。この状態で2つ目の量子ビット列を測定する。先ほども言った通り、重ね合わせの状態を測定すると重ね合わせの状態が壊れて、ランダムに1つの状態になる。例えば、2つ目の量子ビット列を測定して、3という1つの状態になったとしよう。すると先ほどの数式は、下のようになる。
2つ目の量子ビットを観測したことによって重ね合わせの状態が壊れて、3という一つの数字になった。これによって2つ目の量子ビットの3以外の状態が消滅する。実は、1つ目の量子ビット列と2つ目の量子ビット列は、不気味な遠隔作用（「量子もつれ」）でつながっている。2つ目の量子ビットの3以外の状態が消滅したら、3以外の状態と不気味につながりあっていた1つ目の量子ビットの状態も消滅する。
まとめると、2つ目の量子ビット列を測定して3という数字が得られたとすると、3以外の状態は消滅する。そして、2つ目の量子ビット列と不気味につながっている1つ目の状態も消滅して、1つ目の量子ビット列は、「2つ目の量子ビット列の3という状態と不気味につながっている状態」の重ね合わせとなる。
グラフに書いてみるとこんな感じ。これが2つ目の量子ビット列の状態を測定する前の1つ目の量子ビット列の状態。横軸は、1つ目の量子ビット列の状態。縦軸が1つ目の量子ビット列を測定したときにある数が得られる確率。この場合、量子ビット列は、0、1、2、3、4、5、…2047という2048個の状態が同じ割合で重なりあっている。同じ割合で重なりあっているので、量子ビット列を測定して、0、75、435、1265が得られる確率は全て約0.0005（約0.05%）である。
2つ目の量子ビット列を測定して3という数字を得ると、1つ目の量子ビット列に対応するグラフはこのようになる。（むちゃくちゃ分かりにくいが12ごとに針が立っている）さっきは、あらゆる数がそれぞれ0.05%の確率で得られる可能性を持っていたが、2つ目の量子ビット列を測定してしまったことによって、多くの可能性が消滅してしまった。もう1つ目の量子ビット列を測定しても、5とか44みたいな数字が得られる確率は0%である。得られるのは、1、13、25、37といった「2つ目の量子ビット列の3という状態と不気味につながりあっていた状態」のみで、それぞれ約0.005（0.5%）の確率で得られる。
僕たちが欲しいのは、「3をr回かけた数を35で割ると余りが1」という文言中のrである。けれども先ほどの話をした通り、実は、余りが1になる数、3になる数、5になる数、…は、、
、
、
、
、…の列の中でそれぞれr回ごとに登場する。このグラフは、35で割って余りが3になる状態のみ生き残っていて、12ごとに針が立っている。僕らが欲しいのは、r、この場合は12という数字であるが、得られるのは1、13、25、37、…のどれかである。12ごとに針が立っているというこのグラフの周期性をどうにか取り出せないものか…。
「周期性を取り出す」…理系の人は、一発でピンとくるだろう。量子コンピュータ云々を抜きにして、古くから周期性を取り出すためにとある方法が使われていて、理系のほとんどの人は、大学で勉強しているはずである。
そう、フーリエ変換！
「量子フーリエ変換」で「周期性」を取り出す。
理系の人は、フーリエ変換の本を引っ張り出して、「くし型関数のフーリエ変換」を読んで頂ければ、一発で分かると思う。
例えば、左図の波。これは、2という周期を持つ波である。0から2の間に1つの波があって、0から4の間には2つの波がある。これをフーリエ変換すると右図のようになる。このグラフを見ると、「フーリエ変換する前のグラフは、周期2の波が100%混ざった状態」というのが分かるし、実際にフーリエ変換する前のグラフは、周期２のグラフである。
そして、先ほどの1つ目の量子ビット列のグラフをフーリエ変換するとこのようになる。横軸は、量子ビットの状態。縦軸は、ある量子ビットを観測する確率である。
（「周期が12なんだから、上の図のように12のところだけなんでとがらないの？」って思う方もいるかもしれないが、実際にはそうはならない。それは、フーリエ変換する前のとがったグラフが実は様々な周期の波の重ね合わせで出来ているのが原因。ややこしくなるので説明は省略）
つまり、先ほどのグラフをフーリエ変換すると1つ目の量子ビット列は、0、171、341、512、683、853、1024、1195、1365、1536、1707、1877という12種類の状態の重ね合わせになる。そして、それぞれの状態は、約0.08（約8%）か約0.06（約6%）の確率で得られる。最初は、2048状態の重ね合わせ、2つ目の量子ビット列を測定した後は、170状態の重ね合わせ、フーリエ変換後は12状態の重ね合わせ。随分と重ね合わせの状態の数が絞られてきた。
そして、フーリエ変換後のそれぞれの状態には、以下の関係がある。
つまり、とりあえずフーリエ変換後の1つ目の量子ビット列を測定すれば、どんな数が得られようと、間接的に欲しい答えであるrを求めることができるのである。実際のところ、0とか1024が測定されてしまった場合、うまくrを求めることができない。しかし、50%以上の確率で最終的な答えにつながるr = 12を求めることができるのである。単純に素数で割っていくアルゴリズムでは量子コンピュータから出てくる出力のほとんどが欲しくない状態の重ね合わせであったことを思い出してもらうと、これがどれだけすごいことか分かっていただけると思う。50%以上の確率で正しい答えに繋がるのであれば、量子コンピュータを2回動かすだけで、ある数abを2つの素数aとbに因数分解できるのである。
1つ目の量子ビット列を測定して、ある状態「数」を観測した後、連分数展開、ユークリッド互除法なんかをするが、ここら辺は本質的ではないので割愛。
まとめると…。
量子コンピュータは、状態の重ね合わせを使って、計算速度を飛躍的に上げることができる。しかしながら、出てくる出力も「欲しいもの」と「要らないもの」の重ね合わせ。そのため、量子コンピュータの力を十分に発揮するためには、出力の中に重なっている「要らないもの」の割合をできる限り0に近づけるための上手な問題解決の方法（アルゴリズム）が必要。
ショアのアルゴリズムは、「因数分解の問題」を「周期性を求める問題」に上手に変換した。このように変換し、周期性を取り出す方法として古くから使われている「フーリエ変換」を組み合わせることによって、「欲しくないもの」が量子コンピュータの出力に重なりあっている割合をできる限り0に近づけ、「欲しいもの（最終的な答えに繋がる周期の情報）」が重なりあっている割合をできるだけ高めたのである。
RSA暗号を破るには、膨大な量子ビットを制御する量子コンピュータが必要である。確かに量子コンピュータがあれば、ショアのアルゴリズムでRSA暗号を破ることができるが、そんな膨大な量子ビットを制御できる量子コンピュータの完成は、まだまだ先のことだと思うので、RSA暗号はしばらくの間は安全。
ちゃんと勉強したい人向け。
僕が読んだ本は、佐川弘幸著『量子情報理論 第3版』（培風館）。修論書いているときに読み始めたのだが、ものすごく面白くて、修論を放置して、一気に読んでしまった。よくない…。
「僕は『量子情報理論 第3版』で勉強したので、皆さんもどうぞ」っていうのは、余りにも酷な気がする。あくまでこの文章は、一般の人向け。ここでは、どういう道筋をとれば、『量子情報理論 第3版』を読めるようになるかに焦点をあてる。
高校数学（理系）と高校物理の一部。
さすがに理系の高校数学の知識がないと難しいと思う。微分積分とか極座標とか複素平面はちゃんとやった方がいい。それとベクトルは、むちゃくちゃ大事。けれども2次元ベクトル、3次元ベクトルに固執するのではなく、「この話は2次元、3次元ベクトルを例に使っているが、もしそれが4次元、5次元、…になったらどうなるのだろうか」という視点を常に持っていれば、後々楽になると思う。ちなみに新課程は複素平面をやるが、僕らはその代わりに行列演算をやっていた。行列演算は、次に出てくる線形代数で必要となる知識である。余力があれば、旧課程の行列演算の勉強もやっておくと、線形代数をやるときに、かなり楽になると思う。
高校物理は、（古典）力学と電磁気学、光学、量子論をやれば、十分な気がする。力学は、「ものごとをとりあえず数式に置き換えて考えてみる」という物理特有の文化に慣れるために必要。電磁気学と光学は、大学レベルのものを無理にやる必要はないと思う。けれども量子力学の本とかで、電磁気学と光学の話がちょくちょく出てくるので、高校レベルの素養はあった方がいいと思う。さすがに赤外線と紫外線とX線の違いを答えられないのでは、ちょっと厳しい。量子論は、僕らの時代の高校物理にはなかったが、新課程になって、カリキュラムに組み込まれたらしい。量子力学勉強の肩慣らしになるので、高校物理の量子論の話は、なんとなくでいいので読んでおいた方がいいと思う。
線形代数。
実は量子情報の土台になっている量子力学は、ほとんど「線形代数」。そのため、量子情報の本を読みたければ、線形代数の勉強をちゃんとやらないといけない。線形代数は、量子情報、量子力学以外にもあらゆる分野の基盤となっているので、ほとんどの理系の大学1、2年生は、必ず勉強する科目である。
僕が使っていた本は、三宅 敏恒著『線形代数学』（培風館）。この本は、ちょっと難しいのであまりおすすめしない。代わりに馬場敬之著『線形代数キャンパス・ゼミ』（マセマ）とかかいいんじゃないかと思う。ちなみに僕は、この本を読んだことはない。
僕は、線形代数の講義で「エルミート変換」、「ユニタリ変換」とかはやらなかった。代わりに量子力学の本を通じて、これらを勉強した。正直、「固有値」、「固有ベクトル」あたりまでちゃんと勉強すれば、量子力学の本は読めると思う。
大学レベルの微分積分。
まあ、量子情報で難しい微分積分が必要なのかと言われれば、微妙な気がする。
量子力学には、微分積分と仲良しの表現方法と、線形代数と仲良しの表現方法がある。量子情報に必要なのは、微分積分というより、線形代数なのだが、どういうわけか、ほとんどの量子力学の本は、微分積分と仲良しの表現方法を使って説明が始まる。そんなわけで、微分積分は、ちゃんとやった方がいいと思う。
僕が使っていた本は、雪江明彦『概説 微分積分学』（培風館）であるが、これも取っ付きにくいと思うので、馬場敬之著『微分積分キャンパス・ゼミ』（マセマ）なんかを読むのがいいのかもしれない。僕は、この本も読んだことはないが、本屋でよく見かけるので、多分いい本だと思う。
ちなみに線形代数と仲良しの表現方法から始まる量子力学の本を僕は、持っているのだが、この本は、最初の1冊目として絶対に選んではいけないと思う。難しい。
後は、微分方程式とか、フーリエ変換とか、複素解析とかの知識が必要であるが、ここら辺は分からなかったら、ネットで調べる程度で十分だと思う。
古典力学（ニュートン力学）。
量子力学を勉強する前に古典力学（ニュートン力学）を勉強すべきか否かは、悩ましい問題。量子力学を勉強するためには、古典力学で勉強したことを一旦、捨て去らないといけない。僕の周りでは、結構これができない人たちがいて、「高校の頃までは物理が好きだったけども、量子力学のせいで物理が嫌いになった」っていう話も時々聞く。
それじゃあ、最初から古典力学を勉強せずに量子力学を勉強すればいいような気がするが、量子力学の本のほとんどは「あななたちは、ちゃんと古典力学の勉強はしているはずだよね」といった感じで話を進めてくるので、「やっぱり古典力学は量子力学の前に勉強した方がいいのかなあ」って思う。それに加えて、さっきも言った「物事をとりあえず数式に置き換えて考えてみる」という物理の独特な文化は、古典力学をやることでしっかり身に着くと思うし、量子力学は、ちょこちょこ古典力学の話を参照しにやってくるので、結局はやった方がいいと思う。
けれども古典力学を勉強するときは、「量子力学を勉強するためには、今勉強している古典力学の考え方を捨て去らないといけない」ということはしっかり念頭に入れなければいけない。
僕は学部1年の頃、佐川弘幸著『力学 第2版』（丸善）で勉強した。説明が分かりやすいし、実は『量子情報理論 第3版』（丸善）と同じ方が書いた本なので、おすすめ。
量子力学。
何よりも大事なことが1つある。それは、「本屋で量子力学の本を買うときは、絶対に物理学系の本棚で本を選ぶ」ということである。本を開いて「引き寄せの法則」なんて書いてあったら、本を閉じて、その本棚から一目散に逃げなければいけない。
オカルト・スピリチュアル系の方々は、量子力学という言葉がお好きで「量子力学によるとあなたと私の波動が共鳴して、…」、「量子力学によると、引き寄せの法則が…」といった感じで、彼らの理論は、科学的に正しいと主張しているが、それは間違いである。少なくとも現段階において、オカルト・スピリチュアル理論と量子力学は、科学的には全く無関係である。
オカルト・スピリチュアル系をやりたいのであれば、自己啓発とか宗教系の本棚から量子力学と書かれてある本を選べばいいと思うが、科学、そして量子情報をやりたいのであれば、絶対に物理系の本棚から量子力学の本を選ばないといけない。
僕は、生物系だったので、量子力学関連の講義では、『〇〇〇〇〇 物理化学』という本を使った。伏字にしているが、生物・化学全般の人は、分かると思う。まず初めに言いたいことは、この本で量子力学の勉強は、やってはいけない。量子力学の勉強をしたいのであれば少なくともタイトルに「量子力学」と書かれてある本を選ぶべきだと思う。（〇〇〇〇〇の物理化学』に書かれてある量子力学は、オカルト・スピリチュアル系と違って正しいが、内容が量子力学の本から作られたメモ書きみたいにしかなっていないので、この本できちんと勉強することはできない）
初めて量子力学に触れるのであれば、中嶋貞雄著『量子力学Ⅰ・Ⅱ』（岩波書店）がいいと思う。古典力学が破綻して、量子力学が誕生する過程が丁寧に書かれてあると思う。しかし、量子力学に触れたことがある人からすると、ちょっと説明が冗長な感じがすると思う。僕は、『量子力学Ⅰ』の途中まで読んだことがあるが、冗長すぎて、途中で読むのをやめてしまった。
量子力学のさわりぐらいを知っているのであれば、猪木慶治『基礎量子力学』（講談社）がいいと思う。僕は、物理系の量子力学の講義にもぐりこんだことがあるのだが、そこでこの本が使われていた。これを読めば、『量子情報理論 第3版』（丸善）はスラスラ読めると思う。
量子力学の多くの本は、「古典力学の破綻→量子力学の誕生」といった歴史の話から始まって、微分積分と仲良しな表現方法で、説明を始めるのだが、先ほど出てきたJ.J. サクライ『現代の量子力学(上・下) 第2版』（吉岡書店）は歴史の話をすっ飛ばして、線形代数と仲良しな表現方法（ディラックのブラ・ケット表記）を使って説明を始める。量子情報で出てくるのは、主に「ディラックのブラ・ケット表記」なので、この本を読むのが近道な気がするが、この本は他に比べて、圧倒的に難しいので、おすすめしない。僕は学部3年の終わりに初版の上巻を読んだ。2版の上巻も持っているが、こちらはちゃんと読んでいない。
量子力学までやれば、『量子情報理論 第3版』を読み通すことができる。量子コンピュータ、量子情報に興味がある人は、是非挑戦してみてください。
この文章を読んで、面白い！役に立った！...と思った分だけ、投げ銭していただけると嬉しいです。
