A Shapley Value Estimation Speedup for Efficient Explainable Quantum AI

This work focuses on developing efficient post-hoc explanations for quantum AI algorithms. In classical contexts, the cooperative game theory concept of the Shapley value adapts naturally to post-hoc explanations, where it can be used to identify which factors are important in an AI's decision-making process. An interesting question is how to translate Shapley values to the quantum setting and whether quantum effects could be used to accelerate their calculation. We propose quantum algorithms that can extract Shapley values within some confidence interval. Our method is capable of quadratically outperforming classical Monte Carlo approaches to approximating Shapley values up to polylogarithmic factors in various circumstances. We demonstrate the validity of our approach empirically with specific voting games and provide rigorous proofs of performance for general cooperative games. As Artificial Intelligence (AI) becomes a larger part of critical decision-making processes, it is important to understand the logic behind the decisions being made. Transparency in AI has become a topic of substantial regulatory importance worldwide. In the European Union, the General Data Protection Regulation (GDPR) provides citizens the right to explanations for impactful automated decisions which relate to personal data [1]. More recently, in 2024, the European Union enacted the AI act. The AI act provides individuals, in the context of high-risk AI systems, the right to an explanation for: (i) the use of an AI system in the decision-making process; (ii) the most important elements of that decision [2]. NIST's plan listed explainability as an aspect of trustability, which is one of their key areas of focus. This wave of legislative attention poses a substantial challenge, as many of today's state-of-the-art AI algorithms, such as deep learning models, are unexplainable black boxes [4]. Without specialized tools, AI developers often cannot understand the reasoning of their models.