光を用いた量子アドバンテージ[1]について日本語のまとまった解説があまり(全く?)無いように思えたので、年が変わってしまう前に一筆書きました。
1 光量子計算とサンプリング
超伝導量子ビットやトラップドイオン量子ビットと比較して、光量子ビットの大きな違いの1つは、常に空間を飛び回る点です。この点は我々が日常目にする光と同じです。そのため、光量子コンピューターは必然的に発光源からの光が一定の経路(光路)をとる回路となります。光路上に配置されたデバイスや物質が光と相互作用することで、量子ゲートとして働きます。量子ゲートは光路上に存在するだけで作用するパッシブな量子ゲートと、外部から制御が必要なアクティブな量子ゲートに分けられます。
量子回路に入力された光は自然法則に従い光速で回路を伝わり、少なくともパッシブな量子ゲートは何も手を加えることなく実行されます。もちろん、アクティブな量子ゲートの制御や測定系における電気的プロセスといった律速要因はあります。だとしても、この性質より光量子計算がサンプリングに向いていると言うことは十分可能でしょう。
2 Boson Sampling
[1] で用いられた "Gaussian Boson Sampling (GBS)" という手法は、光量子回路の出力サンプリングから成り立っています。早速 GBS を説明したい所ですが、そのためにまず、その前身である "Boson Sampling" を確認しましょう (文献によっては提案者名の頭文字を付けた略称 ”AABS” が用いられています。”BS” だと ”Beam Splitter” と紛らわしいので、以降 ”AABS” を用います)。
[2] より引用
AABSでは、M 個の入出力パスを持つ量子回路 T を用意します。N (N < M) 個の入力パスにそれぞれ1個のフォトンを入力します。フォトン数が保存されるような量子回路 T であれば、M 個中 N 個の出力パスからフォトンが検出されます(1つの出力パスから複数のフォトンが出力される可能性もありますが、ここでは十分低い確率であるとみなしましょう)。出力パスにおけるフォトン検出のパターンは \bar{n} で表されます。どのようなパターン \bar{n} が検出されるかは、確率的に決まります。この確率分布は量子回路Tによって決まり、以下の式で表されます。
[2] より引用
Perm()は Permanent 関数と呼ばれます。P_N は 置換の集合を表し、例えば N=3 の場合、(1, 2, 3) の全ての置換について総和をとることになります。置換のパターンは N の階乗で増えていくため、Permanent 関数の計算は古典コンピュータで効率的に計算できない問題となります。
T_S は量子回路 T より決まる行列の部分行列(サイズ: N x N)です。部分行列の切り取り方は \bar{n} に依存し、下図のようになります。列はフォトンを入力されたパスから、行はフォトンが検出されたパスから決まります。
[2] より引用
AABSは入力状態の用意が実現上の課題とされました。単一フォトン状態の生成は実験的に難しい課題の1つで、特に多数の単一フォトン状態を同時に用意することは(少なくとも当時は)あまり現実的ではありませんでした。
3 Gaussian Boson Sampling
AABS の課題を回避するために、入力状態をより安定的に生成できるスクイーズド状態に置き換えたのがGBSです。出力パスからは AABS と同様にフォトンを検出します。GBSの場合はフォトン検出パターン \bar{n} の確率分布が次のように表されます。こちらもAABSの場合と同様に、古典コンピュータで効率的に計算できないものです。
[2] より引用
σ_Q は量子回路 T より決まる行列です。 μ_j は「フォトンが検出された出力パスのインデックスに対応する要素を持つベクトル」と思ってください。μ_j \in {PMP} は “Perfect Matching Permutation” であるベクトル μ_j を指します。具体的には次の条件を満たします。
これが何を意味するのでしょうか。仮に μ_j = [1, 2, 3, 4, 5, 6] としましょう。例えば [1, 5, 2, 4, 3, 6] は μ_j のPMPです。k=1, 2, 3 について上記の条件(1), (2)を満たします。
条件(1), (2)をよく見ると分かるのですが、μ_j の PMP は、「 μ_j の要素で重複の無いペアを作れる全ての組み合わせ」に対応します。上で例に挙げたベクトルはそれぞれ "(1, 2), (3, 4), (5, 6)” と “(1, 5), (2, 4), (3, 6)” の組み合わせに対応しています。総和の計算においては、μ_j = [1, 5, 2, 4, 3, 6] に対応する項は となります。
行列 A についてこのような計算を行う関数はハフニアン Haf() と呼ばれ、式(11)は次のように書き換えられます。ただしA_S はフォトン検出パターン \bar{n} より決まる A の部分行列です。GBS および AABS は、このような古典コンピュータで効率的に計算できない関数で表される確率分布からのサンプリングが可能な点で量子の優位性があると言われています。
[2] より引用
「全ての要素についての重複の無いペア」は、グラフにおいて Perfect Matching として知られる重要な問題につながります。ただしグラフの場合は、エッジで接続されているノード同士のペアしか組むことができません。そこでもしも、行列 A をグラフの隣接行列としたらどうでしょうか。エッジの存在しないペアを含む項は 0 となり、逆に全てのペアに対応するエッジが存在する項は 1 ( x 式(11)先頭の係数) となります。
よって、このような行列 A に対応する量子回路 T を用意し、μ_j が全てのノードを含むような出力パターン \bar{n} を得られる確率をサンプリングによって求めることで、グラフのPerfect Matching の個数を計算することができます[3]。ただしこの場合はある特定のパターン \bar{n} を得る確率を求める必要があり、そのような \bar{n} をサンプリングできる確率が行列 A のサイズについて指数関数的に小さくなるという課題があります。この点についてはより優れたアルゴリズムを考案するか、実時間における比較で古典コンピュータを上回る事を目標とする必要があります。
4. Torontonian
GBS にもまだ実験上困難な点が残されていました。フォトン検出器の精度に関する問題です。フォトン1個を検出することは可能な検出器でも、例えばフォトン1個分とフォトン2個分のエネルギーを正確に識別することは現実的に難しかったのです。現実には同一の出力パスから複数個のフォトンが検出される可能性があります (ハフニアンの場合はフォトン数に応じて A_S を拡張することで計算が可能でした)。
そのような困難を緩和するために、フォトン0個とフォトン1個以上を識別可能な ”しきい値付き検出器” を仮定して考案されたのがトロントニアンです[4]。光を用いた量子アドバンテージ論文[1]ではこれを用いています。トロントニアンとハフニアンの接続可能性についても[4]で議論されています。
[1] Zhong, Han-Sen, et al. "Quantum computational advantage using photons." Science 370.6523 (2020): 1460-1463.
[2] Kruse, Regina, et al. "Detailed study of Gaussian boson sampling." Physical Review A 100.3 (2019): 032326.
[3] Brádler, Kamil, et al. "Gaussian boson sampling for perfect matchings of arbitrary graphs." Physical Review A 98.3 (2018): 032310.
[4] Quesada, Nicolás, Juan Miguel Arrazola, and Nathan Killoran. "Gaussian boson sampling using threshold detectors." Physical Review A 98.6 (2018): 062322.