Quantum Singular Value Transformation 詳解
QSVT は、ユニタリ \(U\) のブロックに埋め込まれた行列 \(A\) の特異値を、同じ量子回路内で \(\sigma_j\mapsto p(\sigma_j)\) と変換する枠組みである。Qubitization を知っているなら、 「各特異値 \(\sigma_j\) が作る 2 次元不変部分空間上で QSP を実行し、その結果を SVD 全体に直和的に貼り合わせる」 と見るのが最も短い。
0. QSVT を一文で
\(U\) が \(A/\alpha\) の block-encoding で、\(p\) が \([-1,1]\) 上で \(|p|\le1\) を満たす次数 \(d\) の適切なパリティの多項式なら、 QSVT はおよそ \(d\) 回の \(U,U^\dagger\) の呼び出しで
をユニタリのブロックとして生成する。偶多項式では、同じ向きの写像ではなく \(p(\sqrt{AA^\dagger}/\alpha)\) または \(p(\sqrt{A^\dagger A}/\alpha)\) 型の同側作用素になる。
QSVT で必要な設計判断は、ほぼ次の 4 つに尽きる。
1. 何を埋め込んだか
\(A\) なのか \(A^\dagger\) なのか、Hermitian なのか、正規化係数 \(\alpha\) は何か。
2. 何を変換したいか
非 Hermitian なら特異値変換。Hermitian なら固有値変換として読める場合がある。
3. 多項式は実装可能か
次数、パリティ、\([-1,1]\) 上の有界性、ギャップ領域での近似誤差。
4. 出力のスケールは何か
実装されるのは通常 \(F(A)/\beta\)。状態として取り出すには postselection や amplitude amplification が関わる。
1. 入力モデル:block-encoding と projected unitary encoding
1.1 Block-encoding
ユニタリ \(U\) が \(A\) の \((\alpha,a,\delta)\)-block-encoding であるとは、\(a\) 個の ancilla qubits に対して
が成り立つことをいう。厳密な場合は \(\delta=0\) で、上左ブロックが \(A/\alpha\) そのものになる。 非正方行列は、入出力空間を同じ大きさにパディングするか、次の projected unitary encoding で扱う。
1.2 Projected unitary encoding
QSVT の構造を最も明瞭にするには、直交射影 \(\Pi,\widetilde\Pi\) とユニタリ \(U\) で
と書く。標準 block-encoding は \(\Pi=\widetilde\Pi=\proj{0^a}\otimes I\) の特殊例である。非正方行列では入力側射影と出力側射影を分けることで、右特異空間と左特異空間を自然に扱える。
2. 古典的 SVT の定義
まず量子を忘れる。\(A\in\C^{m\times n}\) の SVD を
とする。右特異ベクトルは \(\ket{v_j}\)、左特異ベクトルは \(\ket{w_j}\) で、 \(A\ket{v_j}=s_j\ket{w_j}\), \(A^\dagger\ket{w_j}=s_j\ket{v_j}\) である。
2.1 奇多項式:\(A\) と同じ向き
奇多項式 \(p\) について
と定義する。これは \(A\) と同じく右特異空間から左特異空間へ写す。単項式なら
2.2 偶多項式:左側または右側の同側作用素
偶多項式 \(p\) では向きが変わる。左側版と右側版がある。
左特異空間上
\[ p^{(\mathrm{SV}),L}(A) =\sum_j p(s_j)\ket{w_j}\!\bra{w_j} =p(\sqrt{AA^\dagger}) \]右特異空間上
\[ p^{(\mathrm{SV}),R}(A) =\sum_j p(s_j)\ket{v_j}\!\bra{v_j} =p(\sqrt{A^\dagger A}) \]\(p(0)\ne0\) の場合は、\(\ker(A^\dagger)\) や \(\ker(A)\) 上のゼロ特異値成分にも \(p(0)\) が作用する。 そのため厳密には、SVD をゼロ特異値まで含む完全な特異ベクトル基底へ拡張して読むのが安全である。
非 Hermitian \(A\) に QSVT をかけても、一般には固有値 \(\lambda\) は \(p(\lambda)\) にならない。 変換されるのは特異値である。Hermitian \(A\) では特別な読み替えにより固有値変換として使えるが、一般行列の eigenvalue transform とは別物である。
3. Qubitization から見た QSVT
Qubitization では、Hermitian 信号の固有値 \(\lambda\) ごとに \(\cos\theta=\lambda\) を満たす 2 次元回転が現れる。 QSVT では、特異値 \(\sigma\) ごとに同じ構造が現れる。
3.1 特異値ペアが作る 2 次元構造
\(A=\widetilde\Pi U\Pi\) とし、\(A\ket{v}=\sigma\ket{w}\), \(A^\dagger\ket{w}=\sigma\ket{v}\) とする。 \(0<\sigma<1\) なら
したがって、各 \(\sigma\) はスカラー信号
と同型な 2 次元ブロックを作る。QSVT はこのブロックへ \(Z\)-方向の位相変調を挿入する。
3.2 位相付き反射
Qubitization の反射 \(2\Pi-I\) を、QSVT では
へ拡張する。2 次元ブロック内では、これが QSP の \(Z\)-回転に対応する。
4. QSP の多項式核
QSVT の実体は、次のスカラー QSP 定理を全ての特異値 \(\sigma_j\) に同時適用することにある。
一つの convention として
を考える。このとき上左成分は多項式になり、全体は
の形を持つ。ここで \(\deg P\le d\), \(\deg Q\le d-1\)、\(P\) は \(d\) と同じ偶奇、\(Q\) は \(d-1\) と同じ偶奇であり、 ユニタリ性から
実係数多項式 \(p\in\R[x]\) が
を満たすなら、適切な位相列 \(\Phi\) により、QSP/QSVT の目的ブロックとして \(p(x)\) を実装できる。 複素多項式を直接扱う場合は、上の \(Q\) とのユニタリ補完条件まで含めて設計する。
5. QSVT 定理
以下では exact encoding を書く。近似 encoding の誤差は後の誤差節で扱う。
\(A=\widetilde\Pi U\Pi=\sum_j\sigma_j\ket{w_j}\!\bra{v_j}\) とする。 \(p\) が奇多項式、\(\deg p\le d\)、\(|p(x)|\le1\) を満たすなら、\(U,U^\dagger\) と \(R_\Pi(\phi),R_{\widetilde\Pi}(\phi)\) の交互列 \(U_\Phi\) が存在して
を満たす。これは入力側 \(\im(\Pi)\) から出力側 \(\im(\widetilde\Pi)\) への写像である。
\(p\) が偶多項式なら、QSVT 列の端点を入力側または出力側にそろえることで
のどちらかを実装できる。ゼロ特異値の補空間では \(p(0)\) の作用を含む。
5.1 スケール付き block-encoding と出力スケール
\(U\) が \(A/\alpha\) を block-encode しているなら、QSVT は \(\sigma_j=s_j/\alpha\) に作用する。 欲しい関数が \(f(s)\) なら、実装する多項式は
したがって出力ブロックは \(F(A)/\beta\) である。ここで \(\beta\) は出力の正規化係数であり、postselection 成功確率にも影響する。
5.2 回路列の convention
実装上は、位相ゲートを \(\Pi_\phi=(I-\Pi)+e^{i\phi}\Pi\) とする流儀と、 \(R_\Pi(\phi)=e^{i\phi(2\Pi-I)}\) とする流儀がある。両者は global phase と \(\phi\) の再スケールで関係する。 典型的な QSVT 列は概略的に
のように、\(U\) と \(U^\dagger\) を交互に使う。どちらの側から始め、どちらの側で終えるかが、奇変換・偶変換・左側版・右側版を決める。 位相合成ソフトの convention と回路の convention を一致させることが必須である。
6. 証明の骨格
Step 1: SVD で直和分解する
\((\sigma_j,\ket{v_j},\ket{w_j})\) ごとに、\(\ket{v_j},\ket{v_j^\perp}\) と \(\ket{w_j},\ket{w_j^\perp}\) が作る小さな不変構造を取り出す。異なる \(j\) は直交している。
Step 2: 各ブロックを QSP の信号行列に同型化する
\(\sigma_j=\cos\theta_j\) と置くと、\(U\) はそのブロック上で \(W(\sigma_j)=e^{i\theta_jX}\) と同じ役割を果たす。 \(R_\Pi(\phi)\) と \(R_{\widetilde\Pi}(\phi)\) は \(Z\)-回転に対応する。
Step 3: QSP が \(P(\sigma_j)\) を生成する
位相列 \(\Phi\) を選べば、各ブロックの目的行列要素は \(p(\sigma_j)\) になる。
Step 4: 直和を戻す
同じ位相列は全ての \(\sigma_j\) に同時に作用するので、 \(\sum_j p(\sigma_j)\ket{w_j}\bra{v_j}\) が得られる。
端点 \(\sigma=0,1\) の扱い
\(\sigma=1\) では補ベクトルが消え、\(\sigma=0\) では良い成分が消える。QSP の多項式表示は連続なので定理は端点にも拡張される。 ただし \(1/x\) や \(\sgn(x)\) のような特異・不連続関数を近似するには、スペクトルが 0 から離れているというギャップ仮定が必要になる。
パリティがなぜ出るか
\(W(x)\) を \(d\) 回使うと、上左成分に現れる \(x\) の次数は \(d,d-2,d-4,\ldots\) だけになる。 したがって \(d\) が奇なら奇多項式、偶なら偶多項式が目的ブロックに現れる。
7. 多項式設計
- スペクトル領域を決める。SVT なら通常 \(s/\alpha\in[0,1]\)、Hermitian eigenvalue transform なら \(\lambda/\alpha\in[-1,1]\)。
- 欲しい関数 \(f\) を決める。例:\(e^{-itx}\), \(1/x\), \(\sgn(x)\), threshold, power, filter。
- 出力スケール \(\beta\) を選び、\(|p|\le1\) となる \(p(x)=f(\alpha x)/\beta\) を設計する。
- 次数とパリティを合わせる。一般関数は偶奇分解や LCU 合成を使う。
- Chebyshev 展開、Bessel/Jacobi-Anger 展開、Remez/minimax、Jackson damping などで近似多項式を作る。
- 位相合成で \(\Phi\) を求め、回路 convention に合わせて変換する。
7.1 代表的な次数スケール
| 目的 | 近似対象 | 必要な仮定 | 次数の目安 |
|---|---|---|---|
| Hamiltonian simulation | \(e^{-i\tau x}\) | \(x\in[-1,1]\) | \(O(\tau+\log(1/\eps))\) 程度 |
| 行列反転 | \(1/x\) | \(x\in[1/\kappa,1]\) | \(O(\kappa\log(\kappa/\eps))\) |
| sign / threshold | \(\sgn(x)\), step | \(|x|\ge\Delta\) | \(O(\Delta^{-1}\log(1/\eps))\) |
| 滑らかな解析関数 | analytic \(f\) | 複素近傍で正則 | しばしば \(O(\log(1/\eps))\) |
上表は設計指針であり、定数・対数因子・最適性は入力モデルや近似法に依存する。
7.2 反転の正規化
\([1/\kappa,1]\) 上で \(1/x\) は最大 \(\kappa\) なので、直接 \(1/x\) は block に入らない。 QSVT が実装するのは典型的には
そのため出力は \(A^+/\kappa\) 型になる。状態として取り出すときには、この \(\kappa\) による成功振幅低下が別途効く。
8. 位相合成
多項式 \(p\) を決めただけでは回路はできない。QSP/QSVT では位相列 \(\Phi=(\phi_0,\ldots,\phi_d)\) が回路を指定する。
8.1 補多項式 \(Q\)
目標成分 \(P=p\) に対して、ユニタリ性を満たす補多項式 \(Q\) が必要である。
この補完は spectral factorization / Fejér–Riesz 型の問題として扱える。そこから Laurent 多項式表示へ移り、最高次数項を剥がして位相を抽出する。
8.2 実用上の方法
| 方法 | 特徴 | 注意点 |
|---|---|---|
| Laurent / algebraic factorization | 多項式構造を直接使う。多くの実装の標準。 | 根の条件数、丸め、convention に注意。 |
| Haah の halving 系 | 高次数でも機械精度で位相を見つけることを狙う。 | 入力多項式の正規化が重要。 |
| 数値最適化 | 位相を直接フィットする。考え方は単純。 | 高次数で遅く、局所解や不安定性がある。 |
| Symmetric QSP | 対称位相列を仮定し、変数を減らす。 | 対象多項式のクラスが制限される。 |
phase list は convention 依存である。\(W_x\) と \(W_z\)、\(e^{i\phi Z}\) と \(e^{-i\phi Z}\)、位相列の順序、 global phase の扱いが違うと、同じ数列でも \(p(x)\), \(p(-x)\), \(p(x)^*\), \(ip(x)\) など別の多項式を実装し得る。
9. 回路実装
9.1 Projector-controlled phase
標準 block-encoding では \(\Pi=\proj{0^a}\otimes I\) なので、位相ゲートは
である。global phase を無視すれば、ancilla が \(\ket{0^a}\) のときだけ位相をかける多重制御 phase で実装できる。
9.2 Query count
次数 \(d\) の QSVT は \(\Theta(d)\) 回の \(U\) または \(U^\dagger\) を使う。 projector-controlled phase も \(\Theta(d)\) 個である。追加 qubit は通常、block-encoding 用 ancilla に加えて定数個で済むが、 LCU 合成や複素多項式の実装方法により変わる。
9.3 出力は block であって状態ではない
QSVT 回路は \(F(A)/\beta\) を「ユニタリのブロック」として実装する。 入力 \(\ket b\) に \(F(A)\) を作用させた状態を得るには、ancilla が所定状態に戻った成分を postselect する。 成功振幅はおおよそ \(\|F(A)\ket b\|/\beta\) であり、小さい場合は amplitude amplification が必要になる。
10. 誤差と資源
実装誤差は少なくとも次のように分けて管理する。
| 項目 | 意味 | 設計上の処理 |
|---|---|---|
| \(\eps_{\rm poly}\) | \(p\) が \(f\) を近似する誤差 | 次数を上げる、近似法を変える。 |
| \(\eps_{\rm phase}\) | 位相合成の数値誤差 | 高精度演算、安定な factorization、検証。 |
| \(\eps_{\rm query}\) | \(U,U^\dagger\) の実装誤差 | 回路積の telescoping で概ね \(O(d\delta_U)\)。 |
| \(\eps_{\rm input}\) | block-encoding 自体の近似誤差 | 多項式の感度とギャップ余裕を考慮。 |
\(d\) 回の query を使うため、各 query の operator norm 誤差が \(\delta_U\) なら総回路誤差は保守的に \(O(d\delta_U)\) と見積もる。 入力行列そのものの誤差 \(E\) は、多項式 \(p\) の Lipschitz 定数にも依存する。特に閾値や反転の近似では、境界近くのスペクトルに余裕を持たせる。
11. 応用
11.1 Hamiltonian simulation
Hermitian \(H/\alpha\) の block-encoding があるとき、固有値 \(x=\lambda/\alpha\in[-1,1]\) に
を作用させれば \(e^{-iHt}\) を得る。実装は複素 QSP として行うか、\(\cos(\alpha tx)\) と \(\sin(\alpha tx)\) の実多項式を組み合わせる。 Chebyshev/Jacobi-Anger 展開
を切り詰めるのが基本的な構成である。
11.2 Linear systems / pseudoinverse
\(A=W\Sigma V^\dagger\) の pseudoinverse は \(A^+=V\Sigma^+W^\dagger\) である。 したがって \(A^+\) を得るには、\(A^\dagger=V\Sigma W^\dagger\) の block-encoding に
を作用させるのが自然である。出力は \(A^+/\kappa\) の block-encoding であり、解状態の取り出しには成功振幅の増幅が絡む。
11.3 Amplitude amplification
振幅増幅は、成功振幅を 1 つの特異値として見る QSVT の特殊例である。 Grover 型の反復は \(\sin((2m+1)\arcsin x)\) という多項式変換に対応し、fixed-point amplitude amplification は 小さい振幅を過剰回転なしに抑える bounded polynomial の設計として理解できる。
11.4 Thresholding, filtering, PCA
step 関数や滑らかな窓関数を多項式近似すれば、特異値が閾値を超える部分空間を抽出できる。 principal component regression、rank filtering、preconditioning、ground-state filtering などはこの見方で整理できる。
12. Interactive Lab
12.1 Scalar QSP response explorer
位相 \(\phi_k\) を動かすと、QSP の上左成分 \(P_\Phi(x)\) が変わる。これは各特異値ブロック内の QSVT の動作である。
12.2 Singular values transformation demo
2 つの特異値 \(\sigma_1,\sigma_2\) にテンプレート多項式を作用させる。
12.3 Degree rough calculator
定数を含まない目安。実際の論文レベルの資源見積もりでは、近似多項式・入力モデル・失敗確率を固定して再計算する。
13. 計算例
13.1 \(p(x)=x^3\)
\(\|A\|\le1\) として、奇多項式 \(p(x)=x^3\) を使うと
小さい特異値は \(s^3\) で強く抑えられる。大きい特異値を強調する滑らかなフィルタの最小例である。
13.2 \(p(x)=x^2\) は \(A^2\) ではない
非 Hermitian \(A\) に対する偶多項式 \(x^2\) は
であり、一般には \(A^2\) ではない。これは QSVT 初学者が最も頻繁に間違える点である。
13.3 Pseudoinverse
\(A=W\Sigma V^\dagger\) なら \(A^+=V\Sigma^+W^\dagger\)。したがって \(A^\dagger=V\Sigma W^\dagger\) に \(p(s)\approx1/(\kappa s)\) をかけると
これが QSVT 版の線形方程式解法の基本ブロックである。
14. 落とし穴チェック
特異値変換と固有値変換の混同
非 Hermitian \(A\) で \(\lambda\mapsto p(\lambda)\) は一般には起きない。
偶多項式の向き
\(x^2\) は \(A^2\) ではなく \(AA^\dagger\) または \(A^\dagger A\)。
スケール忘れ
入力は \(A/\alpha\)、出力は \(F(A)/\beta\)。成功確率にも影響する。
位相 convention の混合
phase list はそのまま移植できないことが多い。
ギャップなしの反転
\(1/x\) や sign は 0 近傍で一様近似できない。ギャップが次数を支配する。
block-encoding コストの無視
QSVT は query-efficient でも、1 query の実装が高ければ全体は重い。
参考文献
- [GSLW19] András Gilyén, Yuan Su, Guang Hao Low, Nathan Wiebe, “Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics,” STOC 2019 / arXiv:1806.01838.
- [LC19] Guang Hao Low, Isaac L. Chuang, “Hamiltonian Simulation by Qubitization,” Quantum 3, 163 (2019), arXiv:1610.06546.
- [LC17] Guang Hao Low, Isaac L. Chuang, “Optimal Hamiltonian Simulation by Quantum Signal Processing,” Physical Review Letters 118, 010501 (2017), arXiv:1606.02685.
- [LYC16] Guang Hao Low, Theodore J. Yoder, Isaac L. Chuang, “The Methodology of Resonant Equiangular Composite Quantum Gates,” Physical Review X 6, 041067 (2016), arXiv:1603.03996.
- [MRTC21] John M. Martyn, Zane M. Rossi, Andrew K. Tan, Isaac L. Chuang, “A Grand Unification of Quantum Algorithms,” PRX Quantum 2, 040203 (2021), arXiv:2105.02859.
- [CDGHS20] Rui Chao, Dawei Ding, András Gilyén, Cupjin Huang, Mario Szegedy, “Finding Angles for Quantum Signal Processing with Machine Precision,” arXiv:2003.02831.
- [pyqsp] Isaac Chuang group, “pyqsp: Python quantum signal processing.”
- [PennyLane] Xanadu, “Intro to QSVT” and “QSVT in Practice.”