定義、QSP の多項式条件、QSVT 定理、奇偶パリティ、応用、誤差、位相合成までを確認する 45 問。各問題に解答を付け、理解済みチェックとフィルタを入れた。
Qubitization までは理解している前提で、QSVT の抽象定理を「自分で使える形」にすることを目的にしている。各問題はまず自力で式を書き、次に解答を開いて比較するのがよい。
演習の核は次の3つである。
これは \(A\) と同じ形を持つ代表的な読み方。
矩形行列では次元が変わるので特に注意。
さらにユニタリ completion が必要。
次数がそのまま量子回路コストの主要因になる。
\(a\) 個の ancilla を持つユニタリ \(U\) が
\[ (\bra{0^a}\otimes I)U(\ket{0^a}\otimes I)=A/\alpha \]を満たすとする。このとき \(U\) は何を block-encode しているか。信号として QSVT に入る特異値は何か。
\(U\) は \(A/\alpha\) を block-encode している。したがって QSVT の信号は \(A\) の特異値 \(\sigma_j(A)\) そのものではなく、正規化された特異値
\[ x_j=\sigma_j(A)/\alpha \]である。\(f(A)\) を得たい場合、QSVT の多項式は \(x\mapsto f(\alpha x)\) を近似するように設計する。
projected unitary encoding \(A=\widetilde{\Pi}U\Pi\) が、通常の ancilla block-encoding を含むことを説明せよ。
通常の block-encoding では \(\Pi=\widetilde{\Pi}=\ket{0^a}\bra{0^a}\otimes I\) と置けばよい。このとき
\[ \widetilde{\Pi}U\Pi = (\ket{0^a}\bra{0^a}\otimes I)U(\ket{0^a}\bra{0^a}\otimes I) \]の非自明部分が \((\bra{0^a}\otimes I)U(\ket{0^a}\otimes I)\) であり、これが \(A/\alpha\) になる。projected unitary encoding は入力側と出力側の射影が異なってもよいので、矩形行列やより一般のブロック構造を扱いやすい。
\(A=0.8\ket{w_1}\bra{v_1}+0.3\ket{w_2}\bra{v_2}\) に奇多項式 \(P(x)=x^3\) を適用した \(P^{(\mathrm{SV})}(A)\) を求めよ。
奇多項式なので、出力は \(A\) と同じく右特異空間から左特異空間への写像である。
\(A=\sum_j\sigma_j\ket{w_j}\bra{v_j}\) に \(P(x)=x^2\) を適用する。奇 SVT と同じ形 \(\sum_j\sigma_j^2\ket{w_j}\bra{v_j}\) と書いてよいか。理由を述べよ。
一般にはそう書かない。\(P(x)=x^2\) は偶多項式なので、代表的な出力は右特異空間上の
\[ \sum_j\sigma_j^2\ket{v_j}\bra{v_j}=A^\dagger A \]または左特異空間上の
\[ \sum_j\sigma_j^2\ket{w_j}\bra{w_j}=AA^\dagger \]として現れる。矩形行列ではこれらの次元が \(A\) と異なるため、形の違いは本質的である。
\(P(x)=2x\) は QSP/QSVT でそのまま実装できるか。できないなら、どの条件に反するか。
そのままでは実装できない。ユニタリ行列の行列要素として実装される多項式は、少なくとも \([-1,1]\) 上で \(|P(x)|\le1\) を満たす必要がある。しかし \(P(1)=2\) なので条件に反する。スケールして \(P(x)=x\) にする、または有効領域を制限して別の実現可能多項式を設計する必要がある。
次数 \(d=5\) の標準的な実数 QSP 多項式 \(P\) は、どの偶奇を持つべきか。\(P(x)=x^4\) は候補になるか。
標準的な実数 QSP では \(P(-x)=(-1)^dP(x)\) が必要なので、\(d=5\) なら \(P\) は奇関数でなければならない。\(x^4\) は偶関数なので、次数 5 の奇パリティの主多項式としては不整合である。ただし次数を偶数として扱う、または別のブロック・補助構成を考えるなら話は変わる。
\(U\) が \(A/10\) を block-encode している。\(A\) の固有値または特異値 \(\sigma\) に対して \(e^{-it\sigma}\) を実装したい。QSVT の信号 \(x\) 上ではどの関数を近似するか。
信号は \(x=\sigma/10\) であるから、\(\sigma=10x\)。したがって QSVT の多項式は
\[ P(x)\approx e^{-it(10x)}=e^{-i(10t)x} \]を近似する。Hamiltonian simulation の文脈では \(\tau=\alpha t=10t\) が有効時間として現れる。
QSVT 回路が \(U\) または \(U^\dagger\) を合計 \(d\) 回使う。各 \(U\) の実装誤差が演算子ノルムで高々 \(\eta\) なら、粗くどの程度の誤差を見込むべきか。
最も単純な telescoping bound では、各使用箇所の誤差が足し合わされるため \(O(d\eta)\) の寄与を見込む。したがって総誤差を \(\epsilon\) にしたいなら、入力実装誤差を少なくとも \(\eta=O(\epsilon/d)\) 程度に抑える設計が自然である。
\(P_3(a)=\sin(3\arcsin a)\) を \(a\) の多項式として展開せよ。
\(\theta=\arcsin a\) と置くと \(a=\sin\theta\)。三倍角公式より
\[ \sin 3\theta=3\sin\theta-4\sin^3\theta. \]したがって
\[ P_3(a)=3a-4a^3. \]これは次数 3 の奇多項式である。
\(T_3(x)\) を求め、\(|T_3(x)|\le1\) が \([-1,1]\) 上で成り立つ理由を述べよ。
\(x=\cos\theta\) と置くと \(T_3(x)=\cos(3\theta)\)。三倍角公式より
\[ T_3(x)=4x^3-3x. \]\(x\in[-1,1]\) なら \(x=\cos\theta\) と書けるので、\(|T_3(x)|=|\cos(3\theta)|\le1\)。
QSP の 2×2 ブロックで、ある行列要素を \(P(x)\) にしたい。なぜ補多項式 \(Q(x)\) の存在が問題になるのか。
全体は各 \(x\in[-1,1]\) でユニタリ行列でなければならない。典型的な形では
\[ U_\Phi(x)= \begin{pmatrix} P(x) & iQ(x)\sqrt{1-x^2}\\ iQ^*(x)\sqrt{1-x^2} & P^*(x) \end{pmatrix} \]のように書かれ、ユニタリ性は概念的に
\[ |P(x)|^2+(1-x^2)|Q(x)|^2=1 \]を要求する。したがって \(|P|\le1\) だけでなく、その不足分を多項式 \(Q\) で埋められることが必要になる。
\(P(x)=x\) に対し、\(|P(x)|^2+(1-x^2)|Q(x)|^2=1\) を満たす簡単な \(Q\) を求めよ。
\(Q(x)=1\) とすれば
\[ |P(x)|^2+(1-x^2)|Q(x)|^2 =x^2+(1-x^2)=1. \]これは信号ユニタリそのものが \(x\) を行列要素として含むことに対応する。
\(e^{-itx}=\cos(tx)-i\sin(tx)\) を QSP で扱うとき、実部と虚部の偶奇はどうなるか。
\(\cos(tx)\) は \(x\) の偶関数、\(\sin(tx)\) は \(x\) の奇関数である。したがって実部は偶多項式列、虚部は奇多項式列で近似するのが自然である。実際の QSP/QSVT convention では複素多項式としてまとめる場合もあるが、偶奇構造は回路長とブロックの読み方に影響する。
QSP における主多項式 \(P(x)\) が \([-1,1]\) 上で \(|P(x)|\le1\) を満たすべき理由を、ユニタリ行列の観点から説明せよ。
各 \(x\) に対して QSP sequence は 2×2 ユニタリ行列 \(U_\Phi(x)\) を与える。ユニタリ行列の任意の行列要素の絶対値は 1 以下である。\(P(x)\) はその行列要素として実現されるため、必ず \(|P(x)|\le1\) でなければならない。
文献やソフトウェアで \(W_x\) convention と \(W_z\) convention が異なると、位相列 \(\Phi\) は同じまま使えるか。注意点を述べよ。
一般には同じまま使えない。信号ユニタリを \(X\)-rotation と見るか \(Z\)-rotation と見るか、位相回転をどちらの軸に置くか、位相列を左から読むか右から読むかで、同じ多項式を実現する位相列の表記が変わる。実装時には、位相合成器が採用する convention と、回路ライブラリが採用する convention を一致させる必要がある。
QSVT で SVD の各特異値 \(\sigma_j\) が QSP の 1 変数信号 \(x\) として見える理由を説明せよ。
\(A=\widetilde{\Pi}U\Pi\) とし、\(A\ket{v_j}=\sigma_j\ket{w_j}\) とする。ユニタリ性により、\(\ket{v_j}\) から \(U\) で出た状態は \(\widetilde{\Pi}\) 成分 \(\sigma_j\ket{w_j}\) と直交補空間成分に分かれる。適切な補ベクトルを取ると、\(\ket{v_j}\) とその補方向、または \(\ket{w_j}\) と補方向が作る 2 次元空間上で \(U\) と射影反射が閉じた 2×2 信号ブロックを作る。そこに QSP が作用し、\(x=\sigma_j\) の多項式応答を作る。
QSVT 定理の内容を、厳密な定数や convention を省いて、入力・条件・出力・コストの 4 点で述べよ。
\(P\) が奇多項式で、\(A=\sum_j\sigma_j\ket{w_j}\bra{v_j}\) のとき、代表的な出力ブロックを書け。
代表的には
\[ \widetilde{\Pi}U_\Phi\Pi = \sum_jP(\sigma_j)\ket{w_j}\bra{v_j} \]の形で出る。これは \(A\) と同じく右特異空間から左特異空間への写像である。
\(P(x)=x^2\) に対応する右特異空間上の出力を \(A^\dagger A\) と比較せよ。
SVD から
\[ A^\dagger A = \sum_j\sigma_j^2\ket{v_j}\bra{v_j}. \]偶 QSVT で右特異空間側のブロックを読むと、まさに \(\sum_jP(\sigma_j)\ket{v_j}\bra{v_j}\) であり、\(P(x)=x^2\) なら \(A^\dagger A\) になる。
\(A=H=H^\dagger\) で \(\|H\|\le1\) のとき、QSVT はどのように固有値変換として見えるか。
エルミート行列では特異値だけでなく符号付き固有値を扱う構成が可能である。固有分解 \(H=\sum_j\lambda_j\ket{u_j}\bra{u_j}\) に対し、適切な QSVT/QSP 構成で
\[ P(H)=\sum_jP(\lambda_j)\ket{u_j}\bra{u_j} \]を block-encode する。Hamiltonian simulation の \(P(x)\approx e^{-itx}\) はこの代表例である。
\(H_A=\begin{pmatrix}0&A\\A^\dagger&0\end{pmatrix}\) の非ゼロ固有値が \(\pm\sigma_j(A)\) であることを示せ。
\(A\ket{v_j}=\sigma_j\ket{w_j}\), \(A^\dagger\ket{w_j}=\sigma_j\ket{v_j}\) とする。このとき
\[ H_A\frac{1}{\sqrt2}\begin{pmatrix}\ket{w_j}\\ \ket{v_j}\end{pmatrix} = \sigma_j\frac{1}{\sqrt2}\begin{pmatrix}\ket{w_j}\\ \ket{v_j}\end{pmatrix}, \] \[ H_A\frac{1}{\sqrt2}\begin{pmatrix}\ket{w_j}\\ -\ket{v_j}\end{pmatrix} = -\sigma_j\frac{1}{\sqrt2}\begin{pmatrix}\ket{w_j}\\ -\ket{v_j}\end{pmatrix}. \]したがって非ゼロ固有値は \(\pm\sigma_j\) である。
次数 \(d=101\) の QSVT 多項式を使う。\(U,U^\dagger\) へのクエリ回数は概ねどの程度か。
convention により \(d\), \(d+1\), または同程度の差はあるが、基本的には \(O(d)\) 回である。\(d=101\) なら約 100 回程度の \(U\) または \(U^\dagger\) の使用を見込む。射影位相回転も同程度の回数必要である。
次数 \(d\) の QSP sequence では、位相パラメータは典型的に何個あるか。
典型的には \(\Phi=(\phi_0,\phi_1,\dots,\phi_d)\) の \(d+1\) 個である。文献や実装 convention により端の位相を吸収したり対称性を使ったりする場合があるが、基本スケールは次数に線形である。
\(A\) が \(m\times n\) 行列である。奇 SVT と偶 SVT の代表的な出力次元を述べよ。
奇 SVT の代表形 \(\sum_jP(\sigma_j)\ket{w_j}\bra{v_j}\) は \(m\times n\) で、\(A\) と同じ形である。偶 SVT は右特異空間側なら \(n\times n\)、左特異空間側なら \(m\times m\) の演算として現れる。
\(1/x\) や \(\operatorname{sgn}(x)\) を QSVT で使うとき、なぜ \(x=0\) 近傍のギャップを仮定するのか。
\(1/x\) は \(x=0\) で発散し、\(\operatorname{sgn}(x)\) は \(x=0\) で不連続である。有限次数多項式は連続かつ有界なので、これらをゼロ近傍を含む区間全体で一様に高精度近似することはできない。したがって \(|x|\ge\delta\) や \(x\in[1/\kappa,1]\) のような有効領域を設定する。
初期成功振幅 \(a=0.2\) に対し、\(P_3(a)=3a-4a^3\) を計算せよ。成功確率はどう変わるか。
初期成功確率は \(0.2^2=0.04\)。増幅後は約 \(0.568^2\approx0.323\)。1 回の Grover 型増幅で大きく増える。
\(a=0.8\) に対して \(P_3(a)=3a-4a^3\) を計算せよ。この結果から何が分かるか。
成功振幅は \(0.8\) から \(0.352\) に下がる。これは振幅増幅に過回転があることを示す。初期振幅が未知または既に大きい場合は、固定点型や適応的な手法が必要になる。
固定点振幅増幅は、標準 Grover 反復のどの問題を解決するために使われるか。
標準 Grover 反復は回転角を正確に知らないと過回転により成功確率が下がる。固定点振幅増幅は、ある閾値以上の成功振幅を単調に高成功確率へ押し上げ、過回転を避けることを目指す。QSVT では、適切な Chebyshev 型・フィルタ型多項式の設計問題として理解できる。
\(\sigma\in[1/\kappa,1]\) で \(1/\sigma\) を使いたい。QSVT でなぜ \(P(\sigma)\approx 1/(\kappa\sigma)\) のようにスケールするのか。
\(1/\sigma\) は \(\sigma=1/\kappa\) で \(\kappa\) になり、\(\kappa>1\) なら \(|P|\le1\) 条件に反する。そこで最大値が 1 になるように \(1/\kappa\) を掛け、
\[ P(\sigma)\approx \frac{1}{\kappa\sigma} \]を実装する。このスケール係数は出力振幅や成功確率に現れる。
\(\kappa=10\)、\(\sigma=(1,0.5,0.1)\) に対して \(P(\sigma)=1/(10\sigma)\) を計算せよ。
最小許容特異値 \(1/\kappa=0.1\) で出力が 1 になる。これより小さい特異値に同じ式を適用すると 1 を超えてしまう。
疑似逆 \(A^+\) を QSVT で実装するとき、小さい特異値をなぜ切り捨てることが多いか。
疑似逆は \(\sigma_j^{-1}\) を掛けるため、小さい特異値ほど出力が大きくなる。ゼロに近い特異値をそのまま反転すると、近似次数、スケール係数、成功確率、ノイズ感度が悪化する。そこで \(\sigma_j\ge1/\kappa\) の範囲だけで逆数を近似し、それ以下をフィルタで抑制する。
\(e^{-itx}\) を Chebyshev 多項式で近似することが Hamiltonian simulation に有用な理由を述べよ。
\(\|H\|\le1\) のエルミート \(H\) の固有値は \(x\in[-1,1]\) に入る。Chebyshev 多項式 \(T_k(x)\) はこの区間上で安定で、\(e^{-itx}\) は Jacobi-Anger 展開
\[ e^{-itx}=J_0(t)+2\sum_{k\ge1}(-i)^kJ_k(t)T_k(x) \]を持つ。したがって有限次数で打ち切った多項式を QSP/QSVT で固有値変換として実装できる。
しきい値 \(\tau\) で \(\sigma\ge\tau\) を残し \(\sigma<\tau\) を消すフィルタを多項式で近似する。なぜ遷移幅 \(\Delta\) を許すのか。
理想的な step function は不連続であり、有限次数多項式で区間上に一様近似するには困難がある。そこで \(\sigma\le\tau-\Delta\) では 0、\(\sigma\ge\tau+\Delta\) では 1 に近づけ、その間の遷移領域では誤差を許す。次数は典型的に \(1/\Delta\) に依存して大きくなる。
主成分回帰で使いたい特異値関数の概形を書け。
大きい特異値には逆数をかけ、小さい特異値は捨てるので、概形は
\[ f(\sigma)\approx \begin{cases} 1/\sigma,&\sigma\ge\tau,\\ 0,&\sigma\le\tau-\Delta. \end{cases} \]QSVT では有界性のため \(c/\sigma\) の形にスケールし、ギャップ領域を設けて多項式近似する。
\(A=\sum_j\sigma_j\ket{w_j}\bra{v_j}\) の極分解 \(A=Q|A|\) における \(Q\) を特異値変換として表せ。
フルランクまたはギャップ付きの場合、部分等長成分は
\[ Q=\sum_j\ket{w_j}\bra{v_j}. \]これは奇 SVT の形で、\(\sigma_j\) を \(1\) に写す \(P(\sigma)\approx1\) を \(\sigma\ge\delta\) 上で実装することに対応する。ゼロ特異値近傍では不連続性があるためギャップが必要である。
エルミート \(H\) の正固有空間への射影を、\(\operatorname{sgn}(H)\) を用いて表せ。
ゼロ固有値がない、またはギャップがあるとすると、正固有空間への射影は
\[ \Pi_+ = \frac{I+\operatorname{sgn}(H)}{2}. \]QSVT で \(\operatorname{sgn}(H)\) を近似できれば、この線形結合により正固有空間フィルタを得られる。
\(e^{-\beta H/2}\) を QSVT で block として実装するとき、なぜ係数 \(c\) を掛けて \(c e^{-\beta H/2}\) とすることがあるか。
QSVT の主多項式は \([-1,1]\) 上で絶対値 1 以下である必要がある。\(e^{-\beta x/2}\) は \(x\) の範囲によって 1 を超える可能性があるため、全領域で \(|c e^{-\beta x/2}|\le1\) となるように \(c\) を選ぶ。係数 \(c\) は出力ブロックの成功振幅や正規化に影響する。
sign や step のような急峻な関数の近似で、ギャップ \(\delta\) が小さくなると次数はどうなるか。直感的に説明せよ。
ギャップが小さいほど、関数は狭い領域で急激に変化しなければならない。有限次数多項式は変化の速さに限界があるため、急峻な遷移を作るには高い次数が必要になる。典型的な見積もりでは \(1/\delta\) に比例する因子が現れる。
有限次数多項式で step function を \([-1,1]\) 全体に一様誤差 \(\epsilon<1/2\) で近似できるか。
できない。有限次数多項式は連続関数であるが、step function は不連続である。不連続点を含む区間全体で一様に \(\epsilon<1/2\) 近似しようとすると、左右極限の差を連続関数が同時に満たせない。したがって遷移領域を除外する必要がある。
数値的に位相列 \(\Phi\) を得た後、実装前に何を検証すべきか。
少なくとも次を検証する。
対称な位相列を使う QSP 位相合成にはどのような利点があるか。
対称位相は探索空間を減らし、得られる多項式の構造を制御しやすく、数値最適化を安定化することがある。また実装や検証で、位相数の実効自由度が減るため扱いやすい。実際のソフトウェアでは対称 QSP を利用した高速・安定な位相合成手法がよく用いられる。
QSVT で \(c f(A)\) の block-encoding を得た。\(c\ll1\) のとき、なぜ後段で振幅増幅を検討するのか。
block として得られた作用を postselection で取り出す場合、振幅スケール \(c\) は成功確率 \(c^2\) 程度に反映されることが多い。\(c\ll1\) だと成功確率が小さいため、振幅増幅により成功確率を上げることを検討する。ただし振幅増幅自体にも追加クエリと誤差が必要である。
線形システム \(Ax=b\) を QSVT で解く設計の主要ステップを順に挙げよ。
\(\|H\|\le\alpha\) の Hamiltonian simulation を QSVT/QSP で設計する主要ステップを述べよ。
非エルミート行列 \(A\) について、通常の行列多項式 \(P(A)\) と singular value transformation \(P^{(\mathrm{SV})}(A)\) が一般に異なる理由を説明せよ。
\(P(A)\) は \(A\) の積 \(A^2,A^3,\dots\) によって定義され、固有構造や非正規性に依存する。一方、奇 SVT の代表形は
\[ P^{(\mathrm{SV})}(A)=\sum_jP(\sigma_j)\ket{w_j}\bra{v_j} \]であり、SVD の特異値だけを変換し、左右特異ベクトルを保つ。非エルミート・非正規行列では固有値分解と SVD は一致しないため、両者は別物である。エルミート正定値など特別な場合には関係が単純になる。
| 迷い | 確認する式 | 見るべき問題 |
|---|---|---|
| QSVT が \(P(A)\) なのか分からない | \(P^{SV}(A)=\sum_jP(\sigma_j)\ket{w_j}\bra{v_j}\) | P03, P45 |
| 偶多項式の出力が分からない | \(A^\dagger A\), \(AA^\dagger\) | P04, P19, P24 |
| 逆数でスケールが出る理由 | \(P(\sigma)\approx1/(\kappa\sigma)\) | P29, P30, P31 |
| Hamiltonian simulation の多項式が分からない | \(e^{-itx}\) の Chebyshev 展開 | P32, P44 |
| 位相合成の実装が不安 | convention と \(P_\Phi(x)\) の検証 | P15, P40, P41 |
本レポートは Qubitization を既習と仮定し、QSVT/QSP の構造を理解するための補助教材として書いた。定理の厳密な証明、位相合成アルゴリズム、定数因子まで含む資源解析は原論文を参照すること。
d3-graphviz は DOT 言語で書かれたグラフをブラウザ内で SVG として描画するライブラリであり、Graphviz の WebAssembly 実装を利用する。