究極の物理系であり、究極のソフトウェアであるものへの情熱

プログラミング言語では物理工学の博士号は取れないだろう。しかし、それでも自分は量子プログラミング言語が好きだ。（まあ情報理工の院試の問題を見てチキったのが一番悪いんだけど）

だからこれは供養になるかもしれない。もしくは「本当に忘れたくないもの」だ。

本当に気持ちだけで書いたから、論理展開にはかなり飛躍があるが、若さとか情熱というのはそういうものだと思ってほしい。このために大学院に入ったのだ。

究極の物理系としての量子プログラミング言語

物理学は基本的には、現実世界のことを客体として測定し、機序と力学を解き明かす営みだと理解している。

その中でも、プログラミング言語は究極の物理系だと思う。

任意の物理系は何かしらの計算にマッピングできることは有名だが、ある程度強力なプログラミング言語はその計算や物理系すべてを表現できる。とても普遍的だ！

逆に、プログラミング言語はあらゆる物理系をモデル化するだけの力を持たなければいけないだろう。

しかも、物理学は人間による人間のための学問だから、そのモデルは人間が扱いやすいものである必要がある。

あらゆる物理系を、扱いやすくモデル化する力を持つ。もちろんそれ自体は一般的すぎて何もできないが、適切に制約と整合性を加えて特定の系について論じることができる。これは物理学に他ならない。

現代のプログラミング言語は普遍的な物理的モデルとしての能力を持つべきだ。

現代の物理学において、量子情報理論はかなり根源的な理論とみなされているから、理想的なプログラミング言語はその理論構造を反映したものになるであろう。

コンピューター内であらゆる実験を原理的には行えるように、量子プログラミング言語はあらゆる物理現象をサブモデルとしてモデル化できる必要があり、「扱いに習熟することで量子力学を自然と理解できる」ものになるだろう。 そして、逆に、あらゆる物理現象や推論を計算とみなして抽象化することで、理想的な量子プログラミング言語に到達できると考えている。

理想的な量子プログラミング言語は、強力で扱いやすい量子情報理論の構造をバックボーンに持っているはずであり、そのために理論の理解が進むことが必要である。

究極のソフトウェアとしての量子プログラミング言語

全てのソフトウェアは理念的にはプログラミング言語によって書かれるはずだ。（過激派）

だから、理想的なプログラミング言語はすべてのソフトウェアを書けるだけの表現力が必要になる。

プログラミング言語もソフトウェアだから、プログラミング言語はすべてのソフトウェアを生成できる存在、究極のソフトウェアと言えるだろう。

プログラミング言語はソフトウェアを書く人に使われるものなので、どのようなソフトウェアを人々が書いているかに大きな影響を受ける。

なので、量子計算機を用いたソフトウェア、量子ソフトウェアだったり、量子アルゴリズムをすべて表現できるプログラミング言語である量子プログラミング言語があるのが適切だろう。

古典計算機でメモリの破壊を実行前に推論できたりするように、量子プログラミング言語は量子ソフトウェアを書く上で便利な機能、たとえば量子ビットの複製の禁止などを保証できるようにするべきだろう。

そして、そもそも量子ビットではない物理系に対処する必要もある。私が知る限り、ボソン系とフェルミオン系による量子計算の両方をいい感じに表現できる言語はまだない。

量子プログラミング言語との触れ合いとこれから

B2だかB3だったかではじめて量子回路を組んだ時は本当に驚いたものだ。

古典計算機におけるアセンブリ言語にも満たないような抽象度、ビット演算レベルの処理を並べて計算を記述している。

そして、量子力学を知っていないと何をやっているかほとんど何も理解できないのにも驚いた。

中学生の、古典力学も計算機科学も、つい最近まで右クリックも知らなかった人間が「Hello world」できるのとは対照的だ。

とても使いにくいというのが最初の感想だった。これでは将来量子計算機ができても、使う人はほとんど増えないだろう。

しかし、大学院に入り、量子情報の教育を受ける傍らで折に触れて再考するとかなり違う景色が見えてくる。

まず一番重要なのは量子情報は量子計算よりもはるかに多様で広い分野であることだ。量子計算の実現に限った話でも「回路をゲートからアセンブリする」よりは非常に広い話題に触れる必要がある。

そして、ビット演算レベルのきわめて低レイヤーと思えた量子ゲート演算も、物理系の立場からすればきわめて高レイヤーであり、抽象的な存在だ。今よく使われている量子ゲート演算セットは「組み合わせれば一応なんでも表現できる」だけの存在であり、それ以上でもそれ以下でもないことが分かってきた。

量子計算も、どちらかというと必要なのは量子力学というよりかは線形代数（+α）である。

そして量子ソフトウェアは物理学ではないという見方が圧倒的だった。（まあ自分でもかなりこれは思うので妥当なんだけど）一応断っておくと、弊研究室は極めて理解がある方だ。特に、指導教員には修論で「物理と言えそうな貢献」を相談する上でかなり苦労をかけたと思う。何より、そういう方向性に興味を持ってくれる知り合いや若手研究者、ITエンジニアに自分は恵まれていた。かなり恵まれている。しかし、色々模索したが博士号は多分これでは取れないだろう。これは物理工学科に来た自分が全面的に悪い。

上で書いた理想の言語の要求は極めて高い。人生をかけてもたどり着くかは怪しいだろうし、博士課程ではなおさら難しい。そして博士論文にはならない。だからしばらく忘れることにしよう。

だから、これのために量子情報を志したという気持ちだけは残すことにした。未来の自分が、これを見て少しでも量子プログラミング言語のやる気を取り戻すことを祈る。それではまた。

量子コンピューターに必要なソフトウェアを概観してみる

これは、情報科学若手の会 56thで発表した内容(非公開)を修正してテキストベースで公開したものです。 そして、量子コンピューター Advent Calendar 2023の14日目でもあります。（遅刻してすみません。完全に忘却していました......）

量子コンピューターのどこがすごいのか

量子コンピューター、なにやらすごそうなイメージがありますよね。ニュースとかで調べると、「次世代の計算機！」「スーパーコンピューターでも解けない問題を短時間で解いた！」というキャッチーな解説が踊っています。

実際、量子コンピューターは特定の問題、たとえば素因数分解*1や「問題の構造に依存しない全探索」*2を通常のコンピューター（この記事では以降「古典コンピューター」と呼ぶことにします）よりも少ない計算量で解けることが知られています。*3

特に、これらの問題を高速に解くことによって、量子コンピューターはRSA暗号や対象鍵暗号の解読を今までよりも効率的に（特に、RSA暗号に関しては現実的な時間で）解読ができるようになると考えられています。

また、量子コンピューターが提案されたそもそもの経緯の一つ*4である、「複雑な量子物理的な現象の効率的なシミュレーション」なども期待されており、これらによって新しい材料や薬などの開発が加速することが期待されています。

未来は明るいですね！！！

「すごい」量子コンピューターのためには何が必要なのか

......もちろんそんなうまい話はなく、現実には非常に大きな障害が複数存在しており、先ほど述べたような「すごい量子コンピューター」はまだ実現していません。

その中でも一番大きな障害の一つが「ノイズ」です。 量子コンピューターは量子ビットを用いて計算をしていくのですが、1ステップ計算を進めるごとに量子ビットにノイズが乗っていきます。このノイズのため、先ほど述べたような「大規模な」計算をしようとすると求めたい答えがノイズの中に埋もれて取り出せなくなってしまうのです。

IBMが公開している量子コンピューターの情報。（ibm_brisbane, 23年12月17日00:10時点）大体の量子ビットに1%程度の誤差がある。

これに対するアプローチはいくつか存在しますが、その中でもある程度根本的に問題に対処するために必要なのが「量子誤り訂正」です。量子誤り訂正の基本的なアプローチは、複数の量子ビットが分散して一つの量子ビットの情報を持つことで、ノイズで少し情報が破損しても残りから情報を復元できるようにする、というものです。

表面符号*5による量子誤り訂正符号。黒丸と白丸がそれぞれ量子ビットであり、全体で1量子ビット分の情報を保持する。

ではこれで問題がすべて解決するかというと、そんなことはありません。 一つの量子ビットを表現するために多数の量子ビットが必要になる上に、「情報を分散したまま」「ノイズを訂正しながら計算する」必要がある*6ため、量子計算の手続きがかなり複雑かつ長大になります。

例えば、先ほどの図の表面符号を用いたRSA暗号の解読では、素因数分解のためになんと「2000万量子ビットで8時間」のコストが必要である*7と試算されています。 *8

量子コンピューターは制御する古典コンピューターがいないとまともに扱える代物ではありません。 しかし、ここまで複雑になってくると、古典コンピューター側の制御プログラムも非常に複雑になってくることが予想されます。困りました。

量子コンピューターの実現に必要なソフトウェア

実用的な量子コンピューターを実現するには、超多数の量子ビットを適切に制御し、抽象的なタスクを実現しなければいけません。 そのため、通信プロトコルのように複数の階層からなるソフトウェアスタックが必要になります。 以下の項目に分けて紹介していきます。

物理制御組み込みソフトウェア

量子ビットは方式にもよりますが、近代まで発見されなかっただけあって、極めてデリケートであることが多いです。 そのため、量子計算を実現する一番オーソドックスな手段は、「古典コンピューターにあらかじめ実行したい計算を格納しておき、ほぼ自動的*9に物理制御をする」というものになります。

超伝導量子ビットの場合、適切な波形のマイクロ波を量子ビットに対して適切なタイミングで照射することで制御をするわけですが、これを「数万量子ビットレベル」までスケールするような装置があることが望ましいです。 みなさんはパソコンに「数万個レベル」の外部機器を接続できますか？ちょっと考えただけでも気が遠くなりそうですね。

理研のプレスリリースより引用。
冷凍機（中心白）から青い配線が伸びている左右の筐体が制御部と思われる。

量子回路シミュレーター

直接量子コンピューターの実現には寄与しないものの、古典コンピューター上で動く量子回路シミュレーターは研究にとって非常に重要です。 量子コンピューター（実機）は数がまだ限られていますが、古典コンピューターは世界中に文字通り遍在していますし、研究者もユーザーも圧倒的に多いです。 そもそも、今の量子回路シミュレーターは大体の量子コンピューターよりも精度が良く、現在も進歩を続けています。 そのため、「このアルゴリズムを実際に動かしてデバッグしたい！」となったとき、実機で動かす前にまずはシミュレーターで試すというのがよくあります。

2023年末現在、量子コンピューターの実機とシミュレーターの精度はかなり拮抗しており、何かしらの技術的ブレイクスルーで量子ビット数はそのまま精度が数桁向上するか、同じ精度のまま腕力で多数量子ビット（少なくとも万レベル）を制御するまではこの状況は変わらないと私は考えています。

IBMが今年7月にnatureに発表した「量子コンピューターの有用性」を示す論文*10に対する反論の一つ*11から引用。実機（青丸）の結果をシミュレーション結果（水色線）がきれいに再現している。この分野の人間にとってはもはやおなじみの光景。

誤り訂正・デコーダー

ニューラルネットワークで表面符号の誤り訂正を計算する手法の論文。*12左の列から、アルゴリズム、閾値*13、精度pに対応する計算時間(ms)

量子誤り訂正をソフトウェアの観点で見た場合、かなり要求はハードです。 量子状態がデコヒーレンスによりノイズに埋もれるマイクロ秒～ミリ秒単位の時間で100から1000個のオーダーの入力をもとにエラーを推定してリカバリーまでしないといけません。 計算量を減らしつつ、誤り訂正の精度を損なわない誤り訂正アルゴリズムの研究や、「そもそも少ない計算量で誤り訂正ができる符号」*14の研究開発などが重要です。

量子回路オプティマイザ・コンパイラ

量子コンピューターには相対的に得意な（=精度よく高速にできる）操作と、苦手な操作があります。 例えば、1量子ビットだけを操作するのが2量子ビットをもつれさせる操作よりも得意だったりすることが多いです。 また、同じ2量子ビットをもつれさせる操作でも、近くにあるもの同士でやる方が遠くにあるもの同士でやる方よりも得意だったりします。 そうすると、同じ計算を実現する量子回路でも、「苦手な操作を減らした表現」の方が精度が上がったりします。

また、少し方向性は変わりますが、「ある量子ビットが操作されている間になるべく同時に他の量子ビットを操作して計算時間を圧縮する」なんて方向性もあります。

素因数分解を従来より高速化したと主張する論文*15より引用、抜粋。こういう「量子ビットが遊んでいる時間」は減らしていきたいときもある。

利便性を上げるために必要なソフトウェア

古典コンピューターでWebアプリケーションを作りたいときに毎回TCPスタックから自作しなければいけないとしたらとても大変ですね。 せっかく量子コンピューターができても、抽象化が足りていないと使いづらくて悲しいです。 ということで、ここでは計算機を抽象化して使いやすくするソフトウェアについて以下のものを紹介していきます。

量子ライブラリ・ソフトウェア

複雑性を隠蔽する一番オーソドックスな手段です。 例えばQiskitでは量子アプリケーション モジュールとして化学、金融、機械学習、最適化の4分野について、「簡単に量子計算ができる」ライブラリを提供しています。

他に有名なライブラリだとCirqやPennylaneなどがあります。

量子プログラミング言語

先ほどのアプローチでは問題の数だけライブラリが必要になってしまいます。 より細やかな制御がしたいときはそれでは足りないので、量子コンピュータの挙動をもっとプリミティブに記述できるようなプログラミング言語を作ると便利です。 また、古典コンピューターについて手続き型パラダイムよりもスケール手段として関数型パラダイムが注目されているように、量子コンピューターについてもよりスケールする手法が提案されるかもしれません。

量子プログラミング言語だと代表的なものとして QuipperやSilqが知られています。

量子クラウド・サービス

一般の家庭で量子計算機を保有することはまだ難しいです。*16なので大部分の人はどこかの量子計算機を間借りすることになると思います。 これは現在のクラウドとほぼ同じものであるため、量子クラウドと呼ばれています。 IBM Quantumなどが有名ですね。 また、実機だけでなく、オンラインで量子コンピューターの学習ができるサービスも重要です。未踏での取り組み*17もあり、こういった取り組みでそもそも「量子コンピューターに関わる人口を増やす」というのも重要になっていくでしょう。

個人的雑感

量子コンピューターの実現はまだまだ遠いので課題が山積みです。 情報科学が80年近くかけて蓄積してきた試行錯誤の結果のいいとこどりをしてスムーズに実現を目指せるというのが理想ですが、今の状況では物理学系の人が多く、思ったより知見を導入できていないのではないかと感じることが多いです。 量子ソフトウェアはこれからますます重要性を増していくと思うので、よければぜひ大学の量子コンピューターの研究室の見学や、OSS活動などをしてみてください。

*1:Shor, P. W. (1994, November). Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science (pp. 124-134). Ieee.

*2:Grover, L. K. (1996, July). A fast quantum mechanical algorithm for database search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing (pp. 212-219).

*3:よくある誤解として「なんでも速くなる」というのがありますが、量子コンピューターの方が速く解けることが理論的にわかっている問題はかなり限られているのが現状です。

*4:Feynman, R. P. (2018). Simulating physics with computers. Int. j. Theor. phys, 21(6/7).

*5:Fowler, A. G., Mariantoni, M., Martinis, J. M., & Cleland, A. N. (2012). Surface codes: Towards practical large-scale quantum computation. Physical Review A, 86(3), 032324.

*6:古典コンピューターの通信のように、いったん一つの量子ビットに情報を復号してしまうと、そこにノイズが乗って情報が破壊されてしまうためです

*7:Gidney, C., & Ekerå, M. (2021). How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits. Quantum, 5, 433.

*8:ちなみにコストがあまりにもでかいので、もっといいやり方あるんじゃね？という研究も多く存在しています。

*9:量子ビットの測定結果に応じて計算を変えることもありますが、そのプログラムごと送り込むと考えることが普通です

*10:Kim, Y., Eddins, A., Anand, S., Wei, K. X., Van Den Berg, E., Rosenblatt, S., ... & Kandala, A. (2023). Evidence for the utility of quantum computing before fault tolerance. Nature, 618(7965), 500-505.

*11:Begušić, T., & Chan, G. K. (2023). Fast classical simulation of evidence for the utility of quantum computing before fault tolerance. arXiv preprint arXiv:2306.16372.

*12:Meinerz, K., Park, C. Y., & Trebst, S. (2022). Scalable neural decoder for topological surface codes. Physical Review Letters, 128(8), 080505.

*13:詳しく説明すると長くなるので割愛するが、誤り訂正の精度だと思うとよい。数値が高いほど良い。

*14:有名なものだと Dinur, I., Hsieh, M. H., Lin, T. C., & Vidick, T. (2023, June). Good quantum LDPC codes with linear time decoders. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing (pp. 905-918). など

*15:Litinski, D., & Nickerson, N. (2022). Active volume: An architecture for efficient fault-tolerant quantum computers with limited non-local connections. arXiv preprint arXiv:2211.15465.

*16:情報科学若手の会ではこの部分に質問があって、量子コンピューターを自作する方法を紹介しましたが、それが一番ウケが良かったです。

*17:https://x.com/small_onions/status/1734531013131588088?s=20

notion + paperpileからobsidian + zoteroに移行したい

修士の間ずっと慣れ親しんできたnotion + paperpileによる情報管理をobsidian + zoteroに移行することにした。4月から博士課程だったのでちょうどよいだろう。 obsidianへの移行はほぼ完了しており、zoteroはこれからだ。 ここではかつてnotion + paperpileを選んだ理由と移行の理由について備忘録的に書いていく。

かつてnotion + paperpileを選んだ理由

修士以前、自分はメモを蓄積する体系的な方法を持たなかった。 しかし、大学院と会社員生活を並行に進めるにあたって、頭の中だけのメモ+αでは立ち行かなくなっていき、notionを選択することにした。 当時obsidianにしなかったのは単純にobsidianを知らなかったからなのだが、当時の比較対象への評価は以下の状況だったと記憶している。

つまり、重要視していたのは以下の3つだった。

重すぎない

evernoteはB2の時期に一瞬使っていたが、スマホでの動作がもっさりしすぎという印象だった。 具体的に言うと、アプリをタップで立ち上げてから書けるようになるまでの時間が長い。

スマホでの読み書きが必須

当時、スマホで記事を読んで保存するという行為を頻繁にしていたため、スマホから書き込みができることは重要だった。特に、ウェブページを簡単に取り込めることは重要だった。これはvscodeでmarkdownを書くだけでは達成が非常に難しい。

スケールする

複雑なメモを大量にストックし、整理する能力である。 google keepはその点で対象外だった。なぜならフォルダのような階層構造を形成できなかったためである。

paperpileを選んだのも似た理由であるが、追加で2つ理由がある。

手軽である

公式アプリがiPad, android, chrome拡張の形式で提供されており、google drive経由の同期が自動でセットアップされて使いやすい。 文献管理初心者としてセットアップの手間がかからないのは楽である。

モバイルアプリがある

東大はmendeleyが無料で使えるのだが、iPadで書き込みできない、スマホから取り込めないというのは痛いと考えた。paperpileはiPadで直接書き込みができるのと、スマホから簡単に文献を取り込めるのが良い。

notion管理の問題とobsidianへの移行

notion管理はM2の夏くらいまではうまく行っていたが、秋くらいから以下の問題が出てくるようになった。

気軽に書き込めない

思いついたときにぱっと書き込む、という使い方をしづらくなってきた。これは、notion管理が成熟してどこに何を書くかが決まってきたからである。notionのスマホアプリは最後に書き込んだページではなくワークスペースのホームページが立ち上げ時に出るため、書き込む先まで移動しないといけず、書き込みコストが上がってしまった。

拡張しづらい

notionを長く使っているとプログラマーとしては拡張したいケースが出てくる。例えばカスタムコマンドを追加するなどだ。しかし、notionでそれを行うにはwebで開いた上でchrome拡張になってしまう。これは正直微妙だ。

というわけで、色々調べた結果、obsidianに移ることにした。 obsidianは、上の2つの問題を以下のように解決できる。

  • 気軽に書き込めない > デイリーノートが自動で立ち上がるようにすることで、アプリを開くとすぐに書き込める。
  • 拡張しづらい > プラグイン機構がある。コミュニティープラグインだけでなく、自分で作ることもできる。

逆に、obsidianで面倒だったこととして、同期のセットアップがある。多分プログラマーじゃないとめんどくさいだろうが、自分はプログラマーだったのでそんなに問題ではなかった。ここは結構人を選ぶポイントだと思う。あと、共同作業はほぼ不可能な気がするのでそこも諦めポイントだ。

paperpileからzoteroへ行きたい

obsidianへの移行をしてしばらく経ち、論文をobsidianで書いていると、当たり前だが文献管理ツールとつなげたくなってくる。 しかし、そうなるとpaperpileはつらい。なぜならプログラマティカルに外部から操作する手段がほぼないためである。その点でいうとzoteroは既にobsidian用のプラグインもあり、apiもあるので問題ないように見える。 paperpileのエクスポート機構はよくできているようなので、多分そこまで移行は困らないだろう。

最後に

zoteroへの移行はまだやってないので最終的に上手くいくかは不明である。うまく行ったとしてD3で嫌になって出戻りする可能性もある。だがしばらくはこれで行きたい。

素朴な定義では量子人狼は物理的に実現不能

これは「ボードゲーム・パズルプログラミング Advent Calendar 2022」の19日目の記事です。

量子人狼って何

量子人狼は以下の記事で解説されている、「参加者の役職・生死が量子的に重ね合わさった状態のまま進む人狼」です。

uhyo.hatenablog.com

詳しいことは上の記事を読んでいただきたいのですが、この記事では「占い」に関する以下の事実に特に注目します。

「占い」では、確率的に参加者の重ね合わせのパターンを削減することが可能です。

例えば以下の重ね合わせの可能性が残っていたとしましょう。

  • （50%）Aさんは村人、Bさんは人狼、Cさんは占い
  • （30%）Aさんは占い、Bさんは人狼、Cさんは村人
  • （20%）Aさんは占い、Bさんは村人、Cさんは人狼

このとき、Aさんは占いとしての行動を取ることができ、例えばBさんを占ったとします。そうすると、60%の確率でBさんが人狼、40%の確率でBさんが村人である事実がAさんに通知されます。

すると、例えば人狼であることが判明すると占い後は以下のような盤面になります。

  • （50%）Aさんは村人、Bさんは人狼、Cさんは占い
  • （50%）Aさんは占い、Bさんは人狼、Cさんは村人

素朴な定義

素朴な定義とは、「量子人狼が想定しているであろう方法で各人の状態を量子化してあげること」です。具体的には、以下の条件が必要となります。

1. 各参加者の役職・生死は量子状態として直接表現される。

例えば上のパターンだと「$\sqrt{1/2}\ket{A:村}\ket{B:狼}\ket{C:占}+\sqrt{3/10}\ket{A:占}\ket{B:狼}\ket{C:村}+\sqrt{1/5}\ket{A:占}\ket{B:村}\ket{C:狼}$」とエンコードする、という制約を設けます。各人の量子状態が整合性を保ったまま、各人それぞれの視点では量子重ね合わせが量子状態として実現しているという単純なモデルです。

この制約を設けないと、自明に物理的に可能になります。上の量子人狼は確率の表をベースとして計算をするので、その確率の表の全体を量子状態にエンコードしてしまえばよいためです。

2. ゲームの状態は常に純粋状態である

量子人狼では「測定するが、その結果を消去する」という動作はありません。そのため、測定結果は決まったレジスタに必ず書き出され、ゲームの状態は常に何らかの純粋状態になると考えるのが自然でしょう。

この制約を設けないと、1で表現した量子状態の古典的な確率的重ね合わせにより、確率表を再現できてしまいます。それは量子人狼ではなくもはや「古典ベイズ人狼」と呼ぶべきでしょう。

3. トモグラフィーはしない

トモグラフィーは雑に言うと、量子状態を準備する方法を知った状況で、同じ量子状態を量産し測定しまくる操作です。これによって任意の精度で量子状態を推測できます。 これを許すと古典計算機で量子状態を格納して好きなようにいじることが可能になるため、量子人狼ではなく「古典計算人狼」になります。

人狼が噛んだり処刑することは可能

不可能性に入る前に、この2つの動作が量子的に実現できることを簡単に述べておきます。

1. 人狼の噛む動作

安直に実装しようとすると「役職の状態のqutrit（3状態なのでqubitではなくなります）」を制御量子ビットにして「対象の生死の状態のqubit」を反転させれば良いのですが、それだと人狼が同じ人を2回噛んだときに噛まれた人が生き返ってしまいます。これを防ぐには、「自分が人狼であり、かつ噛もうとしている人が生きているか」という情報を高階制御ゲートによって噛むたびに補助qubitに書き出せば解決できます。補助qubitは測定しないでそのまま確保しておけば純粋状態のままゲームを進めることができます。

2. 処刑

処刑は量子人狼では「役職が確定し、それまで生きていたことも確定する」とあります。これを物理的に実現するなら、生死を観測するときに「生きている」という結果が出るまでゲームを繰り返すという、いわゆる「post-selection」の方法が使えます。トモグラフィーとかなり似ていますが、生死の確率だけでは盤面の量子状態は一意に定まらないのでセーフです。

不可能性

では不可能性を示していきます。 まず、以上の制約の下で、占いによる操作は以下のように表現されます。

『スタート「$a\ket{A:占}\ket{B:村}\ket{その他}$+ $b\ket{A:占}\ket{B:狼}\ket{その他}$+ $c\ket{A:非占}\ket{B:何でも}\ket{その他}$」から

確率$|a|^2/(|a|^2+|b|^2)$で

「$\sqrt{|a|^2+|b|^2}\ket{A:占}\ket{B:村}\ket{その他}$+$c\ket{A:非占}\ket{B:何でも}\ket{その他}$」を、

確率$|b|^2/(|a|^2+|b|^2)$で

「$\sqrt{|a|^2+|b|^2}\ket{A:占}\ket{B:狼}\ket{その他}\ket{その他}$+$c\ket{A:非占}\ket{B:何でも}\ket{その他}$」を得る。』

実際にこれを実現しようとすると、（占い後でもBの役職は完全には確定していないので）Bの役職を書き出して観測するための補助qubitが必要になるため、実際には以下のような操作になります。補助qubitが本体の量子状態に依存してはいけないことに注意すると、

『スタート「$a\ket{A:占}\ket{B:村}\ket{その他}\ket{補助: 0}$+ $b\ket{A:占}\ket{B:狼}\ket{その他}\ket{補助: 0}$+ $c\ket{A:非占}\ket{B:何でも}\ket{その他}\ket{補助: 0}$」から

「$a/\sqrt{|a|^2+|b|^2}$$(\sqrt{|a|^2+|b|^2}\ket{A:占}\ket{B:村}\ket{その他} + c\ket{A:非占}\ket{B:何でも}\ket{その他})\ket{補助: 0}$+ $b/\sqrt{|a|^2+|b|^2}$$(\sqrt{|a|^2+|b|^2}\ket{A:占}\ket{B:狼}\ket{その他} + c\ket{A:非占}\ket{B:何でも}\ket{その他})\ket{補助: 1}$」を得る。』という操作になります。 補助qubitを測定して1になった場合が占いでB:狼を得た場合に対応します。（そして占いではない場合の確率は変わらない）

操作の途中に追加で定数個の補助系を許したとしても、操作の前後は必ず純粋状態であることを要求すると最終的にこのような入出力を持つ量子過程が必要になります。なぜなら、途中で追加した補助系を観測して、観測結果をもとに役職を古典的に計算できる場合、途中で追加した補助系を2次元の空間に落とし込む操作がつねに存在するためです。（古典計算を真似るような量子ゲート列を定義し、最終結果以外の追加した量子ビットを全部0or1にリセットする、uncomputationと呼ばれる操作です）

しかし、このような量子過程は不可能です。なぜなら、量子過程である場合は入力について線形であるため、スタートにおいてa=0, cをc/2とした場合とb=0, cをc/2としたの場合のときのそれぞれの出力を線形和しても正しい出力が得られるはずですが、実際はそうなっていないからです。

色々書いてきましたが、ざっくりいうと、「自分が占いでないパターンの確率を変えないまま、占い結果以外のパターンを削減する」という部分が量子的に不可能であることの本質になります。

実現可能な占いを考えてみる

例えば、補助qutritを役職の完全な重ね合わせ状態として用意します。（初期状態からその状態に移行する操作をFとします。）

そして、「自身が占いかつ対象者の状態がiのとき、Fの逆操作をして状態iを書き込む」ような制御ゲートを用いると、役職を観測する確率は条件付き確率とは異なるものの、「自分が占いであったが観測した役職とは違っていた」という量子状態を排除することができます。

（自分が占いでないパターンの確率を変えることを許すとどうなるかは解析していません）

終わりに

この記事はアドベントカレンダーの担当であることを忘れていた自分が急いででっち上げた代物のため、議論がかなり雑です（すみません）。なにか指摘あったらコメントお願いします。

気がついたら社会人学生になってた話

社会人アドベントカレンダー2022、13日目です。

TL; DR

  • 起業の流れに乗ると社会人学生に進化することがある
  • 労働と研究の両立は大変
  • 学費や就活の心配はなくなる
  • 業務と研究のシナジーがあるよ

前提

あなたは誰？

学生としては、工学系の修士2年で、博士進学予定です。量子計算機の理論に関する研究をしています。

社会人としては、都内のとあるweb系企業でテックリードをしています。フロントエンド設計が得意分野です。

あなたは誰ではない？

大学を卒業してから再入学したわけではないです。（一回留年はしましたが）

通常の就職活動をしていません。

長期インターンとして会社に所属しているわけではありません。

研究職でもありません。

社会人学生になった経緯

社会人学生になる経緯は今から5年前、学部2年の夏までさかのぼります。2017年のことです。

当時学園祭のシステム部局の統括者を勤めていたためか、大学内の起業のときにエンジニアとして手伝ってほしいという誘いを何度か受けていました。とはいえ、そもそも学園祭の業務が忙しかったのと、「そもそも自分である必要があるのか」「（申し訳ないけど）あまりビジネスモデルに興味が持てない」といったことでお断りをすることが多かったです。

そんな中、9月の半ばにTwitterの大学の知り合いからDMが飛んできました。「仮想通貨の仕組みと動画配信サービスを用いてマイナーなスポーツチームを支援しよう」というものです。2022年現在ではNFTやメタバースなどの名前で知られているビジネスモデルですが、2017年の当時としては非常に野心的なビジネスモデルでした。そして今ほど胡散臭さがなく、楽観的な雰囲気があったようです。（ちなみに現在は全然違うことをしています）

それと、Twitterでフロントエンドをやっていると公言していた自分に、仮想通貨と動画配信！というのは大きな驚きでした。今までのお誘いは基本的にはウェブメディアの整備であり、技術的にもビジネス的にもあまり興味を惹かれなかったのに対して、自分のやったことのない領域にトライできるというのはかなり魅力的でしたし、「やったことない」と返答してもなお「いや、来てみなよ」と返してくれたのは「自分と仕事したいんだな」という感覚を強めました。

そして、2017年11月にその会社は登記されました。僕自身は創業メンバーではありますが、インターンという名目で参画していました。2020年にはパートタイムの正社員に契約が切り替わり、今に至ります。

色々ありましたが、ざっと要約すると「起業に誘われてやってたら気がついたら正社員になってた」ということです。推測ですが、「起業に誘われて学生でありながら正社員になる」というやり方にはある程度の再現性があると考えています。少なくとも東大のような学生の起業が活発な大学では、一定の割合で「知り合いの能力がわかっているエンジニアを取る」というスタートアップが現れるでしょう。起業プログラムで仲間を見つける事もできます。そして、時間的にクリティカルでない仕事がメインでかつ十分長い間会社に所属した場合、「学生でありながら正社員」という立場になると考えられます。

労働と研究の両立の大変さ

現在、労働時間としては週20-25時間ほどです。つまり、フルタイムの人間の半分ほど働いていることになります。これは労働するにしても研究するにしても大変です。

正直あまりおすすめできないです。

労働の面では、単純計算でフルタイムの人の半分しか仕事ができません。設計などのように代替不能な仕事をする場合はこれでもなんとかすることはできますが、緊急対応のような仕事がほとんどできなくなるというのは大きな制約になります。（大学の講義が終わってみたらめっちゃメンションが飛んできており、問題が発生して解決していたみたいなことがあったりする）何より給料もフルタイムの半分になります。

研究の面では、まとまった時間がとりにくいことやコンテキストスイッチが非常に辛いところです。他の人がやるように「1日で一気に進捗する」みたいな挙動がほぼ封印されますし、仕事モードから研究モードに頭を切り替えて研究内容をメモリにロードするのをやったと思ったら時間が終わってた、みたいなのが起こったりします。

このタイプの社会人学生のメリット

一方で明確なメリットもいくつかあります。

まず、就活の心配をほとんどしなくていいことです。会社での立ち位置がほぼ保証されているため、仮に就活に失敗しても問題がありません。また、同じ年代の学生に比べて圧倒的に実績が積めます。特にスタートアップではプロダクトの企画、立ち上げから運用保守、フロントエンドからインフラまでオールラウンドに関わるため、経験値は莫大です。これはエンジニアのように経験が採用に効いてくる状況では特に有利になります。

また、学費の心配をしなくてもよくなります。学振が取れなくても自分の好きな研究を自分のお金である程度できるようになるというのは相当な安心感があります。（理論系の場合は特に）

業務と研究のシナジー

最後に、（少なくとも知的生産業の場合の）社会人学生の強みとして、「労働と研究のシナジーを観測できる」というのがあると思っています。

研究から業務に活かせることについては今までいろんな人が述べているので軽い言及にとどめます。説得力のある分析や学習能力などですね。基本的には知的生産における質と深さが効いてくると考えています。

一方で、逆に、業務から研究に活かせることもあります。（プログラミングのような）知的生産業の業務の場合、スピードと安定性、特に「不確実性」のハンドリングが重要になることが多いです。（まあ研究でも重要ですが、業務だとより表面化しやすいと思っています）これは研究において、純粋な結果を成果物に仕上げるというプロセスの安定性とスピードを上げるのに応用することができます。少なくとも自分のような未熟な修士学生としては、ミーティングで何話すかとかどういう進め方をしたらよいかなどの知見を業務での経験から部分的に構築できるのはかなり助かりました。

まとめ

なんだかんだ言ってこのタイプの社会人学生はあまりおすすめできません。やっぱ両立が辛いです。とはいえ、嫌になったらどっちか全振りに移行するのもそんなに難しくないですので、シナジーが気になる方や就活嫌すぎる方はやってみる価値はあると思います。

そしてすでにこうなっている方は反応をいただけると幸いです。周りではほとんど観測できておらず、かなり手探りなので知見を共有したいためです。

それではまた。

学内限定マイクラ鯖 UT-Craftの話

この記事は Calendar for VUTD（バーチャル東大Discord） | Advent Calendar 2021 - Qiita の19日目です。

UT-Craftとは？

「東大生オンリー」「普通のマイクラと違う世界」をコンセプトに作られた鯖です。

VUTDアドベントカレンダーにいるのは、多少技術っぽさが無いわけではないのと、UT-CraftがVUTDと非常に深いかかわりを持っているからですね。

発端

VUTDは1/30でできてから、急速に整備がなされました。その際に作られたゲームチャンネルの一つがマイクラだったのですが、早速マイクラ鯖を建てようという話になりました。チャンネルを遡ると色々案があったようです。（modを入れたり、特殊なワールドだったりetc）

で、僕自身も色々案があったわけですが、結局のところ「modを入れずに全員バニラで入れるようにしつつ、ワールドはなるべく『普通ではない』世界にする」という折衷案になりました。

そんなこんなで、2/7にサーバーとUT-Craft専用のDiscordを公開しました。

浮島と炎のネザーの世界

最初の世界はオーバーワールドが無数の浮島で構成されており、ネザーが過酷な世界でした。（それぞれ、sanonasu floating islandと、incendiumというデータパックの効果です）また、浮島どうしを効率的に移動するためにフックショットのデータパックを導入しました。

鯖構成としては非常にシンプルにAWSのEC2を一つ立てて、その中で動かしているだけです。データ管理の方式もシンプルで、（バイナリ以外の）設定ファイルをgitで管理してるほかは自分のPCに保存されているだけです。とはいえ、プラグインを入れるなどのアップデートをするたびにマシンのスナップショットを取っていたので、そんなに心配はしていませんでした。

コマンド一つでPCから鯖へのアップロードとダウンロードがそれぞれ行えるようにしているため、プラグインやデータパックを入れるなどのアップデートの際はテストプレイと称してテスト用の鯖を立てて色々やったりもしました。

とはいえ、アクシデントはいくつかありました。今に至るまでの最大のアクシデントですが、やはり「/kill @e」を実行してすべてのモブとエンティティーをkillしてしまったのが一番影響がでかかったですね....killの利用は慎重にしましょう。何かを殺したいときは半径を指定すると致命的なことはだいたい避けられます。

洞窟と崖の世界

マルチプレイあるあるだと思うんですが、マイクラって大人数で作業するとめちゃくちゃ捗るんですよね。僕自身も島を一つ消してますし、中には街ごと作ってしまった人もいました。

そんなわけで、だいぶ開拓されたので次の世界やるかー、ということで、バージョンを1.17にアプデするついでに世界を一新して、（当時はまだ来なかった）1.18の洞窟と崖 +アルファの世界に移行しました。

また、鯖代が結構バカにならなかったので、ちょっと安めのAWS Lightsailに移行しました。（性能を上げたので、結局今までとそんなに鯖代は変わっていませんが、倍くらい良い鯖になりました）

そんなわけで色々やっていたわけですが、1.17の状態で無理やりワールドの高度限界を拡張したりしたためか、めちゃくちゃサーバーが重くなる事態が頻発しており、原因もよく分かっていないので苦しんでいます。また、現在はlog4j2の脆弱性の対応のために一旦鯖は止めています。

これから

log4j脆弱性対応と1.18移行

log4j2脆弱性に対応するついでに1.18に移行してしまおうと思っています。おそらく1.17ではワールドが重いのは変わらないでしょう。もちろんいくつかのデータパックは動かなくなってしまう可能性が高いですが、カスタムエンチャントなどが動けば問題ないかな、と思っています。1.18はワールドがだいぶ改変されており、ワールド改変データパックがなくても充分に「普段とは違うマイクラ」になっているでしょう。

鯖缶bot

なかなか開発が進んでいませんが、Discordから鯖を起動したり削除できるようにしたり、人が居ない時間は落とすことで、「月当たりの鯖代を節約し、その分良い性能のサーバーに移る」という計画をしています。できると嬉しいですね。

終わりに

ということでUT-Craftの話でした。普通のマイクラに飽きた東大生の皆さんはぜひお越し下さい。また、初めてマイクラをやる場合でも、マルチは色々と楽しめると思いますし、他の鯖よりも「最初は易しく、奥が深い」世界になっていると思います。ではまた。

QSVT（Quantum Singular Value Transformation）を3分で説明してみる

序文

この記事は量子コンピューターアドベントカレンダー 2021と、物理学アドベントカレンダー 2021の16日目として作成された。本来は物理学の方には量子誤り訂正について書き、ついでにシリーズ物にしていい日本語資料になればいいかなと思ったが、書きたい内容の1/3くらいを量子コンピューターの方で書かれてしまったので、急遽揃えたというわけだ。記事を2つも書く暇がなかったとも言う。

タイトルで3分で説明してみると言っているのは、説明を端折るための口実でもある。というのも、12月は想像以上に忙しく、記事に時間をたくさん割いているとやるべきことが終わらないということで短くした。大変申し訳ない。

詳しく知りたい方は、以下の論文を読むと良さそうである。いずれもフリーアクセス（arXiv）であり、（英語ではあるが）はるかにこの記事よりも詳しく解説してくれている。

背景

Shorによる量子計算機上での素因数分解が一番知られているが、その他にも様々な「量子アルゴリズム」が考案されてきた。しかし、なぜ量子計算機でのアルゴリズムを研究するのか。その答えは、「古典的な計算機よりも速くなる可能性があるから」である。だが、量子計算機が古典計算機よりも高速にできるタスクというのはあまり知られていないのか、量子アルゴリズムを調べているといくつか基本的なモジュールを見かける事が多い。それは「Quantum Fourier Transform」や「Amplitude Amplification」、「Quantum Phase Estimation」であったり、「Hamiltonian Simulation」だったりである。今回紹介するQSVTは、（ある程度）それらのアルゴリズムを統一的に扱うことができるアルゴリズムである。

QSVT(Quantum Singular Value Transformation)

元論文では、Quantum Signal Processingから順を追ってQSVTを紹介しているが、この記事ではいきなりQSVTを紹介することにする。以下のとおりである。

まず、行列Aなるものを用意する。このとき、任意の行列Aについて、以下のような特異値分解（Singular Value Decomposition）が存在する。

A = W_\Sigma\Sigma V^\dagger_\Sigma

ここで、 W_\Sigma, V_\Sigma はunitaryで、 \Sigma はnon-negativeな実数 \alpha_k をもつ対角行列である。

W_\Sigma, V_\Sigmaの列をそれぞれ {|w_k\rangle},{|v_k\rangle}として、 \tilde{\Pi}:=\sum_k|w_k\rangle\langle w_k|,\Pi:=\sum_k|v_k\rangle\langle v_k|とした上で、 A = \tilde{\Pi}U\PiとなるようなunitaryなUを考える。つまり以下のように左上のブロックにAがあるようなUを考える。

U = \begin{bmatrix} A & \cdot \\ \cdot & \cdot \end{bmatrix}

さらに、このような $U, U^\dagger$ と、 $ \Pi_\phi:=e^{i\phi(2\Pi-I)},\tilde{\Pi}_\phi:=e^{i\phi(2\tilde{\Pi}-I)} $ を用いると、（より厳密には$ \Pi$-controlled notを実行できれば）実は以下のことが言える。

$\phi$の列を$\vec{\phi}$として、以下のような操作を定義したとき、

$$ U_{\vec{\phi}} = \begin{cases} \Pi_{\phi_1}U^\dagger\tilde{\Pi}_{\phi_2}U...\Pi_{\phi_{d-1}}U^\dagger\tilde{\Pi}_{\phi_{d}}U & (d \mathrm{\;is\;even}) \\ \tilde{\Pi}_{\phi_1}U\Pi_{\phi_2}U^\dagger...\Pi_{\phi_{d-1}}U^\dagger\tilde{\Pi}_{\phi_{d}}U & (d \mathrm{\;is\;odd}) \end{cases} $$

以下のような条件を満たす多項式$P(x)$について、

  1. $\mathrm{deg}(P)\leq d$
  2. Pの偶奇とdの偶奇が一致する
  3. $|P|^2\leq1$

必ず以下になるような$\vec{\phi}$が存在する

$$ U_{\vec{\phi}} = \begin{bmatrix} P(A) & \cdot \\ \cdot & \cdot \end{bmatrix} $$

このとき、

$$ P(A) := \displaystyle \sum_{k} P(\alpha_{k}) \ket{w_k}\bra{v_k} $$

であり、

$$ P(A) = \begin{cases} \Pi U_{\vec{\phi}}\Pi & (\mathrm{d\;is\;even}) \\ \tilde{\Pi}U_{\vec{\phi}}\Pi & (\mathrm{d\;is\;odd}) \end{cases} $$

となる。

要約と応用

要するに、「Aを埋め込むようなUnitary Matrixを作る（Block Encoding）」と「$ \Pi$-controlled not」を実現できれば、「Aの特異値（Singular Value）」を基本的に好きな多項式に通して変換できるというアルゴリズムである。

任意の行列について特異値分解が存在すること、そして、特異値を通すための多項式についての制約がかなり少ないことを考えると、幅広い計算がこのアルゴリズムで実現できることがわかるだろう。

実際、元論文では、「Hamiltonianの固有値をtransformする」ことによって「Hamiltonian Simulation」を、「1/xを多項式で近似して、それに特異値を通す」ことによって、「Matrix Inversion」を実現している。Matrix Inversionに関しては、HHLよりも高速化されている。

もちろん、多項式の選び方によっては他の応用もある。詳しくはぜひ元論文を読んでみてほしい。

余談

（ここからは個人的な感想であるので、気にしない人はそのまま別のページに行くと良いだろう。）

基本的にQSVTを実行するためには行列Aをユニタリ行列に埋め込まなければいけない。ここらへんを詳しくやっているのが二本目の論文なのだが、読むと結構大変であることがわかる。大まかに言うと、行列Aの記述をかなりの精度で把握した上で、大量の高階CNOTを行う必要があるのだ。

さらに、QSVTはいくつかのアルゴリズムについては既存のより速いとはいえ、「古典計算機よりも速くする」ためには厳しい課題がある。というのも、（必要な精度で計算することを考えると）単位命令あたりにかかる時間が量子では古典より数百倍〜数千倍遅いためだ。そのため、実用的にこれを行うためには誤り耐性量子計算機で、古典計算機だと到底計算できないような巨大な問題を解くことでようやく利得が現れる。

QSVTに関して最近出た結果として興味深いものに [2111.09079] Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjectureがある。僕もまだ詳しくは中身を精査できていないが、「行列のサイズが小さかったら古典計算機で効率的に計算できる」という主張をしており、つまり、現在の量子計算機（NISQ）だと量子化学計算などを古典計算機よりも高速に行うのはだいぶ厳しいことが示唆される。

NISQ自体の有用性に疑問を投げかけるような論文は今年の後半にいくつか出ており、なかなか先行きが険しいのを感じるが、これからはゆっくりと誤り耐性量子計算機の実装が進んでゆくのだろう。