Quantum Causal Discovery via Amplitude Estimation of Kullback-Leibler Divergence

• URL: http://arxiv.org/abs/2604.23451v2
• Date: Sun, 03 May 2026 17:50:46 GMT
• Title: Quantum Causal Discovery via Amplitude Estimation of Kullback-Leibler Divergence
• Abstract summary: We present QKLA (Quantum Kullback-Leibler Amplitude estimation), a quantum algorithm that encodes a clipped logdensity ratio as amplitude estimation to recover a clipped KL expectation.<n>QKLA achieves a quadratic precision improvement, needing only $mathcalO((L/)log (1/)$ queries, where $L$ is the log-ratio clip bound.<n>Under per-stratum conditional-oracle access and a margin assumption for CI decisions, embedding this estimator in the PC algorithm compounds to an $widetilde (1/(L
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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 \mid Z)$ to additive precision $τ$ and thresholding against it. Classically this requires $Θ(1/τ^{2})$ 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 $\mathcal{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 $\widetildeΩ(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 $\mathcal{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_1$ while using $2.7$--$3.2\times$ fewer oracle queries at $τ= 5\cdot 10^{-3}$ bits and $4.0$--$7.4\times$ fewer at $τ= 10^{-3}$ bits.

Related papers

• Quantum Approximate Counting with Bernoulli Oracles [3.8743350688734988]
  We prove an upper bound of $tildeO!big(fracsqrt+frac1sqrtbig)$ queries, achieving a quadratic speedup over classical sampling.<n>We complement this upper bound with a near-matching lower bound of $(sqrt/())$ via a new composition theorem for the quantum adversary method.
  arXiv  Detail & Related papers  (2026-09-07T15:13:44Z)
• Quantum Speedups for Stochastic Optimization with Heavy-Tailed Noise [49.730496294398726]
  We develop a novel quantum mean estimator for heavy-tailed random variables.<n>We derive stronger lower bounds for tail index>4/3$, showing that a nontrivial dependence on a dimension is unavoidable.<n>For a convex objective function, we propose a quantum projected gradient descent method.
  arXiv  Detail & Related papers  (2026-07-28T09:29:37Z)
• Minimax PAC Bounds for Learning in Exogenous Contextual MDPs [26.599514971653615]
  PAC learning in discounted decision processes with i.i.d. contexts, with discount factor $$, finite state space $mathcal X$, action space $mathcal A$, and context space $mathcal Z$.
  arXiv  Detail & Related papers  (2026-06-23T21:02:18Z)
• Blind Catalytic Quantum Error Correction: Target-State Estimation and Fidelity Recovery Without \textit{A Priori} Knowledge [0.0]
  We introduce emphblind CQEC, which estimates the target from the noisy output alone before catalytic recovery.<n>Five estimation strategies are benchmarked across three noise models.
  arXiv  Detail & Related papers  (2026-04-13T08:27:08Z)
• Covariant quantum error correction in a three-layer quantum brain model: computational analysis of layer-specific coherence dynamics [0.0]
  We evaluate approximate covariant quantum error correction (CQEC) across two radical-pair proteins.<n>CQEC maintains coherence of 0.83 (95% CI [0.76, 0.79); versus 0.12 without tunneling, $times6.96.9 improvement.<n>A $T sensitivity analysis confirms: at $T = 26$ms, CQEC-protected coherence remains 0.69.
  arXiv  Detail & Related papers  (2026-03-31T11:47:00Z)
• qc-kmeans: A Quantum Compressive K-Means Algorithm for NISQ Devices [3.4129039170001314]
  Clustering on NISQ hardware is constrained by data loading and limited qubits.<n>We present qc-kmeans, a hybrid $k$-means that summarizes a dataset with a constant-size Fourier-feature sketch and selects centroids by solving small per-group QUBOs with shallow QAOA circuits.
  arXiv  Detail & Related papers  (2025-10-26T05:44:17Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• End-to-end complexity for simulating the Schwinger model on quantum computers [0.6449786007855248]
  We propose an efficient implementation of block-encoding of the Schwinger model Hamiltonian. As an end-to-end application, we compute the vacuum persistence amplitude. Our results provide insights into predictions about the performance of quantum computers in the FTQC era.
  arXiv  Detail & Related papers  (2023-11-29T06:36:11Z)
• Detection-Recovery Gap for Planted Dense Cycles [72.4451045270967]
  We consider a model where a dense cycle with expected bandwidth $n tau$ and edge density $p$ is planted in an ErdHos-R'enyi graph $G(n,q)$. We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree algorithms.
  arXiv  Detail & Related papers  (2023-02-13T22:51:07Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• A lower bound on the space overhead of fault-tolerant quantum computation [51.723084600243716]
  The threshold theorem is a fundamental result in the theory of fault-tolerant quantum computation. We prove an exponential upper bound on the maximal length of fault-tolerant quantum computation with amplitude noise.
  arXiv  Detail & Related papers  (2022-01-31T22:19:49Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)
• Quantum Algorithms for Simulating the Lattice Schwinger Model [63.18141027763459]
  We give scalable, explicit digital quantum algorithms to simulate the lattice Schwinger model in both NISQ and fault-tolerant settings. In lattice units, we find a Schwinger model on $N/2$ physical sites with coupling constant $x-1/2$ and electric field cutoff $x-1/2Lambda$. We estimate observables which we cost in both the NISQ and fault-tolerant settings by assuming a simple target observable---the mean pair density.
  arXiv  Detail & Related papers  (2020-02-25T19:18:36Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.