そこ曲がったら、量子坂？(下り)
【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) 量子優位性及び量子超越性
量子アルゴリズムが、最も高速な古典アルゴリズムよりべき乗で速くなること(指数関数的加速;指数加速)を量子超越性と呼ぶ。これに対して、2乗で速くなること(二次関数的加速;二次加速)は、量子優位性と呼ばれる。最も有名な｢ショアのアルゴリズム｣は、指数加速(量子超越)である。ただし、ショアのアルゴリズムよりも速い古典アルゴリズムが『存在しないことが、数学的に証明されているわけではない』。
一方、グローバー･アルゴリズムは二次加速(量子優位)に過ぎないが、グローバー･アルゴリズムよりも速い古典アルゴリズムが『存在しないことが、数学的に証明されている』。本論文の主張｢グローバー･アルゴリズムよりも、速い古典アルゴリズムを見つけた｣と矛盾するように見えるが、実は、矛盾しない。その点に関しては、追々記述する。
(1) 量子アルゴリズムの2大ファミリー
本論文の記述によると、量子アルゴリズムには、2大ファミリーが存在する。
1⃣ 量子フーリエ変換を使うファミリー
このファミリーには、既存の暗号を危険に晒す｢ショアのアルゴリズム｣、量子化学問題を解くために提案された量子位相推定アルゴリズム(※)他が含まれる。これらのアルゴリズムは、指数加速を実現する。
※ ただし、量子フーリエ変換(QFT)はハードウェア効率が悪いため、実務上は、QFTを使わない｢ベイズ推定(ベイジアン)量子位相推定アルゴリズム｣等が使用されている。例えば、米Quantinuumの研究者は、ベイジアン量子位相推定アルゴリズムを使った量子化学計算を(NISQマシンで)実行した、という論文を発表している。こちらを参照。
2⃣ 振幅増幅を使うファミリー
グローバー･アルゴリズムは、このファミリーに属する。GAは、関数の最適化・グラフ問題の解決・金融デリバティブの(オプション)価格付け・パターン認識、といった多くの使用例が考えられるので、実用性が高いと見做されている。
実用性が高いと見做されているものの、実は、重要なピースが欠けている。GAには、｢オラクル｣(†)という重要な要素がある。オラクル(この場合、正確には量子オラクル)は、入力に依存した量子操作を行うブラックボックス演算子、と定義できる。GAでは、アプリケーション毎に最適な量子オラクルが、既知である(言い方を変えれば、”誰かの手によって、勝手に準備されている”)ことを前提としている。しかし、実際に実装する際には、量子オラクルを特定の量子回路として実現する必要がある。本論文では、これは実際には簡単でないとして、量子オラクルを古典的に表現した量子インスパイアード･アルゴリズムを提案している。
†オラクル(Oracle)は、日本語では｢神託｣という意味である。なぜ神託と呼ばれているかというと、｢中身はブラックボックスで、ただ答えを教えてくれる、抽象的な存在｣に過ぎないからである。探索問題全体で言うと、当然、古典オラクルというものも存在するが、ここでは、触れない。
(2) グローバー･アルゴリズム(GA)
ここでは、観念的な話ではなく、アルゴリズム的な説明を行う。
GAは、当たりを高確率で推測するアルゴリズムである。まず関数y = f(b)を考える。ここで、bはN = 2n 個の値を取ることができる。bをビット列あるいは、nビットの文字列と考えると分かり易いかもしれない。yはシンプルには、0(失敗)、1(成功)で表される。
GAは、f(b)を実装する量子オラクルへの √N 回の呼び出しだけで、与えられたy に対する値 b = f−1(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では、(非解空間の折り返しである)量子オラクル UwをMPOで表現する(解の個数がS個の場合、結合次元は1+S)。QiGA の入力は、古典オラクルではなく、量子オラクル(つまりは、量子回路)である。量子オラクルの量子回路が古典的にシミュレートできる場合、量子コンピューターが量子オラクルへの O(2n/2) 回の呼び出しを必要とする一方で、QiGA はO(n) 回の計算で、問題を解決できる(多くの場合は量子オラクルへの 1 回の呼び出しで問題を解決できる)と主張している。
QiGAの計算ステップは以下の通り。
❶ 古典シミュレーション手法を使用して、結合次元χ = 1 + S の MPS として |Ψw⟩ を計算(†)。
❷ |W˜⟩ = |Ψw⟩ − |s⟩ を計算し、正規化して結合次元 χ = S の MPS |W⟩ を取得。
|s⟩は、初期状態にアダマール･ゲートを作用させて作成した、(重みが等しい)重ね合わせ状態である。
❸ |W⟩からサンプリングして、一様な確率で状態 |wα⟩を取得(††)。|wα⟩が求める解である。
† 本論文では、|Ψw⟩= Uw|s⟩を直接求める代わりに、|±⟩状態の積である|β⟩に対して振幅 ⟨β|Ψw⟩を古典的手法(テンソルクロス補間アルゴリズム[*17])で求める。テンソル･クロス補間法は、能動学習を利用して、量子回路 Uwについて知ることなく、外部の古典的なサブルーチンのみを使用して⟨β|Ψw⟩ を計算する。
†† MPSには、一般的にlog(N)×S2でスケーリングする、非常に効率的なサンプリングアルゴリズムが認められている[*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 2n/2 に達する。最終的な成功確率を1/2 としても、各ゲートにおける典型的な誤差率εは、1/(60 n 2n/2) 程度となる。40量子ビット(n=40)とすると、εは 3.97×10−10となる。つまり、数十億ゲートに対して、10億分の1よりも高い精度で、40量子ビットを操作する必要がある。本論文では、これは、非現実的であろうとみなしている。
2⃣ FTQCの場合
量子誤り訂正符号として、表面符号を想定している。あまり定量的な議論は行われていないが、GA実行には(先に述べたように)、2n個のトフォリ･ゲート＝2n×[6個のCNOT ゲートと 7 個のT ゲートを含む15個のゲート]が要求される。ただでさえ、アップアップのパンパンなのに、GAをFTQCで実行するために要求される、量子誤り訂正が破綻するのは明らかであろう、と結論付けている(ただ、GAとは無関係に、表面符号で誤り耐性量子計算というアプローチは、いずれにしてもダメだろう)。
【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に限った話ではない。なお、表面符号を使った量子誤り訂正符号は破綻していると思うが、別の量子誤り訂正符号を使って誤り耐性量子計算が行えるはずなので、｢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) ただ、そもそも、比較すべき古典コンピュータは、スパコンではないか？と思う。少なくとも、エンタープライズ･サーバーと比較すべきだと思う。その場合、量子＞古典になるかは、疑問である。
人類の歴史上、量子優位性が初めて実験的に実証されたのは、2019年10 月23 日と記録されるのだろうか。米グーグルは同日、natureに｢Quantum supremacy using a programmable superconducting processor｣と題する論文[*29]を投稿した(今でも、オープンアクセスで閲覧できる)。同論文は、Sycamoreと名付けられた54量子ビットの量子プロセッサー(QPU)は、当時世界最速のスパコン(IBMのSummit)🐾1が｢1万年かかる計算を200秒で実行した｣と主張し、一大センセーショナルを巻き起こした。しかし、直ちにIBMが｢1万年かかるとグーグルが主張する計算は2.5日で行える｣反論した。さらに、その後、古典コンピューターが、QPUより速く実行できたという報告(論文)が相次いだ。
量子誇大宣伝の嚆矢と言えなくもない、この騒動以来、いくつかの新しい実験が行われ、以前の実験は、異議を唱えられたり･反論されたりしてきた。米ミシガン州立大学🐾2の研究者は、｢これまで量子計算の優位性を主張してきた、全ての実験をまとめ｣、｢その後の研究で明らかになった課題、抜け穴、反論に焦点を当て、これらの実験の現状の全体像を示す｣論文[*30](以下、本論文)を発表した(24年12月19日@arXiv)。誇大宣伝が横行していると目されている量子界隈の信用と信頼を回復するためには、必要な作業であろう。
🐾1 2018年6月(に行われるTOP500の発表)から2019年11月(の発表)まで、IBMのSummit(サミット)が世界最速だった。2020年からは、富岳が世界最速となった。
🐾2 同大学は、州立大学である”が”、名門大学として知られている。アイビー･リーグ同等の評価を受けている｢パブリック･アイビー｣の1校でもある。
【1】本論文の構成
(1) 量子コンピューター(NISQ)実機を用いた、実験的な量子優位性の実証事例が8件、示されている。この8件には、量子アニーラ(D-Wave)を使った事例が1件含まれている。実証事例の内容、異議、反論が集められ、計算優位性の現状が説明されている(☞本稿では【2】にて、まとめた)。｢計算優位性｣については、【2】(0)1⃣を参照。なお、計算優位性は特定の問題に関して定義され、その問題は有用性がある場合とない場合がある。
(2) 実験的な量子優位性の実証事例に加えて、理論的な量子優位性に関して、現状説明が成されている。具体的には、㊀近似最適化及び、㊁推奨システムにおける量子計算優位性の現状、㊂量子シミュレーションにおける指数加速の見通しについて、説明が行われている(☞本稿では【3】にて、まとめた)。
加えて、ショアのアルゴリズムに関しては、以下の説明がなされている(本稿では、割愛)：ショアのアルゴリズムを実行するに当たり、論理量子ビットと論理ゲートが大量に必要であるが、1995 年のアルゴリズム開始以来、大幅に削減されている。
(3) 本論文では、量子誤り訂正符号についても軽く触れられているが、本稿では割愛。
【2】実験的量子優位性
(0) 約束事
1⃣ 量子優位性の意味
本論文では、量子優位性と量子超越性に加えて、古典計算を超える、も区別しない。通常の区別では、量子アルゴリズムが古典アルゴリズムに比べて、指数加速する場合、量子超越という文言を使う。2次加速以上･指数加速未満には、量子優位という文言を使う。本論文では、｢ある特定の計算タスクが、古典計算機で可能と考えられているよりも、量子計算機で高速に実行される｣場合は全て、量子優位という文言を使う。
量子優位性は、計算優位性の意味で用いる。計算優位性は、いくつかの側面(たとえば、エネルギー消費量の削減や精度の向上など)を指す可能性がある。ただし、本論文では、実行時間が短いという意味で使用する(計算複雑性の意味での量子優位性と表現しても良いだろう)。
なお、実行時間が、ウォール･クロック･タイム(壁時計時間)なのか？、といった議論はなされていない(そこまでの必要はない)。
2⃣ 計算優位性に関する注意点
最も優れたコンピューターと最も優れたアルゴリズムは、古典設定と量子設定の両方で、時間の経過とともに変化する。したがって、計算上の優位性は動く目標であり、古典コンピュータと量子コンピュータの間で、位置が入れ替わることがある。
なお、理論上は、計算優位性を持つ量子アルゴリズムであっても、量子誤り訂正のオーバーヘッドのために、実際には量子加速が失われるものもある。
3⃣ 量子優位性が検討された計算タスク
量子優位性が検討されてきた計算タスクは、これまで3 種類ある：ランダム回路サンプリング(RCS)、ガウス･ボソン･サンプリング(GBS)及び、量子シミュレーションである。
RCSは、ランダム量子回路からビット文字列をサンプリングする計算タスクである。GBSは、連続変数量子コンピューターにおけるRCS類似の計算タスクである。量子シミュレーションは、㊀指定されたハミルトニアン下で量子状態を時間発展させ、㊁時間発展した状態から特定のプロパティ(オブザーバブルの期待値など)を計算するタスクである。
量子優位性の文脈において、各タスクには、主要なパラメータが2つ存在する。RCSと量子シミュレーションでは、量子ビット数と、量子回路の深さ(レイヤー数またはサイクル数とも呼ばれる)である。GBSでは、入力光子の数nと、光子をサンプリングできるモード(場所)の数mである。
4⃣ ｢反論｣という文言の意味
量子優位性の主張に対する反論とは、量子優位性を持つ実験の古典シミュレーション時間が大幅に改善されることを実証することである。弱い反論とは、改良された古典アルゴリズムや数値的実証により、合理的に予想される将来の古典計算機で、量子優位性の主張が古典的にシミュレート可能であることを証明することである。強い反論とは、量子コンピュータよりも高速に量子優位性実験を古典的にシミュレーションすることである。
弱い反論は、曖昧というか、射程が長い(広い)。
(1) グーグル 其の壱╏世界初の量子優位性[*31]
1⃣ まとめ
㈠ 計算タスク・・・RCS(53量子ビット、量子回路の深さ20)
㈡ 論文公開日・・・2019年10月23日
㈢ 顛末・・・およそ4年半後(2024年6月27日🐾3)に、｢強い反論｣
🐾3 2024年6月27日の論文[*32]は、arXivにて公開された(つまり査読なし)。査読済論文は、24年9月12日、National Science Reviewにて公開された[*33]。National Science Reviewは、中国科学院後援の下、英オックスフォード大学出版が発行するオープン･アクセス科学雑誌。
2⃣ 補足
反論した論文[*34]は、1432個のGPUクラスターを使用して、300 万個のサンプルを 86.4 秒で計算した。マルコフ連鎖モンテカルロ法(MCMC)を使用してサンプリングし、ビット文字列を事後選択して、線形交差エントロピー･ベンチマーク(XEB)忠実度を最大化した。技術的に説明すると、｢ビッグ･ヘッド･アルゴリズム🐾4、動的スライシング、テンソルネットワークの縮約における最適化｣等のテクニックが総動員された結果である。なおグーグルの結果は、4.3 kWhの電力消費によって達成された(超伝導量子ビットの冷却に、それなりの電力が必要)。[*34]は13.7kWhを要した🐾5。
本稿では、｢XEB 忠実度の抜け穴を利用する古典的なアルゴリズムを考案する｣という偽装戦略について割愛した。
🐾4 平たく言えば、テンソルネットワークの縮約順序を最適化するアルゴリズムである。テンソル ネットワーク全体は、ヘッド･サブ･テンソルネットワークとテール･サブ･テンソル ネットワークに分割され、ヘッド･サブ･テンソルネットワークで発生するオープン量子ビットの数を最大化するように最適化が行われる。このため、ビッグ･ヘッド･アルゴリズムと呼ばれる。
🐾5 24年6月30日にarXivにて公開された論文[*35]では、｢消費電力0.29kWh、17.18秒｣という結果が示されている。
(2) 中国科学技術大学 其の壱[*36]
1⃣ まとめ
㈠ 計算タスク・・・GBS(入力光子数50、サンプリング･モード数100、最大クリック🐾6数76)🐾7
㈡ 論文公開日・・・2020年12月3日
㈢ 顛末・・・ およそ2年半後(2023年6月6日🐾8)に、｢弱い反論｣
🐾6 光子検出器によって光子が検出されたイベントを｢クリック｣と呼ぶ。
🐾7 2021年6月29日、USTC の同じチームは、入力光子数50、サンプリング･モード数144、最大クリック数113のGBSを実行した。合計サンプリング時間は、同じく200 秒。
🐾8 arXivに第1版が投稿された日。第2版は23年12月4日付け[*37]。査読済論文は、24年6月25日にnatureに投稿された[*38]。
2⃣ 補足
潘建偉が主導して開発したGBS用マシン｢九章｣によって達成された。ちなみに、比較対象のスパコンは、中国の神威･太湖之光スパコンである。ちなみに、神威･太湖之光は2017年11月まで世界最速だったのであり、2020年12月時点では世界最速ではない(当時は、富岳が最速)。
テンソルネットワーク(正確には、行列積状態)を使用してGBSを古典的にシミュレートする研究[*38]で、サンプリング時間が9.5分(570秒)に短縮した。この事実をもって、本論文では、弱い反論が成された判断している。古典アルゴリズムは、CuPy🐾9とMPI🐾10を使用してPythonで実装され、コードはm個のGPUのクラスターで実行された。ここで、mはGBSのモード数である。MPSの結合次元は 104であった。
🐾9 CuPy は NumPy と高い互換性を持つ数値計算ライブラリ。 NumPy で提供されている多くの関数を NVIDIA GPU で実行することで簡単に高速化できるように設計されている(https://tutorials.chainer.org/ja/10_Introduction_to_CuPy.html)。NumPyとは、多次元配列を効率的に扱うライブラリ。 Pythonの標準ライブラリではないが、科学技術計算や機械学習など、ベクトルや行列の演算が多用される分野では、事実上の標準ライブラリとしての地位を確立している(https://utokyo-ipp.github.io/5/5-3.html)。
🐾10 MPI(Message Passing Interface)は、さまざまな並列コンピューターで機能するように設計された、標準化されたポータブルなメッセージ･パッシング･システム(https://scrapbox.io/PythonOsaka/mpi4py%E3%82%92%E4%BD%BF%E3%81%A3%E3%81%A6%E3%81%BF%E3%82%88%E3%81%86)。
(3) 中国科学技術大学 其の弐[*39]
1⃣ まとめ
㈠ 計算タスク・・・RCS(60量子ビット、量子回路の深さ24)
㈡ 論文公開日・・・2021年9月8日
㈢ 顛末・・・(1)と同じ｢反論｣が適用される？→本論文では、challengedとされている
(4) Xanadu🐾11[*40]
🐾11 連続変数の量子光を量子ビットとして使用する量子コンピューターを開発しているカナダのスタートアップ。量子機械学習用PythonライブラリーPennyLaneで有名。22年11月の増資(シリーズC)でユニコーンとなった。
1⃣ まとめ
㈠ 計算タスク・・・GBS(入力光子数216、サンプリング･モード数216、最大クリック数219)
㈡ 論文公開日・・・2022年6月1日
㈢ 顛末・・・(2)と同じ弱い反論が成立
2⃣ 補足
この実験では(2)とは異なり、しきい値(型の)検出器🐾12ではなく光子数分解検出器を使用している。また、GBS専用マシンを使っているのではなく、｢完全にプログラム可能な｣量子コンピューター(正確には、NISQデバイス)を使って、達成された。 完全にプログラム可能とは、任意の計算が実行可能であることを意味している。
🐾12 しきい値(型の)検出器は実験的には扱いやすい反面、同検出器を使ったGBSは古典的にシミュレート容易である。
(5) グーグル 其の弐[*41]
1⃣ まとめ
㈠ 計算タスク・・・RCS(67量子ビット、深さ32╏70量子ビット、深さ24)
㈡ 論文公開日・・・2023年4月21日
㈢ 顛末・・・(1)と同じ｢反論｣が適用される？→本論文では、未反論
(6) 中国科学技術大学 其の参[*42]
1⃣ まとめ
㈠ 計算タスク・・・GBS(入力光子数50、サンプリング･モード数144、最大クリック数255)
㈡ 論文公開日・・・2023年4月24日
㈢ 顛末・・・(2)と同じ弱い反論が成立する
2⃣ 補足
(4)に対抗して、(2)で使用していたしきい値検出器ではなく、疑似光子数分解検出器が使用されている。
㈠ 計算タスク・・・量子シミュレーション🐾13｜横磁場イジングモデル(量子ビット数127、深さ60)
㈡ 論文公開日・・・2023年6月14日
㈢ 顛末・・・およそ2週間後(23年6月26日)に、｢強い反論｣
🐾13 ゼロノイズ外挿(ZNE)と確率的誤差増幅(PEA)を使用した、量子誤り緩和が実行された。ZNEにおける主要課題の1つは、ターゲット回路に影響を与えるノイズを正確に増幅することである。PEAは、正確な増幅を行う技術である(https://docs.quantum.ibm.com/guides/error-mitigation-and-suppression-techniques#probabilistic-error-amplification-pea)。
2⃣ 補足
① 2023年6月26日：古典アルゴリズムは、ラップトップで数分で実行された。テンソルネットワークを使用[*44]。
② 2023年6月28日：古典アルゴリズムは、ラップトップで1～2分で実行された。使用された技法は、テンソルネットワークではなく、クリフォード摂動論[*45]。
③ 2023年8月6日：古典アルゴリズムは、1CPUで3秒で実行された。テンソルネットワーク(正確には、射影エンタングル対演算子🐾14(Projected Entangled Pair Operator:PEPO))を使用。PEPOの結合次元は184であった[*46]。
🐾14 テンソルネットワークは異なる分野･異なる時間軸で発見されていることもあり、同じものを違う名で呼ぶということが多い。テンソル積状態(TPS)は、射影エンタングル対状態(PEPS)とも呼ばれる。TPSは、行列積状態(MPS)の高次元系への拡張である。
④ 2023年9月27日：古典アルゴリズムは、ラップトップで2秒で実行された。テンソルネットワーク(正確には、グラフベースの射影エンタングル対状態🐾14(再)(Projected Entangled Pair State))を使用[*47]。
㈠ 計算タスク・・・量子シミュレーション｜横磁場イジングモデル(576 量子ビット)
㈡ 論文公開日・・・2024年3月1日 ➡ 査読済版(Science、[*48]に併記)が、25年3月12日に公開されて話題沸騰？
㈢ 顛末・・・本論文発表時点で、反論なし🐾15
🐾15 本論文は、いずれ反論されると予想しているーフラットアイアン研究所のE.M.Stoudenmireが、立ちはだかるか？
👉 部分的な反論として、フラットアイアン研究所の[*51](25年3月7日)及び、スイス連邦工科大学ローザンヌ校の[*52](25年3月11日)がある。
2⃣ 補足
D-waveのAdvantageとAdvantage2が使用された。 結合トポロジーは、正方格子、ダイヤモンド格子などがランダムに選択される。最大の入力は、576 量子ビットを必要とする 12 × 12 × 16 ダイヤモンド格子である。古典的なアルゴリズムは、テンソルネットワークとニューラルネットワークを使用して実行される。 テンソルネットワークは、具体的に言うと、MPSとPEPSである。ニューラルネットワークは、自己回帰ボルツマン･マシン、トランスフォーマー、リカレント･ニューラルネットワークが検討されている。
『科学的に興味深い問題で、量子優位性を達成したのは初めてだ、と考えている』ーAndrew King(D-Waveの物理学者)
【3】理論的量子優位性
(1) QAOA
1⃣ 本論文は『QAOA(近似的量子最適化アルゴリズム🐾16)が、証明可能な計算上の量子優位性を達成できるかどうかという問題は、未解決である』と述べている。未解決の意味とは、｢量子優位性の検証は、p=1に対して行われているだけであり、p>1については行われていない｣という意味である(と合理的に推論 ☞2⃣を参照)。pについては、3⃣を参照。
🐾16 和訳は、いくつか存在し、必ずしも定まっていない。
2⃣ QAOA のパフォーマンスはp >1でも低下することはなく、向上することが期待できる。しかし、p >1は解析表現が難しいため、ほとんどの場合p = 1が選択される。QAOAのオリジナル論文では、p=1でも古典アルゴリズムを超える性能を得られると主張された。しかし、その主張は後に、否定された。
3⃣ QAOAは、近似的な断熱量子計算である。断熱量子計算は、ゆっくり･滑らか･連続的に時間発展していく。QAOAは、2つのハミルトニアン🐾17H0とH1から作られる、2つのパラメータ付きユニタリー時間発展演算子を、交互に”繰り返し”適用して、時間発展させていく。この”繰り返し”の数を、本論文ではpとしている。
🐾17 これも和訳が定まっていない(カタカナ表記すら定まっていない)。本稿の表記で言うと、自明な基底状態を持つハミルトニアンがH0で、求めたい解を基底状態に持つハミルトニアンがH1である。H0は、初期ハミルトニアン、参照ハミルトニアン、ミキシング･ハミルトニアン、ミキサー･ハミルトニアンなどと呼ばれる。H1は、問題ハミルトニアン、コスト･ハミルトニアン、ドライバー･ハミルトニアンなどと呼ばれる。
(2) 量子推薦システム
0⃣ 古くから良く知られた、”脱量子化”の事例である🐾18。脱量子化(古典アルゴリズム)とは、量子加速が生じる理由を古典的に再現することで、量子アルゴリズムと同程度の速度で実行可能な古典アルゴリズムである。同程度とは、高々、多項式時間のオーバーヘッドであることを意味する。
🐾18 14歳でテキサス大学に入学したエウィン･タンが、スコット･アーロンソンから与えられた”量子優位性を示す”という課題を、否定的な意味で解決した[*49]。
1⃣ 量子推薦(レコメンド)システム･アルゴリズムは、最も良く知られている古典的なアルゴリズムよりも指数関数的に高速化される。定量的には、量子アルゴリズムは、O(poly(k)×log(mn))で実行される。 古典アルゴリズムは、O(poly(n)×ploly(m))である。ここで、nはユーザー数、mは商品(あるいはサービス)の数である。ｋはn×mの嗜好行列のランクである🐾19。
推薦アルゴリズムにおいて量子加速が生じる理由は、データ構造にある。データ構造が、いわゆる二分木構造である場合に、量子加速が生じる。
🐾19 問題を扱いやすくするために、嗜好行列は低ランクである(つまりkは小さい)と仮定される。低ランクという仮定は、経験的に、よく当てはまることが分かっている(らしい)。
2⃣ ところが、二分木データ構造を使用すると古典アルゴリズムも、O(poly(k)×log(mn))で計算を実行できる。つまり、量子アルゴリズムと脱量子化古典アルゴリズムの実行時間は漸近的には同じである。
3⃣ コメント➡本論文では、この良く知られた事例に対して、｢漸近的に同じとは言っても、厳密に言えば違う(量子アルゴリズムの方が、少し速い)｣という主張を取り上げているが、その主張(そんな細かい話)は、量子優位性を議論するケースでは、ルール違反であろう。
(3) 量子位相推定ー量子化学シミュレーション
1⃣ 一般的には、｢量子位相推定(QPE)は、指数加速が証明されている｣と認識されている。しかし、本論文では『基底状態のエネルギー計算におけるQPEの指数加速は証明されているわけではない』ことを示唆する論文[*50]が取り上げられている。つまり、｢強力な古典的なヒューリスティック･アルゴリズムが多項式オーバーヘッドで、QPEをシミュレートできる可能性は残されている｣と主張されている。
2⃣ なお、オリジナルのQPEは計算コストが高いため、量子優位性を主張できる問題サイズで実験的に実証されていない。オリジナルのQPEとは、逆量子フーリエ変換を使用するQPEを指している。
【5】考察
(1) ｢量子優位性の達成宣言｣は2019年、華々しく行われた。本論文によれば、実機による実験で量子優位性を主張した事例は8件あるが、新しい事例1を除いて、弱い反論が3、強い反論が4と思われる。つまり、量子アルゴリズムより速い古典アルゴリズムが存在すると、事後的に明らかになった事例が半分もある(と思われる)。そして、近い将来、量子アルゴリズムと同程度に速い古典アルゴリズムが現れるだろう、という事例が3つある(と思われる)。古典アルゴリズムの底力は侮れない。
(2)【2】(0)1⃣で述べたように、本論文における量子優位性は、計算優位性の意味で用いている。ここで見方を変えて、仮に量子優位性を、｢量子的手法の方が古典的手法より、"成功確率"が高い｣という意味で捉えてみよう。すると、量子優位性は金融分野において、既に達成されている。
実は、上場株式の高頻度取引(HFT)を、CHSH(Clauser･Horne･Shimony･Holt)ゲームと呼ばれるゲームに変換することで、量子優位性が実現できる。ここで、重要なポイントは、CHSHゲームによる量子優位性の実現には、2つの物理量子ビットと1つの量子ビットゲートだけが必要で、誤り耐性などは不要なことである。詳しくは、こちらを参照。
｢数億年が数秒に｣といった浅薄かつ煽情的な標語を掲げるのは、マスメディアの常であろう。そのマスメディアとともに量子コミュニティが共謀して作り上げた、量子コンピューティングに対する熱狂的な興奮は、思惑を越えて、非現実的な期待に繋がった(と思われる)。先端技術のハイプ･サイクル🐾1に幻滅期の登場は不可避なり、と冷静に状況分析できれば良いのだろうが、非現実的な期待に対する反動のおかげで、量子コンピューティングが将来もたらすと期待された約束は、量子誇大宣伝と揶揄されるに至った。
Algorithmiq🐾2他🐾3の研究者は、｢近い将来の量子コンピューティングの機能と限界、および完全な誤り耐性量子コンピューティングへの移行の可能性に関する一般的な見解を再検討し、批判的に評価｣した論文[*A-1](以下、本論文)を発表した(25年1月10日@arXiv)。平たく言えば、非現実的な期待に対する反動がもたらした『6つの通説』に対して、反論するという内容である。結論を言えば、反論できているのは2つ(2.5?)のみであろう。
🐾1 米調査会社ガートナー固有の用語であろう。
🐾2 フィンランドの量子ソフトウェア･スタートアップ。創薬支援に関わるソフトウェアを開発している。
🐾3 HUN-RENウィグナー物理学研究センター(ハンガリー)、英オックスフォード大学、英Quantum Motion(シリコンスピン方式量子コンピューター開発スタートアップ)、スイス連邦工科大学ローザンヌ校、レーニ・アルフレード数学研究所(ハンガリー)、米グーグル(Quantum AI)、米カリフォリニア工科大学、光科学研究所(スペイン)、カタルーニャ先端研究所(スペイン)、Technology Innovation Institute(アラブ首長国連邦アブダビ)、伊フィレンツェ大学、イタリア国立核物理学研究所、米AWS、英Phasecraft(量子ソフトウェア･スタートアップ)、英ユニバーシティ・カレッジ・ロンドン、トリニティ・カレッジ・ダブリン(アイルランド)、米NVIDIA、ヘルシンキ大学(フィンランド)、IBM(チューリッヒ基礎研究所、スイス)
【1】本論文で扱う『6つの通説』
(通説1) 量子誤り緩和(QEM：Quantum Error Mitigation)は、役に立たない。
(通説2) 実用的な問題を解決するには、NISQ🐾4で実現可能な回路よりも、はるかに大きな回路が必要である。
(通説3) 量子誤り訂正が実現されれば、量子誤り緩和は、不要になる。
(通説4) 変分量子アルゴリズムは、役に立たない。
(通説5) 変分量子アルゴリズムは NISQ 時代にのみ関連している。
(通説6) 商業的価値を保証する指数関数的な量子高速化は、実証されていない。
🐾4 Noisy Intermediate-Scale Quantumデバイス
【2】『6つの通説』に対する反論
(通説1) 量子誤り緩和(QEM：Quantum Error Mitigation)は、役に立たない。
|通説1に対する反論の内容と解釈|
QEMには指数関数的な数のサンプルが必要である。したがって、QEMを通じて意味のある結果を得るには、指数関数的な時間を要する。つまり、QEMを使った量子計算は、たとえ量子計算自身が古典計算より指数関数的に高速であったとしても、QEMに要する指数関数的に冗長な余計な時間によって、高速性が相殺されてしまうので、意味がない＝役に立たない。
この理屈に対して、本論文は、次のように定量的な反論を行っている：QEMに指数関数的なサンプル･オーバーヘッドがかかることは事実である。ただ、この場合、指数関数の引数は、ε×N×Lと表される🐾5。εは、物理ゲート誤り率。Nは量子回路の深さで、Lは量回路の幅である。仮に、εが1/(NL)であれば、指数関数と言ってもexp(1)≒2.72である。本論文では、exp(10)≒2万2千を許容範囲としている。N＝100でL＝1000なら、ε＝10－4で成立する。このεは、どれだけ現実的であろうか。
例えばグーグル(超伝導トランズモン方式)のWillowであれば、ε＝3.3×10－3であり、到達していない。ただし、英オックスフォード･イオニクス(トラップイオン方式)であれば、ε＝2.9×10－4であり、ほぼ到達している。このまま、改善されれば、exp(10)には到達できるだろう、と期待をしている。
まとめれば、技術が期待通りに進歩すれば、QEMが成立する未来が訪れると反論している。
🐾5 正確に言うと、サンプル･オーバーヘッドは、poly(εNL)×exp(εNL×B)と表され(てい)る。poly(･)は多項式を表している。εNL→1なので、まずpoly(εNL)を無視した。次にBは、例えば、ゼロノイズ外挿法を使うことで、B＝1にできる。つまり、exp(εNL×B)＝exp(εNL)となる。
╏裁定1及び、裁定1へのコメント╏
本論文は、通説1に対する反論を通して、通説1への裁定(裁定1)を下している。裁定1は、debunked(通説は、偽りであることが証明された)である。言葉の意味は相当強い(英語の細かいニュアンスは分からない)ものの、少なくとも通説1は、｢正しいとまでは言えない｣だろう。
(通説2) 実用的な問題を解決するには、NISQで実現可能な回路よりも、はるかに大きな回路が必要である。
|通説2に対する反論の内容と解釈|
通説2に対する反論は、問題のすり替えである。 実用的な問題を解決するには、大きな回路が必要であることを議論せずに、現実的な量子回路サイズで解決可能な実用的問題を探そう、という”解決策”を提示している。
具体的に言うと、2量子ビット･ゲートの物理誤り率から許容される回路サイズを推定している。(通説1)で議論した、QEMの許容可能なサンプリング･オーバーヘッドをexp(10)とした場合、ε＝10－4に対して、100×1000というサイズあるいは300×300というサイズの量子回路が、現実的になる。この回路サイズで解決可能な実用的問題を探すことが、肝要といっているに過ぎない。この主張に、どれだけ意味を見出すかは、見解が分かれるところであろう。
╏裁定2及び、裁定2へのコメント╏
本論文は、通説2に対する反論を通して、通説2への裁定(裁定2)を下している。裁定2は、open question(議論の余地がある)とdebunkedの間である。曖昧な結論であるが、絶妙な落とし所であろう。
(通説3) 量子誤り訂正が実現されれば、量子誤り緩和は、不要になる。
|通説3に対する反論の内容と解釈|
シンプルに、QEMをQEC(量子誤り訂正)と組み合わせることでメリットが生じるので、通説3は否定される。そこに、議論はないであろう。
╏裁定3及び、裁定3へのコメント╏
本論文は、通説3に対する反論を通して、通説3への裁定(裁定3)を下している。裁定3は、ほぼdebunkedである。これは、妥当であろう。
(通説4) 変分量子アルゴリズムは、役に立たない。
|通説4に対する反論の内容と解釈|
米ロス･アラモス研究所･米オークリッジ研究所他の研究者により、23年12月14日に(arXivにて公開→24年3月19日に第2版が)公開された論文によれば、1⃣｢変分量子アルゴリズム(VQA)において現れる不毛な台地を、回避できる問題のほとんどは、古典的にシミュレート可能｣と予想されている(こちらを参照)。同じ著者他によって書かれた別の論文では、2⃣｢不毛な台地の原因全てを、一つのフレームワークで理解できる｣と主張(こちらを参照)しており、1⃣は間違いないであろう。
本論文も通説4に関しては、実質的に白旗を上げている。具体的に言えば、｢ただ待って様子を見る必要がある｣と述べている。
╏裁定4及び、裁定4へのコメント╏
本論文は、通説4に対する反論を通して、通説4への裁定(裁定4)を下している。裁定4は、open questionである。(変分量子アルゴリズムは役に立たつと信じたい)気持ちは分かるが、これは、やや甘い(希望的観測が前面に出過ぎている)と思われる。
(通説5) 変分量子アルゴリズムは NISQ 時代にのみ関連している。
|通説5に対する反論の内容と解釈|
(通説4) 変分量子アルゴリズムは、役に立たない。を是とすれば、この反論はそもそも意味を成さない。
╏裁定5及び、裁定5へのコメント╏
本論文は、通説5に対する反論を通して、通説5への裁定(裁定5)を下している。裁定5は、ほぼdebunkedである。これは前述の通り(｢変分量子アルゴリズムが、役に立たつ｣前提で議論しているので)、無意味と思われる。
(通説6) 商業的価値を保証する指数関数的な量子高速化は、実証されていない。
|通説6に対する反論の内容と解釈|
通説6に対しても、反論は行っていない。それは、主張が正しいからである。本論文では、｢(計算複雑性の意味での)量子優位性が、多項式加速であるか指数加速であるかに関係なく、成功は最終的に現実世界の課題に対処する能力によって測定される｣と問題をすり替えている。
╏裁定6及び、裁定6へのコメント╏
本論文は、通説6に対する反論を通して、通説6への裁定(裁定6)を下している。裁定6は、corrrect(通説は正しい)とopen questionの間である。これも、やや甘く感じるものの、落とし所としては絶妙かもしれない。
【尾註】
*1 "最も賢い億万長者"チャールズ･サイモン(と妻)が設立した、サイモンズ財団により2016年に設立された研究所。計算天体物理学センター、計算生物学センター、計算数学センター、計算神経科学センター、計算量子物理学センター、科学コンピューティング･コア、という6つのセンターがある。
*2 E.M. Stoudenmire & Xavier Waintal、Grover’s Algorithm Offers No Quantum Advantage、https://arxiv.org/pdf/2303.11317.pdf
*3 https://scottaaronson.blog/?p=7143及びhttps://scottaaronson.blog/?p=7157
本論文のレビューをChat-GPTに書かせてみたが、無理だったので、止むを得ず自分で書いた。というジョーク付き。
*4 Galit Anikeeva et al.、Number Partitioning With Grover’s Algorithm in Central Spin Systems、https://journals.aps.org/prxquantum/pdf/10.1103/PRXQuantum.2.020319
*5 Nikolai A. Sinitsyn ＆ Bin Yan、Topologically protected Grover’s oracle for the partition problem、https://arxiv.org/pdf/2304.10488.pdf
*6 西野友年・大久保毅、|解説| テンソルネットワーク形式の進展と応用、日本物理学会誌Vol. 72、No.10、2017、pp.702-711
*7 大久保毅、テンソルネットワークによる情報圧縮とフラストレート磁性体への応用、|講義ノート| 物性研究･電子版 Vol.7, No.2, 072209 (2018年11月号)、https://mercury.yukawa.kyoto-u.ac.jp/~bussei.kenkyu/wp/wp-content/uploads/6300-072209.pdf
*8 Yong(Alexander)Liu et al.、Closing the “Quantum Supremacy” Gap: Achieving Real-Time Simulation of a Random Quantum Circuit Using a New Sunway Supercomputer、https://arxiv.org/pdf/2110.14502.pdf
ゴードンベル賞受賞によって、より広く知られているバージョンは、https://dl.acm.org/doi/pdf/10.1145/3458817.3487399
*9 Lucas Leclerc et al.、Financial Risk Management on a Neutral Atom Quantum Processor https://arxiv.org/pdf/2212.03223.pdf
*10 https://terraquantum.swiss/news/terra-quantum-and-cirdan-capital
*11 Nikita Gourianov et al.、A Quantum Inspired Approach to Exploit Turbulence Structures https://arxiv.org/pdf/2106.05782.pdf
*12 Youngseok Kim et al.、Evidence for the utility of quantum computing before fault tolerance、https://www.nature.com/articles/s41586-023-06096-3
*13 Tomislav Beguˇsi´c ＆ Garnet Kin-Lic Chan、Fast classical simulation of evidence for the utility of quantum computing before fault tolerance、https://arxiv.org/pdf/2306.16372.pdf
*14 Joseph Tindall et al.、Efficient tensor network simulation of IBM’s Eagle kicked Ising experiment、https://arxiv.org/pdf/2306.14887.pdf
*15 井上克巳・田村直之、 |特集|「最近の SAT技術の発展」SATソルバーの基礎、人工知能学会誌 25巻1号(2010年 1月)、pp.57-67、https://www.jstage.jst.go.jp/article/jjsai/25/1/25_57/_pdf
*16 https://scirate.com/arxiv/2303.11317 ここで投稿された内容が、先にあげたアーロンソンのブログ[*6]に貼り付けられたりしている。
*17 本論文では、以下が上げられている：Yuriel Núñez Fernández et al.、Learning Feynman Diagrams with Tensor Trains、https://journals.aps.org/prx/pdf/10.1103/PhysRevX.12.041018
*18 本論文では、以下が上げられている：Andrew J. Ferris & Guifre Vidal、Perfect Sampling with Unitary Tensor Networks 、https://arxiv.org/pdf/1201.3974.pdf
*19 例えば、ウォルフラム･コミュニティでは、本論文の主張再現が行われている(再現に成功している)。https://community.wolfram.com/groups/-/m/t/2958725
*20 Lorenzo Moro & Enrico Prati、Anomaly detection speed-up by quantum restricted Boltzmann machines、https://www.nature.com/articles/s42005-023-01390-y
*21 https://www.ieice-hbkb.org/files/03/03gun_07hen_05.pdf
*22 https://www.ntt.com/bizon/glossary/e-i/ips-ids.html
*23 谷澤俊樹 他、パケットのヘッダ情報に注目したアノマリ型IDSとシグネチャ型IDSを組み合わせた未知の異常検出、https://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=187373&item_no=1&attribute_id=1&file_no=1
*24 有名なセロデイ攻撃の例として、｢毎月第2火曜日のセキュリティ･アップデート後に、サイバー犯罪者が公開されたゼロデイ脆弱性情報を悪用して、すぐにサイバー攻撃を実行する(ゼロデイ・チューズデー／ハック・ウェンズデー)」がある。
*25 高原尚志、ネットワーク型侵入検知手法を用いたKDD Cup 1999 DataとKyoto2016の比較、https://ipsj.ixsq.nii.ac.jp/ej/?action=repository_uri&item_id=192674&file_id=1&file_no=1
*26 Joffrey L. Leevy & Taghi M. Khoshgoftaar、A survey and analysis of intrusion detection models based on CSE-CIC-IDS2018 Big Data、https://journalofbigdata.springeropen.com/articles/10.1186/s40537-020-00382-x
*27 八冠を達成した将棋界の絶対王者、藤井聡太竜王が所有するパソコンのCPUがThreadripper™ 3990Xである。リリースされたのは2020年であり、2023年時点では、Pro7000シリーズ(最大で192コア)が最新のようである。出典：https://www.amd.com/ja/processors/ryzen
*28 Advantage4.1は2021年リリースであり、2023年時点でも、最新版のようである。出典：https://www.dwavesys.com/media/3xvdipcn/14-1058a-a_advantage_processor_overview.pdf
*29 Frank Arute et al.、Quantum supremacy using a programmable superconducting processor、https://www.nature.com/articles/s41586-019-1666-5.pdf
*30 Ryan LaRose、A brief history of quantum vs classical computational advantage 、https://arxiv.org/pdf/2412.14703
*31 Frank Arute et al.、Quantum supremacy using a programmable superconducting processor、https://www.nature.com/articles/s41586-019-1666-5
*32 Xian-He Zhao Fu et al.、Leapfrogging Sycamore: Harnessing 1432 GPUs for 7× Faster Quantum Random Circuit Sampling、https://arxiv.org/abs/2406.18889
*33 同、https://academic.oup.com/nsr/advance-article/doi/10.1093/nsr/nwae317/7756427
*34 Xian-He Zhao et al.、Leapfrogging Sycamore: Harnessing 1432 GPUs for 7× Faster Quantum Random Circuit Sampling、https://arxiv.org/pdf/2406.18889
*35 Rong Fu et al.、Achieving Energetic Superiority Through System-Level Quantum Circuit Simulation、https://arxiv.org/pdf/2407.00769
*36 Han-Sen Zhong et al.、Quantum computational advantage using photons、https://www.science.org/doi/10.1126/science.abe8770
*37 同、https://arxiv.org/pdf/2306.03709
*38 Changhun Oh et al.、Classical algorithm for simulating experimental Gaussian boson sampling、https://www.nature.com/articles/s41567-024-02535-8
*39 Yulin Wu et al.、Strong Quantum Computational Advantage Using a Superconducting Quantum Processor、https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.127.180501
*40 Lars S. Madsen et al.、Quantum computational advantage with a programmable photonic processor、https://www.nature.com/articles/s41586-022-04725-x
*41 A. Morvan et al.、Phase transitions in random circuit sampling、https://www.nature.com/articles/s41586-024-07998-6
*42 Yu-Hao Deng et al.、Gaussian Boson Sampling with Pseudo-Photon-Number-Resolving Detectors and Quantum Computational Advantage、https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.131.150601
*43 Youngseok Kim et al.、Evidence for the utility of quantum computing before fault tolerance、https://www.nature.com/articles/s41586-023-06096-3
*44 Joseph Tindall et al.、Efficient Tensor Network Simulation of IBM’s Eagle Kicked Ising Experiment、https://journals.aps.org/prxquantum/abstract/10.1103/PRXQuantum.5.010308(この査読済論文は24年1月23日付け。本論文では、査読前論文https://arxiv.org/pdf/2306.14887が引用されてる)。
*45 K. Kechedzhi et al.、Effective quantum volume, fidelity and computational cost of noisy quantum processing experiments、https://www.sciencedirect.com/science/article/pii/S0167739X23004569(この査読済論文は24年4月発行の雑誌に掲載。本論文では、査読前論文https://arxiv.org/pdf/2306.15970が引用されてる)。
*46 Hai-Jun Liao et al.、Simulation of IBM's kicked Ising experiment with Projected Entangled Pair Operator、https://arxiv.org/pdf/2308.03082
*47 Siddhartha Patra et al.、Efficient tensor network simulation of IBM's largest quantum processors、https://arxiv.org/abs/2309.15642➡査読済論文は、同、https://journals.aps.org/prresearch/abstract/10.1103/PhysRevResearch.6.013326(本論文では、本稿で*49に該当する論文を*48と同じとする誤植がある。従って、ここで示した論文は、合理的に推論した結果であることに注意)
*48 Andrew D. King et al.、Computational supremacy in quantum simulation、https://arxiv.org/abs/2403.00910
査読済版(Science、25年3月12日付け)は、論文名が変わっている。Beyond-classical computation in quantum simulation、https://www.science.org/doi/10.1126/science.ado6285
*49 藤井啓祐、驚異の量子コンピューター―宇宙最強マシンへの挑戦、岩波書店、2019
*50 Seunghoon Lee et al.、Evaluating the evidence for exponential quantum advantage in ground-state quantum chemistry、https://www.nature.com/articles/s41467-023-37587-6
*51 Joseph Tindall et al.、Dynamics of disordered quantum systems with two- and three-dimensional tensor networks、https://arxiv.org/pdf/2503.05693
*52 Linda Mauron et al.、Challenging the Quantum Advantage Frontier with Large-Scale Classical Simulations of Annealing Dynamics、https://arxiv.org/pdf/2503.08247
*A-1 Zoltán Zimborás et al.、Myths around quantum computation before full fault tolerance: What no-go theorems rule out and what they don’t、https://arxiv.org/pdf/2501.05694