Explainability in Quantum Search Algorithms on Hypercube with Shapley Values
DOI:
https://doi.org/10.59471/raia2025224Keywords:
quantum explainability, Shapley values, coined quantum walk, hypercube search, Hamiltonian-based interpretation, cooperative contributionAbstract
This work explores the explainability of the coined quantum walk search algorithm on the hypercube by incorporating the SMEF-E (Shapley–Matrix Explainability Framework – Energy) methodology. In this approach, cooperative game theory is combined with Hamiltonian-based value functions to attribute, step by step, the energetic and functional impact of the oracle, the Grover coin, and the flip-flop shift. The resulting Shapley value decomposition offers an interpretable quantification of operator influence throughout the amplification process, revealing how constructive interference emerges and is redistributed as the algorithm approaches its optimal success probability. The experimental analysis confirms theoretical predictions while providing transparent insights into the mechanisms driving quantum advantage in spatial search.
Downloads
References
Burge, D., & et al. (2024). Explainability for Quantum Circuits using Functional Attribution. npj Quantum Information.
Childs, A. M., & Goldstone, J. (2004). Spatial search by quantum walk. Physical Review A, 70(2), 022314. https://doi.org/10.1103/PhysRevA.70.022314
Grover, L. K. (1996). A fast quantum mechanical algorithm for database search. Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing (STOC ’96), 212-219. https://doi.org/10.1145/237814.237866
Nielsen, M. A., & Chuang, I. L. (2011). Quantum Computation and Quantum Information: 10th Anniversary Edition (10th anniversary ed.). Cambridge University Press.
Portugal, R. (2018). Quantum Walks and Search Algorithms. Springer. https://doi.org/10.1007/978-3- 319-97813-8
Shapley, L. S. (1953). A value for n-person games. En H. W. Kuhn & A. W. Tucker (Eds.), Contributions to the Theory of Games (pp. 307-317, Vol. 2). Princeton University Press.
Shenvi, N., Kempe, J., & Whaley, K. B. (2003). Quantum random-walk search algorithm. Physical Review A, 67(5), 052307. https://doi.org/10.1103/PhysRevA.67.052307
Young, H. P. (1985). Monotonic solutions of cooperative games. International Journal of Game Theory, 14(2), 65-72. https://doi.org/10.1007/BF01770228
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
