Quantum Monte Carlo Estimation via Probabilistic Programming
Monte Carlo methods are fundamental to finance, system verification, and scientific simulation, but converge slowly: achieving an additive error of $\epsilon$ requires $O(1/\epsilon^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 \emph{probabilistic programming} addresses. QPPL achieves \emph{generality} by supporting joint distributions, conditional updates, dynamic probabilities, and real-valued expectations in a single language; \emph{usability} by offering a sequential, imperative syntax with named variables and direct arithmetic that hides all quantum details; and \emph{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.
Tue 6 OctDisplayed time zone: Pacific Time (US & Canada) change
13:30 - 15:00 | Quantum ProgrammingOOPSLA at East Hall 2 Chair(s): Jens Palsberg University of California at Los Angeles | ||
13:30 18mTalk | Compiling Quantum Regular Language States OOPSLA Armando Bellante Max Planck Institute of Quantum Optics; Munich Center for Quantum Science and Technology, Reinis Irmejs Max Planck Institute of Quantum Optics; Munich Center for Quantum Science and Technology, Marta Florido-Llinàs Max Planck Institute of Quantum Optics; Munich Center for Quantum Science and Technology, María Cea Fernández Max Planck Institute of Quantum Optics; Munich Center for Quantum Science and Technology, Marianna Crupi Max Planck Institute of Quantum Optics; Munich Center for Quantum Science and Technology, Matthew Kiser TU Munich; IQM Quantum Computers, J. Ignacio Cirac Max Planck Institute of Quantum Optics; Munich Center for Quantum Science and Technology DOI | ||
13:48 18mTalk | Quantum Monte Carlo Estimation via Probabilistic Programming OOPSLA Seungmin Jeon KAIST, Jaeho choi HyperAccel, Jonguk Jeon KAIST, Kanguk Lee KAIST, Kyeongmin Cho Rebellions, Sukyoung Ryu KAIST, Jeehoon Kang FuriosaAI DOI | ||
14:06 18mTalk | Synthesis of Compact and Expressive Quantum-Circuit Optimizations OOPSLA DOI Pre-print | ||
14:24 18mTalk | Granthi: Higher-Order Quantum Programming via Unitary Wiring OOPSLA DOI | ||
14:42 18mTalk | Verifying Repeat-until-Success Protocols using Automata OOPSLA Jyun-Ao Lin National Taipei University of Technology, Yu-Fang Chen Academia Sinica, Jakub Havlík Brno University of Technology, Ondřej Lengál Brno University of Technology, Fang-Yi Lo Academia Sinica, Wei-Lun Tsai National Taiwan University, You-Jie Wu National Taipei University of Technology DOI | ||