QSVT（Quantum Singular Value Transformation）を3分で説明してみる

序文

この記事は量子コンピューターアドベントカレンダー 2021と、物理学アドベントカレンダー 2021の16日目として作成された。本来は物理学の方には量子誤り訂正について書き、ついでにシリーズ物にしていい日本語資料になればいいかなと思ったが、書きたい内容の1/3くらいを量子コンピューターの方で書かれてしまったので、急遽揃えたというわけだ。記事を2つも書く暇がなかったとも言う。

タイトルで3分で説明してみると言っているのは、説明を端折るための口実でもある。というのも、12月は想像以上に忙しく、記事に時間をたくさん割いているとやるべきことが終わらないということで短くした。大変申し訳ない。

詳しく知りたい方は、以下の論文を読むと良さそうである。いずれもフリーアクセス（arXiv）であり、（英語ではあるが）はるかにこの記事よりも詳しく解説してくれている。

背景

Shorによる量子計算機上での素因数分解が一番知られているが、その他にも様々な「量子アルゴリズム」が考案されてきた。しかし、なぜ量子計算機でのアルゴリズムを研究するのか。その答えは、「古典的な計算機よりも速くなる可能性があるから」である。だが、量子計算機が古典計算機よりも高速にできるタスクというのはあまり知られていないのか、量子アルゴリズムを調べているといくつか基本的なモジュールを見かける事が多い。それは「Quantum Fourier Transform」や「Amplitude Amplification」、「Quantum Phase Estimation」であったり、「Hamiltonian Simulation」だったりである。今回紹介するQSVTは、（ある程度）それらのアルゴリズムを統一的に扱うことができるアルゴリズムである。

QSVT(Quantum Singular Value Transformation)

元論文では、Quantum Signal Processingから順を追ってQSVTを紹介しているが、この記事ではいきなりQSVTを紹介することにする。以下のとおりである。

まず、行列Aなるものを用意する。このとき、任意の行列Aについて、以下のような特異値分解（Singular Value Decomposition）が存在する。

A = W_\Sigma\Sigma V^\dagger_\Sigma

ここで、 W_\Sigma, V_\Sigma はunitaryで、 \Sigma はnon-negativeな実数 \alpha_k をもつ対角行列である。

W_\Sigma, V_\Sigmaの列をそれぞれ {|w_k\rangle},{|v_k\rangle}として、 \tilde{\Pi}:=\sum_k|w_k\rangle\langle w_k|,\Pi:=\sum_k|v_k\rangle\langle v_k|とした上で、 A = \tilde{\Pi}U\PiとなるようなunitaryなUを考える。つまり以下のように左上のブロックにAがあるようなUを考える。

U = \begin{bmatrix} A & \cdot \\ \cdot & \cdot \end{bmatrix}

さらに、このような $U, U^\dagger$ と、 $ \Pi_\phi:=e^{i\phi(2\Pi-I)},\tilde{\Pi}_\phi:=e^{i\phi(2\tilde{\Pi}-I)} $ を用いると、（より厳密には$ \Pi$-controlled notを実行できれば）実は以下のことが言える。

$\phi$の列を$\vec{\phi}$として、以下のような操作を定義したとき、

$$ U_{\vec{\phi}} = \begin{cases} \Pi_{\phi_1}U^\dagger\tilde{\Pi}_{\phi_2}U...\Pi_{\phi_{d-1}}U^\dagger\tilde{\Pi}_{\phi_{d}}U & (d \mathrm{\;is\;even}) \\ \tilde{\Pi}_{\phi_1}U\Pi_{\phi_2}U^\dagger...\Pi_{\phi_{d-1}}U^\dagger\tilde{\Pi}_{\phi_{d}}U & (d \mathrm{\;is\;odd}) \end{cases} $$

以下のような条件を満たす多項式$P(x)$について、

  1. $\mathrm{deg}(P)\leq d$
  2. Pの偶奇とdの偶奇が一致する
  3. $|P|^2\leq1$

必ず以下になるような$\vec{\phi}$が存在する

$$ U_{\vec{\phi}} = \begin{bmatrix} P(A) & \cdot \\ \cdot & \cdot \end{bmatrix} $$

このとき、

$$ P(A) := \displaystyle \sum_{k} P(\alpha_{k}) \ket{w_k}\bra{v_k} $$

であり、

$$ P(A) = \begin{cases} \Pi U_{\vec{\phi}}\Pi & (\mathrm{d\;is\;even}) \\ \tilde{\Pi}U_{\vec{\phi}}\Pi & (\mathrm{d\;is\;odd}) \end{cases} $$

となる。

要約と応用

要するに、「Aを埋め込むようなUnitary Matrixを作る（Block Encoding）」と「$ \Pi$-controlled not」を実現できれば、「Aの特異値（Singular Value）」を基本的に好きな多項式に通して変換できるというアルゴリズムである。

任意の行列について特異値分解が存在すること、そして、特異値を通すための多項式についての制約がかなり少ないことを考えると、幅広い計算がこのアルゴリズムで実現できることがわかるだろう。

実際、元論文では、「Hamiltonianの固有値をtransformする」ことによって「Hamiltonian Simulation」を、「1/xを多項式で近似して、それに特異値を通す」ことによって、「Matrix Inversion」を実現している。Matrix Inversionに関しては、HHLよりも高速化されている。

もちろん、多項式の選び方によっては他の応用もある。詳しくはぜひ元論文を読んでみてほしい。

余談

（ここからは個人的な感想であるので、気にしない人はそのまま別のページに行くと良いだろう。）

基本的にQSVTを実行するためには行列Aをユニタリ行列に埋め込まなければいけない。ここらへんを詳しくやっているのが二本目の論文なのだが、読むと結構大変であることがわかる。大まかに言うと、行列Aの記述をかなりの精度で把握した上で、大量の高階CNOTを行う必要があるのだ。

さらに、QSVTはいくつかのアルゴリズムについては既存のより速いとはいえ、「古典計算機よりも速くする」ためには厳しい課題がある。というのも、（必要な精度で計算することを考えると）単位命令あたりにかかる時間が量子では古典より数百倍〜数千倍遅いためだ。そのため、実用的にこれを行うためには誤り耐性量子計算機で、古典計算機だと到底計算できないような巨大な問題を解くことでようやく利得が現れる。

QSVTに関して最近出た結果として興味深いものに [2111.09079] Dequantizing the Quantum Singular Value Transformation: Hardness and Applications to Quantum Chemistry and the Quantum PCP Conjectureがある。僕もまだ詳しくは中身を精査できていないが、「行列のサイズが小さかったら古典計算機で効率的に計算できる」という主張をしており、つまり、現在の量子計算機（NISQ）だと量子化学計算などを古典計算機よりも高速に行うのはだいぶ厳しいことが示唆される。

NISQ自体の有用性に疑問を投げかけるような論文は今年の後半にいくつか出ており、なかなか先行きが険しいのを感じるが、これからはゆっくりと誤り耐性量子計算機の実装が進んでゆくのだろう。