NISQ時代のQuantum Utility Algorithm: 「QSCI (SQD)」
※本記事の内容は筆者個人の見解です。
はじめに
こんにちは、QunaSys Inc.で研究員をしているNaoと申します。
普段は量子アルゴリズムの研究開発ならびに、場の量子論におけるリサージェンス理論などの研究もしています。
以前、計測自動制御学会（SICE）の学会誌「計測と制御」にて、『量子化学計算における量子コンピュータの進展』 [1] という解説記事を寄稿させていただきました。
そこでも触れたのですが、現在NISQ（Noisy Intermediate-Scale Quantum）デバイスの活用法として、QSCI (Quantum-Selected Configuration Interaction) という手法が注目を集めています。
今回は、このQSCI（IBM等はSQDと呼称）について、一般論としての数理的枠組みから解説し、最近のIBMによる大規模実験 [2] の話も交えつつ、その応用と課題点などについて解説したいと思います。
1. QSCI (SQD) の一般的枠組み
QSCIは、2023年にQunaSysのメンバーらが提案した手法 [3] です。
この手法の本質は、量子化学に限らず、 「巨大な次元を持つエルミート行列の固有値問題を、量子・古典ハイブリッドで近似的に解く一般的手法」 として定式化できます。
アルゴリズムの核心：サンプリングによる部分空間の選択
$N=2^n$次元のヒルベルト空間において、解きたいハミルトニアン $\hat{H}$ の基底状態 $|\Psi_{GS}\rangle$ を考えます。
一般に、この基底状態は空間全体に一様に広がっているわけではなく、いくつかの特定の基底に対して局在している（重みが集中している）ことが多いです。
QSCIでは、量子コンピュータをこの「重みの大きい重要な基底」を見つけ出すサンプラーとして利用します。
- 状態準備: 量子コンピュータ上で、 求めたい基底状態に近い近似状態 $|\Psi_{in}\rangle$ を用意する。
-
サンプリング: これを計算機基底で測定する。ある基底 $x$ が観測される確率は、その振幅の二乗に比例する。
$$P(x) = |\langle x | \Psi_{in} \rangle|^2$$ - 部分空間の構成: 出現頻度の高い $R (R\ll N)$ 個の基底を選び出し、それらによって張られる部分空間 $\mathcal{S}_R = { |x_1\rangle, \dots, |x_R\rangle }$ を定義する。
有効ハミルトニアンと古典対角化
選ばれた基底 $\mathcal{S}_R$ を用いて、元のハミルトニアン $\hat{H}$ をこの部分空間に射影した 有効ハミルトニアン $\hat{H}_{eff}$ を構成します。
具体的には、以下のような $R \times R$ 行列になります。
\hat{H}_{eff} =
\begin{pmatrix}
\langle x_1 | \hat{H} | x_1 \rangle & \langle x_1 | \hat{H} | x_2 \rangle & \cdots & \langle x_1 | \hat{H} | x_R \rangle \\
\langle x_2 | \hat{H} | x_1 \rangle & \langle x_2 | \hat{H} | x_2 \rangle & \cdots & \langle x_2 | \hat{H} | x_R \rangle \\
\vdots & \vdots & \ddots & \vdots \\
\langle x_R | \hat{H} | x_1 \rangle & \langle x_R | \hat{H} | x_2 \rangle & \cdots & \langle x_R | \hat{H} | x_R \rangle
\end{pmatrix}
あとは、この小さな行列 $\hat{H}_{eff}$ を古典的に対角化すれば、$\hat{H}$の近似的な最小固有値 $E_R$ が得られます。
またこの手法では、行列要素を古典的に厳密計算するため、ノイズが乗っても変分原理が厳密に成り立ちます [3]。
$$E_{exact} \le E_R$$
この手法を QSCI (Quantum-Selected Configuration Interaction)またはSQD (Sample-based Quantum Diagonalization)と呼びます。
2. なぜ量子化学でうまくいくのか？
さて、この手法は一般のエルミート行列に対して定義できますが、特に量子化学計算において大きな成果を上げています。
その理由は、量子化学特有の事情にあります。
第二量子化ハミルトニアンとHartree-Fock近似
量子化学において、ハミルトニアンは以下のように第二量子化による生成消滅演算子により記述されます。
$$
\hat{H} = \sum_{p,q} h_{pq} \hat{a}_p^\dagger \hat{a}_q + \frac{1}{2} \sum_{p,q,r,s} h_{pqrs} \hat{a}_p^\dagger \hat{a}_q^\dagger \hat{a}_r \hat{a}_s
$$
量子化学では、平均場近似であるHartree-Fock(HF)状態が、多くの場合において基底状態の良い近似（出発点）となります。Hartree-Fock状態は単一のスレーター行列式（計算機基底の一つ）で表されるため、真の基底状態はこの周辺の基底に重みが集中していることが物理的に保証されています [1]。したがって、解の候補として
$$
|\Psi_{in}\rangle=|HF\rangle+U(\theta)|HF_\perp\rangle
$$
のように$|HF\rangle$とそれに直交する基底 $|HF_\perp\rangle$ にansatz $U(\theta)$ を作用させたものを用意し、ある程度最適化をした後に非自明である$U(\theta)|HF_\perp\rangle$をsamplingで求めてQSCIを実行すれば良いことになります。
つまり、量子化学では 「解に近い状態を準備するためのヒント（Hartree-Fock状態など）」があらかじめ分かっている ため、QSCIのアプローチが極めて有効に機能するのです。
IBMによる大規模実証（SQD）
2024年、IBMと理研のグループは、この手法を用いて、[4Fe-4S]（鉄硫黄クラスター）などの複雑な分子計算を行いました [2]。
最大77量子ビットの実機とスパコン「富岳」を連携させたこの実験では、 「Configuration Recovery」 という、物理的対称性（粒子数保存則など）を利用してノイズ混じりのサンプリング結果を事後的に補正する技術を導入し、高精度な計算を実現しています [2]。
これをもって実用的な問題への量子コンピュータの応用: Quantum Utilityとしてこのアルゴリズムをpre-FTQC時代の今積極的に利用しようという姿勢を見せています。
3. 「状態準備」という本質的なボトルネック
しかし、ここで一度立ち止まって考えてみます。
QSCI (SQD) が機能するためには、 「サンプリングによって重要な基底を拾い上げられる程度には、解に近い状態 $|\Psi_{in}\rangle$」 を量子コンピュータ上に用意する必要があります。これは 状態準備の問題 と呼ばれ、QSCIだけでなくFTQCアルゴリズムである 量子位相推定 で固有値, 固有ベクトルを求める際にも全く同じ問題が生じます。
復習をすると、量子位相推定（QPE）とはあるエルミート演算子 $\hat{H}$ に対応するユニタリー演算子 $U = e^{i\hat{H}}$ およびその固有状態 $\ket{u_\lambda}$ が与えられたときに、$\hat{H}$ の固有値 $\lambda$ をユニタリー演算 $U_{\text{QPE}}$ を用いて計算するアルゴリズムです。
$$
U_{\text{QPE}} |u_\lambda\rangle |0\rangle_r = |u_\lambda\rangle |\lambda\rangle_r
$$
ここで$\ket{0}_r$ は固有値を格納するレジスタービットであり、$\ket{\lambda}_r$ は固有値 $\lambda$ の2進数表現（例：$\lambda=12$ に対して $\ket{1100}$）を基底エンコードした状態です。
また、QPEを用いて$\lambda$ を $n$ 桁の精度（$\lambda = \sum_{m=0}^{n} k_m 2^m$）で求めるとき、必要な計算量は $O(n^2)$ であり、古典的な固有値推定アルゴリズムの計算量 $O(2^n)$ と比較して指数的に早いアルゴリズムとして知られています。
上式はあらかじめ固有状態が与えられていなければ適用できないように見えますが、実際には任意の状態 $\ket{\psi}$ に対して適用することが可能です。これは、エルミート演算子の固有ベクトルの完全性により：
$$
\ket{\psi} = \sum_k \langle u_{\lambda_k} | \psi\rangle \ket{u_{\lambda_k}}
$$
と展開できるので，これに対してQPEを実行すれば
$$
U_{\text{QPE}} |\psi\rangle |0\rangle_r
= \sum_k \langle u_{\lambda_k} | \psi\rangle |u_{\lambda_k}\rangle |\lambda_k\rangle_r
$$
という重ね合わせ状態が得られるためです。したがって、レジスタービットを測定すれば各固有値 $\lambda_k$と固有状態$\ket{u_{\lambda_k}}$が確率 $|\langle u_{\lambda_k}|\psi\rangle|^2$ で得られることになります。
したがって、QSCIのセットアップと同じく、初期状態$|\psi\rangle$は解$\ket{u_\lambda}$そのものではなくとも、解に ほどほどに近い ( $|\langle u_{\lambda}|\psi\rangle|^2 \sim \frac{1}{4}$などでも十分)状態である必要があります。
NPとBQP
もし仮に、任意のハミルトニアンに対して、その基底状態に近い状態を多項式時間で準備できる万能な手法があるならば、それは世界を変えてしまいます。
例えば、離散最適化の問題の一つである 3-SAT はNP-completeとして有名ですが、この問題はイジングモデルのハミルトニアンの基底状態を求める問題にマッピングできてしまいます。したがって、このクラスの問題でも状態準備が可能であるとすれば、それは NP$\subseteq$BQPが成り立ってしまう ことを意味し、あらゆるクラスNPの問題が量子コンピュータで簡単に解けてしまうことになるからです。
（もし$|\langle u_{\lambda}|\psi\rangle|^2 \sim \frac{1}{4}$であれば、$25\%$の確率で正解で、$75\%$で解ではない状態が得られますが、得られた状態が解であるかどうかの検証はSAT式に代入すれば容易にできるため、高々数十回の試行で問題が解けます）
計算複雑性理論の観点から、BQP（量子計算で解けるクラス）が全てのNPを含むとは考えにくいです。（もちろんNP$\subseteq$BQPが絶対にありえないと主張しているわけではありませんが……）
したがって、「ほどほどに解に近い状態を用意する（状態準備）」ということ自体が、一般にはNP-completeレベルで難しいと言えます。
量子化学でQSCIが成功しているのは、あくまで「自然界の分子ハミルトニアン」が特殊な構造を持っており、Hartree-Fockなどの近似が良い出発点を与えてくれるからに他なりません。
逆に言えば、そうしたヒントがない一般の問題に対しては、QPEもQSCIも「状態準備の壁」に阻まれることになります。
4. 結論
QSCI (SQD) は、現在のNISQデバイスにおいて、量子と古典の役割分担を最適化した非常に現実的かつ強力なアプローチで、量子コンピュータを用いて有効的な基底を探し出し、古典計算で扱えるサイズの行列にし、対角化をする アルゴリズムです。特にポイントとして以下の点が挙げられます。
- なんらかのドメイン知識により状態準備を行う必要がある（Hartree-Fock, CCSDなど）。
- 量子コンピュータは有効な基底のサンプリングだけに使用し、現状のノイズのある実機では難しい高精度の基底状態探索には用いない（そこは信頼できる古典対角化で行う）
- 状態準備の問題はQPEでも存在し、一般にはそれ自体がNP-completeレベルで難しい。
参考文献
- [1] 居石直久, "量子化学計算における量子コンピュータの進展", 計測と制御 (SICE), No. 7, Vol. 64, 2025
- [2] J. Robledo-Moreno et al., "Chemistry Beyond the Scale of Exact Diagonalization on a Quantum-Centric Supercomputer", arXiv:2405.05068 (2024).
- [3] K. Kanno et al., "Quantum-Selected Configuration Interaction: classical diagonalization of Hamiltonians in subspaces selected by quantum computers", arXiv:2302.11320 (2023).