Microsoft Q# Coding Contest - Winter 2019

去年の夏に第一回が行われた、マイクロソフトによるQ#のプログラミングコンテストが再びやってきました。個人的に凄く楽しかったので、次回があると良いなあと勝手に期待していたのですが、案外早くやってきてくれて嬉しいです。

2018夏とタイトルに着いていたので、いずれ別の季節にやってくれるのではと思っていたので、今年の夏頃にも是非とも期待しておりますマイクロソフトさん。

さて、ご存じの方も多いかと思いますが、Q#というのはマイクロソフトが開発している、量子コンピューター向けのプログラミング言語です。量子コンピューターとは何かと言いますと、バズワードです。バズワードってなんやねんって仰る方がいるかもしれませんが、バズワードになってしまったことは仕方がありません。わたしもよもや量子コンピューターがこんな扱いになるなんて、 2010年代も広範になるまで全く思いもよらないことだったんですから。

それはともかく、昨今の量子アニーリングマシンに端を発する、量子コンピューターとはなんぞや問題がどんどん拡大を続けている風潮に反して、マイクロソフトが社内で開発しているという噂の量子コンピューターは、古式ゆかしい、量子チューリングマシンの定義に基づく、量子ゲートを組み合わせた量子回路によって実現されるも、いわゆる「狭義」の量子コンピュータと呼べるもののようで、どういう計算ができるのだとか、どういう計算が古典コンピューターと比較して真に高速に行えるのかという、そういう研究もおそらく量子コンピューターの中ではもっともしっかりやられている分野であろうと思います。

計算複雑性理論によると、BQP の定義の逆からして、これを多項式時間で解からしむるデバイスがまさに量子コンピューターであると言えるし、しかるモチベによって、BQP研究はそれこそもう死ぬほど行われているはずなので、これがある程度のサイズ以上で実現したら、世の中的にはいくつかの、有用であるにかかわらず時間的な都合で解けなかった問題が解けるようになるはずなので、世の中の様相が少なからず変わるという可能性が高いでしょう。

最たるものが素因数分解で、これが効率よく解けないと言うことが、現代の良く用いられている公開鍵暗号の破られにくさの根拠に用いられているので、これが破られると、全世界の暗号が全部破られてしまい、そういうものを失った人類は再び戦争の世の中へと歩みを進めていくことになるのであった……。

などと言うことにもならなさそうで、私個人的には多項式時間っていうのはそんな楽観的なものだと思っていなくて、有名な素因数分解の量子アルゴリズムであるShorのアルゴリズムでは、桁数の3乗回のゲート数やら測定やらが必要だそうで、そういうのを例えば、桁数数千の素因数分解に適用しようと思うと、結局の所計算量のオーダーとしては数十億に及びますし、これが現実的な時間でできるかはまた別問題じゃないかとも思っています。

ましてや桁数を倍にするのは簡単だけど、桁数を倍にされたら、量子計算で素因数分解する手間はあっという間に8倍にされてしまいます。きっと多項式時間が現実的に解けるという風潮の背景には、かつてのシリコン半導体が、ムーアの法則に従っている、乃ち、コンピューターの持ちうる計算性能が、時間に対して指数的なのびを示すという事実が元となっている可能性がありますし、だとすれば多項式時間アルゴリズムは何時かの未来には漸近的に定数時間で解けてしまうというのも乱暴とも言えないのでしょうけれども、残念ながらシリコン半導体には物理限界が近そうですし、また、量子コンピューターはそもそも本質的に指数的に性能が伸びていくものなのかもよく分かりません（少なくとも僕には）。

だからすぐにどうなるという話でもないと思いますし、まあそもそもだからなんやねんという話で、もっと別の、どこかの誰かがとても解きたかった問題にはキッチリマッチすることもある可能性もあるので、やっぱりそういう計算を行うツールが一つ増えることは、我々プログラマーにとっては全く無視できるものではありませんよね。

前置きが長くなり過ぎました。 Microsoft Q#コーディングコンテストについて少し説明しましょう。

このコンテストは、MicrosoftのQ#というプログラミング言語を用いて、与えられたタスクの条件を満たすコードを書いて提出して、制限時間以内に正解を返すプログラムを書けばOKというものです、なるべく沢山のタスクについて、速く正確に作った者が勝者になります。プロコンに慣れ親しんでいる方にとっては、Q#という所だけが独特で、それ以外は普通のプロコンと余り変わらないと考えて良いと思います。そういう風に考えて大丈夫なので、プロコン好きな人、次のQ#コンテストがあったら、いっしょに、でましょ？(,,´･_･`,,)

今コンテストは、量子コンピュータのプログラミング自体が大変難しい上に、従来のプログラミングとはやり方も目的も何もかも異なってきますので、その全く異なる環境への柔軟性を見せられるかと言うところが一つのポイントだと思っています。オッサンのカチカチ頭ではきびしくて、お子様のプルプル脳みそだとジュワーッと新概念がみるみる浸透していって、なんなら小学生とかが優勝してもおかしくないコンテストだと思います。

問題のカテゴリーは大きく4つに分けられており、まず1つ目がAグループ、「特定のQubitの状態を作れ」というものです。初期状態のQubitをぐりぐり動かして複数のQubitをコネコネもつれさせて、お望みの形を作り上げるという、いうなれば粘土工作（？）のようなタスクですね。いろいろ試しているのが楽しい問題です。ですが、そういう職人的な楽しみをすててシステマティックに解く画一的な方法を考えるのも一つのテーマな気はします。

次のBグループは、Aとは逆な感じで、与えられたQubitの状態がどういう状態なのかを判別する系のタスクになります。問題としては、2つの状態のうちのどちらであるか、とか、100%分からないなら、20%の確率で絶対に正解を出せとか、結構バリエーションに富んでいます。与えられたQubitをもちもちねばねばうごかし、これなら見破りやすいぞという形に持っていって、そこで測定して、スパーン！と正解を言い当てる、とてもかっこいいタスクです。でもここが一番難しいんですよね。いわば量子の世界から現実の世界へデータを持ってくるフェーズですし、そういうときに情報はどんどん失われる。でも量子の世界で閉じこもったままで何も計測しないなら、量子計算自体何の意味もないんですよね。猫が死んでるのかも生きているのか、勇気を振り絞って、Qubitを叩き潰すタイプの問題です。

つぎのCグループは、オラクルがテーマです。オラクルと一言で言ってもいろいろありますしなんだろうと思われるかもしれませんが、ここでのオラクルは量子オラクルです。量子オラクルというのは、なんか関数渡すから、その結果をこの別のQubitにもつれさせた形で記録してくれ、というあんまり直感的ではない自明的な一連のプロトコルになります。要するに、Qubit上の関数を書けという話だと思うのですが、Qubitは破壊できないし、コピーもできない（No cloning theoremとか）ので、結局出力を何か他のビットにもつれさせるしかないんでしょうね。問題のカテゴリーの中では、これが一番適当に書けば良いだけだから簡単だと思いました。

最後のDグループは、なんかユニタリー行列の条件が与えられるので、それを満たすユニタリー行列を、使える量子ゲートを組み合わせて組み立てて下さいと言うものです。量子ゲートによるプログラミングでは、ユニタリー行列を作ることがまさにプログラミングなんですが、このタスクでは、大体こことここを非ゼロにしてという大雑把な仕様が与えられるので、それを満たす行列の組み立て方をひたすら頑張って考えるわけです。何時の時代もプログラマーというのはそういういい加減な仕様を満たすコードをなんとかして考えなきゃ行けないもので、ツライのですねと言う哀愁漂う問題（？）で、しかし、まさにこういうユニタリー行列による量子プログラムの記述から、それを既知のゲートの組み合わせで表現する方法を見つけるというのは、いまさらそういうことをやる必要があるのか！と思うぐらいには、非常にプリミティブで重要な量子プログラミングにおいては、重要な進捗が求められる分野だと思います。この辺解きながらサーベイしていて、あんまりパッとした超すごいやり方が2020年になろうという今でもなかなかないんだなあと思いながら解いていました。

と、そんなことを書いているうちに長くなりすぎて、参加記を書く余白がなくなったので、本編は明日以降書いていきたいと思います。