Ⅰ　グローバー･アルゴリズムに量子優位性はない、と主張する論文

【0】はじめに
　フラットアイアン研究所[*1]の研究者は、『グローバー･アルゴリズムに、量子優位性はない』と題する論文[*2](以下、本論文と呼ぶ)を発表した(23年3月20日arXivにて公開)。グローバー･アルゴリズムは、ショアのアルゴリズムに次いで(1996年、Lov Kumar Groverによって)発見された由緒正しい量子アルゴリズムであり、古典アルゴリズムよりも速いことが『数学的に証明されている』。従って、本論文は相当衝撃的であり、例えトンデモ論文であったとしても、吟味する価値はあると思われる。しかし、なぜか日本では全く触れられていない(ようである)。第一人者であるスコット･アーロンソンは、直ちに反応し｢もちろん優位性はある！｣とブログ[*3]に投稿している。
　なお、数理分野でGAと言えば、一般的には、遺伝的アルゴリズム(ITなら、グーグル･アナリティクス)を指すと思われるが、本論文では、グローバー･アルゴリズムをGAと略しているので、以下、それに倣う。

【1】本論文の主張
(1)　本論文の題名は、相当”いきってる”。ただ、実際の主張は、そこまでと尖っていないと思われる。まず、本論文では、GAの重要な要素である量子オラクルの構築は、実は簡単ではない、という問題意識がある。同じ問題意識を持った論文[*4]が、2021年5月、スタンフォード大学の研究者によって発表されている。｢数の分割問題｣をGAで解くというお題において、量子オラクルを物理実装することで、｢オラクル構築は簡単じゃない問題｣を解決した、という内容である。
　[*4]の量子オラクルの実装には隠れた計算コストがあって、古典アルゴリズムを越えていないと指摘する論文[*5]が、米ロスアラモス国立研究所の研究者によって発表された(23年8月)。その上で、同じお題において、隠れた計算コストを取り除き、二次加速を達成する量子オラクルを生成した、と主張している。
(2)　本論文に戻る。
1⃣　本論文は、古典的な物理形式(物理表現)や、古典的に効率的にシミュレートできる量子回路を使って、GAの量子オラクルを構築できるのであれば、GAを古典アルゴリズムでシミュレートできると主張する。誤解を恐れずに言えば、特定条件下でGAの｢脱量子化｣が可能であると主張する。
2⃣　さらに、NISQ(Noisy Intermediate-Scale Quantum device)でもFTQC(誤り耐性汎用量子コンピュータ)でも、量子優位性は期待できない、と一刀両断している。NISQに対しては、｢数十億ゲートに対して、10億分の1よりも高い精度で、40量子ビットを操作する必要があるので、非現実的｣と定量的に批判している。FTQCに関しては、表面符号を例に出し、ただでさえ誤り訂正は破綻しているのに、GAで追加された複雑さを、さらにカバーするなんて不可能、という議論を展開している。

【2】本論文のアイデア
　本論文の重要なアイデアは、｢量子オラクルへの呼び出しの間に、GA を実行している量子コンピューターの内部状態に存在する、量子もつれのレベルが低い｣という観察に基づいている。つまり、GA は重ね合わせ (量子並列性)は強力に活用している一方で、量子もつれは、ほとんど利用していない、という観察に基づいている。言い換えれば、量子計算の象徴であり量子計算高速化の源であると目されている、量子もつれを利用していないから、古典的にシミュレートできるであろうという洞察である。
　実際GA において、❶ 折り返しで発生する量子状態は低もつれ状態であり、結合次元１＋Sの｢行列積状態(MPS)｣で、❷量子オラクルは、結合次元１＋Sの｢行列積演算子(MPO)｣によって古典的に表現できる、と主張する。ここで、解の数をS個としている。

【3】事前整理
(0)　量子優位性及び量子超越性
　量子アルゴリズムが、最も高速な古典アルゴリズムより10のべき乗で速くなること(指数関数的加速;指数加速)を量子超越性と呼ぶ。これに対して、2乗で速くなること(二次関数的加速;二次加速)は、量子優位性と呼ばれる。最も有名な｢ショアのアルゴリズム｣は、指数加速(量子超越)である。ただし、ショアのアルゴリズムよりも速い古典アルゴリズムが『存在しないことが、数学的に証明されているわけではない』。
　一方、グローバー･アルゴリズムは二次加速(量子優位)に過ぎないが、グローバー･アルゴリズムよりも速い古典アルゴリズムが『存在しないことが、数学的に証明されている』。本論文の主張｢グローバー･アルゴリズムよりも、速い古典アルゴリズムを見つけた｣と矛盾するように見えるが、実は、矛盾しない。その点に関しては、追々記述する。

(1)　量子アルゴリズムの2大ファミリー
　本論文の記述によると、量子アルゴリズムには、2大ファミリーが存在する。
1⃣　量子フーリエ変換を使うファミリー
　このファミリーには、既存の暗号を危険に晒す｢ショアのアルゴリズム｣、量子化学問題を解くために提案された量子位相推定アルゴリズム(※)他が含まれる。これらのアルゴリズムは、指数加速を実現する。
※　ただし、量子フーリエ変換(QFT)はハードウェア効率が悪いため、実務上は、QFTを使わない｢ベイズ推定(ベイジアン)量子位相推定アルゴリズム｣等が使用されている。例えば、米Quantinuumの研究者は、ベイジアン量子位相推定アルゴリズムを使った量子化学計算を(NISQマシンで)実行した、という論文を発表している。こちらを参照。
2⃣　振幅増幅を使うファミリー
　グローバー･アルゴリズムは、このファミリーに属する。GAは、関数の最適化・グラフ問題の解決・金融デリバティブの(オプション)価格付け・パターン認識、といった多くの使用例が考えられるので、実用性が高いと見做されている。
　実用性が高いと見做されているものの、実は、重要なピースが欠けている。GAには、｢オラクル｣(†)という重要な要素がある。オラクル(この場合、正確には量子オラクル)は、入力に依存した量子操作を行うブラックボックス演算子、と定義できる。GAでは、アプリケーション毎に最適な量子オラクルが、既知である(言い方を変えれば、”誰かの手によって、勝手に準備されている”)ことを前提としている。しかし、実際に実装する際には、量子オラクルを特定の量子回路として実現する必要がある。本論文では、これは実際には簡単でないとして、量子オラクルを古典的に表現した量子インスパイアード･アルゴリズムを提案している。
†オラクル(Oracle)は、日本語では｢神託｣という意味である。なぜ神託と呼ばれているかというと、｢中身はブラックボックスで、ただ答えを教えてくれる、抽象的な存在｣に過ぎないからである。探索問題全体で言うと、当然、古典オラクルというものも存在するが、ここでは、触れない。

(2)　グローバー･アルゴリズム(GA)
　ここでは、観念的な話ではなく、アルゴリズム的な説明を行う。
　GAは、当たりを高確率で推測するアルゴリズムである。まず関数y = f(b)を考える。ここで、bはN = 2ⁿ 個の値を取ることができる。bをビット列あるいは、nビットの文字列と考えると分かり易いかもしれない。yはシンプルには、0(失敗)、1(成功)で表される。
　GAは、f(b)を実装する量子オラクルへの √N 回の呼び出しだけで、与えられたy に対する値 b = f⁻¹(y) を見つけるアルゴリズムである。一方、単純な総当たり検索(古典的探索)では、約 N 回の呼び出しが必要になる。GAは、重ね合わせ状態に対して、当たり外れの判別が可能である。その量子並列性の利用が、高速性に貢献している。一方で、重ね合わせは使っても、もつれは使っていないことは、既に述べた。
　細かい話をすれば、解(上記の設定ではb)が一つの場合には、√N 回の呼び出しで十分である。複数個(例えばK個)の場合には、√(N/K)回の呼び出しで十分である。また、解の個数が、未知の場合にも｢量子数え上げ｣という手法を援用することで、GAは適用可能である。
　さらに余談･･･GAの二次加速は、探索する対象のサイズNが大きくないと成立しないが、Nが大きい場合にGAは価値があるとされているので、問題とはみなされない(サイズが小さい場合に、GAが有効なケースは、こちらを参照)。

(3)　テンソルネットワーク[*6]、[*7]
　物理の文脈で述べると、テンソルネットワークは、近似表現の一つ(ただし、めっちゃ使える近似表現)ということになる。テンソルネットワークは、情報圧縮を効率的に行って、重要な自由度を抽出するというポリシーに則って自由度を減らすことで、精度の高い近似を可能にする。物理的に重要な自由度を抽出することを、量子情報理論の言葉で表現すると、｢エンタングルメント･エントロピーを可能な限り保持すること｣だという。また、計算理論の文脈で述べると、テンソルネットワークを利用したシミュレーション計算は、縮約をとる順序(contraction path)の工夫及び特異値分解による低ランク近似によって、計算コストを下げることが可能な計算ということになるだろう。縮約は、ベクトルや行列(≃テンソル)から、演算を通じて、スカラーを計算することを指している。トレース･アウト(tr)をイメージすると分かり易いだろう。
　次に行列積状態(Matrix Product State:MPS)と行列積演算子(Matrix Product Operation:MPO)について、簡単に整理する。1次元のテンソル(鎖)に対して縮約を取ったものを、行列積と呼ぶ。行列積の量子力学的描像は、近似波動関数である。行列積(≃波動関数)に対応する量子状態が、MPSである。MPOは、演算子の行列積表現という説明で十分であろう。また、テンソルの各足の数(行列の行数、列数)を結合次元(bond dimension)と呼ぶ。
　蛇足ながら、量子計算におけるテンソルネットワークの実例には、以下がある：
1⃣　2019年にGoogleは、｢ランダム量子回路サンプリング｣という問題で、量子超越性を達成したと宣言した(直ちに、IBMが反論した)。中国の研究者は2021年11月、エクサスケールのスパコンがあれば、この問題が同程度の時間で解けるという論文[*8]を発表した。この時、使われた古典アルゴリズムが、テンソルネットワークである。
2⃣　クレディ･アグリコルCIB、Pasqal及びMultiverse Computingは、ブラックｰショールズｰバレンブラット･モデル及び、ヘストン･モデルを対象に、次の２つを報告した(23年1月)[*9]：
❶　テンソルネットワークを利用して、深層ニューラルネットワーク(DNN)と同じ精度を達成するのに必要なパラメータ数を、大幅に削減した。
❷　DNNと同じパラメータ数では、高速化を実現した。
　こちらを参照。
3⃣　スイスTerra QuantumとCirdan Capital(英国の金融ブティック)は、マルチアセット(つまり高次元)の自動コーラブル･オプションを、"ベンチマークに比べて"75%速くプライシングできた、と発表した(23年7月6日)[*10]。テンソルネットワークを使った量子アルゴリズムを使用した、ようである。
4⃣　英国(オックスフォード大学、ケンブリッジ･クォンタム･コンピューティング、バース大学)、米国、シンガポール、ドイツの研究者は、テンソルネットワークを用いた乱流解析と、LES(ラージ･エディ･シミュレーション)の結果とを比較して、速度場を表すために必要な自由度(計算格子点の数)を1桁以上減らしても、同等以上の精度が得られた、と発表した[*11]。こちらを参照。
5⃣　IBMの研究者は、｢物理シミュレーションにおいては、NISQマシンであっても量子誤り抑制(緩和とも言う)を用いることで、量子計算は古典計算では得ることができない結果を得ることができる｣という内容の論文[*12]を発表した(23年6月15日)。ちなみに、ここでは、速さではなく精度で古典を上回ると、主張されている。詳しくは、こちらを参照。古典計算には、テンソルネットワーク法を使用している。
　ちなみに、これに対して、スウェーデンのチャルマース工科大の研究者は｢スパースパウリダイナミクスに基づく古典的アルゴリズム｣は、シングルコアのPCで実行した場合でも、量子シミュレーションの計算時間よりも桁違いに高速で、同様の結果を得られたと主張した[*13]。
　さらに、フラットアイアン研究所とNY大の研究者は、｢テンソルネットワーク法で、量子手法や他の多くの古典的手法から得られた結果よりも、著しく正確で精密な古典的シミュレーションを行うことができる｣ことを示した[*14]と主張した。[*14]の著者の一人は、本論文の筆頭著者でもある。

(3)　命題論理式の充足可能性判定(SAT)問題[*15]
　本論文では、GAを3-SAT問題に適用している。3-SATはSATの特別な場合なので、SATについて簡単に整理する。なお、SATは、最初にNP完全性が証明された間題である。
　いくつかの用語を導入する。｢真偽割り当て｣により、命題論理式に真(true)が割り当てられるとき、真偽割り当ては、命題論理式を充足するという。｢真偽割り当て｣とは、ブール変数を{(真＝)1、(偽=)0}に対応させる関数である。命題論理式を充足する真偽割り当てが存在するとき、命題論理式は充足可能という。
　論理演算･論理関数の文脈で、論理変数及び論理変数を否定した変数を、リテラルという。リテラルを論理和で結合した論理式を節(英語ではclause。ちなみにclauseは、法律の文脈では条項と訳される)という。節を論理積で結合した論理式をCNF(Conjunctive Normal Form)式という。Conjunctionは、節を論理積で結合したもので、日本語では｢連言｣と呼ばれる。リテラルを論理和で結合したものは、｢選言｣と呼ばれ、英語ではdisjunctionである。
　全ての節の長さがkで与えらえるSAT問題を、k-SAT問題という。kが3以上の場合のk-SAT問題が、NP完全である。中でも、3-SATは代表的な NP完全問題であり、多くの問題で NP困難性を示すのに使われている。
　なお[*16]では、Googleの量子化学者Ryan Babbushが『GAを3-SATに標準的な方法で適用しても、3-SATに対する最良の古典的アルゴリズムに対して、最悪の場合(特に平均的な場合)2次的なスピードアップは得られないことはよく理解されている(ので、検証対象としては妥当ではなく)』、『3-SATではなく回路充足可能制問題であれば、最悪のケースでも、全ての古典アルゴリズムに対してGAは二次加速を達成する(ので妥当)』と穏やかに指摘している。

【4】量子インスパイアード･グローバーアルゴリズム(Quantum inspired GA:QiGA)
(1)　QiGAの詳細
　QiGAでは、(非解空間の折り返しである)量子オラクル U_wをMPOで表現する(解の個数がS個の場合、結合次元は1+S)。QiGA の入力は、古典オラクルではなく、量子オラクル(つまりは、量子回路)である。量子オラクルの量子回路が古典的にシミュレートできる場合、量子コンピューターが量子オラクルへの O(2^n/2) 回の呼び出しを必要とする一方で、QiGA はO(n) 回の計算で、問題を解決できる(多くの場合は量子オラクルへの 1 回の呼び出しで問題を解決できる)と主張している。
　QiGAの計算ステップは以下の通り。
❶　古典シミュレーション手法を使用して、結合次元χ = 1 + S の MPS として |Ψ_w⟩ を計算(†)。
❷　|W˜⟩ = |Ψ_w⟩ − |s⟩ を計算し、正規化して結合次元 χ = S の MPS |W⟩ を取得。
|s⟩は、初期状態にアダマール･ゲートを作用させて作成した、(重みが等しい)重ね合わせ状態である。
❸　|W⟩からサンプリングして、一様な確率で状態 |w^α⟩を取得(††)。|w^α⟩が求める解である。
†　本論文では、|Ψ_w⟩= U_w|s⟩を直接求める代わりに、|±⟩状態の積である|β⟩に対して振幅 ⟨β|Ψ_w⟩を古典的手法(tensor cross interpolationアルゴリズム[*17])で求める。tensor cross interpolationアルゴリズムの和訳は未だないようなので、便宜上、直訳した｢テンソル相互補間法｣とする。テンソル相互補間法は、能動学習を利用して、量子回路 U_wについて知ることなく、外部の古典的なサブルーチンのみを使用して⟨β|Ψ_w⟩ を計算する。
††　MPSには、一般的にlog(N)×S²でスケーリングする、非常に効率的なサンプリングアルゴリズムが認められている[*18]。故に、|W⟩から|w^α⟩を取得するのは効率的である。S<100、n<100の場合、この方法で1サンプルを収集する時間は1秒以下らしい。

(2)　3-SAT問題に対するシミュレーション
　本論文では、QiGA をデモンストレーションするために、3-SAT問題に対してシミュレーションを行った。正確には、①完全にランダムな SAT 節と、②準一次元構造を持つ節の2パターンで実行しているが、①の結果のみを示す。
1⃣　セットアップ
　最大 n = 40 個の変数または量子ビットに対して、テストを実施した。変数に対する節の比率は4.2である。 4 つの Xeon 3.6 GHz プロセッサと 256 Gb の RAM を備えた単一のワークステーション上でITensor ソフトウェアを使用した。ITensorは、テンソルネットワーク法で用いる線形演算などの機能をサポートしているC++ライブラリ。元々は多体電子系の計算用らしい。
2⃣　結果
　QiGAが現実的な時間で結果を出せることを示した。n = 40 個及び解の個数が174個で、6.5時間を要した(この場合の結合次元は10,374)。解の個数が0の場合、4.2分であった(結合次元は1,402)。

(3)　GAにおける量子優位性の検証
　本論文では、GAはNISQにおいてもFTQC(誤り耐性汎用量子コンピュータ)においても、量子優位性を示さないので、QiGAはGAよりも優れている、と主張する。本論文で、GAが量子優位性を示さないと考える理由は、ノイズを除去しきれないと考えるからである。GAにおいては、 オラクル演算子と拡散演算子の適用を複数回繰り返す。オラクル演算子と拡散演算子の適用を「1セット」と考えて、セットとセットの間に、1回のノイズを考慮する。具体的には、 脱分極ノイズを導入する。オラクル演算子が作用している間び、拡散演算子が作用している間には、ノイズはないと仮定しているので、GAにとって都合が良い条件となっている(と、本論文では述べている)。
1⃣　NISQの場合
　通常、拡散演算子には 2n個のトフォリ･ゲートが必要で、各トフォリ･ゲートは、6個のCNOT ゲートと 7個のT ゲートを含む15個のゲートに分解する必要がある(らしい)。全結合を仮定すると、GA の(オラクル演算子と拡散演算子を合わせた)総ゲート数Nは 、N ≥ 60 n 2^n/2 に達する。最終的な成功確率を1/2 としても、各ゲートにおける典型的な誤差率εは、1/(60 n 2^n/2) 程度となる。40量子ビット(n=40)とすると、εは 3.97×10⁻¹⁰となる。つまり、数十億ゲートに対して、10億分の1よりも高い精度で、40量子ビットを操作する必要がある。本論文では、これは、非現実的であろうとみなしている。
2⃣　FTQCの場合
　量子誤り訂正符号として、表面符号を想定している。あまり定量的な議論は行われていないが、GA実行には(先に述べたように)、2n個のトフォリ･ゲート＝2n×[6個のCNOT ゲートと 7 個のT ゲートを含む15個のゲート]が要求される。ただでさえ、アップアップのパンパンなのに、GAをFTQCで実行するために要求される、誤り訂正が破綻するのは明らかであろう、と結論付けている。(ただ、GAとは無関係に、表面符号でFTQCというアプローチは、いずれにしてもダメだろう。)

【5】考察など
(1)　GAは、非構造的データベースに対する探索において、古典アルゴリズムよりも二次関数的に高速であることが数学的に証明されている。構造的データベースは、その限りではない。つまり、古典アルゴリズムに対して、二次加速は必ずしも保証されない。構造的データベースに対する探索では、古典アルゴリズムが速いこともあるし、量子アルゴリズムが速いこともある。ケースバイケースということになる。
　QiGAは、量子オラクルにテンソルネットワーク構造を見出しているため、構造的データベースに対する探索アルゴリズムと考えられる。つまり、量子インスパイアード古典アルゴリズムであるQiGAが、量子アルゴリズムであるGAよりも高速であっても、実は、不思議ではない。
　蛇足ながら、構造があるのと構造がないのとで、大きな違いが現れるケースのイメージ(?)として、次のような分かりにくい例えを上げてみよう：物理的描像では、系の対称性を計算に反映することができれば、計算が速く行える(あるいは、解析解が得られる)。機械学習の文脈では、ドメイン知識を使うと収束が速くなる。コンサルティング･サービスの提供だと、業務知識を使うこと、上滑りしない納得感のある施策を提示できる(はず)。

(2)　改めてQiGAの高速化の理由を探索すると、次のように整理できるだろう：㊀まず、振幅⟨β|Ψ_w⟩を、古典的手法で効率的に計算する(それができなければ、高速化は実現しない)。それが可能なのは、|Ψ_w⟩ がMPSで表現されているからだろう。㊁⟨β|Ψ_w⟩から、|Ψ_w⟩を計算する。㊂|Ψ_w⟩ から|s⟩ を減算したものを正規化して、|W⟩というMPSを求める。㊃|W⟩から効率的にサンプリングして、一様な確率で解状態 |w^α⟩を得る。効率的にサンプリングできるのは、|W⟩がMPSだからであろう。㊀と㊃は、ミラクル連発に見えるが、MPS(＝テンソルネットワーク形式)であることを十分に活用した結果ということだろうか。

(3)　本論文は、多くの議論が交わされ[*16]、検証も行われている[*19](ただし、どちらも日本人は参加していないようである)。議論の中には、｢GAが構造化データベース探索で、二次加速を必ずしも達成しないことは既知であり、本論文は、分かり切ったことを述べているに過ぎない｣、｢(本論文のアルゴリズムは)GAではないから、比較が妥当ではない｣等の指摘がある。また、構造化データベース探索という土俵なので、QiGAよりも速い古典アルゴリズムが存在するかもしれない。

(4)　GAには量子優位性が生じないという主張をNISQ、FTQCのどちらにも展開している。NISQに対しては、複雑なアルゴリズムは制御精度の意味で、非現実的というロジックであるから、GAに限った話ではない。FTQCに関しては、表面符号を使った量子誤り訂正が破綻しているというロジックなので、これもGAに限った話ではない。
　本論文に対しては、量子オラクルを古典的に構築する実践方法を提示した、というシンプルな見方ができるかもしれない。

(5)　本論文を否定せずに、GAを使い｢NP完全問題(数の分割問題)で、二次加速を達成した｣と主張する論文がある。先に示した[*5]である。

Ⅱ　サイバーセキュリティ･システムで、量子＞古典と主張する論文　
【0】はじめに
　伊ミラノ工科大学他の研究者は、サイバーセキュリティ分野の計算において、量子的手法が古典手法よりも、高速であると主張する論文[*20](以下、本論文)を発表した(2023年9月23日公開)。サイバーセキュリティ･システムとは、具体的には、ネットワーク型侵入検知システム(NIDS)を指している。古典手法とは、制約付きボルツマン･マシン(RBM)であり、量子的手法は量子版のRBM(QRBM)である(詳細は後述)。

【1】本論文の主張
　実際のサイバーセキュリティ･データセットを使用してRBMとQRBM を比較したところ、QRBMでは、ネガティブ･フェーズ(negative phase)の推定が、”最大” 64 倍高速化された。ネガティブ･フェーズとは、RBMにおけるパラメータ更新式(コスト関数の勾配計算)に現れる、計算が困難な項と呼ばれるアレを指している(正式な和訳はないようである)。古典的には、ネガティブ･フェーズの計算は、モンテカルロ･マルコフ連鎖法(MCMC)≒ギブス･サンプリングを使った(改良した)、コントラスティブ･ダイバージェンス(CD)という近似手法で計算される。
　つまり｢学習において計算量が多いと見込まれる部分に要する計算時間が、量子的手法に使用によって、最大64倍短縮された｣と主張している(がミスリードさせる表現だと思われる)。

【2】事前整理
(1)　侵入検知システム(IDS)とネットワーク型侵入検知システム(NIDS)
　侵入検知システム(Intrusion Detection System:IDS)は、情報システムに対する不正行為や 情報システムの異常を検出する情報システムである[*21]。IDS＋通信の遮断＝不正侵入防止システム(IPS)という分け方もあるが、現在は、殊更区別されないようである(従って、IDSとIPSを混同する)。 　IDSが攻撃を検知する方法には、不正検出(シグネチャ型)と、異常検出(アノマリー型)の2つがある[*22]。攻撃パターンをシグネチャに登録し、一致する通信を攻撃と見なす方法が｢不正検出｣で、正常な通信の挙動をあらかじめ学習した上で、そこから逸脱した通信を異常として検知する方法が｢異常検出｣である。シグネチャ型は、(アノマリー型に比べて)誤検知が少ないが、未知の(未登録の)攻撃に対処できない。アノマリー型は、未知の攻撃に対処できるが、誤検知が多いとされる[*23]。
　ネットワークを流れる通信パケットを監視するIDSがネットワーク型侵入検知システム(NIDS)である。IDSには、NIDS以外に、ホスト型IDS(HIDS)、クラウド型IDSがある。ホスト型IDSは、監視対象のサーバー上にソフトウェアとしてインストールされ、通信の結果生成されたサーバー上の受信データやログを監視する。クラウド型はこれらの仕組みを、クラウドサービスとして提供する[*22]。
　ゼロデイ攻撃の脅威[*64]が非常に懸念される現状(2023年)、多くのIDSは、シグネチャ型とアノマリー型を兼ね備えていると思われるが、2009年頃の文献である[*21]には、｢最初のNIDSは、今日主流となるシグネチャ型に代表される不正検出型ではなく異常検出型であった｣という興味深い記述がある。

(2)　現実世界のサイバーセキュリティ･データセット：NSL-KDDとCSECIC-IDS2018
1⃣　NSL-KDDは、KDD99から冗長なデータを削除したデータセットである。加ニュー･ブラウンズウィック大学のカナダ･サイバーセキュリティ研究所から、提供されている(らしい)。KDD99は、DARPA98を基に作成。DARPA98は、DARPAと米空軍研究所(AFRL)の支援下で、MITリンカーン研究所が作成した世界初のNIDS(ネットワーク型侵入検知システム)評価用データセットである[*25]。 2⃣　CSE-CIC-IDS2018は、ネットワークベースの侵入検知に関する予測モデルを学習するために作成された。シグネチャ型検知システムのリポジトリとして機能することを意図しているのではなく、様々な機械学習アプローチによるアノマリー型検知システムに関する研究を促進することを目的としている。CSE-CIC-IDS2018は、10日間にわたって収集された約16,000,000のインスタンスが含まれたビッグデータで、一般公開されており、幅広い攻撃タイプをカバーする最新の侵入検知データセットである。インスタンスの約17%が攻撃(アノマリー)トラフィックで構成されている[*26]。

(3)　QRBMによるネガティブ･フェーズの計算
　ここで改めて、ネガティブ･フェーズの計算(期待値計算)の困難性について述べる。ネガティブ･フェーズの期待値計算に使用される確率分布は、モデル全体の(取り得る)確率分布全体である。従って、モデル･サイズ(ユニット数)が大きくなると指数的に計算量が増えて、実行が非現実的となる(いわゆる、組み合わせ爆発)。そこで、サンプリングを使った平均で近似する。古典RRMでは、ネガティブ･フェーズの計算にギブス･サンプリングを用いる(ことが多い)。
　QRBMは、量子アニーラをサンプリングマシンとして使う。そのために、RBMの構造を量子アニーラに埋め込む。｢埋め込み｣とは、量子アニーラで取り扱えるような形式に、対象モデルを変換することを(D-Waveでは)指す。量子演算処理ユニット(QPU)内の物理量子ビットのグループ(D-Waveでは｢チェーン｣と呼ばれる)を識別することで構成され、物理量子ビットが個別のユニットとして動作することでトポロジーを形成する。各チェーンの結合性は、量子ビット間に強力な強磁性結合(Jchain)を作成することによって強化できる。最適なチェーン強度を達成するには、バランスを見つける必要がある。最適な埋め込みを見つけることは、それ自体、一般に NP 困難である！
　本論文では、QRBM の埋め込みを見つけるために D-Wave が提供するminorminerアルゴリズムを利用している。同アルゴリズムは、あくまでヒューリスティックであり、ある程度の確率で埋め込みを見つける。このため、QRBM ごとにアルゴリズムを 3 回実行して、埋め込みに関与する物理量子ビットの数とチェーンの長さを削減した。

【3】RBMとQRBMの比較結果
　本論文では、｢ネガティブ･フェーズの計算時間、精度等のパフォーマンス指標、目標精度に達するまでのエポック数｣の3点について、RBMとQRBMの比較を行っている。
(1)　ハイパーパラメータ等
　古典(RBM)、量子(QRBM)を区別していない場合は、両者とも同じ値である(ただし、㊅と㊆を除く)。
㊀　学習率　0.01
㊁　バッチサイズ　128(RBM)、10(QRBM)
㊂　オプティマイザー　Adam
㊃　可視ユニットの数　156(CSE-CIC-IDS2018)、85(NSL-KDD)
㊄　隠れユニットの数　90(CSE-CIC-IDS2018)、30(NSL-KDD)
㊅　アニーリング時間　2μ秒
㊆　再スケーリングパラメータ^†　0.088
†　実際にサンプリングされる確率分布は、チップ内の熱雑音によって決定される実効温度の影響を受ける。再スケーリングパラメータは、この影響を相殺するために、設定する。

(2)　パフォーマンス指標
　先に述べた｢精度等のパフォーマンス指標｣とは、以下の6つである：精度、F1 スコア、真陽性 (TP)、偽陰性(FN)、偽陽性(FP)、真陰性(TN) 。
　精度は、正しく分類された予測全体の割合を表す。F1 スコアは、精度と再現率の調和平均を表す。1 は最良のスコアを表し、0 は最悪のスコアを表す。TPは、モデルによって正しく分類された攻撃の数を示す。TNは、モデルによって正しく分類された通常のイベントの数を示す。FNは、モデルによって通常のイベントとして分類された攻撃の数を示す。FPは、モデルによって攻撃として分類された通常のイベントの数を示す。

(3)　ネガティブ･フェーズの計算時間
　使用したハードウェアは、古典(RBM)では、米AMD社のRyzen Threadripper3990X[*27]。量子(QRBM)では、加D-Wave社のAdvantage4.1[*28]を使用。条件として、CDステップ数κは100と10。量子アニーラからのサンプル数sは、10が設定されている。
　QRBMの計算に使ったハードウェア(量子アニーラ)には、クラウド経由でアクセスしている。そのため、普通に計算終了までの時間を計測すると、そこにはネットワーク遅延時間も含まれてしまう。本論文では、QPUアクセス時間を記録することで、ネットワーク遅延時間を控除している。
1⃣　(より実データに近い)CSE-CIC-IDS2018を使用した場合
　Threadripper3990Xのシングルコアを使い、κ＝100の場合で、QRBMが64倍高速であった。コア数が128だと、41倍まで落ちる。
2⃣　(仮想データに過ぎない)NSL-KDDを使用した場合
　Threadripper3990Xのシングルコアを使い、κ＝10の場合で、QRBMが4倍高速であった。コア数が128だと、2倍まで落ちる。

(4)　精度等のパフォーマンス指標
　(1)で示した通り、RBMとQRBMで同じハイパーパラメータを使って、学習を行った結果を比較する。ただし、サンプル数は10に固定している。CDステップ数κは、1、10、100、1000の4パターンを設定している。
1⃣　(より実データに近い)CSE-CIC-IDS2018を使用した場合
　κ＝1を除いて(つまり、κ＝10であっても)全ての指標で、RBMに劣後している。
2⃣　(仮想データに過ぎない)NSL-KDDを使用した場合
　指標によって優劣が”まだら”であるものの、ざっくり言うとκ＝100の場合と、ほぼ同じパフォーマンス。精度とF1スコアに関しては、κ＝1000と比肩する。

(5)　目標精度に達するまでのエポック数
　目標精度として、73%、76%、80%、83%、86%、90%を設定している。
1⃣　(より実データに近い)CSE-CIC-IDS2018を使用した場合
　全ての精度において、RBMに劣後している(ただし、86%、90%についてQRBMは値無し)。ざっくり言って、QRBMは2倍のエポック数を要する。
2⃣　(仮想データに過ぎない)NSL-KDDを使用した場合
　全ての精度において、QRBMが勝っている。RBMが3倍程度のエポック数を要する。

【4】考察など
(0)　インターネット上で参照できるサイバーセキュリティ分野の資料は、総じて古い。常に新しく変化している分野であることを差し引いても、酷い。また、製品をアピールするコンテンツは溢れているが、全体像を俯瞰できるような、見通しの良い資料も皆無である。こういうところにも、日本がサイバーセキュリティ分野で弱い原因があるように感じる。
(1)　量子と古典の比較という構図になっているが、ソフトウェア実装とハードウェア実装を比較しているので、少しズレているように感じる。
(2)　それはさて置き、結果(数字)だけを見てみよう。そして、ベンチマーク･データセットは、より実データに近いCSE-CIC-IDS2018に限定しよう。 量子(QRBM)が勝っているのは、｢ネガティブ･フェーズの計算｣部分の計算時間だけ、である。定めた精度に達するエポック数も、パフォーマンス指標も、全て古典(RBM)に劣っている。論文の主張は量子がスピードで勝るであるが、あえて総合評価を持ち出すと、古典が圧勝と言えるのではないだろうか。
(3)　スピードにしても、メニーコアなら40倍程度しか速くない。そして、比較対象はパソコンである。とりあえず、それで良いとしても、メモリ容量やメモリアクセスのスループット等によっても、結果は違ってくるように思う。
(4)　ただ、そもそも、比較すべき古典コンピュータは、スパコンではないか？と思う。少なくとも、エンタープライズ･サーバーと比較すべきだと思う。その場合、量子＞古典になるかは、疑問である。