Quantum Monte Carlo Estimation via Probabilistic Programming

Abstract

Monte Carlo methods are fundamental to finance, system verification, and scientific simulation, but converge slowly: achieving an additive error of є requires O(1/є2) samples. Quantum Amplitude Estimation (QAE) offers a quadratic speedup by encoding the target probabilistic model into a quantum circuit. However, constructing such a circuit demands low-level quantum expertise, and existing tools for this task all sacrifice at least one of generality, usability, or efficiency. To address these, we design QPPL (Quantum Probabilistic Programming Language), a simple imperative language, and a compiler that translates probabilistic programs into quantum circuits. The key insight is that the circuit construction amounts to specifying a probability distribution, precisely the task that probabilistic programming addresses. QPPL achieves generality by supporting joint distributions, conditional updates, dynamic probabilities, and real-valued expectations in a single language; usability by offering a sequential, imperative syntax with named variables and direct arithmetic that hides all quantum details; and efficiency by modularly compiling each construct into reversible circuit primitives, achieving scalable circuit synthesis. We prove that the compilation is semantics-preserving. On benchmarks spanning finance and probabilistic model checking, QPPL is the only tool that covers all benchmarks, while producing circuits with up to 8.8× fewer gates and 26× shallower depth than existing tools.