Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2604.23451

Quantum Causal Discovery via Amplitude Estimation of Kullback-Leibler Divergence

Shabnam Sodagari

quant-phSubmitted Apr 25, 2026• Announced Apr 28, 2026• 0 citations
v1 · Apr 25, 2026v2 · May 3, 2026
arXivHTMLPDF

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 the KL divergence. Given coherent oracle access to the joint distribution, QKLA achieves a quadratic precision improvement, needing only $\mathcal{O}((L/τ)\log(1/δ))$ queries, where $L$ is the log-ratio clip bound. Embedded in the PC algorithm, this compounds to an $\widetildeΩ(1/(Lτ))$ reduction in total queries for the full causal discovery procedure. 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 slope accuracy $\pm 0.005$. On two benchmark networks (\textsc{Asia}, 8 nodes; \textsc{Synthetic-12}, 12 nodes), quantum PC matches classical skeleton-recovery F1 while using $2.5$--$3.0\times$ fewer oracle queries at $τ= 5\cdot 10^{-3}$ bits and up to $12\times$ fewer at $τ= 10^{-3}$ bits.

Related papers

Optimal algorithmic complexity of inference in quantum kernel methods

Elies Gil-Fuster, Seongwook Shin, Sofiene Jerbi +2 more

Quantum kernel methods are among the leading candidates for achieving quantum advantage in supervised learning. A key bottleneck is the cost of inference: evaluating a trained model on new data requires estimating a weighted sum $\sum_{i=1}^N α_i k(x,x_i)$ of $N$ kernel values to additive precision $\varepsilon$, where $α$ is the vector of trained coefficients. The standard approach estimates each term independently via sampling, yielding a query complexity of $O(N\lVertα\rVert_2^2/\varepsilon^2)$. In this work, we identify two independent axes for improvement: (1) How individual kernel values are estimated (sampling versus quantum amplitude estimation), and (2) how the sum is approximated (term-by-term versus via a single observable), and systematically analyze all combinations thereof. The query-optimal combination, encoding the full inference sum as the expectation value of a single observable and applying quantum amplitude estimation, achieves a query complexity of $O(\lVertα\rVert_1/\varepsilon)$, removing the dependence on $N$ from the query count and yielding a quadratic improvement in both $\lVertα\rVert_1$ and $\varepsilon$. We prove a matching lower bound of $Ω(\lVertα\rVert_1/\varepsilon)$, establishing query-optimality of our approach up to logarithmic factors. Beyond query complexity, we also analyze how these improvements translate into gate costs and show that the query-optimal strategy is not always optimal in practice from the perspective of gate complexity. Our results provide both a query-optimal algorithm and a practically optimal choice of strategy depending on hardware capabilities, along with a complete landscape of intermediate methods to guide practitioners. All algorithms require only amplitude estimation as a subroutine and are thus natural candidates for early-fault-tolerant implementations.

quant-pharXiv:2604.15214•Apr 17, 2026•0 citations

Quantum amplitude estimation for Wright–Fisher parameter inference: Theoretical query complexity advantages conditional on efficient oracle construction

Behrouz Parsa Moghaddam, Mahmoud A. Zaky, Arman Dabiri +1 more

We establish theoretical foundations for applying quantum amplitude estimation to Wright– Fisher population genetics, demonstrating that quantum methods could provide substantial query complexity improvements — reducing sample requirements from [Formula: see text] to [Formula: see text] — conditional on efficient oracle construction. Through paired classical simulations comparing high-variance vs low-variance estimation strategies across extensive computational replicates, we isolate the effects of variance reduction on evolutionary dynamics while validating theoretical predictions with exceptional precision. Our comprehensive statistical analysis confirms distributional equivalence between methods through consensus across multiple independent tests, including Bayesian model comparison and generational Kolmogorov–Smirnov testing. Overlapping confidence intervals for fixation probability validate that query complexity reduction does not degrade evolutionary prediction quality — the central requirement for practical quantum advantage. Fixation timing distributions remain statistically indistinguishable, demonstrating that variance reduction preserves both stochastic establishment dynamics and deterministic sweep phases across the complete evolutionary trajectory. These theoretical advantages depend entirely on three unresolved prerequisites: (i) oracle construction overhead must remain polynomial in problem parameters, requiring either quantum random access memory (qRAM) — experimentally undemonstrated at practical scales — or problem-specific circuits for fitness landscape encoding; (ii) fault-tolerant quantum hardware with gate error rates orders of magnitude below current technology; (iii) scalable quantum architectures maintaining coherence across the required computational depth. Break-even analysis establishes that without efficient oracle construction, query complexity advantages may be offset by oracle overhead, resulting in marginal or zero net computational benefit. This work contributes: (a) rigorous characterization of variance propagation through evolutionary dynamics with near-perfect scaling law validation, (b) identification of weak-selection, high-noise regimes where quantum variance reduction provides maximum benefit and (c) transparent delineation of necessary vs sufficient conditions for practical quantum advantage. Our framework establishes that reduced estimation variance, if achievable through quantum or other advanced methods, yields measurable evolutionary benefits while explicitly acknowledging that translating theoretical query advantages into end-to-end computational speedup requires coordinated breakthroughs in quantum algorithmic primitives and hardware capabilities.

International Journal of Modern Physics C•Apr 22, 2026•1 citation

Quantum Rare-Event Estimation for Ising Graphical Models with Belief-Propagation State Preparation

Mario Hernández Vera, Narges Jamialahmadi, Burak Mete +2 more

Quantum amplitude estimation can reduce the sampling cost of rare-event probability estimation, but applying it to correlated Ising graphical models is limited by the difficulty of preparing the target distribution and building a practical event oracle. This work explores two approximate strategies for mitigating these challenges. We introduce a sample-free state-preparation method combining loopy belief propagation with the Chow--Liu algorithm. The resulting tree approximation is compiled into a quantum circuit with linear gate count and depth, and its accuracy is evaluated across graph families spanning different topologies, coupling strengths, and coupling signs. We also construct a structural oracle that evaluates threshold rules with reversible Boolean gates. Using a twenty-node supply-chain disruption model as a case study, we compare maximum likelihood amplitude estimation against four classical Monte Carlo baselines. Under the fixed-depth schedule used throughout this work, the quantum estimator has the same asymptotic error scaling as the classical methods but achieves lower estimation error by a constant factor. This reduction narrows when amplitude-encoding queries replace raw shots as the resource metric. We separate statistical error from the deterministic errors caused by approximate state preparation and oracle construction, and identify the requirements for achieving an improvement beyond a constant factor.

quant-pharXiv:2608.26840•Aug 28, 2026•0 citations

Sample Complexity for Generative Learning of Quantum Measurement Data

Shuhan Zhang, Yi-Zhuang You

Generative learning of a quantum measurement distribution from finite data requires choosing a model capacity that balances representation accuracy against estimation cost. We develop a bias-variance framework that decomposes the expected population Kullback-Leibler error at model capacity $s$ and sample size $N$ as $E(s,N)=B(s)+V(s,N)$, with representation bias $B$ and a variance term $V$ capturing the mean estimation error. In the well-sampled regime, $V(s,N)\simeq[NC(s)]^{-1}$, and exponential or algebraic laws for $B$ and $C$ yield four scaling templates for the optimal error, from inverse powers of $N$ to inverse powers of $\ln N$. For local autoregressive models, the context radius sets the model capacity, and $B$ is the summed conditional mutual information lost by truncating the context. For a smoothed histogram learner, we derive an exact finite-sample estimation cost that accounts for rarely observed contexts and recovers the parameter-count law in the well-sampled regime. For transverse-field Ising Born distributions, the independently evaluated bias and estimation cost predict both the optimal context radius and the optimal error. In the well-sampled regime, the estimation cost grows exponentially with context radius. Its competition with approximately exponential bias decay in the gapped regimes predicts power-law error decay in $N$, while algebraic bias decay at criticality predicts asymptotic inverse-power decay in $\ln N$. Bulk-site results are consistent with the corresponding finite-sample predictions. These results connect the structure of quantum measurement distributions to the model capacity justified by finite data.

quant-pharXiv:2610.38028•Oct 29, 2026•0 citations

Quantum PC Algorithm: Data-Efficient and Nonlinear Causal Discovery

Yota Maeda, Ken Arai, Yu Tanaka +3 more

Causal discovery is the task of finding causal relationships between random variables from observed data. Typically, one assumes that the causal relationships can be represented by a directed acyclic graph (DAG), and makes additional assumptions to ensure that the DAG can be recovered from the observed data. In this study, we propose the quantum Peter-Clark (qPC) algorithm for nonlinear causal discovery based on quantum kernel methods. The qPC algorithm takes advantage of the quantum kernel-based conditional independent test. Through the synthetic data experiment, we show that the qPC algorithm outperforms the classical method in the regime of a small number of samples. This suggests that the kernel-based causal discovery can significantly improve performance under such conditions. Our experiments highlight that the proposed algorithm can accurately support classical algorithms in causal discovery, paving the way for future advances with the utilization of quantum computation.

IEEE International Conference on Quantum Computing and Engineering (QCE)•Sep 15, 2024•0 citations

High Precision Qubit-Efficient Variational Continuous Optimization via Amplitude Estimation

Parth Danve

Optimization of continuous-variable objectives on standard gate-based quantum computers via variational algorithms such as QAOA is typically approached by first discretizing each decision variable into a finite binary representation. This increases qubit requirements and restricts solution precision through fixed-resolution encodings. We propose a qubit-efficient variational framework for continuous optimization that instead encodes each decision variable into the squared amplitude or equivalently, the measurement probability of a single qubit state. This removes explicit discretization from the variable representation while remaining entirely within the standard qubit circuit model unlike methods like CV-QAOA employing qumode based hardware to achieve the same. To read out encoded variables, we propose using amplitude estimation rather than naive sampling or tomographic reconstruction, with the goal of improving precision scaling for continuous-value recovery. We outline how amplitude-estimation error propagates to decision-variable error and then to objective-value error under standard regularity assumptions, suggesting a distinct width-versus-precision tradeoff relative to discretized approaches. In particular, the framework replaces the logarithmic increase in qubits needed for finer binary precision with a constant cost of one qubit per decision variable, while shifting accuracy requirements into the estimation procedure. We position this approach relative to traditional discretized variational formulations, and argue that it provides a promising new direction for continuous optimization on standard qubit architectures.

quant-pharXiv:2606.08690•Jun 9, 2026•0 citations
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)I(X;Y \mid Z)I(X;Y∣Z) to additive precision τττ and thresholding against it. Classically this requires Θ(1/τ2)Θ(1/τ^{2})Θ(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 the KL divergence. Given coherent oracle access to the joint distribution, QKLA achieves a quadratic precision improvement, needing only O((L/τ)log⁡(1/δ))\mathcal{O}((L/τ)\log(1/δ))O((L/τ)log(1/δ)) queries, where LLL is the log-ratio clip bound. Embedded in the PC algorithm, this compounds to an Ω~(1/(Lτ))\widetildeΩ(1/(Lτ))Ω(1/(Lτ)) reduction in total queries for the full causal discovery procedure. We validate the theory in three experiments. A gate-level state-vector simulation of the full QKLA circuit confirms the predicted O(1/M)\mathcal{O}(1/M)O(1/M) error decay. Across K=20K=20K=20 random binary distributions, classical and quantum error scalings match theory to slope accuracy ±0.005\pm 0.005±0.005. On two benchmark networks (\textsc{Asia}, 8 nodes; \textsc{Synthetic-12}, 12 nodes), quantum PC matches classical skeleton-recovery F1 while using 2.52.52.5--3.0×3.0\times3.0× fewer oracle queries at τ=5⋅10−3τ= 5\cdot 10^{-3}τ=5⋅10−3 bits and up to 12×12\times12× fewer at τ=10−3τ= 10^{-3}τ=10−3 bits.
Quantum kernel methods are among the leading candidates for achieving quantum advantage in supervised learning. A key bottleneck is the cost of inference: evaluating a trained model on new data requires estimating a weighted sum ∑i=1Nαik(x,xi)\sum_{i=1}^N α_i k(x,x_i)∑i=1N​αi​k(x,xi​) of NNN kernel values to additive precision ε\varepsilonε, where ααα is the vector of trained coefficients. The standard approach estimates each term independently via sampling, yielding a query complexity of O(N∥α∥22/ε2)O(N\lVertα\rVert_2^2/\varepsilon^2)O(N∥α∥22​/ε2). In this work, we identify two independent axes for improvement: (1) How individual kernel values are estimated (sampling versus quantum amplitude estimation), and (2) how the sum is approximated (term-by-term versus via a single observable), and systematically analyze all combinations thereof. The query-optimal combination, encoding the full inference sum as the expectation value of a single observable and applying quantum amplitude estimation, achieves a query complexity of O(∥α∥1/ε)O(\lVertα\rVert_1/\varepsilon)O(∥α∥1​/ε), removing the dependence on NNN from the query count and yielding a quadratic improvement in both ∥α∥1\lVertα\rVert_1∥α∥1​ and ε\varepsilonε. We prove a matching lower bound of Ω(∥α∥1/ε)Ω(\lVertα\rVert_1/\varepsilon)Ω(∥α∥1​/ε), establishing query-optimality of our approach up to logarithmic factors. Beyond query complexity, we also analyze how these improvements translate into gate costs and show that the query-optimal strategy is not always optimal in practice from the perspective of gate complexity. Our results provide both a query-optimal algorithm and a practically optimal choice of strategy depending on hardware capabilities, along with a complete landscape of intermediate methods to guide practitioners. All algorithms require only amplitude estimation as a subroutine and are thus natural candidates for early-fault-tolerant implementations.
We establish theoretical foundations for applying quantum amplitude estimation to Wright– Fisher population genetics, demonstrating that quantum methods could provide substantial query complexity improvements — reducing sample requirements from [Formula: see text] to [Formula: see text] — conditional on efficient oracle construction. Through paired classical simulations comparing high-variance vs low-variance estimation strategies across extensive computational replicates, we isolate the effects of variance reduction on evolutionary dynamics while validating theoretical predictions with exceptional precision. Our comprehensive statistical analysis confirms distributional equivalence between methods through consensus across multiple independent tests, including Bayesian model comparison and generational Kolmogorov–Smirnov testing. Overlapping confidence intervals for fixation probability validate that query complexity reduction does not degrade evolutionary prediction quality — the central requirement for practical quantum advantage. Fixation timing distributions remain statistically indistinguishable, demonstrating that variance reduction preserves both stochastic establishment dynamics and deterministic sweep phases across the complete evolutionary trajectory. These theoretical advantages depend entirely on three unresolved prerequisites: (i) oracle construction overhead must remain polynomial in problem parameters, requiring either quantum random access memory (qRAM) — experimentally undemonstrated at practical scales — or problem-specific circuits for fitness landscape encoding; (ii) fault-tolerant quantum hardware with gate error rates orders of magnitude below current technology; (iii) scalable quantum architectures maintaining coherence across the required computational depth. Break-even analysis establishes that without efficient oracle construction, query complexity advantages may be offset by oracle overhead, resulting in marginal or zero net computational benefit. This work contributes: (a) rigorous characterization of variance propagation through evolutionary dynamics with near-perfect scaling law validation, (b) identification of weak-selection, high-noise regimes where quantum variance reduction provides maximum benefit and (c) transparent delineation of necessary vs sufficient conditions for practical quantum advantage. Our framework establishes that reduced estimation variance, if achievable through quantum or other advanced methods, yields measurable evolutionary benefits while explicitly acknowledging that translating theoretical query advantages into end-to-end computational speedup requires coordinated breakthroughs in quantum algorithmic primitives and hardware capabilities.
Quantum amplitude estimation can reduce the sampling cost of rare-event probability estimation, but applying it to correlated Ising graphical models is limited by the difficulty of preparing the target distribution and building a practical event oracle. This work explores two approximate strategies for mitigating these challenges. We introduce a sample-free state-preparation method combining loopy belief propagation with the Chow--Liu algorithm. The resulting tree approximation is compiled into a quantum circuit with linear gate count and depth, and its accuracy is evaluated across graph families spanning different topologies, coupling strengths, and coupling signs. We also construct a structural oracle that evaluates threshold rules with reversible Boolean gates. Using a twenty-node supply-chain disruption model as a case study, we compare maximum likelihood amplitude estimation against four classical Monte Carlo baselines. Under the fixed-depth schedule used throughout this work, the quantum estimator has the same asymptotic error scaling as the classical methods but achieves lower estimation error by a constant factor. This reduction narrows when amplitude-encoding queries replace raw shots as the resource metric. We separate statistical error from the deterministic errors caused by approximate state preparation and oracle construction, and identify the requirements for achieving an improvement beyond a constant factor.
Generative learning of a quantum measurement distribution from finite data requires choosing a model capacity that balances representation accuracy against estimation cost. We develop a bias-variance framework that decomposes the expected population Kullback-Leibler error at model capacity sss and sample size NNN as E(s,N)=B(s)+V(s,N)E(s,N)=B(s)+V(s,N)E(s,N)=B(s)+V(s,N), with representation bias BBB and a variance term VVV capturing the mean estimation error. In the well-sampled regime, V(s,N)≃[NC(s)]−1V(s,N)\simeq[NC(s)]^{-1}V(s,N)≃[NC(s)]−1, and exponential or algebraic laws for BBB and CCC yield four scaling templates for the optimal error, from inverse powers of NNN to inverse powers of ln⁡N\ln NlnN. For local autoregressive models, the context radius sets the model capacity, and BBB is the summed conditional mutual information lost by truncating the context. For a smoothed histogram learner, we derive an exact finite-sample estimation cost that accounts for rarely observed contexts and recovers the parameter-count law in the well-sampled regime. For transverse-field Ising Born distributions, the independently evaluated bias and estimation cost predict both the optimal context radius and the optimal error. In the well-sampled regime, the estimation cost grows exponentially with context radius. Its competition with approximately exponential bias decay in the gapped regimes predicts power-law error decay in NNN, while algebraic bias decay at criticality predicts asymptotic inverse-power decay in ln⁡N\ln NlnN. Bulk-site results are consistent with the corresponding finite-sample predictions. These results connect the structure of quantum measurement distributions to the model capacity justified by finite data.
Causal discovery is the task of finding causal relationships between random variables from observed data. Typically, one assumes that the causal relationships can be represented by a directed acyclic graph (DAG), and makes additional assumptions to ensure that the DAG can be recovered from the observed data. In this study, we propose the quantum Peter-Clark (qPC) algorithm for nonlinear causal discovery based on quantum kernel methods. The qPC algorithm takes advantage of the quantum kernel-based conditional independent test. Through the synthetic data experiment, we show that the qPC algorithm outperforms the classical method in the regime of a small number of samples. This suggests that the kernel-based causal discovery can significantly improve performance under such conditions. Our experiments highlight that the proposed algorithm can accurately support classical algorithms in causal discovery, paving the way for future advances with the utilization of quantum computation.
Optimization of continuous-variable objectives on standard gate-based quantum computers via variational algorithms such as QAOA is typically approached by first discretizing each decision variable into a finite binary representation. This increases qubit requirements and restricts solution precision through fixed-resolution encodings. We propose a qubit-efficient variational framework for continuous optimization that instead encodes each decision variable into the squared amplitude or equivalently, the measurement probability of a single qubit state. This removes explicit discretization from the variable representation while remaining entirely within the standard qubit circuit model unlike methods like CV-QAOA employing qumode based hardware to achieve the same. To read out encoded variables, we propose using amplitude estimation rather than naive sampling or tomographic reconstruction, with the goal of improving precision scaling for continuous-value recovery. We outline how amplitude-estimation error propagates to decision-variable error and then to objective-value error under standard regularity assumptions, suggesting a distinct width-versus-precision tradeoff relative to discretized approaches. In particular, the framework replaces the logarithmic increase in qubits needed for finer binary precision with a constant cost of one qubit per decision variable, while shifting accuracy requirements into the estimation procedure. We position this approach relative to traditional discretized variational formulations, and argue that it provides a promising new direction for continuous optimization on standard qubit architectures.