Optimal Quantum Speedups for Repeatedly Nested Expectation Estimation

Motivation

• Known: 고전적으로 Syed & Wang (2023)은 randomized Multilevel Monte Carlo (rMLMC) 프레임워크를 이용해 RNE를 $O(\varepsilon^{-2})$ 샘플 복잡도로 추정하는 알고리즘을 제시했으며, 이는 classical Monte Carlo 추정량 중 최적이다. 또한 Blanchet et al. (2026)은 단일 nested expectation에 대해 $\tilde O(\varepsilon^{-1})$ quantum 알고리즘을 개발했다.
• Gap: 단일 nested expectation을 넘어 optimal stopping을 포함한 다중(repeated) nesting 구조로 quantum speedup을 확장하는 것은 미해결이었으며, classical rMLMC를 그대로 quantize하면 rMLMC의 random truncation level로 인한 variable-time 문제가 amplitude amplification과 상충하여 의도한 quadratic speedup을 얻을 수 없다는 기술적 난점이 존재했다.
• Why: RNE는 optimal stopping, credit valuation adjustment risk estimation, probabilistic programs 추론 등 통계·순차적 의사결정·수리금융 전반에 걸쳐 광범위하게 나타나는 근본적인 계산 문제이므로, 이에 대한 최적의 quantum speedup 확립은 이론적으로나 응용적으로나 중요한 의미를 가진다.
• Approach: 고전 rMLMC 알고리즘을 직접 quantize하는 대신, random truncation level을 제어된 deterministic schedule로 대체하는 새로운 derandomized MLMC 알고리즘을 먼저 개발한 뒤, 이를 표준 quantum mean-estimation subroutine(QAMC)으로 quantize하는 2단계 전략을 취한다.

Achievement

1. Classical derandomization: rMLMC의 random level을 truncated geometric distribution으로 대체해도(Proposition 2.2) 동일한 보장이 유지됨을 보이고, 나아가 자연스러운 deterministic level scheduling을 사용하는 새로운 classical MLMC 알고리즘(Theorem 1.4)을 제시하여 Syed & Wang (2023)의 미해결 질문에 답한다.
2. Naive quantization의 한계 규명: 고전 알고리즘을 그대로 quantize하면 variable-time 문제로 인해 샘플 복잡도가 $\Omega(\varepsilon^{-D+d-1}\log^{D-d+1}(\varepsilon^{-1}))$로 horizon $D$에 지수적으로 나빠짐을 Proposition 1.5로 증명한다.
3. 최적 quantum 알고리즘: derandomized MLMC를 QAMC로 quantize하여 $O(\varepsilon^{-1}\log^{3(D-d)+1}(\varepsilon^{-1}))$의 샘플 복잡도를 갖는 quantum MLMC 알고리즘(Theorem 1.6)을 제시하며, 이는 standard quantum lower bound에 의해 log-factor를 제외하고 최적임을 보인다.
4. 오차 척도 개선: classical 결과의 $L_{p_d}$-error ($p_d\in(1,2)$) 대신 RMSE(L2-error)를 직접 통제함으로써, 복잡도의 $\varepsilon^{-O(\delta)}$ 항을 명시적인 poly-logarithmic factor로 대체하는 개선을 이룬다.

How

• LBL (last-component bounded Lipschitz) 조건 하에서 recursive Algorithm 1 (Syed & Wang 2023의 rMLMC)을 기반으로 함
• Step 1: random level $N \sim Pd$를 $B_d = \Theta(\log(\varepsilon^{-1}))$에서 truncate한 geometric distribution으로 대체(Proposition 2.2), unbiased·cost·moment 보장이 유지됨을 증명
• Step 2: truncated 버전을 다리 삼아 완전히 deterministic한 level scheduling으로 대체하는 classical MLMC 알고리즘 구성(Theorem 1.4)
• Step 3: Montanaro (2015), Kothari & O'Donnell (2023)의 quantum mean estimation subroutine (Grover's algorithm 기반)을 사용해 QAMC(Quantum-Accelerated Monte Carlo)를 정의
• Step 4: naive quantization(고전 rMLMC를 그대로 quantize)의 branch별 최대 cost 문제를 분석하여 실패 원인을 규명(Proposition 1.5)
• Step 5: derandomized deterministic-schedule MLMC 알고리즘에 QAMC를 재귀적으로 적용(quantum-inside-quantum)하여 horizon마다 log-factor만 누적되는 quantum MLMC 알고리즘 구성(Theorem 1.6)

Originality

• 단일 nested expectation에 대한 기존 quantum speedup(Blanchet et al., 2026)을 임의의 constant horizon을 갖는 repeatedly nested expectation으로 확장한 최초의 결과
• classical rMLMC의 variable-time 특성이 quantum amplitude amplification과 근본적으로 충돌한다는 문제를 명시적으로 규명하고, 이를 우회하기 위해 직접 quantize하는 대신 classical 알고리즘 자체를 derandomize하는 새로운 전략(quantum quantization을 위한 classical algorithm 재설계)을 제시
• Syed & Wang (2023)이 남긴 deterministic level scheduling에 대한 공개 질문을 classical 세팅에서도 해결
• An et al. (2021)의 quantum MLMC(단일 telescoping 구조)나 Doriguello et al. (2022)의 quantum LSM(파라메트릭 근사 오차 포함)과 달리, non-parametric이며 일반적인 RNE 문제(optimal stopping을 특수 케이스로 포함)에 적용 가능한 quantum 알고리즘 제시

Limitation & Further Study

• horizon $D$를 상수로 취급하여 점근 분석을 수행하므로, $D$에 대한 의존성(로그 인자의 지수 $3(D-d)+1$)이 실제로는 $D$가 커질수록 지수적으로 증가하여 큰 horizon에서는 실용성이 제한될 수 있음
• LBL 가정(Lipschitz 조건, $L_2$ 적분가능성)에 의존하므로 이 조건이 성립하지 않는 더 일반적인 RNE 문제로의 확장이 후속 과제로 남음
• 이론적 샘플 복잡도 분석에 초점을 맞추고 있어 실제 quantum hardware 상에서의 구현 및 실험적 검증(회로 깊이, decoherence 등 실제 제약)은 다루지 않음
• log-factor 상수들(특히 exponent에 나타나는 $D-d$에 대한 의존성)을 더 정교하게 줄이는 것이 향후 개선 방향으로 언급됨

Evaluation

총평: RNE 추정에 대한 quantum speedup을 단일 nesting에서 임의의 constant horizon으로 확장하고 그 최적성을 이론적으로 확립한 견고한 이론 논문으로, variable-time 알고리즘의 quantization 문제를 derandomization을 통해 해결하는 기법적 통찰이 독창적이다.