量子コンピュータに思いを馳せる

量子コンピュータの雑記

この動画が面白い

僕と量子力学

僕は量子力学を大学で勉強した．ウィーンの法則から始まり，シュレディンガー方程式の井戸型ポテンシャルの練習問題を解いたり，量子を壁ポテンシャルに染み込ませたりする練習問題を解くくらいまで進む半期のカリキュラム．僕は半期では理解できず，次半期にあった（同じ内容の）講座も受講した．しかし僕の能力の不足によって，取得した単位は0．大学から「あなたは何も身に付いてないし，理解してないよ」との判定を受けました．

そもそも解析力学の概念が身に付いてないと量子力学の概念を理解するのは難しいらしいことを知ったのは最近．そういえば解析力学も大学で勉強したけど，さっぱり分からなかった．「質量」や「速度」のような直感的な物理量より，「運動量」という1つ抽象化された物理量のほうが本質的らしい．だから運動量を中心に考えることで運動を記述するのがより簡単になる，という程度の理解です．これも正しいかどうかちょっと自信ないけど笑．

僕なりの量子コンピュータの説明（正しくないかもしれない！）

だから正確なことは全然理解してないんだけど，雰囲気をざっくりと知りたいという気持ちはある．意識的に量子コンピュータの話題を読んで，知識を得てるつもり．量子コンピュータはCPUというよりGPUっぽい感じかと思ってる．汎用な計算を何でもできる訳じゃないけど，ハードウェアに固有の計算を猛烈な速度で済ませることができる，という認識．

例えばアナログの微分回路とか積分回路とかあるじゃん．抵抗，コイル，コンデンサで構成される原始的なやつ．僕の量子コンピュータの理解は，アナログ回路回路からの類推に依るところが大きい．CPUで数値的に（デジタルに）微分を計算することもできるけど，微分専用の回路でザクッと計算したほうが早そうだよね（実際の速度は知らないけど…）．その延長に，行列計算が凄く早いけどそれしかできないGPUがある．行列計算を自分で実装してCPUに計算させることだってできるけど，行列計算用の回路でザクっと計算したほうが早そうだよね（実際の速度は知らないけど…）．

そしてさらに延長に，組合せ最適化問題が凄く早いけどそれしかできない量子コンピュータがある，という認識．組み合わせによって問題が複雑になるケースは「巡回セールスマン問題」が有名かもしれない．現在のコンピュータは巡回セールスマン問題を解くのに長い時間を要するけど，量子コンピュータなら現在のコンピュータが解くのにかかる時間の平方根の時間しか所要しないらしい．現在のコンピュータが丸1年かかってやっと解き終わる問題も，量子コンピュータなら1時間半で解き終わるらしい．凄いね．

Quantum Computers Explained – Limits of Human Technology – YouTube

量子コンピュータはRSA暗号を破る

ところで，量子コンピュータ技術は公開鍵暗号方式の安全性を根底から揺さぶる．公開鍵暗号とは，現在標準的に使用されてる暗号方式で，RSA暗号が有名．RSA暗号も組合せ爆発によって計算時間が膨大になってしまうことを安全性の根拠にしてる．

例えば悪意のある人が1年でRSA暗号を破ってクレジットカードの暗証番号を割り出したとしよう．でも，暗証番号を変更されたら1年間解読に費やした意味が無いよね．また解読の計算のやり直しだ．暗号を破るための計算量と，そこから得られるメリット（と言っても盗みだから悪いこと）が吊り合わない．だからどんなに悪意のある人もRSA暗号を破ろうとは思わない．やるにしても，別の悪事に手を染めるはず．こういう理屈．

しかし量子コンピュータが普及したら，RSA暗号がたったの1時間半で破られてしまうかもしれない(この試算は適当なので当てにしないで．正確な時間を計算した記事も，きっとどこかにあるでしょう…)！これは危険だ！先にも述べたようにRSA暗号は現在とても広く使われてる暗号化方式だから，これが破られてしまったら大変だ．しかし希望が無いわけではない．

耐量子コンピュータ暗号の発明へ…

格子暗号というものがある．量子コンピュータの解読に耐え得る，という意味で「耐量子コンピュータ暗号」と呼ばれている．「耐量子コンピュータ暗号」は他にもあって，多変数暗号系，代数曲面暗号，組み紐群暗号などなどたくさんの候補があるらしい．どれが最適なのか，1位の座を争って暗号方式の発明競争が起きてるわけだ．

「中でも格子暗号は有望なのかなー」と僕はぼんやり思ってたんだけど，2016年7月20日に，KDDIと九州大学が60次元の格子暗号を解読したと発表した．しかも解読に要した時間は約16日．相場を知らないけど，これはたぶん驚異的な速さでの解読なんだと思う．

今回解読されたのは格子暗号の中でもLWE（Learning With Errors）という実装のもの（だと思う）．LWE暗号は，安全性と解読可能性がトレード・オフの関係になっていて，安全性を高めすぎれば（誰にも）読めなくなってしまうらしい．で，「安全性を高める」とは「問題空間の次元を大きくする」ということになるらしい．

今回の発表によって，「60次元LWE暗号は安全ではない」となるんでしょうか？僕は耐量子コンピュータ暗号としては格子暗号しか知らないから，このニュースによって他の候補たちが有利になったのかどうか全然分からない．

いずれにせよ耐量子コンピュータ暗号の必要性は高いので，格子暗号以外でも何でもいいから早く確立されて欲しいですね．というかそれより早く，量子コンピュータが普及して欲しいけどね！新技術大好き！

カテゴリー:ことばtech