2025-11-10T02:50:58.421797

Quantum algorithms for solving a drift-diffusion equation: A complexity analysis

Devereux, Datta

We present four quantum algorithms for solving a multidimensional drift-diffusion equation. They rely on a quantum linear system solver, a quantum Hamiltonian simulation, a quantum random walk, and the quantum Fourier transform. We compare the complexities of these methods to their classical counterparts, finding that diagonalization via the quantum Fourier transform offers a quantum computational advantage for solving linear partial differential equations at a fixed final time. We employ a multidimensional amplitude estimation process to extract the full probability distribution from the quantum computer.

academic

ドリフト拡散方程式を解くための量子アルゴリズム：複雑性分析

基本情報

論文ID: 2505.21221
タイトル: Quantum algorithms for solving a drift-diffusion equation: A complexity analysis
著者: Ellen Devereux (ウォーリック大学 & Fujitsu UK Ltd)、Animesh Datta (ウォーリック大学)
分類: quant-ph
発表日時: 2025年10月16日 (arXiv プレプリント)
論文リンク: https://arxiv.org/abs/2505.21221

概要

本論文は、多次元ドリフト拡散方程式を解くための4つの量子アルゴリズムを提案している。これらは量子線形系ソルバー、量子ハミルトニアンシミュレーション、量子ランダムウォーク、および量子フーリエ変換に基づいている。複雑性分析を通じてこれらの方法と古典的対応方法を比較した結果、量子フーリエ変換に基づく対角化法が、固定最終時間における線形偏微分方程式の解法において量子計算優位性を有することが明らかになった。本論文では、多次元振幅推定プロセスを採用して、量子コンピュータから完全な確率分布を抽出している。

研究背景と動機

問題定義

ドリフト拡散方程式(DDE)は重要な偏微分方程式のクラスであり、具体的な形式は以下の通りである：

$\frac{\partial p(x,t)}{\partial t} = \sum_{i=1}^d \left[a\frac{\partial}{\partial x_i}[p(x,t)] + D\frac{\partial^2}{\partial x_i^2}[p(x,t)]\right]$

ここで $x = \{x_1, ..., x_d\} \in \mathbb{R}^d$ は $d$ 次元ベクトル、 $a$ と $D$ はそれぞれ正のドリフト係数と拡散係数である。

研究の重要性

理論的意義：DDEはFokker-Planck方程式として粒子速度を記述し、Black-Scholes方程式およびNavier-Stokes方程式と密接に関連している
実用的応用：金融リスク建模、風力発電出力予測など、複数の産業における意思決定支援に使用されている
計算上の課題：従来の数値手法は大規模で複雑な問題領域の離散化を必要とし、膨大なメモリと計算資源を消費する

既存手法の限界

古典的なPDE求解法には以下が含まれる：

共役勾配法などの線形方程式ソルバー
ランダムウォーク法
高速フーリエ変換に基づく対角化法

これらの手法は高次元問題の処理において、計算複雑性が次元に対して指数関数的に増加するという課題に直面している。

核心的貢献

4つの量子アルゴリズムの提案：量子線形系ソルバー、量子時間発展、量子ランダムウォーク、および量子フーリエ変換に基づくもの
複雑性理論分析：詳細な時間複雑性分析を提供し、量子優位性の存在条件を証明
多次元振幅推定法：PDE求解に多次元振幅推定を初めて適用し、完全な確率分布の抽出を実現
実用性検証：金融建模の例を通じて、方法の商業的応用価値を検証

方法の詳細

タスク定義

DDE の近似解 $\tilde{\tilde{p}}(x,t)$ を求め、 $t=T$ 時刻において以下を満たすこと： $||\tilde{\tilde{p}}(x,t) - p(x,t)||_\infty \leq \epsilon$ ここで $\epsilon \in (0,1)$ は与えられた誤差、 $x \in [-L,L]^d$ である。

離散化戦略

前進時間・中心空間差分スキームを採用：

空間ステップサイズ： $\Delta x = 2L/n_x$
時間ステップサイズ： $\Delta t = T/n_t$
安定性条件： $\Delta t \leq \Delta x^2/(2dD)$

4つの量子アルゴリズム

1. 量子線形系ソルバー

基本的考え方：離散化されたPDEを線形方程式組 $A\tilde{p} = b$ に変換
時間複雑性： $\tilde{O}\left(\frac{d^5T^2\zeta(aL+D)^2}{\epsilon_q\epsilon_c}\right)$
適用条件：条件数が有界である必要がある( $\kappa_L = 5$ （ $D\Delta t/\Delta x^2 \leq 1/5$ かつ $a/D < 2\sqrt{10}$ の場合）

2. 量子時間発展

基本的考え方：ハミルトニアンシミュレーションとユニタリ演算子の線形結合を使用して時間発展を実現
時間複雑性： $\tilde{O}\left(\frac{d^{d/2+3}T^{d/2+2}\zeta^{d/4+1}L^2(aL+D)^{d/2}}{\epsilon_q\epsilon_c^{d/4+2}}\right)$
特徴：量子時間発展プロセスを直接シミュレート

3. 量子ランダムウォーク

基本的考え方：DDEの確率的性質を利用し、量子ランダムウォークによってシミュレート
時間複雑性： $\tilde{O}\left(\frac{d^{(d+7)/2}T^{d/2+1}\zeta^{d/4+1/2}(aL+D)^{d/2+1}}{\epsilon_q\epsilon_c^{d/4+1/2}}\right)$
利点：非線形確率PDE への拡張が可能

4. 量子フーリエ変換対角化（最適方法）

基本的考え方：QFTを使用して循環行列を対角化し、 $L^{n_t}$ を直接計算
時間複雑性： $\tilde{O}\left(\frac{d^{(d/2+2)}T^{d/2}\zeta^{d/4}(aL+D)^{d/2}}{\epsilon_q\epsilon_c^{d/4}}\right)$
主要な利点：量子重ね合わせ状態内のすべての固有値を同時に適用

多次元振幅推定

単次元振幅推定を多次元の場合に革新的に拡張：

サンプリングにより確率≥ $\epsilon_q$ の座標を識別
関数 $f(x) = \langle x,p \rangle$ を構築
位相推定を使用して確率分布を抽出
複雑性： $O\left(\frac{\log(n_x^d/\delta)\log(1/\epsilon_q)}{\epsilon_q}\right)$

実験設定

パラメータ設定

金融建模におけるOrnstein-Uhlenbeck過程に基づく：

$T = 5000$ 日、 $L = 10$ ドル
$a = 0.2366$ 、 $D = 0.2455$
$d = 3$ 次元、 $\zeta = 1$ ドル $^{-4}$

評価指標

時間複雑性の比較
空間複雑性の分析
量子優位性の条件

実験結果

主要な結果

量子優位性の条件： $\epsilon_q \geq \tilde{O}\left(\frac{\epsilon_c^{d/4}d^D d^{d/2}}{\zeta^{d/4}L^d(aL+D)^{d/2}}\right)$ の場合、量子対角化法は古典的方法より優れている。

複雑性比較表

方法	古典複雑性	量子複雑性	量子優位性
線形方程式	$4.85 \times 10^{22}/\epsilon_c^3$	$4.14 \times 10^{10}/(\epsilon_c\epsilon_q)$	✓
時間ステップ進行	$1.24 \times 10^{18}/\epsilon_c^{2.5}$	$5.23 \times 10^{17}/(\epsilon_c^{2.75}\epsilon_q)$	×
ランダムウォーク	$1.24 \times 10^{18}/\epsilon_c^{2.5}$	$4.73 \times 10^{12}/(\epsilon_c^{1.25}\epsilon_q)$	✓
対角化	$8.07 \times 10^{11}/\epsilon_c^{1.5}$	$6.98 \times 10^7/(\epsilon_c^{0.75}\epsilon_q)$	✓