C&C受賞記念講演行ってきた Aho編 (1/3)

目次

Aho編: ここ
Hopcroft編:
pandaman64.hatenablog.jp
Ullman編:
pandaman64.hatenablog.jp

NECのC&C財団が出している賞をAho, Hopcroft, Ullmanの三人が受賞したのでその記念講演.
2017年度 C&C賞 受賞記念特別講演会 「若きコンピュータサイエンティストたちへのメッセージ」を見よ.

この3人は有名な教科書を書いていて,例えばAhoはドラゴンブックの著者だしHopcroftとUllmanが書いたオートマトンと計算理論の教科書を今期の講義で使っている.
以下講演のメモ,自分が興味あることだけメモって知ってることは書いてないので内容には偏りがあります.

メモ

会場は最前列が関係者席で2列目から自由席だったので,2列目ど真ん中という最高の位置を確保.
講演の開始数分前に3人が入ってきたらなんと目の前に着席.
毛穴まで見える!*1

最初に座長がうだうだ紹介したあと,講演本体のスタート.
トップバッターはAho.
Ahoの若者へのメッセージは「最高の人間と働けるところにいけ*2」とのこと.

掴みはインターネットの話から.
全人類の半分以上がインターネットを使っていて,それはネット越しに様々なサービスにアクセスするためである.
それらのサービスはソフトウェアに依存しており,コードベースはどんどん肥大化している.
巨大なソフトウェアの行数を調べた研究*3によると,

にもなる.
これらのソフトウェアはみんなアルゴリズムによって構成されている.
アルゴリズム大事*4

アルゴリズムが何故大事かというと,計算効率に関わってくるからだ*5
Aho–Corasickという文字列マッチングアルゴリズムがある.
これはCorasickが見つけたもので,ある日相談を受けたので「そのままこのアルゴリズムの研究を続けなさい」と言った.
その後Ahoが一般化した.

AWKのAはAhoのA←かっこいい
AWKはパターンとアクションを組にしたものを並べて記述する.
AWKの文字列マッチングはPythonPerlと比べて極めて速い.
アルゴリズムの力*6

ここからは量子コンピュータの話をします.←マジ????????
量子コンピュータの計算モデルは量子力学に基づいていて,状態は複素ヒルベルト空間で表現.
状態の変化はユニタリ行列を掛けることで表される.これは可逆だね.
複数のQubitをまとめた系はヒルベルト空間のテンソル積.なので計算基底が 2^nで増えていく.
測定によってQubitから古典bitに落とすことができる.測定は可逆ではない.

量子コンピュータの嬉しいところは古典よりも速く計算できる分野があるところ.
因数分解の現在見つかっている最良の古典アルゴリズムは指数オーダー*7なのに対し,量子コンピュータ(Shor's Algorithm)だと O(n^3)で解ける.
今の暗号は因数分解の困難さに依っているので量子コンピュータができると大変.1GHzの量子コンピュータがあるとすると,1024bitの因数分解が31時間で終わる.
なので,今では耐量子*8暗号が考えられている.

量子コンピュータのモデルにも色々ある*9
一つは量子回路.
量子断熱計算というのもある.DWaveはここに属する.
Microsoftがやっている量子コンピュータはTopological Quantum Device*10というもの.
トポロジカル量子計算は一つの粒子を二つに分裂させたquasiparticleを使って計算を行う.
バイス上ではquasiparticleを並べておき,そのうち一つをつまんで他のquasiparticleの周りをぐるっと周らせる*11
この回転が量子ビットにユニタリ変換を加えることに相当する.
最後に二つに分裂したquasiparticleを一つに戻すと計算結果の量子状態が得られる.
ぐるっと周らせるquasiparticleは一つだけで量子回路と等価になることが知られている.

トポロジカル量子計算では,どのquasiparticleの周りを周らせるかだけが重要で,実際の周るルート(ノイズが乗る)は関係ない(ここがトポロジー).
なのでノイズに対して強いだろうと言われている.
一方量子回路の場合は量子誤り訂正のために10倍ぐらいはQubitが必要.

量子プログラミングにもコンパイラ必要.
高級言語→Device-independentな言語(QASMなど)→Device-dependentな言語(QPOL)→具体的なデバイス用の記述
と変換していく.
量子プログラミングにはコンパイラだけでない開発スタックが必要で,例えばシミュレータが必要.
MSのLiquidはこの開発スタックの一つ.
LiquidはKrystaというMSコロンビアの人がメインメンバーの一人としてやっている*12
MSはVisual Studioに統合した量子プログラミングの開発スタックを来月公表予定.

最近やってる分野としてはQuantum Approximate Optimization Algorithmがある*13
難しい組み合わせ最適化問題を解く.

この本がお勧めらしい

Homo Deus: A Brief History of Tomorrow

Homo Deus: A Brief History of Tomorrow

感想: 量子コンピュータの話を聞くとは全く思ってなかったので興奮した.量子プログラミング言語チューリング賞取りたい!!!!
あとHopcroftの講演中に飲み終わった紙コップを口元で左右にくるくるしてたのがかわいかった.

*1:ホンマか?

*2:work with the best people as you can

*3:これはAhoのやったものなのかは分からん

*4:ちなみに,アルゴリズムを1つだけ教えるとしたらユークリッドの互除法を教えるべきだそうだ.2500年前のアルゴリズムで今でも使われているものが他にあるだろうか?って言っていた

*5:これ言ったか記憶が曖昧

*6:記憶が曖昧

*7: \exp(O(n^\frac{1}{3}\log^\frac{2}{3}n) ) とのこと

*8:Quantum-proof

*9:筆者注: 以下の三つは計算能力の上で等価.ただしDWaveは量子断熱計算のサブセット

*10:日本語だとトポロジカル量子計算

*11:PowerPointのアニメーションでquasiparticleが激しく動く

*12:この人とAhoは面識あるっぽい

*13:研究室のドクターがやってるっぽい?