QSVT の具体例集：多項式を選ぶと何が起きるか

最も単純な例では、対象行列は \(1\times1\) 行列 \(A=[a]\) である。\(a=0.6\) とし、奇多項式 \(P(x)=x^3\) を選ぶ。

\[ P^{(\mathrm{SV})}(A)=[P(0.6)]=[0.216]. \]

この例は「QSVT は各特異値に同じ関数をかける」ことをそのまま表す。スカラーでは特異値と値の符号の扱いが見えにくいが、奇多項式なら符号付きの写像として直感的である。

\(A=\operatorname{diag}(0.9,0.3)\) とし、\(P(x)=x^3\) を適用する。

\[ P^{(\mathrm{SV})}(A)=\operatorname{diag}(0.9^3,0.3^3)=\operatorname{diag}(0.729,0.027). \]

大きい特異値は比較的残り、小さい特異値は強く抑制される。低ランク化・ノイズ抑制の直感はここから始まる。

左特異ベクトル \(\ket{w_1},\ket{w_2}\in\mathbb C^3\)、右特異ベクトル \(\ket{v_1},\ket{v_2}\in\mathbb C^2\) を持つ

\[ A=0.8\ket{w_1}\bra{v_1}+0.4\ket{w_2}\bra{v_2} \]

に \(P(x)=x^3\) を適用すると、

\[ P^{(\mathrm{SV})}(A)=0.512\ket{w_1}\bra{v_1}+0.064\ket{w_2}\bra{v_2}. \]

出力は \(A\) と同じく \(3\times2\) 型である。奇多項式は左右特異空間をつなぐ。

同じ \(A=\sum_j\sigma_j\ket{w_j}\bra{v_j}\) に偶多項式 \(P(x)=x^2\) を使うと、奇多項式のような \(m\times n\) 行列ではなく、右特異空間または左特異空間上の演算として現れる。

\[ \sum_j \sigma_j^2\ket{v_j}\bra{v_j}=A^\dagger A \quad\text{または}\quad \sum_j \sigma_j^2\ket{w_j}\bra{w_j}=AA^\dagger . \]

矩形行列では \(A^\dagger A\) は \(n\times n\)、\(AA^\dagger\) は \(m\times m\) であり、形が異なる。

初期成功振幅を \(a=\sin\theta\) とすると、標準的な Grover 反復 \(m\) 回後の成功振幅は

\[ P_{2m+1}(a)=\sin((2m+1)\theta)=\sin((2m+1)\arcsin a). \]

これは次数 \(2m+1\) の奇多項式であり、QSVT/QSP の多項式変換として読める。例えば \(m=1\) では

\[ P_3(a)=3a-4a^3. \]

ただし過回転により \(P_{2m+1}(a)\) が小さくなることがあるため、未知の \(a\) には固定点型増幅が有用になる。

固定点振幅増幅では、ある閾値以上の成功振幅を高い成功確率へ押し上げ、同時に過回転を避ける多項式を設計する。概念的には

\[ P(a)\approx 1\quad(a\ge a_0),\qquad |P(a)|\le1 \]

を満たす奇多項式を使う。Chebyshev 多項式を用いると、失敗確率を指数的に小さくする固定点型の設計が可能になる。

低ランク近似や主成分抽出では、\(\sigma\ge\tau\) の成分だけを残したい。理想は段差関数

\[ f(\sigma)=\begin{cases}1,&\sigma\ge\tau,\\0,&\sigma<\tau,\end{cases} \]

だが、不連続関数は有限次数多項式で完全には表せない。実際にはギャップ \([\tau-\Delta,\tau+\Delta]\) を許し、その外側で近似する。

\[ P(\sigma)\approx 0\;(\sigma\le\tau-\Delta),\qquad P(\sigma)\approx 1\;(\sigma\ge\tau+\Delta). \]

エルミート \(H\) の固有値 \(\lambda\in[-1,1]\) に対し、\(\operatorname{sgn}(\lambda)\) を近似する多項式を使うと、正負固有空間を分離できる。

\[ H=\sum_j\lambda_j\ket{u_j}\bra{u_j} \quad\Longrightarrow\quad P(H)\approx \sum_j\operatorname{sgn}(\lambda_j)\ket{u_j}\bra{u_j}. \]

ゼロ近傍にギャップ \(|\lambda|\ge\delta\) が必要で、次数は典型的に \(1/\delta\) に依存する。

\(\sigma\in[1/\kappa,1]\) 上で \(1/\sigma\) を実装したい。ただし \(|1/\sigma|\) は最大 \(\kappa\) なので、そのままでは \(|P|\le1\) に反する。そこで

\[ P(\sigma)\approx \frac{1}{\kappa\sigma} \]

を実装し、出力振幅に \(1/\kappa\) のスケールを持たせる。成功確率や振幅増幅を含めると、条件数 \(\kappa\) が資源量に現れる。

矩形行列 \(A=\sum_j\sigma_j\ket{w_j}\bra{v_j}\) の Moore-Penrose 疑似逆は

\[ A^+=\sum_{\sigma_j>0}\sigma_j^{-1}\ket{v_j}\bra{w_j}. \]

QSVT では \(\sigma_j\ge 1/\kappa\) の範囲で \(1/\sigma\) を近似し、\(\sigma_j\) が非常に小さい領域はフィルタで抑制する。これにより ill-conditioned な成分の爆発を避ける。

多くの実装では \(U\) が \(A\) ではなく \(A/\alpha\) を block-encode する。

\[ (\bra{0^a}\otimes I)U(\ket{0^a}\otimes I)=A/\alpha. \]

QSVT の信号は \(\sigma_j(A)/\alpha\) である。したがって \(f(A)\) を得たいなら、実際には \(x=\sigma/\alpha\) 上で \(f(\alpha x)\) を近似する必要がある。

\(\|H\|\le1\) のエルミート行列に対し、固有値 \(\lambda\) 上の関数 \(e^{-it\lambda}\) を実装したい。Jacobi-Anger 展開により

\[ e^{-itx}=J_0(t)+2\sum_{k=1}^{\infty}(-i)^kJ_k(t)T_k(x) \]

と Chebyshev 多項式で展開できる。QSP/QSVT はこの多項式近似を固有値変換として実装する。

\(H=Z=\operatorname{diag}(1,-1)\) の場合、

\[ e^{-itZ}=\operatorname{diag}(e^{-it},e^{it}). \]

固有値は \(\pm1\) だけなので、実は低次数補間でもこの 2 点上では正確に合わせられる。一般の \(H\) では固有値が連続的に分布し得るため、\([-1,1]\) 全体での近似が必要になる。

データ行列 \(A\) の大きい特異値だけを使う主成分分析では、しきい値多項式 \(P\) によって

\[ \sum_j \sigma_j\ket{w_j}\bra{v_j} \mapsto \sum_j P(\sigma_j)\sigma_j\ket{w_j}\bra{v_j} \]

のような抑制を考える。\(P\) が \(0/1\) フィルタなら主成分を残す射影に近い。

主成分回帰では、小さい特異値を捨て、大きい特異値には逆数をかける。

\[ f(\sigma)\approx \begin{cases} 1/\sigma,&\sigma\ge\tau,\\ 0,&\sigma\le\tau-\Delta. \end{cases} \]

これは「しきい値フィルタ」と「逆数変換」の合成として理解できる。QSVT はこのような特異値依存の非線形処理を統一的に扱う。

フルランクに近い \(A=\sum_j\sigma_j\ket{w_j}\bra{v_j}\) に対し、極分解の部分等長成分は

\[ Q=\sum_j\ket{w_j}\bra{v_j}. \]

これは特異値を \(1\) に置き換える変換であり、\(P(\sigma)\approx1\) をギャップ領域 \(\sigma\ge\delta\) で実装することに相当する。ゼロ特異値近傍は不連続性のためギャップが必要。

非エルミート \(A\) は、

\[ H_A=\begin{pmatrix}0&A\\A^\dagger&0\end{pmatrix} \]

とエルミート化できる。\(H_A\) の固有値は \(\pm\sigma_j(A)\) であり、固有値変換として QSVT を見る入口になる。ただし QSVT 本来の projected unitary encoding はこの構成より直接的に特異値を扱う。

上のブロックエルミート行列 \(H_A\) に \(\operatorname{sgn}\) を適用すると、形式的に

\[ \operatorname{sgn}(H_A)= \begin{pmatrix} 0&Q\\Q^\dagger&0 \end{pmatrix} \]

が得られる。ここで \(Q\) は \(A\) の極分解の部分等長成分である。これも sign 近似と特異値ギャップの例である。

位相推定は固有値をビット列として読む手法だが、QSVT 的には「ある区間に固有値が入るか」を多項式フィルタで判定する見方ができる。

\[ P_{\Delta,c}(x)\approx \begin{cases} 1,&x\in[c-\Delta,c+\Delta],\\ 0,&\text{outside a wider interval}. \end{cases} \]

多くのサブルーチンは、精密な数値推定ではなく、このような yes/no フィルタで十分な場合がある。

量子ウォーク探索では、marked subspace への重なりが小さい初期状態から開始し、その成分を増幅する。QSVT では、対応する block-encoding の特異値または固有位相に対して、振幅増幅多項式を適用する見方ができる。

具体的には、良い空間への遷移振幅 \(a\) を \(\sin((2m+1)\arcsin a)\) 型または固定点型の多項式で変換する。

入力候補のうち少なくとも 1 つが marked であるかを調べる OR 問題は、Grover 探索の基本例である。QSVT の言葉では、marked subspace への振幅を高める奇多項式変換として読める。

固定点型にすれば、marked 数が未知でもロバストに成功確率を上げる設計が可能になる。

QSVT の魅力は、単にスカラー関数を特異値へかけるだけでなく、ブロックの読み方により \(A,A^\dagger,AA^\dagger,A^\dagger A\) に関わる非可換な行列演算へ接続できる点にある。

例えば奇変換は左右特異空間をつなぎ、偶変換は片側の特異空間内で作用する。この切替が行列算術の部品になる。

\(T_2(x)=2x^2-1\) は \([-1,1]\) 上で \([-1,1]\) に収まる偶多項式なので QSP 条件の候補になる。

しかし偶多項式なので、\(A\) と同じ形の \(m\times n\) ブロックではなく、右または左特異空間のブロックとして実装される。矩形 \(A\) に対して「\(2A^2-I\)」と読むのは誤りである。

\(T_3(x)=4x^3-3x\) は奇多項式で、\(|T_3(x)|\le1\) を満たす。

\[ T_3(\cos\theta)=\cos(3\theta). \]

QSP が Chebyshev 構造と相性が良い理由は、信号 \(x=\cos\theta\) の角度を多倍角に変換するこの恒等式にある。

\(P(x)=2x\) は奇で次数 1 だが、\([-1,1]\) 上で \(|P(1)|=2\) となる。

ユニタリの行列要素の絶対値は 1 を超えられないため、この多項式はそのまま QSP/QSVT では実装できない。スケールして \(P(x)=x\) にするか、有効領域を狭めて別の設計にする必要がある。

\(1/x\) は \(x=0\) で発散するため、\([-1,1]\) 全体では一様近似できない。線形システムでは特異値下限 \(1/\kappa\) を仮定し、

\[ x\in[1/\kappa,1] \]

だけで近似する。ギャップ外の振る舞いは \(|P(x)|\le1\) を守るように制御する。

物理応用では、急峻なステップ関数の代わりに Fermi-Dirac 型の滑らかな関数

\[ f_\beta(x)=\frac{1}{1+e^{\beta(x-\mu)}} \]

を近似したい場合がある。滑らかさがあるため不連続なステップより近似しやすいが、\(\beta\) が大きいほど遷移幅が狭くなり、次数が増える。

熱状態準備などでは \(e^{-\beta H/2}\) のような非ユニタリ作用が欲しい。QSVT はユニタリ全体の中のブロックとして

\[ P(H)\approx c\,e^{-\beta H/2} \]

を実装できる。係数 \(c\) は \(|P(x)|\le1\) を満たすためのスケールであり、成功確率に影響する。

ブロック符号化された対角行列や確率分布の振幅に対し、特異値変換で重み関数をかけると、新しい分布に比例する状態を作る部品になる。

ただし出力は一般にブロック内にあり、正規化と成功確率の管理が必要である。

正定値行列または特異値に対して \(x^\gamma\) を近似すると、平方根、逆平方根、分数冪が得られる。

\[ P(\sigma)\approx \sigma^\gamma,\qquad 0<\gamma<1. \]

\(\sigma=0\) 近傍の滑らかさや導関数の発散が次数に影響するため、通常は \(\sigma\ge\delta\) のギャップを置く。

LCU などで得た block-encoding は成功振幅が固定値に近いことが多い。Oblivious amplitude amplification は、データ状態に依存せず ancilla 成功振幅を増幅する。

QSVT では、ancilla の成功振幅を特異値として見て、対応する多項式で成功ブロックを強める操作として理解できる。

入力 block-encoding が \(\epsilon_U\) だけずれていると、QSVT 回路中で \(U\) または \(U^\dagger\) を \(O(d)\) 回使うため、粗い評価では出力誤差に \(O(d\epsilon_U)\) が現れる。

したがって多項式近似誤差 \(\epsilon_{\mathrm{poly}}\) だけを小さくしても、入力実装が粗ければ総誤差は改善しない。

位相列 \(\Phi=(\phi_0,\dots,\phi_d)\) を有限精度で実装すると、各位相ゲートのずれが蓄積する。多くの場合、各位相を十分なビット数で表せば全体誤差は制御できるが、高次数では数値安定性も問題になる。

実務では、位相合成後に得られる \(P_\Phi(x)\) をサンプル点で検証し、目標 \(P(x)\) との最大誤差を見る。

\(e^{-itx}=\cos(tx)-i\sin(tx)\) は複素値関数である。QSP convention によっては、実部と虚部を別々の多項式として扱うか、複素多項式を直接扱う。

\[ \cos(tx)\ \text{は偶成分中心},\qquad \sin(tx)\ \text{は奇成分中心}. \]

この偶奇の違いが、回路のブロック読み出しや補助操作に反映される。

QSVT で \(c f(A)\) の block-encoding を得たとき、\(c<1\) は単なる係数ではなく、postselection の成功振幅に関わる。

たとえば逆数変換で \(c=1/\kappa\) が必要になると、成功確率は典型的に \(1/\kappa^2\) スケールになり得るため、振幅増幅で補うか、アルゴリズム全体でこの係数を受け入れる必要がある。

\(\kappa=5\) で特異値が \(\sigma=(1,0.5,0.2)\) の場合、scaled inverse \(P(\sigma)=1/(5\sigma)\) は

\[ P(1)=0.2,\qquad P(0.5)=0.4,\qquad P(0.2)=1. \]

最小許容特異値 \(1/\kappa=0.2\) でちょうど 1 になり、これより小さい特異値へはそのまま延長できない。