{"id":"4807bb79-ae48-4ee3-bddd-2b999cbfcc75","arxiv_id":"2412.14639","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Quantum amplitude estimation can estimate Shapley values with O(1/ε) queries to the value function, a quadratic improvement over classical Monte Carlo's O(σ²/ε²).","lead":"Quantum algorithms that estimate Shapley values, a standard measure of feature importance in explainable AI, with a quadratic speedup over classical Monte Carlo sampling. The result could make explanations of AI decisions and cooperative game analyses faster on future quantum computers.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 5's error analysis treats two separate amplitude-estimation runs as one; per-run errors add, so the claimed O(sqrt(DeltaV(Phi_i-V_min))/eps) complexity is unsupported and can be too small by an arbitrarily large factor.","rationale":"The reader's CORDIC dependency concern is legitimate and is a real obstacle to the improved algorithm, but the present paper contains a more fundamental, internal error in the proof of its main theorem. The algorithm estimates Phi_+ and Phi_- in two separate amplitude-estimation calls, so the errors add; Appendix D.3 instead treats the two calls as a single estimation of mu = Phi_i/DeltaV and chooses the number of iterations using sqrt(Phi_i - V_min). This is not a matter of an unverified external resource: it is a mistaken error-propagation step inside the paper. The consequence is that Theorem 5's stated bound, which is the paper's strongest quantitative claim, is not established and can be violated by an arbitrarily large factor when Phi_i is small while Phi_+ and Phi_- are both large. The qualitative claim that a quantum algorithm can outperform Monte Carlo by a quadratic factor in the inverse precision is likely repairable, since even a corrected bound of O(DeltaV/eps) beats a classical O(sigma^2/eps^2) bound when sigma^2 is bounded away from zero, but the theorem as stated and the comparison in Table 4 need correction. Other parts of the paper, including the Riemann-sum weight construction and the error analysis for Steps 1 and 2, appear internally coherent, and the empirical demonstration is a useful sanity check, though it does not benchmark against the classical baseline. The verdict should remain CONDITIONAL, but the condition is not only about validating the CORDIC construction: the Step 3 error analysis must be reworked and Theorem 5 restated before the central complexity claim can be accepted.","tokens_in":31107,"tokens_out":24639,"duration_ms":183064,"concrete_test":"Construct a game where, under the gamma distribution over S subset of F\\{i}, E[V(S union {i})] = E[V(S)] = 1/2 and Phi_i = delta = 0.01, with DeltaV = 1. Take eps = 1e-4. Equation (40) gives t = 28*sqrt(0.01)/1e-4 = 28000. But a single amplitude-estimation run with mu = 1/2 requires t >= 2pi*sqrt(0.25)/(eps/2) = 2pi/eps ~= 62832 to guarantee per-run error eps/2. Simulate two independent amplitude-estimation runs with t = 28000 on Bernoulli(0.5) sources, subtract the estimates, and check whether the absolute error exceeds eps = 1e-4 with probability greater than the claimed failure bound. Alternatively, recompute the Step 3 error bound in Appendix D.3 using mu_+ and mu_- separately for this game and compare it with the claimed bound.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The proof of Theorem 5 (Section 7, with the Step 3 analysis in Appendix D.3) analyzes amplitude estimation as if a single run were estimating mu = (Phi_i - V_min)/(V_max - V_min). But the algorithm in Section 5, Step 3, and used again in Section 7, performs two separate amplitude-estimation runs, one on |phi_+> and one on |phi_->, and subtracts the resulting estimates. Montanaro's bound applies separately to mu_+ = (Phi_+ - V_min)/DeltaV and mu_- = (Phi_- - V_min)/DeltaV, so the error of the difference is bounded by 2pi(sqrt(mu_+) + sqrt(mu_-))/t + 2pi^2/t^2, not by 2pi sqrt(mu)/t. Equation (40) chooses t = O(sqrt((Phi_i - V_min)DeltaV)/eps), which can be much smaller than what is needed: for an almost-null player with mu_+ and mu_- both near 1/2 and Phi_i = delta > 0, the claimed t is O(sqrt(delta)/eps), while each of the two runs requires t = Omega(1/eps) to keep per-run error at eps/2. The ratio of the required t to the claimed t grows as 1/sqrt(delta), so Theorem 5's bound does not follow from the algorithm as written. The qualitative quadratic-in-eps speedup may survive after replacing sqrt(Phi_i - V_min) by a term depending on max(mu_+, mu_-), but the specific complexity stated in Theorem 5 and Table 4 is incorrect.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes quantum algorithms for estimating Shapley values of cooperative games, with applications to explainable AI. The main construction encodes Shapley weights as expected values of a constructed quantum state and uses Montanaro amplitude estimation to achieve a claimed quadratic speedup over classical Monte Carlo. Section 5 gives a first algorithm relying on a partition-register state D_ℓ that approximates Riemann sums of beta functions; Section 7 replaces D_ℓ with a Quantum CORDIC arcsin circuit from a companion paper to improve the overhead. Empirical demonstrations on weighted voting games and a companion repository are included. The central claimed result is Theorem 5 and Table 4: the quantum algorithm estimates Φ_i with additive error ε and fixed success probability using O(sqrt(ΔV(Φ_i - V_min))/ε · (log²(ΔV n/ε) + n log(ΔV n/ε) + C_V(ε/(4ΔV)))) operations, versus classical O(σ²/ε² C_V(ε)).","tokens_in":31456,"tokens_out":10151,"duration_ms":76875,"significance":"If the claims were correct, the paper would be a meaningful contribution to quantum Monte Carlo speedups and to explainable quantum AI: it gives an explicit circuit-level construction, a rigorous error-propagation framework in Appendix D, and concrete simulations with reproducible code. The identification of Shapley weights with beta functions and the use of Riemann-sum state preparation are elegant. However, the flagship Theorem 5 and Table 4 rest on an error analysis that conflates two independent amplitude-estimation runs, so the stated complexity bound is not proven and can be arbitrarily wrong. The qualitative idea is plausible and may survive a corrected analysis, but the manuscript in its current form does not establish its main speedup theorem.","major_comments":[{"comment":"The Step 3 error analysis treats two separate amplitude-estimation runs as a single run estimating μ = (Φ_i - V_min)/(V_max - V_min). The algorithm described in Section 5, Step 3, and used again in Section 7, performs one amplitude-estimation run on |ψ_+⟩ and a second run on |ψ_-⟩, then subtracts the estimates. Montanaro's bound applies separately to μ_+ = (Φ_+ - V_min)/ΔV and μ_- = (Φ_- - V_min)/ΔV, so the error of the difference is bounded by ΔV(2π(√μ_+ + √μ_-)/t + 2π²/t²), not by ΔV(2π√μ/t + π²/t²). For an almost-null player with Φ_i = δ > 0 and μ_+, μ_- both near 1/2, Eq. (40) chooses t = O(√(ΔVδ)/ε), while each of the two runs requires t = Ω(1/ε) to keep the per-run error at ε/2. The ratio of required t to claimed t grows as 1/√δ, so Theorem 5's complexity bound and the corresponding entry in Table 4 are unsupported by the algorithm as written.","section":"§7 Theorem 5; Appendix D.3; Eq. (40)"},{"comment":"The recovery formula in Theorem 5 is inconsistent with the construction. From Equations (8) and (9), the utility-register expectation values satisfy E_± = (Φ_± - V_min)/ΔV, so the difference E_+ - E_- equals Φ_i/ΔV; multiplying by ΔV yields Φ_i, with no subtraction of V_min. The phrase 'multiplying by V_max - V_min, and subtracting by V_min' does not reconstruct Φ_i from the two measured expectations and should be corrected.","section":"§7 Theorem 5 statement"},{"comment":"The complexity count for the arcsin-based weight preparation appears undercounted. The Quantum CORDIC arcsin operation from [30] produces a single-qubit rotation whose angle depends on the partition-register value k; applying this operation to each of the n player qubits costs n · O(ℓ²) CNOTs in the obvious implementation, i.e., n · O(log²(ΔV n/ε)). The proof instead states that the results are encoded using O(n log(ΔV n/ε)) operations. Unless a sharing or fan-out mechanism that avoids repeating the arcsin computation n times is intended and explicitly described, the polylogarithmic overhead claimed in Theorem 5 does not follow.","section":"§7 Theorem 5 proof"},{"comment":"The improved algorithm depends entirely on the claim from [30] that arcsin can be implemented with O(ℓ²) CNOTs, 4ℓ + O(log ℓ) ancillary qubits, and error 2^{-(ℓ+1)}. This result is not proved or reproduced in the present manuscript. Because the entire advantage of the improved algorithm over the Section 5 version rests on this external result, the paper should either supply a proof in an appendix or refer to a peer-reviewed published version of [30].","section":"§7, first paragraph after Eq. (25)"}],"minor_comments":[{"comment":"The error bound contains typographical inconsistencies: the text alternately writes '2π t√μ' and '2π/(t√μ)', while Montanaro's bound and the subsequent choice of t require '2π√μ/t'. These expressions should be corrected and made consistent.","section":"Appendix D.3"},{"comment":"The affiliation for Michel Barbeau reads 'carleron'; it should be 'Carleton'.","section":"Title page affiliation"},{"comment":"The name 'Riberio' should be spelled 'Ribeiro'.","section":"Reference [31]"},{"comment":"The caption and text should clarify whether the reported errors include only the Step 1 (weight-preparation) error or also the statistical error of the amplitude estimation step, and how the exact Shapley values used as ground truth were computed.","section":"§6.1, Figure 4"}],"recommendation":"major_revision","confidential_remarks":"The main speedup claim (Theorem 5, Table 4) is not supported by the current error analysis, which incorrectly lumps two amplitude-estimation runs into one. A corrected analysis will likely replace the factor sqrt(Φ_i - V_min) with a dependence on max(μ_+, μ_-) or on sqrt((Φ_+ - V_min)(Φ_- - V_min)/ΔV), which may still preserve a quadratic speedup in ε for many games. The paper also needs to resolve the external dependency on the unpublished Quantum CORDIC arcsin result and correct the stated complexity of the arcsin-based state preparation. These are fixable within the manuscript's scope, so I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real attempt at a hard problem, and the beta-function identity for Shapley weights is a nice trick. But the main theorem as stated is wrong, and the paper's strongest claimed speedup leans on an unverified self-cited construction. I'd still send it to review, with a request to fix the error analysis.\n\nWhat's new: the mapping from the gamma(n,m) weights to integrals of b_{n,m}, and using Riemann sums to prepare those weights, is a genuine construction not in their earlier papers (as far as I can tell). The improved algorithm in Section 7 using Quantum CORDIC for arcsin is also new here, and the error analysis in Appendix D is a real attempt at end-to-end bounds. The empirical Section 6 properly shows that the Step 1 discretization error decays exponentially with the partition size.\n\nThe problem is in Step 3. The algorithm estimates Phi_+ and Phi_- with two separate amplitude-estimation runs and subtracts them. Montanaro's bound applies to each run separately, so the error in the difference scales like sqrt(mu_+)+sqrt(mu_-), not sqrt(mu) where mu = (Phi_i - V_min)/Delta V. The paper's Equation (40) chooses t based on sqrt(Phi_i - V_min), which can be far too small when mu_+ and mu_- are both large but nearly cancel, e.g., a near-null player. For Phi_i - V_min -> 0 the claimed t goes to zero, which cannot be right. The qualitative quadratic speedup over Monte Carlo likely survives if you replace that factor by something like Delta V (or sqrt(max(mu_+,mu_-)) Delta V), but the theorem as stated is unsupported. This is a load-bearing flaw for Theorem 5 and Table 4.\n\nSecond soft spot: the improved algorithm's polylogarithmic overhead hinges entirely on the Quantum CORDIC–arcsin result [30], which is not proved or reproduced here. If that result has issues, the claimed improvement over the Section 5 algorithm evaporates. The paper also doesn't benchmark the full algorithm against a classical Monte Carlo baseline; the figure only shows the Step 1 error.\n\nMinor point: I think the reader's note about the n=2 case in Theorem 7 may be backwards; the proof seems to give a stronger bound for n=2 than the theorem's sqrt(n) form, so that looks like a harmless overstatement. The two-run error propagation is the real issue.\n\nBottom line: a paper with a genuinely interesting construction and a serious, mostly-correct analysis heart, but a main theorem that needs repair. I'd recommend sending it to a good venue with a referee who can push on the error analysis and the CORDIC dependency. After those fixes it could be a solid contribution; as is, I would not cite the Theorem 5 bound.","headline":"Worth a serious referee, but the headline quadratic bound in Theorem 5 does not follow from the paper's own error analysis.","tokens_in":31967,"tokens_out":6642,"would_cite":false,"duration_ms":47246,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","91A12","81P68"],"pacs":["03.67.Ac"],"model":"deepseek-v4-flash","headline":"This paper establishes that Shapley values—the standard measure of feature importance in explainable AI—can be estimated on a quantum computer with a quadratic speedup over classical Monte Carlo sampling.","keywords":["Shapley value","quantum algorithm","explainable AI","amplitude estimation","cooperative game theory","Monte Carlo speedup","additive explanations","quantum machine learning"],"falsifier":"Implement the quantum arcsin subroutine from reference [30] on a simulator for ℓ in the range 8 to 12 and compare its CNOT count and output error against the claimed O(ℓ²) gates and $2^{{-(ℓ+1)}}$ bound: if the error does not decay at that rate, or the gate count grows faster than ℓ², then Theorem 5's complexity bound collapses. A complementary check is to measure the empirical error of the earlier algorithm's Step-1 approximation on random weighted voting games and verify it decays like $2^{{-ℓ}}$, as Theorem 7 predicts.","tokens_in":30879,"feed_emoji":"⚛️","tokens_out":5000,"duration_ms":39634,"temperature":0.7,"pith_summary":"The paper tries to establish that Shapley values, the standard game-theoretic measure of feature importance in post-hoc AI explanations, can be estimated on a quantum computer with a quadratic speedup over classical Monte Carlo sampling: precision ε costs O(1/ε) quantum operations rather than O(1/ε²). It proposes two algorithms, proves error and complexity bounds for general cooperative games, and validates the construction empirically on weighted voting games. The authors also show how the same method adapts to local explanations of quantum binary classifiers.","feed_headline":"Shapley values get a quadratic quantum speedup","feed_subtitle":"A new quantum algorithm estimates feature-importance scores in O(1/ε) queries instead of O(1/ε²).","key_machinery":"The carrying object is an amplitude-encoded Riemann sum: a partition register prepared in a superposition whose amplitudes are the interval widths w_ℓ(k), followed by controlled rotations that create binomial amplitudes b_{n,m}(t'_ℓ(k)) over player coalitions. Tracing out the auxiliary registers leaves exactly the Shapley weights γ(n,m) up to a bounded error. Combining this construction with a quantum amplitude-estimation subroutine reduces the query count from quadratic to linear in 1/ε. In the improved version, the same Riemann sum is built on a uniform grid using a quantum arcsin circuit, which bypasses the costly non-uniform partition preparation of the earlier version.","core_discovery":"The central claim is that Shapley weights γ(n,m) coincide exactly with a beta function integral, so the weighted average defining Φ(i) can be rewritten as a Riemann sum and prepared directly in quantum amplitudes. Then the Shapley value appears as the difference of two expected measurements, extractable by amplitude estimation. The improved version removes the expensive state-preparation step by using a quantum arcsin circuit on a uniform partition, giving a query complexity of O(√(ΔV(Φ_i − V_min))/ε · (log²(ΔV n/ε) + n log(ΔV n/ε) + C_V(ε/(4ΔV)))) operations for fixed success probability, compared with classical Monte Carlo's O(σ²/ε² · C_V(ε)).","pith_inferences":["If the cited quantum arcsin construction holds up, the same circuit could replace other expensive state-preparation subroutines in quantum Monte Carlo and quantum-simulation algorithms, not just Shapley estimation.","The identity between Shapley weights and beta-function integrals suggests a classical reduction: any integral-approximation scheme for x^m(1−x)^{n−m} yields a Shapley approximation with the same error behavior, which could inspire new classical estimators.","A testable extension is to run the improved algorithm on larger random weighted voting games and check whether empirical error scales like 1/ε rather than 1/ε², as the complexity bound predicts.","The local-explanation construction points toward a direct quantum analogue of SHAP for quantum classifiers, where the classifier itself could also benefit from quantum speedups."],"forward_implications":["For any cooperative game with an efficient quantum implementation of the value function, Shapley values can be approximated to additive error ε using O(1/ε) queries instead of O(1/ε²).","Doubling precision costs only twice the work, whereas classical Monte Carlo quadruples the work.","The method yields additive explanations, in the style of SHAP, for quantum classifier circuits, including local explanations of particular decisions.","For Boolean value functions with range {0,1}, the speedup is quadratic up to polylogarithmic factors in ε and the value-function implementation cost.","When the value-function implementation is complex enough to dominate the logarithmic overhead, the polylogarithmic terms drop out and the complexity matches the paper's Table 4 comparison."],"supporting_citations":[{"why":"Supplies the amplitude-estimation subroutine that extracts the expected value with error ε in O(1/ε) iterations; the paper's complexity analysis builds on this result.","marker":"[22]"},{"why":"Provides the quantum arcsin construction used by the improved algorithm to prepare uniform-partition weights; its claimed O(ℓ²) gate count and error bound are load-bearing for Theorem 5.","marker":"[30]"},{"why":"Defines the classical Monte Carlo sampling approach whose O(σ²/ε²) query complexity is the baseline the paper claims to beat quadratically.","marker":"[9]"},{"why":"Motivates Shapley values as the unique additive feature-attribution method satisfying local accuracy, missingness, and consistency, framing the explainability problem.","marker":"[6]"},{"why":"Gives the axioms and definition of Shapley values that the quantum algorithms implement and whose uniqueness is used throughout.","marker":"[16]"},{"why":"Supplies the Stirling-approximation bound used in Lemma 12 and the error analysis for the binomial-coefficient sums.","marker":"[45]"},{"why":"Provides the explicit state-preparation scheme behind the placeholder complexity C_D(ℓ) for the earlier algorithm's partition-register preparation.","marker":"[25]"},{"why":"Establishes NP-hardness of exact Shapley computation in weighted voting games, motivating the need for approximation algorithms.","marker":"[7]"}],"fun_headline_variants":["Quadratic quantum speedup for Shapley value estimation","Quantum algorithm accelerates Shapley estimation quadratically","Shapley values: quantum approach halves query complexity","Explainable quantum AI: faster Shapley values via quantum estimation","Quantum Shapley speedup: quadratic advantage over Monte Carlo"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The improved algorithm's speedup rests entirely on a cited quantum arcsin circuit (reference [30]) whose claimed O(ℓ²) cost and $2^{{-(ℓ+1)}}$ error are not proved or reproduced in this paper; if that circuit is flawed, the algorithm falls back to a version whose weight-preparation cost can erase the quantum advantage.","fun_headline_variants_meta":{"raw":{"variants":["Quadratic quantum speedup for Shapley value estimation","Quantum algorithm accelerates Shapley estimation quadratically","Shapley values: quantum approach halves query complexity","Explainable quantum AI: faster Shapley values via quantum estimation","Quantum Shapley speedup: quadratic advantage over Monte Carlo"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000399,"raw_usage":{"total_tokens":2027,"prompt_tokens":830,"completion_tokens":1197,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":446,"completion_tokens_details":{"reasoning_tokens":1115}},"tokens_in":446,"tokens_out":1197,"duration_ms":10491,"temperature":1.0,"reasoning_tokens":1115,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T12:04:05.326733+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Implement the quantum arcsin subroutine from reference [30] on a simulator for ℓ in the range 8 to 12 and compare its CNOT count and output error against the claimed O(ℓ²) gates and $2^{{-(ℓ+1)}}$ bound: if the error does not decay at that rate, or the gate count grows faster than ℓ², then Theorem 5's complexity bound collapses. A complementary check is to measure the empirical error of the earlier algorithm's Step-1 approximation on random weighted voting games and verify it decays like $2^{{-ℓ}}$, as Theorem 7 predicts.","supporting_citations":[{"cited_title":"Montanaro","cited_arxiv_id":null,"evidence_quote":"Supplies the amplitude-estimation subroutine that extracts the expected value with error ε in O(1/ε) iterations; the paper's complexity analysis builds on this result."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Motivates Shapley values as the unique additive feature-attribution method satisfying local accuracy, missingness, and consistency, framing the explainability problem."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Gives the axioms and definition of Shapley values that the quantum algorithms implement and whose uniqueness is used throughout."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Stirling-approximation bound used in Lemma 12 and the error analysis for the binomial-coefficient sums."},{"cited_title":"Plesch and Č","cited_arxiv_id":null,"evidence_quote":"Provides the explicit state-preparation scheme behind the placeholder complexity C_D(ℓ) for the earlier algorithm's partition-register preparation."},{"cited_title":"Matsui and T","cited_arxiv_id":null,"evidence_quote":"Establishes NP-hardness of exact Shapley computation in weighted voting games, motivating the need for approximation algorithms."}],"review_version":1}