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.
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.
Recently, the utilization of real-world medical data collected from clinical sites has been attracting attention. Especially as the number of variables in real-world medical data increases, causal discovery becomes more and more effective. On the other hand, it is necessary to develop new causal discovery algorithms suitable for small data sets for situations where sample sizes are insufficient to detect reasonable causal relationships, such as rare diseases and emerging infectious diseases. This study aims to develop a new causal discovery algorithm suitable for a small number of real-world medical data using quantum computing, one of the emerging information technologies attracting attention for its application in machine learning. In this study, a new algorithm that applies the quantum kernel to a linear non-Gaussian acyclic model, one of the causal discovery algorithms, is developed. Experiments on several artificial data sets showed that the new algorithm proposed in this study was more accurate than existing methods with the Gaussian kernel under various conditions in the low-data regime. When the new algorithm was applied to real-world medical data, a case was confirmed in which the causal structure could be correctly estimated even when the amount of data was small, which was not possible with existing methods. Furthermore, the possibility of implementing the new algorithm on real quantum hardware was discussed. This study suggests that the new proposed algorithm using quantum computing might be a good choice among the causal discovery algorithms in the low-data regime for novel medical knowledge discovery.
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/τ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/δ)) 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 F1 while using 2.7--3.2× fewer oracle queries at τ=5⋅10−3 bits and 4.0--7.4× fewer at τ=10−3 bits.
Abstract Modern machine learning (ML) methods typically fail to adequately capture causal information. Consequently, such models do not handle data distributional shifts, are vulnerable to adversarial examples, and often learn spurious correlations (Schölkopf and von Kügelgen 2022 (arXiv:2204.00607) [cs.AI]). Causal ML, or causal inference, aims to solve these issues by estimating the expected outcome of counterfactual events, using observational and/or interventional data, where causal relationships are typically depicted as directed acyclic graphs. It is an open question as to whether these causal algorithms provide opportunities for quantum enhancement. In this paper we consider a recently developed family of non-parametric, continuous causal estimators and derive quantum algorithms for these tasks. Kernel evaluation and large matrix inversion are critical sub-routines of these classical algorithms, which makes them particularly amenable to a quantum treatment. Unlike other quantum ML algorithms, closed form solutions for the estimators exist, negating the need for gradient evaluation and variational learning. We describe several new hybrid quantum–classical algorithms and show that uniform consistency of the estimators is retained. Furthermore, if one is satisfied with a quantum state output that is proportional to the true causal estimand, then these algorithms inherit the exponential complexity advantages given by quantum linear system solvers.
A causal understanding of a physical theory is vital. They provide profound insights into the implications of the theory and contain the information required to manipulate, not only predict, our surroundings. Unfortunately, one of the most broadly used and successful theories, quantum theory, continues to evade a satisfactory causal description. The progress is hindered by the difficulty of faithfully testing causal explanations in an experimental setting. This thesis presents a novel causal discovery algorithm which allows a direct comparison of a wide variety of causal explanations for experimental data. They include causal influences both classical and quantum mechanical in nature. First we provide relevant background information, predominately on quantum mechanics, quantum optics and statistical inference. Next, we review the framework of classical causality and the connection between a causal assumption and statistical model. We then present a novel causal discovery algorithm for noisy experimental data. Finally, we perform two Bell experiments and apply the newly developed algorithm on the resulting data. \nThe causal discovery algorithm operates on observational data without any interven- tions required. It utilizes the concept of predictive accuracy to assign a score to each causal explanation. This allows the simultaneous consideration of classical and quantum causal theories. In addition, this approach allows the identification of overly complex explanations as these perform poorly with respect to this criterion. \nBoth experiments are implemented using quantum optics. The first Bell experiment has a near maximally entangled shared resource state while the second has a separable resource state. The results indicate that a quantum local causal explanation bests describes the first experiment, whereas a classical local causal explanation is preferred for the second. A super-luminal or super-deterministic theory are sub-optimal for both.
Abstract Recently, the importance of analyzing data and collecting valuable insight efficiently has been increasing in various fields. Estimating mutual information~(MI) plays a critical role in investigating the relationship among multiple random variables with a nonlinear correlation. Particularly, the task to determine whether they are independent or not is called the independence test, whose core subroutine is estimating MI from given data. It is a fundamental tool in statistics and data analysis that can be applied in a wide range of applications such as hypothesis testing, causal discovery and more. In this paper, we propose a method for estimating mutual information using the quantum kernel. We investigate the performance under various problem settings, such as different sample sizes or the shape of the probability distribution. As a result, the quantum kernel method showed higher performance than the classical one under the situation that the number of samples is small, the variance is large or the variables possess highly non-linear relationships. We discuss this behavior in terms of the central limit theorem and the structure of the corresponding quantum reproducing kernel Hilbert space.