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• Revised May 3, 2026 (v2)
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 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 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

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•2 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

Quantum Algorithms for Trading: A Survey of Speedups, Thresholds, and Dequantization

Luigi Laura, Marco Parrillo, Alessio Pascucci +2 more

Quantum algorithms for trading span computational tasks with different input models and standards of evidence. This structured critical review describes its search scope, selection criteria and limitations, and distinguishes reported findings from author assessments. Amplitude estimation estimates bounded expectations to additive error ϵ with O(ϵ−1) oracle queries rather than the O(ϵ−2) samples of plain classical Monte Carlo at fixed confidence. This query advantage does not establish an end-to-end runtime advantage: state preparation, arithmetic, error correction and classical competitors must also be costed. Published resource estimates for benchmark exotics require thousands of logical qubits and demanding logical operation rates. An illustrative sensitivity analysis shows how the crossover depends on classical throughput, oracle depth and the comparison window; its numbers are scenarios, not calibrated hardware forecasts. Portfolio and trading-trajectory formulations have device demonstrations, but a 250-instance benchmark of discretized minimum-variance allocation finds classical mixed-integer programming and a tailored heuristic superior on the tested formulation. Specific low-rank quantum machine learning algorithms have been dequantized under analogous sampling-access assumptions. Separately, a controlled study of quantum kernels for Chinese equity returns finds no significant advantage and demonstrates sensitivity to evaluation design; this does not settle other learning tasks. Entanglement-assisted coordination offers advantages in specified nonlocal games without computational-complexity assumptions, while its financial implementation and economics remain open. We distinguish computational performance from economic value and identify input/output costs, structured algorithms, reproducible benchmarking and explicit financial evaluation as priorities.

Information•Sep 17, 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 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/δ))\mathcal{O}((L/τ)\log(1/δ))O((L/τ)log(1/δ)) queries, where LLL 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τ))\widetildeΩ(1/(Lτ))Ω(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)\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 within 0.010.010.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 F1F_1F1​ while using 2.72.72.7--3.2×3.2\times3.2× fewer oracle queries at τ=5⋅10−3τ= 5\cdot 10^{-3}τ=5⋅10−3 bits and 4.04.04.0--7.4×7.4\times7.4× fewer at τ=10−3τ= 10^{-3}τ=10−3 bits.
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.
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.
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.
Quantum algorithms for trading span computational tasks with different input models and standards of evidence. This structured critical review describes its search scope, selection criteria and limitations, and distinguishes reported findings from author assessments. Amplitude estimation estimates bounded expectations to additive error ϵ with O(ϵ−1) oracle queries rather than the O(ϵ−2) samples of plain classical Monte Carlo at fixed confidence. This query advantage does not establish an end-to-end runtime advantage: state preparation, arithmetic, error correction and classical competitors must also be costed. Published resource estimates for benchmark exotics require thousands of logical qubits and demanding logical operation rates. An illustrative sensitivity analysis shows how the crossover depends on classical throughput, oracle depth and the comparison window; its numbers are scenarios, not calibrated hardware forecasts. Portfolio and trading-trajectory formulations have device demonstrations, but a 250-instance benchmark of discretized minimum-variance allocation finds classical mixed-integer programming and a tailored heuristic superior on the tested formulation. Specific low-rank quantum machine learning algorithms have been dequantized under analogous sampling-access assumptions. Separately, a controlled study of quantum kernels for Chinese equity returns finds no significant advantage and demonstrates sensitivity to evaluation design; this does not settle other learning tasks. Entanglement-assisted coordination offers advantages in specified nonlocal games without computational-complexity assumptions, while its financial implementation and economics remain open. We distinguish computational performance from economic value and identify input/output costs, structured algorithms, reproducible benchmarking and explicit financial evaluation as priorities.