量子レイトレーシングに思いを馳せる

(引用) 左: A Framework for Quantum Ray Tracing [Xi, 2022],
右: Towards Quantum Ray Tracing [Luís, 2022]

1980年代から概念が提唱されるも未だに「なんだかよくわからないけど凄そうワード」として君臨し続けている量子コンピューターですが、最近突如 arXiv に量子コンピューターを用いたレイトレーシングの論文が 2件公開されていました。

我々の知らない間にいつの間にか量子レイトレーシングは実用化されていたのでしょうか。ひょっとすると、ニュースでよく見かけるように超並列計算で無数にレイを飛ばすことでスパコンだと数万年かかるシーンについて数秒でレンダリングできてしまうのでしょうか。 (参考：量子コンピュータ 9000兆倍の破壊力 | 日経クロステック（xTECH）)

もしそうだとしたらサンプリングの改善とかで地道にノイズを減らしたりしている場合ではありません。流行に乗り遅れない為にも、今回は上記の論文を通して最新の量子レイトレーシングの概要を追いかけていきます。

前提知識

量子コンピューターとは

量子コンピューターはその名の通り量子を計算に利用するコンピューターです。量子とは光子、電子、中性子、陽子などに代表される非常に小さな粒子の総称で、我々が直感的に想像する物理法則 (古典力学) からかけ離れた振る舞い (量子力学) をすることが知られています。

詳しい説明は省略していきますが、量子の性質を計算に活かす場合には特に「重ね合わせ」の性質が重要になります。これは量子が複数の状態を重ね合わせとして同時に (確率的に) 保持できることを指し、重ね合わせの状態に対して操作を行うことで並列的に計算結果を行うことができます。

誤解

さて、量子コンピューターでは「並列的に計算が可能」ということを述べましたがこれは「並列的に結果が得られる」ことを意味しないことに注意をする必要があります。

例えば、量子コンピューター上で変数 $x$ が値 0 ～ 9999 の 1万通りの数の重ね合わせの状態で存在していたとします。これに対して演算 $f$ を行うと、 $f(x)$ は $f(0)$ ～ $f(9999)$ の値の重ね合わせになります。ですがこれは「 $f$ を一回評価するだけで 10000 通りの計算が並列に行えてすごい！」ということではありません。重ね合わせの状態は一度観測を行うと壊れてしまうという性質があるため、 $f(x)$ を一度評価すると $f(0)$ ～ $f(9999)$ のうちランダムな値が一つ得られるだけです。 $f(0)$ ～ $f(9999)$ の値をすべて計算したいということならば、当然この方法だと古典的な計算よりも膨大な時間がかかってしまいます。

このように、量子コンピューターを使うとそのまま様々な問題が並列化・高速化できるというわけではなく、高速化をするには量子コンピューター専用のアルゴリズムを用意してやる必要があります。 (そしてもちろん、任意の問題に量子コンピューター用のアルゴリズムが発見されている or 存在する訳ではありません。)

量子ビット

古典コンピューター上ではビット単位で演算を行いますが、量子コンピューターで用いられる単位が量子ビット (Qubit) です。これはひとつで 0 と 1 両方の状態を重ね合わせで持つことができ、 N 個の量子ビットでは $2^N$ 個もの状態を表せます。

量子回路では、複数の量子ビットを並べたレジスタに対して操作を行います。このレジスタ数がどれだけ大きいかが計算可能な問題の大きさを決める一要素になりますが、去年時点で最新の量子コンピューターが 100 量子ビットとからしいのでまだまだ発展途上であるということが伺えます。

IBMが100量子ビット超え量子コンピュータ 1000量子ビット向け次世代システムも23年に予定 - ITmedia NEWS

有名な量子アルゴリズム

Grover のアルゴリズム

Grover のアルゴリズムは、データの検索を高速に行うための量子コンピューター用アルゴリズムです。 $N$ 要素の非構造化データリストからデータを検索する際、古典コンピューター上では $O(N)$ のオーダーの計算量になりますが、 Grover のアルゴリズムを用いると $O(\sqrt{N})$ での計算が可能になります。

量子回路を用いて「 $N$ 要素すべての状態の重ね合わせを入力とし、それに含まれる各状態に対して正解か不正解かを判定する」という操作を構成することがもし可能ならば、その操作に更にいくつかの操作を加えることで「正解の状態のみの振幅を増幅する」という操作を構成することができます。そしてその振幅増幅の操作を $O(\sqrt{N})$ オーダーの回数で行うと正解の振幅を最大化することができます。こうして得られた重ね合わせ状態に対して観測を行うと、高い確率で正解を得ることができます。

なお、この Grover のアルゴリズムのように量子コンピューター上で計算される量子アルゴリズムは確率的に結果が得られるのが特徴です。どうしても得られた結果が本当に望む条件にマッチしているかを確認したい場合は例えば古典コンピューター上で検算するなどの操作が必要になります。まあグラフィックスの場合はちょっとぐらい値が間違っていてもよしとできる場合が多いので量子計算との相性は良さそうですね。

Quantum Counting

Grover のアルゴリズムの問題点ですが、 $N$ 要素のリストの中に正解がいくつあるかを前もって知っていなければならないという事があります。答えは知らないが答えの個数は知っている、という状況は多くないのでこれは大抵の場合で問題になります。

Quantum Counting はこの弱点を補完するもので、 Grover のアルゴリズムでの振幅増幅操作の周期性から正解の個数を推定するようです。 (自分も正直あまり詳しくは理解できてないです。)

A Framework for Quantum Ray Tracing

[2203.15451] A Framework for Quantum Ray Tracing
Xi Lu, Hongwei Lin

いよいよ本題で、まずこちら今年 3月 29日に公開された論文です。シーン内に飛ばす複数のパスを重ね合わせ状態で表現するパストレのフレームワークについて述べています。通常のパストレーシングでは指数的にパスの数が増加するのを嫌って一度の反射ごとに1本のレイしか飛ばしませんが、この論文の手法では反射ごとに複数のレイをサンプルしているのが特徴です。

重ね合わせ状態のレイを入力としたシーンとの交差判定・反射のレイの生成などのオペレーターを定義しそれを繰り返して適用することで重ね合わせ状態のパスを生成します。重ね合わせで表現されたパス集合の放射輝度平均値を得る際には、「パストレをすることで得られる放射輝度の平均値」を「検索アルゴリズムの解の個数」に変換して解く Grover のアルゴリズムを構成し、Quantum Counting でその解の個数を推定しています。 (RGB の 3チャンネルが必要な場合はそれを 3回計算することになる。)

古典的なモンテカルロ法ではエラーを $1/n$ 倍にする場合は $n ^2$ 倍の計算量が必要になりますが、提案手法を使うと $n$ 倍の計算で済むとしています。論文を読む限りだとこれは Quantum Counting がそうした速度で収束することに由来しているようです。

ただし、示されているフレームワークは理論上完全に実装可能とされていますが、現行の量子コンピューター上ではレジスタの数や精度が全く足りないことからシミュレーター上を含め実装はされておらず、この論文はあくまでその理論を示すのみになっています。

課題

現行の量子コンピューターの上では実装不能というのはもちろん課題ですが、その他にも理論的に解決すべき部分はまだ残されています。

まず、論文中では条件を揃えるために古典コンピューターと量子コンピューター両方でレイとシーンの交差判定について Acceleration Structure を使わない場合を想定して比較していますが、量子コンピューターではまだ Acceleration Structure を使用する方法は確立されていないのでそれを考慮すると単純な理屈の上においてもまだ古典コンピューター上の方が高速な場面も多いです。

また、論文中でのレイの反射方向のサンプリングは格子状の単純なものに留まっており、 Importance Sampling などは考慮されません。 (というかそもそも量子回路上でのマテリアルモデル、というのがまだ議論される段階になってないというのもあります。)

複数パスの重ね合わせ状態を作る際、反射ごとに複数のレイをサンプルしていくよりは反射ごとに飛ばすレイを 1本だけにしておいて最初から大量のパスを生成する方がパスの間の相関が下がって良さそうに思いましたが、そうなっていないのも上記の格子状サンプリングをしている事情によるものと思われます。

そのほか、複数のパスを重ね合わせで表現している都合上すべてのパスについて追跡するパス長が同一である必要があり、このためロシアンルーレットなどの手法が取れず unbiased な結果を得ることができないという点についても論文中で言及されています。

Towards Quantum Ray Tracing

[2204.12797] Towards Quantum Ray Tracing
Luís Paulo Santos, Thomas Bashford-Rogers, João Barbosa, Paul Navrátil

続いて今年 4月 27日に公開された論文です。こちらでは、レイとシーンの交差判定に Grover のアルゴリズムを用いることで高速化を図ります。 Acceleration Structure を用いない前提だと古典コンピューターの場合での計算量は $O(N)$ になりますが、提案手法では $O(\sqrt{N})$ となります。

古典アルゴリズムのレイトレーサー実装から量子アルゴリズムの交差判定を呼び出すというハイブリッドな構成をとっていることが特徴で、交差判定のアルゴリズムを示す以外にも量子計算で得られる確率的な結果を安定させるためのテクニックも示しています。

この論文の最もキャッチーな点は量子レイトレーシングを用いた絵が出ていることです。

(論文中より引用) 真ん中と右が量子レイトレーシングによるもの。"Qornell Box" という小洒落たシーン名。

なんとか絵を出すために

プリミティブは axis-aligned な矩形のみにする
座標はすべて整数で扱う
レイトレース時の深度値なども整数で扱う

などの涙ぐましい努力が行われています。

深度値を整数にしたことで上記 "Qornell Box" の部屋の隅は Z-fighting が起きてるわけですが、古典レイトレース時は決定的な動作をするので境界が綺麗な直線になる一方で量子レイトレースの方は同じ深度値のプリミティブが確率的にサンプルされるのでジャギジャギになっているのが面白いですね。

量子コンピューター上でのレイとプリミティブの交差判定は下図のように構成されています。これは、一本のレイとシーン内すべてのプリミティブの重ね合わせに対して交差判定を行います。プリミティブは axis-aligned な矩形なので、プリミティブを含む平面とレイの交点がプリミティブの内部に含まれているか、ということを X,Y,Z 平面それぞれについてチェックすることで交差判定が行われています ( $\hat{c}_X, \hat{c}_Y, \hat{c}_Z$ )。またそれに加え、交点がレイの持つ最大距離よりも近い場合にのみ交差判定を成功させるためのチェックも行っています ( $\hat{c}_D$ )。

さてここで問題になるのが、(座標を整数としていた事からも分かるように) float 値をまともに扱うことができない量子コンピューター上でレイと平面の交点を計算できるのか、ということなのですが 残念ながらこれはできません。するとどうやって絵を出しているかということなのですが、論文中での実験では古典コンピューター上ですべてのプリミティブの平面に対する交点計算を予め行っておいた上でその結果のテーブルを量子コンピューターに渡してやることで実現しています (交点までの距離の計算についても同様です)。つまり古典コンピューター上で計算を行っている以上計算量は結局 $O(N)$ になってしまっているのですが、論文中では今後量子コンピューターが発展すれば理論上実装できない道理はないのでまあ本質的には $O(\sqrt{N})$ だよねという主張になっています。だから一番キャッチーな結果の絵については実は完全に量子コンピューターの上で実現されている訳ではないということに注意する必要があります。論文のタイトルが "Towards Quantum Ray Tracing" という一歩引いた感じになってるのもこの辺の事情かもしれません。

さて、そのほかアルゴリズム的な見どころについてですが、実は上記の交差判定にそのまま Grover のアルゴリズムを適用してもレイトレース用の交差判定を正しく行うことはできません。上記の交差判定は「レイと交差する最近傍のプリミティブを判定する」のではなく「レイと交差するすべてのプリミティブを判定する」ものになっているので、これに対し Grover のアルゴリズムを適用しようとした場合、

答えの数がわからないので Grover のアルゴリズムを適用できない
適用できても、最近傍のプリミティブを返すのではなく、交差するすべてのプリミティブのうちからランダムにひとつを返すアルゴリズムになってしまう

という点が問題になります。

答えの数がわからないという問題については、答えの数の仮定を指数的に増加させながら Grover のアルゴリズムを何度も繰り返して試す Adaptive Exponential Search という手法を用いて論文中では対応しています。 Quantum Counting を使えばいいのでは、と思ったのですが使ってない理由については読み取れませんでした。 Adaptive Exponential Search の繰り返しのオーダーは $O(\log{N})$ になるので全体の計算量はまだ $O(\sqrt{N})$ になるみたいです。

そして最小の距離のプリミティブを得たいという問題については、Minimum Finding Algorithm という方法を用いています。これは「今まで見つけたプリミティブよりも更に距離が近いプリミティブ」のみを選択するフィルターを掛けながら Grover のアルゴリズムを定数回繰り返す、というシンプルなものです。シンプルすぎてこれでいいのかという疑問があるのですが、定数倍なので全体の計算量はやっぱり $O(\sqrt{N})$ です。これは当然得られるプリミティブが常に最近傍となる訳ではないので、上に出た "Qornell Box" シーン真ん中のように描画するプリミティブに穴が空いてしまったりする場合があるのですが、これについては最近傍判定したプリミティブに付いての情報を画像空間で上下左右隣接したピクセルと共有してチェックする事で誤った結果が出る確率を抑える工夫をしています。

課題

繰り返しになりますがこの論文も実際の量子コンピューター上でレイトレーサーを構成するにはまだ遠いということを述べています。レジスタの不足についてもそうですが、この論文は特に実際の量子コンピューターを使用した際のハードウェア由来のノイズについても触れていました。上記の "Qornell Box" シーンのレンダリングを含む実験はシミュレーター上で行われていましたが、ごく小さいシーンでの交差判定を実際の量子コンピューター上で動かしてみた結果も示されていました。その結果が下図ですが、4 つのプリミティブを含むシーンで交差判定を行った場合、シミュレーター上では 100% の確率で正しいプリミティブを返す事ができていましたが同じ計算を量子コンピューター実機上で動かした場合にはほぼ均等な確率で 4つのプリミティブを返す (つまりまったく何も判定してない) ようになってしまったようです。

現行の量子コンピューターは誤差が発生しやすく、実用化するには誤り訂正の仕組みを確立することが重要と言われています。

またこれも一つ前の論文と同じですが、こちらでも Acceleration Structure なしの条件で古典コンピューターとの計算量比較を行っており、量子コンピューターの方が理論上速いということが言えるのはまだ限定的な条件下での話になります。

所感

量子コンピューターのハードウェア性能が語りていない点、 Acceleration Structure や Importance Sampling など古典コンピューター上のレイトレースでは基本となる技術が量子コンピューター上ではまだ実装が存在しない点などから現状ではまだ量子レイトレーシングが十分な性能を発揮するには遠そうです。また、提案されているアルゴリズム自体についても思ったより急激な速度改善がもたらされる訳ではないのだな、と思った方も多いのではないでしょうか。量子コンピューターは夢の技術かと思いきや意外ともっと堅実な概念のようです。

とはいえ、今後色々なアルゴリズムが発見されていくと更に計算量のオーダーが改善されていくことは十分期待できます。この記事の中で触れただけでもまだ手つかずの分野というのがありますし、技術者視点で考えると量子コンピューターはすごく楽しそうなテーマだなと感じます。

みんなもやってみよう

量子コンピューターのライブラリやシミュレーターは既に世の中に色々あるようで、意外と簡単に試すことができます。

例えば Qiskit は python 用のライブラリですが、記述した量子回路についてお手持ちのパソコン上でのシミュレーターを走らせる事ができます。また実機を使いたくなった場合は AWS などで量子コンピューターのインスタンスが借りられるようです。もうそんな時代になっていたのか。

あと量子コンピューターについて詳しく知りたい場合は Qiskit の公式テキストが勉強になったのでこちらもどうぞ。

Qiskit を使った量子計算の学習

余談

レイトレ合宿に量子レイトレーサー持って行って周囲を威圧したかったので読み始めたけどそれはちょっと厳しそうだったね。

水鳥コンビナート

CGとか