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 (University of Warwick & Fujitsu UK Ltd), Animesh Datta (University of Warwick)
분류: quant-ph
발표 시간: 2025년 10월 16일 (arXiv 프리프린트)
논문 링크: https://arxiv.org/abs/2505.21221

초록

본 논문은 다차원 드리프트-확산 방정식을 풀기 위한 네 가지 양자 알고리즘을 제안한다. 이들은 각각 양자 선형 시스템 솔버, 양자 해밀턴 시뮬레이션, 양자 무작위 보행, 양자 푸리에 변환을 기반으로 한다. 복잡도 분석을 통해 이러한 방법들을 고전적 대응 방법과 비교한 결과, 양자 푸리에 변환 기반의 대각화 방법이 고정된 최종 시간에서 선형 편미분방정식을 풀 때 양자 계산 우위를 갖는 것으로 나타났다. 본 논문은 다차원 진폭 추정 과정을 통해 양자 컴퓨터에서 완전한 확률 분포를 추출한다.

연구 배경 및 동기

문제 정의

드리프트-확산 방정식(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는 포커-플랑크 방정식으로서 입자 속도를 기술하며, 블랙-숄즈 방정식 및 나비에-스토크스 방정식과 밀접한 관련이 있다.
실제 응용: 금융 위험 모델링, 풍력 발전 전력 예측 등 다양한 산업에서 의사결정을 지원하는 데 사용된다.
계산 과제: 전통적 수치 방법은 크고 복잡한 문제 영역의 이산화를 필요로 하며, 막대한 메모리와 계산 자원을 소비한다.

기존 방법의 한계

편미분방정식을 푸는 고전적 방법들은 다음을 포함한다:

켤레 기울기법 등의 선형 방정식 솔버
무작위 보행 방법
고속 푸리에 변환 기반의 대각화 방법

이러한 방법들은 고차원 문제를 처리할 때 계산 복잡도가 차원에 따라 지수적으로 증가하는 문제에 직면한다.

핵심 기여

네 가지 양자 알고리즘 제안: 각각 양자 선형 시스템 솔버, 양자 시간 진화, 양자 무작위 보행, 양자 푸리에 변환을 기반으로 함
복잡도 이론 분석: 상세한 시간 복잡도 분석을 제공하고 양자 우위 존재 조건을 증명
다차원 진폭 추정 방법: 편미분방정식 풀이에 다차원 진폭 추정을 처음 적용하여 완전한 확률 분포 추출 실현
실용성 검증: 금융 모델링 사례를 통해 방법의 상업적 응용 가치 검증

방법 상세 설명

작업 정의

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)$

네 가지 양자 알고리즘

1. 양자 선형 시스템 솔버

기본 개념: 이산화된 편미분방정식을 선형 방정식 $A\tilde{p} = b$ 로 변환
시간 복잡도: $\tilde{O}\left(\frac{d^5T^2\zeta(aL+D)^2}{\epsilon_q\epsilon_c}\right)$
적용 조건: 조건수가 유계여야 함 ( $\kappa_L = 5$ when $D\Delta t/\Delta x^2 \leq 1/5$ and $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)$
장점: 비선형 무작위 편미분방정식으로 확장 가능

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)$

실험 설정

매개변수 설정

금융 모델링의 오른슈타인-울렌벡 과정을 기반으로 함:

$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)$	✓