{"id":"d9b6aec4-263c-4eea-a50c-0dc2e2d855fa","arxiv_id":"2412.07623","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A fidelity estimation protocol combining classical shadow tomography and quantum amplitude estimation achieves O(sqrt(d)) computational cost for generic quantum states.","lead":"A new protocol estimates the fidelity between two arbitrary quantum states using a combination of classical shadow tomography and quantum amplitude estimation, reducing the required computational cost from linear to square-root scaling in the Hilbert space dimension. If correct, this is a significant step for quantum device certification, though it requires a fault-tolerant quantum computer to realize the advantage.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1 is not proven as stated: Corollary 10's key inequality fails for ε ≳ 0.09, so the claimed any-ε,δ guarantee lacks a valid derivation.","rationale":"The protocol idea is coherent: Bob's Clifford-shadow data is processed by Alice via QAE to estimate the amplitudes |⟨b|C|ψ⟩|², and the median-of-means structure is a natural way to turn Lemma 3 into a fidelity estimator. The numerics for GHZ-type states are consistent with a √d scaling. However, the paper's main theorem is a formal statement for arbitrary ε and δ, and its only supplied proof (Corollary 10) contains a false implication. The inequality check is not a matter of taste or a loose constant; with δ0 = 1/3 the required condition fails for all ε above about 0.092. The proof also appears to mishandle the K coefficient in the median concentration bound, which is another independent obstruction to the displayed failure probability. These issues are internal to the proof and do not depend on whether one counts oracle queries or elementary gates. The reader's weakest_assumption concerned the unit-cost oracle for A; that is a real and important modeling concern, because the claimed O(√d) is a query complexity result unless the cost of implementing A and the random Clifford unitaries is included. But the Corollary 10 gap is more immediately load-bearing: even granting every oracle, the theorem as written is not established. Both issues are likely fixable — the ε restriction by a trivial cap and the K error by correcting a constant — so a conditional verdict rather than rejection remains appropriate. The communication-cost claim in the abstract is also overstated, since each classical description of a Clifford unitary costs O(n²) bits, but that is secondary to the formal guarantee. Overall, the reader's CONDITIONAL verdict is unchanged, though for a somewhat different primary reason.","tokens_in":14375,"tokens_out":16853,"duration_ms":158885,"concrete_test":"Verify Corollary 10 with δ0 = 1/3 and ε = 0.5: compute LHS = ⌈24/(0.25·1/3)⌉ = 288 and RHS = (13/6)^4/(12·0.0625) ≈ 9.8; the asserted inequality is false. Then check whether capping ε' = min(ε, 0.09) and correcting K to 1/(2(8/π² − 1/2)²)·ln(4N/δ) restores Proposition 9 for all ε, δ; if yes, the issue is a repairable proof gap, and if no, Theorem 1's resource claim is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central guarantee (Theorem 1, Eq. 12) is proved only via Corollary 10 in the SM. Corollary 10 fixes δ0 = 1/3 and asserts that 'Since δ < 0.09' the hypothesis of Proposition 9 holds, namely ⌈24/(ε²δ0)⌉ ≤ (13/6)^4 δ0/(12ε^4). With δ0 = 1/3 this inequality is 72/ε² ≤ (13/6)^4/(36ε^4), equivalent to ε ≤ (13/6)²/√(72·36) ≈ 0.092. It is independent of δ and false for larger ε; for example ε = 0.5 gives LHS = 288 and RHS ≈ 9.8. Thus Proposition 9, and therefore Theorem 1, is established only for ε below a small constant, not 'for any ε, δ ∈ (0,1)' as claimed. The asymptotic O(√d/ε^4) form might be recoverable by running the protocol with ε' = min(ε, 0.09), but the paper does not say this, and the stated reason is incorrect. A second concrete gap in the same proof: Eq. (41)/(74) define K as (1/2)(8/π² − 1/2)² ln(4N/δ), whereas Lemma 5 requires K ≥ ln(4N/δ)/(2(8/π² − 1/2)²); the stated K is too small by about two orders of magnitude, so the displayed failure bound (65) does not follow. These are formal, internal inconsistencies, independent of any oracle-counting interpretation.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a protocol for two parties, Alice and Bob, to estimate the fidelity F = ⟨ψ|ρ|ψ⟩ between Alice's known pure state |ψ⟩ and Bob's arbitrary (possibly mixed) state ρ. Bob performs classical shadow tomography with random Clifford unitaries and sends the classical data to Alice; for each shadow snapshot, Alice runs quantum amplitude estimation (QAE) to estimate the overlap |⟨b|C|ψ⟩|², aggregates the estimates via a median, and then forms a median-of-means fidelity estimator. The main theorem claims that for any ε, δ ∈ (0,1), the protocol achieves error ≤ ε with failure probability ≤ δ using N_B = O(ln(1/δ)/ε²) copies for Bob and N_A = O(ln(1/ε²)ln(1/δ)√d/ε⁴) QAE iterations for Alice, giving an O(√d) computational scaling and a system-size-independent measurement count for Bob. The proof is based on a classical-shadow identity (Lemma 3), Chebyshev and Hoeffding-type concentration bounds, and the QAE error bound of Brassard–Hoyer–Mosca–Tapp. Numerical simulations on noisy GHZ states exhibit the predicted √d scaling of the QAE iteration count.","tokens_in":14579,"tokens_out":8173,"duration_ms":75634,"significance":"If the result holds, it is a notable advance: standard direct fidelity estimation for generic states requires O(d) resources, and this protocol claims a quadratic improvement to O(√d) while reducing Bob's copy count to a d-independent value. The combination of classical shadows with QAE is a conceptually clean and novel idea, and the paper provides a concrete falsifiable scaling prediction that the simulations corroborate. The proof strategy is transparent, built on published external results rather than fitted parameters. However, the current manuscript contains formal gaps in the derivation of the performance guarantee that must be repaired before the central claim can be accepted.","major_comments":[{"comment":"The proof of Corollary 10 asserts that 'Since δ < 0.09, we have ⌈24/(ε²δ0)⌉ ≤ (13/6)^4 δ0/(12ε^4)' with δ0 = 1/3. This inequality is independent of δ and is false for large ε: with δ0 = 1/3 it reads 72/ε² ≤ (13/6)^4/(36ε^4), which holds only for ε ≲ 0.092. For example, ε = 0.5 gives 288 ≤ 9.8, which is false. Consequently, Proposition 9, and hence Theorem 1, is proved only for small ε, not for 'any ε ∈ (0,1)' as claimed. This is a load-bearing gap in the central guarantee. The asymptotic O(√d/ε⁴) form could likely be recovered by running the protocol with ε' = min(ε, 0.09), but the manuscript does not state this, and the stated reason is incorrect.","section":"Supplemental Material, Corollary 10"},{"comment":"The chosen value K ≥ (1/2)(8/π² − 1/2)² ln(4N/δ) does not satisfy the requirement that follows from Lemma 5 and the proof's Eq. (64). The proof needs K ≥ ln(4N/δ)/(2(8/π² − 1/2)²) so that N exp(−2(8/π² − 1/2)² K) ≤ δ/4. The stated K is smaller by a factor of (8/π² − 1/2)⁴ ≈ 0.0093, i.e., about two orders of magnitude, so the displayed failure bound (65) does not follow as written. The constant in the resource bound must be corrected to K = ⌈ln(4N/δ)/(2(8/π² − 1/2)²)⌉; the asymptotic O(√d/ε⁴) scaling is not affected, but the proof is currently invalid.","section":"Supplemental Material, Proposition 9 (Eq. (41)) and Corollary 10 (Eq. (74))"},{"comment":"The advertised 'overall computational cost O(√d)' counts QAE iterations and treats the state-preparation unitary A (and its controlled versions inside Q) as a unit-cost oracle. For generic states, the circuit depth of A can grow exponentially in n, so the actual gate count is O(√d · depth(A)) plus the cost of Bob's Clifford shadow measurements. The manuscript should explicitly state that the O(√d) claim is a query complexity statement in a black-box model for A. As it stands, the abstract's 'overall computational cost' overstates what is proven for physically implemented generic states.","section":"Main text, Abstract and Theorem 1; SM, Protocol 8"}],"minor_comments":[{"comment":"The pronouns in step 1 are inconsistent: Bob 'rotates N copies of her state ρ' and later 'sends a classical description of her sampled data ... over to Bob'; the sender should be Bob and the recipient should be Alice.","section":"SM, Protocol 8, step 1"},{"comment":"The sentence 'we plot the scaling of the number of iterations M that Bob requires' should refer to Alice, since M is the number of QAE iterations performed by Alice.","section":"Main text, Simulations section"},{"comment":"In the proof of Lemma 5, the text says 'ˆB(N, δ) is a binomial random variable with N trials and success probability ε'; this should say 'failure probability δ' (or 'success probability δ', depending on convention).","section":"SM, Lemma 5 proof"},{"comment":"The phrase 'reduces the number of required measurements and the communication cost between parties to finite' is grammatically awkward; it should be 'to finite values' or 'to a finite value independent of system size.'","section":"Main text, Abstract"},{"comment":"There is a typo: 'Alices uses' should be 'Alice uses.'","section":"SM, Corollary 10"}],"recommendation":"major_revision","confidential_remarks":"The core idea is promising and the asymptotic scaling is likely salvageable, but the two proof gaps in the Supplemental Material are real and load-bearing: the ε-range restriction in Corollary 10 and the incorrect K constant in Proposition 9. Both are fixable within the manuscript's scope, so I recommend major revision rather than rejection. The oracle-cost caveat should also be stated prominently, since the advertised 'computational cost' is a query complexity statement."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Chris, the short version: this paper has a real idea—using QAE to let Alice estimate the classical-shadow overlaps directly from her state, avoiding the need for a classical description of |ψ>—and the main √d scaling is probably right behind it. But the proof of Theorem 1 as written has two concrete holes, and they're both in the supplement. Corollary 10 claims any ε∈(0,1) works, but the condition it invokes from Proposition 9 only holds for ε ≲ 0.09; the fact that δ<0.09 doesn't rescue it. And the lower bound on K in (41) is off by a factor of about (8/π²−1/2)^4 ≈ 0.0093; the constant needed for Lemma 5 is the reciprocal, so the stated K is two orders of magnitude too small. Both are fixable without changing the asymptotics, but the theorem as stated isn't proven.\n\nWhat's good: the protocol is genuinely new, the derivation of Lemma 3 is clean, the variance bound is solid, and the numerics support √d scaling. The discussion of why you can't get the speedup by just doing CST on both sides is honest and useful.\n\nThe soft spots beyond the proof gaps: the resource count is query complexity—each QAE iteration treats the state-preparation unitary A as a unit oracle. If A's gate depth is exponential, the total gate count is not √d. The paper should say this explicitly. Also \"finite communication\" is really O(n²) bits per shadow, which is not constant in n; only the number of shadows is d-independent.\n\nBottom line: this deserves a serious referee, but the referee should be told to look at the supplement carefully. The idea and the simulations are worth publishing; the proof needs to be fixed, and the claims need to be scoped to the oracle model and the small-ε regime. I'd send it to review, not rejection.","headline":"Clever QAE+CST combination with a real quadratic query-speedup, but the main theorem's proof has two fixable constant/parameter errors and the resource claims need an oracle-model caveat.","tokens_in":15200,"tokens_out":4487,"would_cite":false,"duration_ms":39398,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":["03.67.-a","03.67.Ac"],"model":"deepseek-v4-flash","headline":"A protocol for generic quantum state fidelity estimation that uses classical shadow tomography on one side and quantum amplitude estimation on the other achieves $O(\\sqrt d)$ operations and finite measurements, a quadratic improvement…","keywords":["quantum fidelity estimation","direct fidelity estimation","classical shadow tomography","quantum amplitude estimation","quadratic speedup","generic quantum states","median-of-means estimator","Hilbert space dimension"],"falsifier":"Implement the protocol on a family of target states with known preparation unitaries $A$ and count physical two-qubit gates instead of quantum amplitude estimation iterations. If the total gate count grows like $2^{n/2}\\,\\mathrm{depth}(A)$, with $\\mathrm{depth}(A)$ exponential in $n$, then the claimed $O(\\sqrt d)$ computational cost is not realized as a gate cost; if the total count stays at $O(2^{n/2}\\,\\mathrm{poly}(n))$ for such families, the claim survives.","tokens_in":14045,"feed_emoji":"⚛️","tokens_out":13633,"duration_ms":120261,"temperature":0.7,"pith_summary":"This paper proposes a protocol for directly estimating the fidelity $F=\\langle\\psi|\\rho|\\psi\\rangle$ between a pure target state $|\\psi\\rangle$ held by Alice and an arbitrary (possibly mixed) state $\\rho$ held by Bob. The main result is that Alice can certify the fidelity to accuracy $\\varepsilon$ with failure probability at most $\\delta$ using $N_A=O(\\ln(1/\\varepsilon^2)\\ln(1/\\delta)\\sqrt d/\\varepsilon^4)$ iterations of quantum amplitude estimation, while Bob needs only $N_B=O(\\ln(1/\\delta)/\\varepsilon^2)$ copies of his state, independent of the Hilbert-space dimension $d$. If correct, this is a quadratic improvement over previous direct fidelity estimation approaches, which use $O(d)$ state copies, and it reduces the communication between the two parties to a finite amount. The protocol works for generic states, including states without efficient classical descriptions, because Alice's amplitude estimation step never requires a classical description of $|\\psi\\rangle$.","feed_headline":"Generic state fidelity checks drop from O(d) to O(√d)","feed_subtitle":"Pairing classical shadows with quantum amplitude estimation cuts the standard O(d) measurement cost to √d, and Bob's share becomes finite.","key_machinery":"The argument rests on two tools and one identity. Classical shadow tomography supplies the snapshot operator $\\hat\\rho=(d+1)C^\\dagger|b\\rangle\\langle b|C-I_d$, whose expectation reproduces $\\rho$; applying it to the projector $|\\psi\\rangle\\langle\\psi|$ yields the identity $F=(d+1)\\,\\mathbb{E}[|\\langle b|C|\\psi\\rangle|^2]-1$, with shadow variance at most $3/(d+1)^2$. Quantum amplitude estimation, an algorithm that estimates the probability of a marked measurement outcome, then estimates each probability $|\\langle b|C|\\psi\\rangle|^2$: with $M$ iterations the estimate is within $O(1/M)$ except with constant probability, and because each shadow sample uses a different bit string $b$, taking the median of $K$ repetitions makes that error small. A median-of-means estimator combines the $N$ samples, using Chebyshev's inequality and the small shadow variance to control the statistical spread. The mechanism producing the $\\sqrt d$ scaling is the combination of the $O(1/M)$ amplitude-estimation error with the $1/(d+1)^2$ shadow variance, which forces the number of QAE iterations per amplitude to scale like $\\sqrt d$.","core_discovery":"The central discovery is that fidelity can be rewritten as a shadow expectation and then evaluated quantumly: for a random Clifford $C$ and a computational-basis outcome $b$ obtained by measuring $C\\rho C^\\dagger$, Lemma 3 gives $F=(d+1)\\,\\mathbb{E}[\\,|\\langle b|C|\\psi\\rangle|^2\\,]-1$. Bob samples $N$ such pairs $(C_i,b_i)$ by classical shadow tomography and sends only classical data to Alice; Alice, for each pair, uses quantum amplitude estimation on her own copies of $|\\psi\\rangle$ to estimate $|\\langle b_i|C_i|\\psi\\rangle|^2$. Taking the median of $K$ amplitude estimates for each pair and then a median-of-means over pairs makes the estimator concentrate: Theorem 1 states that with the $N_A$ and $N_B$ above, $|\\hat F_{\\rm med}-F|\\le\\varepsilon$ with probability at least $1-\\delta$. The quadratic speedup comes from the fact that quantum amplitude estimation estimates a probability with error $O(1/M)$ after $M$ iterations, whereas direct sampling of the same probability would only give $O(1/\\sqrt M)$.","pith_inferences":["The paper's operation count is a query count, not a gate count; as an editorial inference, for target states whose preparation unitary has exponential depth the actual gate cost would be $\\sqrt d$ times that depth, so the practical speedup depends on $A$ being inexpensive.","The same design—write an observable as a shadow expectation, then estimate the individual probabilities with quantum amplitude estimation—could estimate other observables such as overlaps with several pure states or expectation values of low-rank projectors, potentially carrying the $\\sqrt d$ improvement to those tasks.","An optimality proof may be within reach: since the speedup comes from amplitude amplification, a matching quadratic lower bound of the kind known for unstructured search would establish that $O(\\sqrt d)$ is the best possible query cost for this fidelity estimation problem."],"forward_implications":["If Theorem 1 is correct, generic-state fidelity estimation—where the target has no efficient classical description—becomes quadratically cheaper than the established $O(d)$ approach, since the certifier's cost is $O(\\sqrt d)$ operations.","Bob's measurement budget and the classical communication from Bob to Alice become finite and independent of dimension, so a remote party can certify a device while sending only $O(\\ln(1/\\delta)/\\varepsilon^2)$ shadow samples.","The protocol inherits the robustness of classical shadows: it handles arbitrary unknown $\\rho$ and any pure $|\\psi\\rangle$ whose preparation unitary is available, without needing a classical description of the target state.","Because the speedup has a quantum origin, it invites a matching lower bound; a quadratic lower bound would make the $O(\\sqrt d)$ cost optimal for this task."],"supporting_citations":[{"why":"Supplies classical shadow tomography: the snapshot formula and the variance bound used to derive Lemma 3.","marker":"[4]"},{"why":"Supplies the quantum amplitude estimation algorithm and its $O(1/M)$ error bound, which Protocol 8 relies on for each amplitude estimate.","marker":"[11]"},{"why":"Defines direct fidelity estimation with $O(d)$ copies, the baseline that this protocol claims to improve quadratically.","marker":"[1]"},{"why":"Provides the complementary direct fidelity estimation construction whose $O(d)$ scaling motivates the new protocol.","marker":"[2]"}],"fun_headline_variants":["Fidelity estimation for any state: quadratic speedup via shadows","Generic quantum fidelity checks now scale as √d, not d","Square-root cost for direct fidelity estimation of arbitrary states","Shadows and amplitude estimation cut fidelity cost to √d","From linear to square root: faster generic state fidelity tests"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The resource guarantee counts each quantum amplitude estimation iteration as one unit and assumes Alice can apply the unitary that prepares her target state at unit cost; if that preparation requires a number of gates that grows with system size, the true cost can be far larger than $O(\\sqrt d)$.","fun_headline_variants_meta":{"raw":{"variants":["Fidelity estimation for any state: quadratic speedup via shadows","Generic quantum fidelity checks now scale as √d, not d","Square-root cost for direct fidelity estimation of arbitrary states","Shadows and amplitude estimation cut fidelity cost to √d","From linear to square root: faster generic state fidelity tests"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000224,"raw_usage":{"total_tokens":1441,"prompt_tokens":905,"completion_tokens":536,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":521,"completion_tokens_details":{"reasoning_tokens":464}},"tokens_in":521,"tokens_out":536,"duration_ms":5363,"temperature":1.0,"reasoning_tokens":464,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T18:40:43.467000+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Implement the protocol on a family of target states with known preparation unitaries $A$ and count physical two-qubit gates instead of quantum amplitude estimation iterations. If the total gate count grows like $2^{n/2}\\,\\mathrm{depth}(A)$, with $\\mathrm{depth}(A)$ exponential in $n$, then the claimed $O(\\sqrt d)$ computational cost is not realized as a gate cost; if the total count stays at $O(2^{n/2}\\,\\mathrm{poly}(n))$ for such families, the claim survives.","supporting_citations":[{"cited_title":"Quantum amplitude amplification and estima- tion,","cited_arxiv_id":null,"evidence_quote":"Supplies the quantum amplitude estimation algorithm and its $O(1/M)$ error bound, which Protocol 8 relies on for each amplitude estimate."},{"cited_title":"Practical characterization of quantum devices without tomography,","cited_arxiv_id":null,"evidence_quote":"Provides the complementary direct fidelity estimation construction whose $O(d)$ scaling motivates the new protocol."}],"review_version":1}