量子コンピュータのShor’s Algorithmのできるまで。（3月11日更新）
どの分野でもそうだけど、同分野の研究者は会社や大学や研究組織の垣根を超えて交流して議論を戦わせる。特に米国の場合、それぞれの研究者は現在所属している組織に生涯とどまることは稀なので、常に自分の研究や興味に合致する場所を求めている。また、他の研究者との交流で、誘われて所属を変更することも多々ある。これは、米国で４０年以上大学院とその後職を得て数社を転々とした経験に基づく感想である。
量子コンピュータ(以後QC)の分野でも大差はない。たくさんの研究者がこの分野に登場するが、一度に全てを網羅するわけにはいかないので、今回は一番有名なShorのAlgorithmができるまでの話を書いてみる。これは、このAlgorithmの開発者であるPeter Shor教授は現在はMITの応用数学部に属している。ShorのAlgorithmの簡単な説明は以下で。お断り、このブログは難しいことをさらっと簡単に述べることをモットーとしており、技術的に不完全、いいかげんな部分を多々含むので、最初にそこを突っ込まれても、と言い訳をしておく。難しいことを数式を振り回して話をしている人たちのレベルを１０倍くらい抽象化しているので、ご了承を。
Shorのalgorithmをメチャクチャ簡単にいうと
暗号化
現在一番広く使われている暗号化の方式はRSA方式で桁数の大きな数字を２つの素数に因数分解するのは、メチャクチャ難しいことを利用している。因みに２つの素数を掛けてその数になるのを証明することは比較的容易であるが。因数分解は、桁数が大きいと実際にそれに掛かる時間が百年、千年、それ以上ということで、事実上不可能となることを利用している。
暗号の解読
上の話は現在我々が日常使用しているコンピュータ（古典コンピュータ、以後CC)の話だが、ShorのAlgorithmはQC上でこれを指数関数的にスピードアップしてRSA暗号の解読を可能にした。つまり、この因数分解を指数関数的に速く行うことを可能にした。
このため、大きなニュースとなって、現在の暗号が全て破られるのではないかとパニックになったが、このAlgorithmが実行されるためには、エラー訂正が可能で多くのqubit を持った完成度の高いQCが必要で最初のエラー訂正QCができるのは2030年以降とされており、さらに完成度が高まる2040-2050年までは実用はできないと予測されている。
Shor教授の経歴とどのようにして、QCに出会い、どのようにして暗号の分野に関わったのか。
このあたりの情報はShor教授のビデオ(短い版のこれや、長い版のこれ）による話や多々あるウエブ情報（例えばAWSのサイトにあるこれ）をもとにしたものである。最近はこれも追加した。
教授の簡単な経歴としては、1981年にCaltechで数学でBSを取得した。（因みにQC で有名なJohn Preskill教授は現在Caltechで教授職。）
1985年にMITでPh.D.取得、その後同年UC Berkeleyで1年間Post Doctor職。その後Bell研究所（以後ベル研）2003年より、MITで教授職。
以下は教授がQCに関わって行く過程である。
最初にQCを深く意識したのは、(このインタービューで教授が述べている)、時期ははっきりしないが、1989年以後そのすぐ後だろう。その当時IBMに在籍していたCharles Benett氏がBell研でFrancois Bessette氏, Gilles Brassard氏とLouis Salvai氏と開発した鍵配布（Quantum Key Distribution）Algorithmの講演をした時だと、このインタービューで教授が述べている。しかし、この時点ではまだQCに参入しようとは思わなかったそうだ。
これが変わったのは、1992年にUmesh Vazirani (現 UC Berkleyの教授）がベル研にやってきて、Bernstein-Vaziraniのアルゴリズムについて講演した時出そうだ。その時二人に面識があったかどうかは定かではないが、Vazirani教授がUC BerkleyでPh.D.を取得したのが1985年でその年にShor教授はBerkleyのPost Doctorで同じ大学にいた。
Vazirani教授のUC Berkeley での量子コンピュータの授業のビデオ
この授業のビデオはブログに直接は関係がないが、微に入り細に入り詳しく解説している。お薦め。もちろん、Shor’s Algorithmの解説もある。
その後教授は他の問題にもQCが応用できないのかと考えていた。その時Daniel Simon氏の論文が目に入った。それまではあまり進歩がなかったと述べている。
Simon氏のAlgorithmは複雑な問題の中で周期を求めるものであった。（この周期を求めることがShorのAlgorithmのなかで大きな意味を持つ）。そのことをこのビデオで述べている。Simon氏の論文は教授のAlgorithm開発に大きな影響を与えた。Simon氏は1993年のTheoretical computer science conference (STOC 1993)に論文を提出したが、受け入れられなかった。そのコンファレンスのProgram CommiteeにShor教授もいたのだが、反対多数で採用されなかった。その顛末は、Shor教授のビデオ(短い版のこれや、長い版のこれ）に述べられている。また、Simon氏側からの話はAWSのこのブログで述べられている。その後、Shor教授はSimon氏と議論して、両氏は次のFOCS1994 Annual IEEE Symposium on Foundations of Computer Scienceにめいめい論文を提出した。もしまたSimon氏の論文が受け入れられなければ、Shor教授の論文と合体させる予定だった。しかし、それぞれの論文は受け入れられて採択された。
FOCS 1993 なのか FOCS 1994なのか
まあ、大勢に影響はないのだが、単に記事やブログを読んで日本語でまとめるのはあまりにも芸がないので、色々精査すると、Simon氏の論文はFOCS 1993には見当たらない。そこで、1994年（FOCS1994)を調べると確かに掲載されている。なおこの論文はさらに改善されて、1997年のSIAM Journal on Computingの10月号に掲載されている。因みにSTOC1993は1993年の4月で、FOCS1994は1994年の11月だ。Simon氏もShor教授も、STOC 1993に投稿されたSimon氏の論文は採用されなかったと書いている。STOC1993にはShor教授の共著が２つ採用されている。残念ながら、Shor教授がSTOC1993のProgam Committeに属していたかは確認が取れなかった。
Simon氏の論文（現在はSimon’s ProblemともSimon’s Algorithmとして知られている）。人生は偶然の連続。Simon氏がSTOC1993に論文を提出しなければ、そこでShor教授がProgram Committeの一員でなければ、そこでSimon氏の論文が採用されていたら、などなど考えるとShor教授のAlgorithmは生まれなかったかもしれない。まあ、生まれたかもしれないが。。。そんなことを言えば、Shor教授がベル研にいなかったら、Bennett氏が講演に来なければ、Vazirani教授が講演に来なかったら、果たしてすんなりAlgorithmが開発されていただろうか。
