2017-11-30

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

何

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

誰

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

メモ

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

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

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

Microsoft Visual Studio 2012で数千万行
Googleにもなると数億行

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

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

AWKのAはAhoのA←かっこいい
AWKはパターンとアクションを組にしたものを並べて記述する．
AWKの文字列マッチングはPythonやPerlと比べて極めて速い．
アルゴリズムの力*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

作者: Yuval Noah Harari
出版社/メーカー: Vintage
発売日: 2017/03/23
メディア: ペーパーバック
この商品を含むブログ (1件) を見る

感想：量子コンピュータの話を聞くとは全く思ってなかったので興奮した．量子プログラミング言語でチューリング賞取りたい！！！！
あと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:研究室のドクターがやってるっぽい？

2017-10-23

#技術書典3 振り返り

#技術書典3 です pic.twitter.com/L3Ekumo9wF
— 井山梃子歴史館「か03」@技術書典3 (@__pandaman64__) 2017年10月22日

これは説明責任です（書いてあるのはCivilization IVというストラテジーゲームのことです）

優勝です pic.twitter.com/i09CYf4zVo
— 井山梃子歴史館「か03」@技術書典3 (@__pandaman64__) 2017年10月22日

これは売り上げで食った立ち食い焼肉です．

申し訳ない申し訳ない

今回の本は「自作言語の処理系を自作CPUのアーキテクチャ向けの機械語を吐くように作り，それを自作CPUの（シミュレーションで）動かす」という本です．
言語は虎本の下位互換なやつで，CPUも16bit RISCです．
情報系学部生がやることをやったってだけです．．．*1

画像の通り未完成版で，具体的にはコンパイラのバックエンド部分（生存解析とかレジスタ割り付け）の文章がまだ書けてません．
そんな本を60人以上の方がお買い求めくださって本当にありがとうございます．
「完成版期待してます」とおっしゃった方もちらほら居まして痛み入ります．頑張ります．

現在のPDFも定期的にアップデートするつもりです．
そのときにはTwitterとメールで告知するのでお願いします．
「ここ間違ってるぜ」「読みにくいぞ」みたいな指摘でも何でもご意見お待ちしています．

ありがとうございました．
やっていくぞ．

*1:何か後になって開示するみたいでごめんなさい．

2017-10-21

#技術書典3 に自作言語＆自作CPU本を出します

ごめんなさい原稿終わってません

今A4で42ページです
アップデート配布するんで許してください．．．

明日の技術書典3で本を出します．
f:id:pandaman64:20171021140836p:plain
自作言語のコンパイラを書いて自作CPUの上で動かしてみよう！という本です．
電子書籍（PDF配布）オンリーで200円で頒布します．

当日は「か03」までお願いします．

2017-09-06

『量子プログラミングの基礎』 p.57 グローバー回転

hackmd.io

最初は基底使って計算してて分かるまでクソ時間かかった．
アダマール変換が二回適用すると恒等変換になることが分かれば瞬ですね．

2017-09-05

2017年度上半期成績

弊学では今年度よりGPAが正式導入され，そのついででABC+D(不合格)の四段階評価からSABC+D(不合格)という五段階評価に移行しました．
成績基準を見てみましょう:
http://www.gakuji.keio.ac.jp/academic/shoumei/3946mc0000001jyk-att/gakubuseisekikijyun.pdf
これまでは最高評価のAを取るには85点で十分だったのに対して，今学期からはボーダーが上がり90点が必要になりました．
厳しくなりますね．
同様に，今まで70点以上取ればBが出てGPAでは3換算になったのに対してこれからは80点必要です．10点分の基準変化は極めて大きいでしょう．
テストが失敗したら容赦なくGPA2が降ってくることになります．

それでは今学期の成績です．
f:id:pandaman64:20170905204128p:plain
・・・
モロに評価基準の変更を喰らった気がします．
GPAは3.933→3.858と2年前の水準まで下がってしまいました．悲しい．