{"id":"2ec6c3b6-4901-4b6c-843f-f4b2f0d592c2","arxiv_id":"2607.26478","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"One-query lower bounds for permutation and alternating-basis phase unitaries, plus a constant-approximation one-query algorithm for complex phase unitaries.","lead":"This paper proves that certain explicit families of quantum unitaries—permutations and alternating phase/Hadamard layers—cannot be implemented by quantum circuits making only one query to a classical oracle, even though two-query algorithms exist. It introduces new cryptographic games that yield these lower bounds and sharpen separations between one-query synthesis and quantum programs.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the one-query normal form is an external dependency but appears correctly applied.","rationale":"The reader's acceptance with moderate confidence is appropriate. The central claim is supported by detailed arguments: the search-game reductions are sound, the matrix concentration bounds for permutations (via combinatorial matrix sums) and for F2HF1 (via two-stage Rademacher series) are correctly parameterized, and the upper bound for phase unitaries provides a useful contrast. The weakest point is indeed the one-query normal form, but it is a cited, standard result and the paper's use of it is faithful. No internal error was found. Therefore, I agree that the verdict should remain ACCEPT, and no adjustment is needed.","tokens_in":624,"tokens_out":12489,"duration_ms":449373,"concrete_test":"Independently re-derive the one-query normal form for the search game from [LMW24, Cor 3.34], verifying that (i) any one-query algorithm can be expressed as V, O_f, measurement by absorbing the post-query unitary into the projectors, and (ii) the workspace dimension bound log M ≤ n + ℓ + log K holds for the search-game setting. If a counterexample to either point exists, the spectral bound in Lemma 6.1 may not apply to all adversaries.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The lower bounds for Theorems 5.1 and 5.2 rely on the reduction from unitary synthesis to the oracle state search game (Lemma 4.6) and on the spectral relaxation (Lemma 6.1). Lemma 6.1 assumes the LMW24 one-query normal form for search adversaries: an isometry V, a phase oracle O_f, and a projective measurement. This normal form is cited from [LMW24, Cor 3.34] rather than proved here. If it were incomplete, the matrix concentration bounds would only apply to a subset of one-query adversaries. However, the normal form is standard, and the adaptation to the search game is straightforward (absorbing any post-query unitary into the measurement). I found no internal inconsistency; the remaining dependencies are cited prior work rather than errors in this paper.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies one-query unitary synthesis lower bounds. It introduces the oracle state search game and the oracle Choi state game, and proves that one-query adversaries fail to win these games for two natural low-randomness families: states built from random permutation unitaries P (via P H|k>) and states built from random alternating phase unitaries F_2 H F_1 (via F_2 H F_1 H|k>). These search bounds are used to infer one-query synthesis lower bounds for related unitary families, giving separations between one-query and two-query synthesis. The paper also gives a one-query constant-correctness algorithm for arbitrary complex phase unitaries, and a quantum-advice lower bound for the phase-state search game, plus a simplified proof of the LMW24 one-query lower bound for Haar-random unitaries.","tokens_in":55756,"tokens_out":35880,"duration_ms":341560,"significance":"If the results hold as stated, the paper makes a substantial contribution: it extends one-query unitary synthesis lower bounds from Haar-random unitaries to explicit, low-randomness families that admit two-query algorithms, thereby demonstrating the power of adaptivity. The new search/Choi game framework is flexible and likely to be reused, and the paper ships fully explicit proofs with concrete matrix-concentration estimates. The matching upper bound for phase unitaries and the quantum-advice lower bound add further value. The main caveat is that the reduction from search hardness to synthesis hardness contains a quantitative error (fidelity vs. overlap) and the connection to the headline 'permutation' and 'F_2 H F_1' synthesis statements is not explicitly justified; both are fixable.","major_comments":[{"comment":"The proof claims that if the output state has fidelity at least η with |k> (or |Ψ_EPR>), then the measurement outcome k (or EPR acceptance) occurs with probability at least η. With the standard fidelity used in Definition 3.6 and Proposition 3.8, fidelity equals the square root of the overlap, so the success probability is at least η², not η. Consequently, a search bound of δ only rules out synthesis correctness greater than √δ, and the same factor applies to the Choi-game reduction. The lemmas and the derived quantitative synthesis statements (e.g., the informal Theorems 1.1/1.2 and the last sentence of Lemma 4.6) need to be corrected. The qualitative separation survives, but the stated bounds change.","section":"§4.1, Lemma 4.6; §4.2, Lemma 4.10"},{"comment":"The formal theorems (Theorems 5.1 and 5.2) are search-game bounds for the state families P H|k> and F_2 H F_1 H|k>. The informal synthesis theorems claim lower bounds for synthezing random permutation unitaries P and alternating unitaries F_2 H F_1. The unitary that maps P H|k> to |k> is H P^{-1}, not P; the unitary that maps F_2 H F_1 H|k> to |k> is H F_1 H F_2, not F_2 H F_1. The paper does not state or prove that one-query synthesis for permutations (resp. F_2 H F_1) implies one-query synthesis for these relative families. This closure is true (post-compose with H and use the inverse/renaming), but it is load-bearing and should be made explicit.","section":"§1.2, §5, and §4.1"},{"comment":"In bounding ||Π_Win |Φ_1>||², the text obtains (t−2)/N, but a direct norm calculation gives (t−2)/K: the sum over k ∈ {0,1}^n contributes a factor N that cancels the 1/N in the normalization. Since K ≤ N, the displayed bound is too strong. The subsequent 4t/K conclusion still holds if the term is (t−2)/K, so this appears to be a typo rather than a fatal flaw, but it should be corrected.","section":"§10.3, Lemma 10.5"}],"minor_comments":[{"comment":"The phrase 'Ω(1)-approximate in diamond distance' is misleading: the formal guarantee is constant correctness (fidelity) of 1/4 or 1/2, which only implies diamond distance ≤ √(1−η) ≈ 0.87 or 0.71. The formal Theorem 5.5 statement is clearer; the abstract should align with it.","section":"Abstract and §1.2, Theorem 1.5"},{"comment":"The notation [K] is used both as {0,1,...,K−1} and as a key set that excludes 0. This is a source of small off-by-one ambiguities; a cleaner notation such as K∗ for the nonzero key space would help.","section":"§7.2"},{"comment":"The statement of Corollary 8.1 uses 'F1,...,f_t' in the proof while the theorem states f_1,...,f_t; the typesetting of subscripts should be made uniform.","section":"§8.7"},{"comment":"The relationship between 'correctness' η and standard fidelity should be stated explicitly, especially given the Lemma 4.6 issue. A one-line clarification that F is the standard fidelity would prevent ambiguity.","section":"§3.1, Definition 3.6"},{"comment":"The Choi-state permutation proof in Appendix C is dense; several norm bounds are asserted with 'basic properties' and would benefit from a few more intermediate steps. This does not affect the main text.","section":"§C.3, parameter estimates"}],"recommendation":"major_revision","confidential_remarks":"The paper is technically strong and the framework is promising, but the review found two load-bearing fixable issues: (i) the search-to-synthesis reduction overstates the success probability by a square (η vs η²), and (ii) the headline synthesis claims require an unstated closure argument to connect the formal search bounds to the families named in the abstract. Both are local to specific lemmas/sections, and the qualitative results appear sound after correction. I therefore recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThis is a strong paper, and I agree with the reader's accept verdict. The main new results are one-query lower bounds for synthesizing random permutation unitaries and alternating-basis phase unitaries F2 H F1, both families having two-query algorithms. That cleanly separates one-query from two-query synthesis. The oracle state search game and its Choi-state variant are a genuine departure from the pseudorandomness approach of LMW24, and the paper even shows why that older approach fails for these families (the distinguishing attack in Theorem 5.4). The upper bound for complex phase unitaries is also new and useful, as it explains why the lower-bound technique cannot extend to that family. The appendix gives a simplified proof of the LMW24 one-query lower bound, an extension to F2 U0 F1 for small-entry U0, and a quantum-advice lower bound for phase states with a matching algorithm.\n\nThe proofs are explicit and traceable. The main theorems reduce to matrix concentration inequalities (Rademacher series and combinatorial matrix sums) and the parameters check out. I spot-checked Sections 6–8 and found no gaps. The paper is also honest about its main external dependency: the LMW24 one-query normal form (Corollary 3.34) is cited, not proved, and it is load-bearing for all lower bounds. That is a standard result and appears correctly applied, but the dependency is real.\n\nMinor soft spots: the lower bounds are for random instances—'explicit' in the title means the families have efficient two-query algorithms, not that they are fixed deterministic families. The phase-unitary upper bound achieves only constant correctness (fidelity 1/4 in general, 1/2 for fourth roots), so the diamond-distance guarantee is a constant bounded away from 1; 'constant-approximate' is accurate but not high-precision. The Choi-game appendix is dense, and I did not verify every inequality there, but what I read is consistent with the main framework.\n\nWho this is for: anyone working on unitary synthesis, quantum query complexity, or quantum cryptography that uses unitary synthesis hardness. The search game is a new tool that will likely be reused. The paper deserves a serious referee and should go to review; I would be surprised if the main theorems are wrong.\n\nBest.","headline":"Solid and important: new lower bounds for one-query unitary synthesis via a flexible search-game framework, with a clean external dependency on LMW's normal form.","tokens_in":56159,"tokens_out":3824,"would_cite":true,"duration_ms":45650,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","68Q17"],"pacs":["03.67.Lx","03.67.Dd"],"model":"deepseek-v4-flash","headline":"Random permutation unitaries and alternating-basis phase unitaries cannot be synthesized with a single classical query, even though two queries suffice.","keywords":["unitary synthesis","one-query algorithms","quantum query complexity","permutation unitaries","phase unitaries","oracle search game","quantum advice","matrix concentration"],"falsifier":"A concrete one-query algorithm that synthesizes random permutation unitaries (or F₂ H F₁ unitaries) with success probability 1/poly(n) for every permutation would directly contradict the main theorems. Conversely, an explicit adversary that wins the oracle state search game for the permutation state family with probability significantly larger than O(log²M logK / K) would falsify the key spectral bound underlying the proof.","tokens_in":55483,"feed_emoji":"⚛️","tokens_out":4546,"duration_ms":52688,"temperature":0.7,"pith_summary":"This paper proves that some quantum unitaries with simple two-query algorithms cannot be implemented with just one query to a classical oracle. Specifically, random permutation unitaries and unitaries built from two random phase layers separated by a Hadamard transform are shown to resist every efficient one-query algorithm. To establish this, the authors introduce an oracle state search game, where an adversary must identify a hidden index from a single quantum state after one query; hardness of this game is shown to imply synthesis hardness. The same game yields a simpler proof of an existing one-query lower bound for Haar-random unitaries, a constant-correctness one-query algorithm for complex phase unitaries, and a quantitative separation between one-query synthesis and quantum-advice programs.","feed_headline":"One query is not enough for permutation unitaries","feed_subtitle":"Random permutation and alternating-phase unitaries resist one-query synthesis, proving a query-count separation.","key_machinery":"The central object is the oracle state search game, in which a challenger samples a random key k, sends the state |ψ_{R,k}⟩ to the adversary, and the adversary must output k after one query to an oracle that may depend on R but not on k. Hardness of this game implies hardness of unitary synthesis via a fixed normal form for one-query algorithms: an isometry V, a single phase-oracle query, and a projective measurement. The analysis uses a weight-vector decomposition that writes V|ψ_{R,k}⟩ as a rescaling of a fixed unit vector, reducing the search winning probability to the squared spectral norm of a random matrix M_R = (1/√K) Σ Π_k D_{R,k}. Concentration of this matrix is then controlled by t","core_discovery":"The paper's central claim is a separation between one-query and two-query unitary synthesis for explicit, structured families. It proves that for a uniformly random permutation π, no one-query algorithm with workspace dimension M can synthesize the permutation unitary P|x⟩ = |π(x)⟩ with more than O(log²M logK / K) success on the associated search game, and similarly for unitaries F₂ H F₁ with random Boolean phases F₁, F₂, the success is at most O(log M · log(MN) / K). Because both families have clean two-query synthesis algorithms, these bounds establish that the extra query is strictly necessary. The proofs proceed by reducing synthesis hardness to the oracle state search game, then applyin","pith_inferences":["The search-game formulation suggests that one-query synthesis hardness of a unitary family is governed by a single-copy state-identification problem, which may be easier to analyze than pseudorandomness for structured families; this heuristic could be applied to other families, such as unitaries with small circuit depth or low entanglement.","The constant-correctness algorithm for complex phases indicates a sharp boundary: the hardness is specific to binary-phase oracles, so any separation for complex phases must rely on a mechanism beyond the standard approximation-rule-out arguments.","The quantum-advice lower bound and the matching algorithm imply that the advantage of a one-query oracle over an S-qubit quantum program is essentially a factor of S in the success probability for this task; testing whether the same tightness holds for permutation unitaries or F₂ H F₁ would further clarify the role of quantum advice in synthesis.","The Choi state game's connection to quantum bit commitment suggests that these lower bounds double as security proofs for quantum cryptographic primitives; future work might extract explicit commitment schemes from the hardness of the search game for other unitary families."],"forward_implications":["One-query and two-query unitary synthesis are separated for explicit, structured families, showing that adaptivity in the number of oracle queries is a real resource in quantum unitary synthesis.","The oracle state search and Choi state games provide a flexible framework that re-derives the known one-query hardness for Haar-random unitaries with simpler proofs, and extends to families that are not fully random.","Complex phase unitaries admit a one-query algorithm with constant correctness, so binary and complex phase oracles are equivalent up to a constant approximation factor; this explains why approximation-rule-out lower bounds cannot apply to complex phases.","The quantum-advice lower bound (success ≤ O(S/K) with S advice qubits) sharply separates one-query synthesis from quantum programs for phase states, with a matching algorithm up to logarithmic factors.","The one-query hardness extends to any number of alternating layers F_t H ... F₂ H F₁, with a reduction to the t=2 case; the paper proposes that proving t-query hardness for larger t would resolve the full unitary synthesis conjecture."],"fun_headline_variants":["One query not enough for permutation unitaries","Explicit unitaries separate one-query from two-query","Two queries beat one for structured unitaries","Query separation: explicit unitaries need two calls","Unitary synthesis gap: one vs two queries"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The lower bounds assume that every one-query algorithm can be represented as a fixed isometry, a single phase-oracle query, and a projective measurement; if some one-query algorithm escapes this normal form, the spectral relaxation and all derived bounds would not apply to it.","fun_headline_variants_meta":{"raw":{"variants":["One query not enough for permutation unitaries","Explicit unitaries separate one-query from two-query","Two queries beat one for structured unitaries","Query separation: explicit unitaries need two calls","Unitary synthesis gap: one vs two queries"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000243,"raw_usage":{"total_tokens":1464,"prompt_tokens":938,"completion_tokens":526,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":682,"completion_tokens_details":{"reasoning_tokens":454}},"tokens_in":682,"tokens_out":526,"duration_ms":5317,"temperature":1.0,"reasoning_tokens":454,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T14:55:36.354870+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete one-query algorithm that synthesizes random permutation unitaries (or F₂ H F₁ unitaries) with success probability 1/poly(n) for every permutation would directly contradict the main theorems. Conversely, an explicit adversary that wins the oracle state search game for the permutation state family with probability significantly larger than O(log²M logK / K) would falsify the key spectral bound underlying the proof.","supporting_citations":[],"review_version":1}