Abstract
Causal discovery from observational data underpins applications in finance, climate modeling, and machine learning. Constraint-based causal discovery reduces structure learning to a sequence of conditional independence (CI) tests, where each test decides independence by estimating conditional mutual information I(X;Y Z) to additive precision τ and thresholding against it. Classically this requires Θ(1/τ²) samples per test, a cost that dominates in the high-precision regime typical of weak dependencies. We present QKLA (Quantum Kullback--Leibler Amplitude estimation), a quantum algorithm that encodes a clipped log-density ratio as a bounded amplitude and applies amplitude estimation to recover a clipped KL expectation. Given coherent oracle access to the relevant distributions and a reversible log-ratio arithmetic oracle, QKLA achieves a quadratic precision improvement, needing only O((L/τ)log(1/δ)) queries, where L is the log-ratio clip bound. Under per-stratum conditional-oracle access and a margin assumption for CI decisions, embedding this estimator in the PC algorithm compounds to an Ω(1/(Lτ)) reduction in total oracle queries. We validate the theory in three experiments. A gate-level state-vector simulation of the full QKLA circuit confirms the predicted O(1/M) error decay. Across K=20 random binary distributions, classical and quantum error scalings match theory to within 0.01 in slope. In an oracle-model benchmark inside PC on two networks (\textsc{Asia}, 8 nodes; \textsc{Synthetic-12}, 12 nodes), the quantum CI subroutine reaches comparable skeleton-recovery F₁ while using 2.7--3.2× fewer oracle queries at τ = 5· 10⁻³ bits and 4.0--7.4× fewer at τ = 10⁻³ bits.