{"id":"a54d7a36-2b5a-4050-9513-c3076fc4d79f","arxiv_id":"2509.05710","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The query complexity of estimating a function of an unknown unitary under average bias is Θ(Rep_ε(f)), where Rep_ε(f) measures the L2 tail of the function beyond degree 2m polynomials.","lead":"An unknown unitary can be queried to estimate functions like trace, determinant, or representation matrix elements. This paper gives the tight number of queries needed on average and a generalized Hadamard test, claiming optimal sample counts under a PAC criterion.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"PAC optimality claims overreach: amplitude estimation in the paper's own query model improves the 1/ε² dependence to 1/ε, so Section 5.2's 'optimal' bounds are not optimal.","rationale":"Theorem 1 and the G-Hadamard construction appear internally consistent; the polynomial-degree lower bound is valid within the stated query model, and the average-bias characterization is a genuine contribution. The problem is the secondary PAC optimality claim. The paper's own complexity measure Q_{ε,δ} allows generalized queries, which include the coherent operations needed for amplitude estimation. Applying amplitude estimation to the unbiased estimator from Proposition 5 would reduce the ε-dependence from 1/ε² to 1/ε (with an extra log 1/δ), so the stated upper bounds are not optimal in ε. The only lower-bound connection provided, Fact 6, goes through the average-bias complexity and gives no Ω(1/ε²) PAC lower bound. Therefore the optimality claims in the abstract and Section 5.2 need to be either removed, restricted to fixed ε and δ, or replaced by bounds incorporating amplitude estimation. The reader's CONDITIONAL verdict already captures the need for revision, so no verdict change is recommended.","tokens_in":18006,"tokens_out":22416,"duration_ms":267864,"concrete_test":"Implement amplitude estimation on the G-Hadamard circuit for f(g)=g_{11} on d=2: replace the final computational-basis measurement by a QAE routine (with controlled reflections and value encoding), counting controlled-g gates. Simulate the number of controlled-g queries needed for ε ∈ {0.1, 0.05, 0.025} with δ=0.01. If the count scales as (1/ε) log(1/δ) rather than (1/ε²) log(1/δ), then the PAC upper bounds in Prop. 7 are not optimal and Section 5.2's optimality statements must be amended.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing weakness is in the PAC-optimality claims (abstract, Section 5.2), not in Theorem 1. Proposition 1 upper-bounds Q_{ε,δ}(f) as O(||A||_1^2 log(1/δ)/ε^2 · m) by Hoeffding concentration of the G-Hadamard unbiased estimator. But that estimator is produced by a coherent quantum circuit in the paper's own model (Definition 1); the same circuit can be used with standard quantum amplitude estimation. Amplitude estimation estimates the relevant measurement probabilities to additive error ε with O(1/ε) uses of the circuit, each use containing O(m) controlled-g queries, and can be repeated O(log 1/δ) times. Thus, for the functions in Section 5.2, the PAC query complexity is at most O(m log(1/δ)/ε), improving the ε-dependence. The lower bound Fact 6 only gives Q_{ε,δ}(f) ≥ B_{ε'}(f) with ε' = (2δ||f||_sup + ε)^2; for the polynomial examples it yields Ω(m) when ε,δ are fixed constants, but it provides no Ω(1/ε²) lower bound. Hence the claim that the Section 5.2 upper bounds are 'optimal' under PAC is not established, and is false if optimality is meant uniformly in ε. The average-bias Theorem 1 is not affected.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies estimation of an unknown unitary g∈U(d) using controlled-g queries, for a general target function f∈L²(U(d)). It defines B_ε(f) as the optimal query complexity under Haar-averaged squared bias, and Q_{ε,δ}(f) under the PAC criterion. The central result (Theorem 1) states B_ε(f)=Θ(Rep_ε(f)), where Rep_ε(f)=max{m : ||Q^⊥_{≤2m} f||²_{L2} ≥ ε}; the lower bound uses the polynomial method, and the upper bound uses a generalized Hadamard test that gives an unbiased estimator for any polynomial of degree at most m with O(m) queries. The paper then gives a PAC upper bound O(||A||₁² log(1/δ)/ε² · m) for a polynomial f expressed as a trace, with applications to monomials, the normalized trace, and entries of irreducible representations, and claims these upper bounds are PAC-optimal.","tokens_in":18366,"tokens_out":11247,"duration_ms":130670,"significance":"If Theorem 1 is correct, it gives a clean representation-theoretic characterization of average-case query complexity, with a lower bound that holds in a fairly powerful query model and an explicit unitary algorithm achieving the bound. The generalized Hadamard test is a useful primitive. However, the PAC-optimality claims are not supported: standard quantum amplitude estimation improves the ε-dependence in the same query model, so the abstract and Section 5.2 need qualification. The average-bias theorem is unaffected by this criticism.","major_comments":[{"comment":"The PAC 'optimal' claims are not established and, if meant uniformly in ε, are false. The estimator in Proposition 1 is produced by a coherent circuit (G-Hadamard); applying quantum amplitude estimation to that circuit estimates the relevant measurement probability to accuracy ε with O(1/ε) uses of the circuit, each use containing O(m) controlled-g queries, and O(log 1/δ) repetitions give Q_{ε,δ}(f)=O(m log(1/δ)/ε) for the functions in Section 5.2 (g_{11}^α, Tr g/d, irrep entries). This improves the ε^{-2} dependence in Section 5.2. Fact 6 gives only Q_{ε,δ}(f) ≥ B_{ε'}(f) with ε'=(2δ||f||_sup+ε)^2; for fixed ε,δ this supplies Ω(m) but no Ω(ε^{-2}) lower bound. Thus the statement that the Section 5.2 upper bounds are tight can at most mean optimality in the degree parameter for fixed ε,δ, not PAC optimality in ε. Theorem 1 is unaffected because amplitude estimation reduces statistical er","section":"Abstract; Section 5.2, Propositions 7–8, Fact 6"},{"comment":"The bounded-range claim for the G-Hadamard estimator is incorrect. In the proof of Estimation, the estimator takes values 4-(1+i), 4i-(1+i), and -(1+i), so its magnitude is not bounded by 1; for example |4-(1+i)|=√10. Consequently the unbiased estimator for f in Proposition 1 does not 'take values on the interval [−||A||₁, ||A||₁]' as claimed. The Hoeffding argument still works with C₀=c||A||₁ for a fixed constant c, so the stated O(||A||₁² log(1/δ)/ε²) scaling is unchanged up to constants, but the proof as written needs a corrected range bound.","section":"Proposition 1 proof"}],"minor_comments":[{"comment":"The displayed inequality uses d where α is meant: 'for any d∈N₀' should be 'for any α∈N₀'.","section":"Proposition 6 proof"},{"comment":"The first informal definition of Bias_G leaves the square implicit. Make the squared-bias convention explicit in both places to avoid confusion.","section":"Section 1.1.1 vs Definition 2"},{"comment":"The circuit diagrams are low-resolution and the labels (S^{-b}, C_n(g), C'_n(g), Toffoli structure) are hard to read. Please redraw them or add a more detailed textual description.","section":"Figures 1 and 2"},{"comment":"The abstract lists determinant among the applications, but Section 5.2 gives no explicit PAC determinant result. Specify whether determinant is treated only under the average-bias criterion, or add the corollary.","section":"Abstract / Section 5.2"},{"comment":"The scheme is said to use 4m₀ controlled-g operations, while a single Estimation call with m₀ uses 2m₀ queries. If the factor 4 is intentional (e.g., two calls for real and imaginary parts), this should be stated; the Θ result tolerates the constant, but the count should be justified.","section":"Proposition 5 proof"}],"recommendation":"major_revision","confidential_remarks":"The core average-bias characterization (Theorem 1) is sound and a worthwhile contribution. The main problem is the overstated PAC optimality: adding an amplitude-estimation comparison and rephrasing the optimality claims as degree-optimality for fixed ε,δ would resolve it. The range error in Proposition 1's proof is repairable. I would be willing to see a revised version."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe main theorem is the real contribution: B_ε(f)=Θ(Rep_ε(f)) for any f∈L^2(U(d)), where Rep_ε is the representation-theoretic projection tail. The lower bound via the polynomial method and the upper bound via the generalized Hadamard test are clean. I checked the claim that any m-query algorithm's expectation is a polynomial of degree at most 2m, and the G-Hadamard construction using mixed Schur-Weyl duality. Everything there is coherent. The result for matrix elements of irreps is new and fills a gap. This is a useful organizing result for function estimation on U(d).\n\nThe soft spot is the PAC section. The paper claims the O(1/ε²) bounds in Section 5.2 are optimal, but they are not: the same circuits can be fed to amplitude estimation, which estimates the relevant probabilities to error ε with O(1/ε) circuit applications, each using O(m) queries. So Q_{ε,δ}(f)=O(m log(1/δ)/ε) for the polynomial examples, improving the ε dependence. The lower bound via Fact 6 gives only Ω(Rep) for fixed ε,δ, never Ω(1/ε²). So 'optimal under PAC' is not established, and stated as uniformly in ε it is false. That does not affect Theorem 1, but it does change how the paper should be framed.\n\nThere is also a small technical error in Proposition 1's proof: the unbiased estimator outputs values like 3−i or −1+3i, so its range is about √10, not [−1,1]. The claim 'takes values on the interval [−∥A∥1, ∥A∥1]' is wrong; the final bound should have a constant factor, which is harmless, but it should be fixed.\n\nThe representation theory and query model definitions are solid. The lower bound even holds in a more powerful model allowing U, U*, and C-U*, which is a plus. The paper is honest about the difficulty of computing Rep_ε.\n\nOverall, worth refereeing. The core theorem deserves serious referee attention, and the paper should be acceptable after the PAC claims are tempered and the range bound corrected. I'd bring it to a reading group on quantum estimation or representation theory, with a note about the PAC overreach.","headline":"The average-bias query complexity theorem is solid and genuinely new; the PAC 'optimality' claims in Section 5.2 are not supported and should be rewritten.","tokens_in":18789,"tokens_out":5317,"would_cite":true,"duration_ms":57322,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"For any square-integrable function of a unitary, the optimal query count equals the size of its unreachable high-degree tail.","keywords":["unitary estimation","Hadamard test","sample complexity","Peter-Weyl decomposition","Schur-Weyl duality","PAC learning","quantum tomography","representation theory"],"falsifier":"Take $f(g)=\\det(g)$ on $U(d)$ with $d\\ge 3$ and fixed small $\\varepsilon$. The theorem predicts $B_{\\varepsilon}(f)=\\Theta(d)$. An explicit estimator that uses $o(d)$ controlled-$g$ queries while achieving Haar-averaged bias $< \\varepsilon$ would refute the lower bound; a search of existing determinant-estimation literature for such an estimator, or a construction of one, would settle it.","tokens_in":17951,"feed_emoji":"⚛️","tokens_out":6143,"duration_ms":61553,"temperature":0.7,"texified_at":"2026-08-05T20:25:43.924523+00:00","pith_summary":"The paper claims a complete answer to a basic question: given black-box access to a controlled version of an unknown $d\\times d$ unitary $U$, how many queries are needed to estimate any square-integrable function $f(U)$? The answer is that the minimum number of queries under Haar-averaged bias is exactly (up to constants) $\\operatorname{Rep}_{\\varepsilon}(f)$, a quantity that counts how much of $f$'s $L^2$ mass lives in high-degree irreducible components that no $m$-query algorithm can touch. This unifies tasks like estimating traces, determinants, and individual representation matrix elements under one framework. The same machinery yields sample-optimal PAC estimators for polynomial functions of the unitary.","texify_model":"deepseek-v4-flash","texify_usage":{"total_tokens":3490,"prompt_tokens":708,"completion_tokens":2782,"prompt_tokens_details":{"cached_tokens":0},"prompt_cache_hit_tokens":0,"prompt_cache_miss_tokens":708,"completion_tokens_details":{"reasoning_tokens":2043}},"feed_headline":"Exact query count for unitary functions equals the high-degree tail","feed_subtitle":"Estimating any square-integrable function needs Θ(Rep_ε(f)) queries, unifying trace, determinant, and representation entries.","key_machinery":"The quantity $\\operatorname{Rep}_{\\varepsilon}(f)$, defined via the orthogonal projection $Q_{\\leq 2m}^{\\perp}$ onto polynomials of degree $>2m$ in the entries of $g$ and $\\bar{g}$; the lower-bound argument that any $m$-query estimator's expectation lies in $Q_{\\leq 2m}$; and the G-Hadamard algorithm, a generalized Hadamard test that uses $2m$ controlled-$g$ queries to produce an unbiased estimate of any inner product of the form $\\langle \\phi | (\\bigoplus_{n,n'} g^{\\otimes n} \\otimes g^{* \\otimes n'} \\otimes I_E) | \\psi \\rangle$, allowing any polynomial of degree $\\leq m$ to be estimated with $m$ queries.","core_discovery":"The central claim is that $B_{\\varepsilon}(f)$, the minimum number of generalized queries needed to estimate $f$ with averaged squared bias below $\\varepsilon$, is $\\Theta(\\operatorname{Rep}_{\\varepsilon}(f))$, where $\\operatorname{Rep}_{\\varepsilon}(f)$ is the largest $m$ such that the projection of $f$ onto the orthogonal complement of the degree-$\\leq 2m$ polynomial subspace $Q_{\\leq 2m}(U(d))$ has $L^2$ norm at least $\\varepsilon$. In words: an estimator that uses $m$ queries produces an answer whose expectation is a polynomial of total degree at most $2m$ in the matrix entries of $g$ and $\\bar{g}$, so it cannot see the part of $f$ living in higher-degree Peter-Weyl sectors. The optimal strategy is therefore to approximate $f$ by its best degree-$2m$ polynomial projection and estimate that projection with a generalized Ha","pith_inferences":["The theorem suggests a general principle: in the Haar-averaged bias model, query complexity of estimating f is governed not by the complexity of f's evaluation but by the decay of its Fourier (Peter-Weyl) tail; one could test this against known algorithms for phase estimation and other tasks where the function has low-degree truncations.","The characterization might extend to other compact groups, e.g., the orthogonal or symplectic groups, where Peter-Weyl and Schur-Weyl analogues exist; the paper's proof structure is group-theoretic and would likely carry over, changing only the labeling of irreps.","The PAC-optimality results for specific functions rely on the L1 norm of the coefficient matrix A; finding smaller-norm representations of f could yield even better constants, suggesting a resource theory of representability for unitary functions.","The G-Hadamard test can be seen as a primitive for building unbiased estimators for arbitrary bounded functions via polynomial approximation; in practice, one might combine it with Fourier sampling over the unitary group to estimate f without classical polynomial truncation."],"forward_implications":["Estimating det(U) requires Θ(d) queries under small averaged bias, matching the new lower bound; trace requires only O(1).","Matrix elements of irreducible representations π_λ(g)_{i,j} have optimal query complexity Θ((m+m̄)/ε² · log(1/δ)) in the PAC model.","The framework gives a unified way to derive sample-optimal estimators for any continuous function on U(d), not just previously studied special cases.","The polynomial-degree lower bound extends to algorithms with access to U, U*, C-U* as well, so the characterization is robust to query-model extensions.","Full unitary tomography (Θ(d²) samples) is recovered as the special case where f is the whole matrix, showing why tomography is exponentially hard in qubits."],"supporting_citations":[{"why":"Supplies the polynomial method for quantum lower bounds, the template for the lower-bound argument.","marker":"[BBC+01]"},{"why":"Provides unitary property testing lower bounds by polynomials, the direct model for the lower-bound proof.","marker":"[SY23]"},{"why":"Peter-Weyl theorem, the basis for the L2 decomposition into irreducible matrix elements used throughout.","marker":"[PW27]"},{"why":"Gives the Schur-Weyl duality statement used in Fact 4 to relate tensor powers to irreducible representations.","marker":"[EGH+11]"},{"why":"Provides the Mixed Schur-Weyl duality used in Proposition 2 to characterize the polynomial subspace Q_{≤m}.","marker":"[BCH+94]"},{"why":"Supplies Haar moment calculations on compact groups, used to compute G(α,d) for the univariate examples.","marker":"[Mec19]"},{"why":"The standard Hadamard test that the generalized G-Hadamard algorithm extends.","marker":"[Chi]"}],"fun_headline_variants":["Optimal unitary queries: degree-2m tail decides all","Hadamard test generalized to any square-integrable f","Unitary functions: query count equals high-degree tail","Sample complexity for unitaries: tail of Peter-Weyl bounds","Exact query count for unitary functions is a tail sum"],"cache_read_input_tokens":2688,"weakest_assumption_plain":"The characterization relies on the query model in which each query applies only a degree-$1$ polynomial unitary in $g$ and $\\bar{g}$; if a query could instead apply a nonlinear function of $g$ directly, the polynomial degree bound (and the whole lower bound) would not hold.","fun_headline_variants_meta":{"raw":{"variants":["Optimal unitary queries: degree-2m tail decides all","Hadamard test generalized to any square-integrable f","Unitary functions: query count equals high-degree tail","Sample complexity for unitaries: tail of Peter-Weyl bounds","Exact query count for unitary functions is a tail sum"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000145,"raw_usage":{"total_tokens":1015,"prompt_tokens":740,"completion_tokens":275,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":484,"completion_tokens_details":{"reasoning_tokens":190}},"tokens_in":484,"tokens_out":275,"duration_ms":3993,"temperature":1.0,"reasoning_tokens":190,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-05T05:12:29.297751+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $f(g)=\\det(g)$ on $U(d)$ with $d\\ge 3$ and fixed small $\\varepsilon$. The theorem predicts $B_{\\varepsilon}(f)=\\Theta(d)$. An explicit estimator that uses $o(d)$ controlled-$g$ queries while achieving Haar-averaged bias $< \\varepsilon$ would refute the lower bound; a search of existing determinant-estimation literature for such an estimator, or a construction of one, would settle it.","supporting_citations":[],"review_version":1}