量子特異値変換を大まかに理解する

記事の目的

この記事では、近年非常に注目されている量子アルゴリズムである　量子特異値変換(QSVT: Quantum Singular Value Transformation)　をふわっと解説します。

対象読者：量子アルゴリズムについて最低限知っているが、QSVTはわからない。

なぜQSVTを学ぶ必要があるか

QSVTは、特定要素を捜索するGroverのアルゴリズム、固有値を埋め込むQuantum Phase Estimationアルゴリズム、逆行列演算を実現するHHLアルゴリズムといった、個別に発見されてきた量子アルゴリズムを統一して理解できるアルゴリズムになっています。
そのため、QSVTを理解することは量子アルゴリズムを見通し良く理解することにつながります。¹

Pennylaneのデモも、ここ数か月はQSVT一色です。
これらすべてがQSVTか、それに関連する記事です。

https://pennylane.ai/qml/demos/tutorial_intro_qsvt/
https://pennylane.ai/qml/demos/tutorial_apply_qsvt/
https://pennylane.ai/qml/demos/function_fitting_qsp/
https://pennylane.ai/qml/demos/tutorial_block_encoding/
https://pennylane.ai/qml/demos/tutorial_lcu_blockencoding/

QSVTは何ができるか

QSVTは、ざっくりいえば、
「特異値$\sigma_{i}$を持つ行列$U$が与えられた時、$\sigma_{i}$を任意の多項式$P$に通して得られる値$P(\sigma_{i})$を新たな特異値として持つ行列$U_{P}$を、高速に"計算"できる」というアルゴリズムです。
もう少しちゃんと書くと、
$U = \sum_{i} \sigma_{i} \ket{w_{i}}\bra{v_{i}} $ があるとき、
$U_{P} = \sum_{i} P(\sigma_{i}) \ket{w_{i}}\bra{v_{i}} $ を"計算"できる
ということになります。
ここで"計算"は、古典的な計算とは意味が違います。

そこも書き下すと、
$U = \sum_{i} \sigma_{i} \ket{w_{i}}\bra{v_{i}} $ が量子状態への量子ゲート操作として実現できているとき、
$U_{P} = \sum_{i} P(\sigma_{i}) \ket{w_{i}}\bra{v_{i}} $ も量子状態への量子ゲート操作として(古典的に$U_{P}$を計算してゲート操作として構築するよりも効率的に）実現できる
ということになります。²

QSVTで出来ることの具体例として、HHLアルゴリズムを見ます。
HHLでは、量子状態$\ket{x}$および$\ket{b}$に対して線型方程式$A\ket{x} = \ket{b}$の"解"である$\ket{x_{sol.}} = A^{-1}\ket{b}$を量子状態として(古典的に$A^{-1}$を計算してゲート操作として構築するよりも効率的に）実現します。
ここで、行列$A$の逆行列$A^{-1}$は、$A$の特異値$\sigma$に逆数を取れば得られることに注意します。
すると、$P(x) = \frac{1}{x}$と選んでQSVTを実行すると、$A^{-1}$が”計算”され、HHLアルゴリズムと同じ結果が得られることになります。
なんと、この方法はオリジナルのHHLアルゴリズムよりも更に効率的になっています。QSVTは、HHLを再現するばかりではなく、更に”無駄のない”アルゴリズムなのです。

QSVTのご利益が分かったところで、QSVTの具体的な構成を説明します。
また、その構成から自然にGroverのアルゴリズムが導出されることを見ます。

QSVTの構成

QSVTは、もともとQuantum Signal Processing (QSP) というアルゴリズムの一般化です。
そこで、まずはQSPをやりましょう。

Quantum Signal Processing (QSP)

QSPは、NMR量子系において、微小な信号を量子操作により増幅して、強いパルスとして検出するために用いられていた（らしいです）。
QSPは以下のような構成です。

QSPの回路は、$d$層の繰り返し構造を持っています。
各層は、パラメータ$\phi_{i}$による$Z$軸周りの回転と、固定の値$a$による$X$軸周りの回転からなります。
これを$d$層やったあとに、最後に$\phi_{0}$で$Z$軸周りの回転をして整えた後に出力します。
QSPのポイントは、非可換な演算子である$Z$と$X$を回転軸として、交互に回転させることです。³
さて、このような繰り返し構造の回路全体のユニタリ行列$U$はどのようになっているでしょうか。
QSPでは、特にこのユニタリ行列の左上の成分$P(a)$に着目します。
本来は$\phi$を最適化していくのですが、まず動作を見るために$\phi$は全て0とします。
すると、$d$を変えていったときに、$P(a)$は以下のように推移します。

$d=0 \to P(a) = 1$
$d=1 \to P(a) = a$
$d=2 \to P(a) = 2a^{2}-1$
$d=3 \to P(a) = 4a^{3}-3$

明らかに法則性があります。
実はこれはチェビシェフ多項式と呼ばれるものになっています。
https://ja.wikipedia.org/wiki/%E3%83%81%E3%82%A7%E3%83%93%E3%82%B7%E3%82%A7%E3%83%95%E5%A4%9A%E9%A0%85%E5%BC%8F
チェビシェフ多項式は、三角関数の公式と関係があります。そもそもこの量子回路が回転操作から成り立っていることを考えると、納得です。

層の深さ$d$がチェビシェフ多項式の次数と関わっていそうですね。
つまり量子回路の動作を、所望の次数のチェビシェフ多項式となるようにデザインできるということです！
では、$\phi$を変えるとどうなるでしょうか？
何となく想像できますが、もはや生成できる多項式はチェビシェフ多項式に限らなくなります。
生成できる多項式がなんであるかは、数学的に証明されています。
かつ、$\phi$の決定方法も知られています。
実は生成できる多項式への制限は驚くほど緩いのです！

制約があるのは、多項式が偶関数か奇関数か、ユニタリ行列として埋め込んだ時にユニタリ性が保持されなければならない、ということだけです。
実際に、いろいろな関数が、$P$で近似できます。

え？近似の精度が悪いって？
我々の目標は、関数の近似の精度を上げる（古典を超える）ことそのものではないです。
この関数を量子アルゴリズムに活用することです。
例えば、$P(a)=1/a$が量子操作として（近似的に）実現できていますよね。これの用途、思い出してください。

ここで、行列$A$の逆行列$A^{-1}$は、$A$の特異値$\sigma$に逆数を取れば得られることに注意します。
すると、$P(x) = \frac{1}{x}$と選んでQSVTを実行すると、$A^{-1}$が”計算”され、HHLアルゴリズムと同じ結果が得られることになります。

これは、QSPでHHLアルゴリズムと同じことができるといっているわけです！
ただし、QSPによって多項式で加工できるのはあくまでただの数$a$であって、複数ある特異値を一斉に加工するような話ではありません。
それが出来るようにQSPを拡張したものが、QSVTなのです。

Qubitization

QSPを次元拡張するためには、qubitizationという概念を用います。
(ブロック行列というものをご存じであれば、それがqubitizationです。)

Groverのアルゴリズムを考えます。
Groverでは、解状態周りの折り返しと、初期状態周りの折り返しを繰り返していました。
このような操作は、二次元の空間上の回転操作とみなせます。
こんな図をGroverアルゴリズムの説明で見たことがあるかと思います。

きちんとした定式化は以下を参照ください。
https://www.whyitsso.net/physics/quantum_mechanics/quantum_walk_1.html

重要なことは、初期状態も解状態も、それらが1量子ビット状態でなくても、この図式は成立するということです。
実際、1量子ビット状態とは限らない$\ket{B}$と、その直交$\ket{B\perp}$を入力の二次元基底にとり、
1量子ビット状態とは限らない$\ket{A}$と、その直交$\ket{A\perp}$を出力の二次元基底にとると、
量子操作は$2\times2$のユニタリ行列で表現できます。
(もちろんほんとは$2^{N}$次元ベクトルが$2^{N}$次元ベクトルに移るという$2^{N} \times 2^{N}$行列なのですが）

つまりQSPは多次元に拡張できる　ということがいえます。

さらに、block encodingと呼ばれる技があります。
このあたりから難しいので割愛していきますが、

こんな感じで、ユニタリ行列の中にエルミート行列$H$を埋め込むことが出来ます。
(これをBlock encodingとかqubitizationとかいいます)
https://pennylane.ai/qml/demos/tutorial_block_encoding/

このような表現がされているものへ、QSPを適用すると、なんと**$H$が多項式$P$で加工**されます。

ここで、$P(H)$の意味は、$H$の特異値（ここでは正確には固有値ですが、特異値でも成立します）を全て$P$へ通したものです。
私が最初に記載した、

$U = \sum_{i} \sigma_{i} \ket{w_{i}}\bra{v_{i}} $ があるとき、
$U_{P} = \sum_{i} P(\sigma_{i}) \ket{w_{i}}\bra{v_{i}} $ を"計算"できる

にほかならないですね！⁴

Groverのアルゴリズム、fixed-point amplitude amplificationと、QSVT

先に述べたように、QSVTはGroverアルゴリズムと関係します。
それはQSVTの説明の中でもちらほら出てきましたね。
実際、GroverアルゴリズムはQSVTの特別な場合です。

まず、Groverアルゴリズムの一般化であるamplitude apmlificationは、以下の形式で書き直せます。

左辺が、まさにQSVTそのものですよね。（QSVTの定理から右辺がいえます）
Groverのアルゴリズムは、多項式を決めるパラメータ$\phi$を全部$\pi$に固定したものになっています。

実際に、いわゆるGroverアルゴリズムのdiffusionオペレーターが自然に出てきます (17)。
このときに実現されている多項式というのは、sin関数であって、$d=\lceil \pi/(2\sin^{-1}a) \rceil$
までは単調増加する関数になっています。
これがユニタリ行列の左上成分として埋め込まれているわけです。
左上成分とは、量子ゲート操作された状態と解状態の内積を意味しています。
つまり、これが単調増加するから、測定すると高い確率で解状態が得られる（Grover）というわけです。
（詳細は論文のほうをみてください）

sin関数だから、初期状態($a$)で決まる$d$の最適値を超えて操作を繰り返すと、山を通り越して増幅どころか減少に転じます。
これがいわゆるovercookな状態です。
QSVTだと見通しよく理解できます。

では、最適な関数はsin関数でしょうか？
いえ、振動しない関数だと嬉しいですよね。そしたら、overcookは起きないわけですから。
そんな関数が・・・・

あるんだなこれが。
このうまい関数(sign関数)をQSVTで作り出せば、そもそも(ほとんど)振動せずに、収束します。⁵

Fixed-point quantum search with an optimal number of queries

https://arxiv.org/abs/1409.3305

横軸の$\lambda$は$a$と同じ定義。

このような、振動しないように修正されたものを　fixed-point amplitude amplification　といいます。
ただし、amplitude amplificationにおける最小繰り返し回数$d$に対する制約$d \sim O(\sqrt{N})$は、計算量理論における限界なので、この修正でも変わりません。⁶

しかし、$d \sim O(\sqrt{N})$の制約は、QSVTの目線だと「次数$d$の多項式で生成できる関数は、$a$に対する”立ち上がりの速さ"と”収束した後に残る振動の幅"に限界があり、それゆえ$d \sim O(\sqrt{N})$以上速くはできないのだ」と理解されます。
面白い見方ですよね。

QSVTの使い方、わかっていただけたでしょうか？
もはや量子アルゴリズムのデザインとは

• 問題をどのような行列に埋め込むか（そしてそれをブロック行列として埋め込むか）
• 特異値をどのような多項式で加工するか

に帰着することになります。

まとめ

この記事では、厳密性は放り出して、量子特異値変換(QSVT)を大まかに理解するために解説しました。
私も論文を読み始めたのはここ1か月というところで、、なかなか難しいなという印象です。
ただ、まずは使い方を理解してやると、結構手を動かしやすいアルゴリズムでもあります。
Pennylaneのデモをやるのもいいと思います。
一見すると、量子回路上で不完全な精度の回帰が出来るから何なんだ、と思うんですが、この記事で示したように、目的は量子アルゴリズムとしての動作、そのための設計です。
ぜひ論文やPennylaneのデモをチェックしてみてください。
まだまだ日本語の情報は少ないので、プレイヤーが少なくて、やるなら今と思います。

1. ただし、裏を返せばこれまで発見されてきた量子アルゴリズムはQSVTの特別な場合ばかりであり、QSVTに当てはまらない量子アルゴリズムのクラスを新たに見つけることは非常に難しい問題であることが再認識された、と言えると思います。 ↩

2. この”計算”の意味を古典的な計算と混同して、古典的な問題が量子アルゴリズムによって高速に解ける(古典アルゴリズムと同じ出力が得られる)という誤った結論をしばしば見ますので、注意しましょう。解は量子操作あるいは量子状態として実現されるのであり、それを古典情報として漏れなく取り出そうと思うと、その測定に指数的な時間を要してしまい量子加速が打ち消されるということがよくあります。
   https://dojo.qulacs.org/ja/latest/notebooks/7.2_Harrow-Hassidim-Lloyd_algorithm.html ↩

3. (おそらく）これが$Z$と$X$である必要性はなく、$Z$と$Y$でも良いと思います。 ↩

4. 私の理解では、行列$A$を累乗して$A^{n}$としたときに、その固有値$\lambda$も$\lambda^{n}$に移るよね、って話だと思っています。（それの高級版） ↩

5. とはいえ成功率を1に張り付かせることは出来ないんだけども。チェビシェフ多項式に対するギブスの現象ぽい。 ↩

6. 歴史的に最初にfixed-pointが(Grover自身により)実現された時は$d \sim O(3^{n})$, $N=2^{n}$であって、古典$d \sim O(2^{n})$よりも遅い有様でした。しかも、厳密に増幅しようとすると$d \sim O(3^{n})$が理論限界であることも示されており、絶望感があります。近似を許すことで、$d \sim O(\sqrt{N})$を維持しながらfixed-pointができるというのはすごいことなのです。
   https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.95.150501 ↩