A Shapley Value Estimation Speedup for Efficient Explainable Quantum AI

• URL: http://arxiv.org/abs/2412.14639v1
• Date: Thu, 19 Dec 2024 08:50:46 GMT
• Title: A Shapley Value Estimation Speedup for Efficient Explainable Quantum AI
• Authors: Iain Burge, Michel Barbeau, Joaquin Garcia-Alfaro,
• Abstract summary: In classical contexts, the cooperative game theory concept of the Shapley value adapts naturally to post-hoc explanations. We propose quantum algorithms that can extract Shapley values within some confidence interval.
• Score: 0.8739101659113155
• License:
• Abstract: 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.

Related papers

• Quantum algorithm for approximating the expected value of a random-exist quantified oracle [0.0]
  Quantum amplitude amplification and estimation have shown quadratic speedups to unstructured search and estimation tasks. We show that a coherent combination of these quantum algorithms also provides a quadratic speedup to calculating the expectation value of a random-exist quantified oracle.
  arXiv  Detail & Related papers  (2024-11-30T19:42:08Z)
• Efficient Learning for Linear Properties of Bounded-Gate Quantum Circuits [63.733312560668274]
  Given a quantum circuit containing d tunable RZ gates and G-d Clifford gates, can a learner perform purely classical inference to efficiently predict its linear properties? We prove that the sample complexity scaling linearly in d is necessary and sufficient to achieve a small prediction error, while the corresponding computational complexity may scale exponentially in d. We devise a kernel-based learning model capable of trading off prediction error and computational complexity, transitioning from exponential to scaling in many practical settings.
  arXiv  Detail & Related papers  (2024-08-22T08:21:28Z)
• Quantum Algorithms for Compositional Text Processing [1.3654846342364308]
  We focus on the recently proposed DisCoCirc framework for natural language, and propose a quantum adaptation, QDisCoCirc. This is motivated by a compositional approach to rendering AI interpretable. For the model-native primitive operation of text similarity, we derive quantum algorithms for fault-tolerant quantum computers.
  arXiv  Detail & Related papers  (2024-08-12T11:21:40Z)
• Fast Shapley Value Estimation: A Unified Approach [71.92014859992263]
  We propose a straightforward and efficient Shapley estimator, SimSHAP, by eliminating redundant techniques. In our analysis of existing approaches, we observe that estimators can be unified as a linear transformation of randomly summed values from feature subsets. Our experiments validate the effectiveness of our SimSHAP, which significantly accelerates the computation of accurate Shapley values.
  arXiv  Detail & Related papers  (2023-11-02T06:09:24Z)
• Calculating the many-body density of states on a digital quantum computer [58.720142291102135]
  We implement a quantum algorithm to perform an estimation of the density of states on a digital quantum computer. We use our algorithm to estimate the density of states of a non-integrable Hamiltonian on the Quantinuum H1-1 trapped ion chip for a controlled register of 18bits.
  arXiv  Detail & Related papers  (2023-03-23T17:46:28Z)
• Schrödinger as a Quantum Programmer: Estimating Entanglement via Steering [3.187381965457262]
  We develop a quantum algorithm that tests for and quantifies the separability of a general bipartite state by using the quantum steering effect. Our findings provide a meaningful connection between steering, entanglement, quantum algorithms, and quantum computational complexity theory.
  arXiv  Detail & Related papers  (2023-03-14T13:55:06Z)
• A Quantum Algorithm for Shapley Value Estimation [0.8739101659113155]
  We propose quantum algorithms which can extract Shapley values within some confidence interval. We demonstrate the validity of each approach under specific examples of voting games.
  arXiv  Detail & Related papers  (2023-01-11T21:32:59Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  We design, implement, and evaluate three hybrid quantum k-Means algorithms. We exploit quantum phenomena to speed up the computation of distances. We show that our hybrid quantum k-Means algorithms can be more efficient than the classical version.
  arXiv  Detail & Related papers  (2022-12-13T16:04:16Z)
• Entanglement and coherence in Bernstein-Vazirani algorithm [58.720142291102135]
  Bernstein-Vazirani algorithm allows one to determine a bit string encoded into an oracle. We analyze in detail the quantum resources in the Bernstein-Vazirani algorithm. We show that in the absence of entanglement, the performance of the algorithm is directly related to the amount of quantum coherence in the initial state.
  arXiv  Detail & Related papers  (2022-05-26T20:32:36Z)
• Quantum algorithms for quantum dynamics: A performance study on the spin-boson model [68.8204255655161]
  Quantum algorithms for quantum dynamics simulations are traditionally based on implementing a Trotter-approximation of the time-evolution operator. variational quantum algorithms have become an indispensable alternative, enabling small-scale simulations on present-day hardware. We show that, despite providing a clear reduction of quantum gate cost, the variational method in its current implementation is unlikely to lead to a quantum advantage.
  arXiv  Detail & Related papers  (2021-08-09T18:00:05Z)
• Quantum belief function [4.286327408435937]
  We encode the basic belief assignment (BBA) into quantum states, which makes each qubit correspond to control an element. We simulate our quantum version of BBA on Qiskit platform, which ensures the computation of our algorithm experimentally.
  arXiv  Detail & Related papers  (2021-07-08T15:57:32Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.