Quantum PC Algorithm: Data-Efficient and Nonlinear Causal Discovery

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.