{"id":"a4b71c4f-0c32-491a-8058-666d905c836f","arxiv_id":"2607.28402","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Nearly optimal size–depth–ancilla tradeoffs are given for quantum oracles of general, partial, and sparse Boolean functions, matching counting lower bounds up to log factors.","lead":"The paper gives nearly optimal quantum-circuit recipes that turn classical Boolean functions into quantum oracles, trading spare qubits against gate count and depth. These recipes matter because oracle cost often dominates quantum algorithms and QROM.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly identified the main soft spot (existence of linear hash families with stated load, used non-uniformly) and correctly judged it standard rather than disqualifying. Independent review of the three constructions and the matching lower bounds did not surface a deeper algebraic or resource-accounting error that would change size/depth by more than log factors inside the claimed ancilla windows. Omissions (uncompute steps, Theorem 34 sketch, constant cleanup) are ordinary for this genre and appear fillable without asymptotic damage. Therefore the ACCEPT / HIGH confidence verdict stands; no adjustment is warranted.","tokens_in":17016,"tokens_out":505,"duration_ms":131134,"concrete_test":"Expand one full iteration of the m<n case in the proof of Theorem 1 (steps 1–4 plus the implicit U† uncompute, un-zero, and σ_S uncompute) on a concrete n=4, m=1, p=2 instance; verify unitarity and that the input register is restored on both A=0 and A=1 branches while the target receives exactly σ_S∧f_S.","verdict_should_be":"UNCHANGED","load_bearing_attack":"After checking the central constructions (Lupanov regrouping + conditionally clean ancilla for Theorem 1; linear hashing + decision-tree bins for Theorem 3; X-separating hashes + batched membership + sequential AND for Theorem 4) against the counting lower bounds (Theorems 15–17), no correctness gap that would overturn the stated asymptotics was found. The m<n case of Theorem 1 omits explicit uncomputation, but the compute–U–write–U† sandwich restores inputs on the A=0 (dirty) path because U† undoes any action of U. Fact 9’s 0-ancilla log-depth fan-out is slightly overstated for dirty targets, yet m≥1 is always available in the main theorems and restores the log-depth bound. Non-uniform hash matrices (reader’s weakest assumption) are standard in non-uniform circuit complexity and are only required to exist, which the probabilistic method supplies. Sparse “nearly optimal” holds fully only for d=Ω(n); the paper already notes this in related work. None of these points is load-bearing against the central claims.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper gives nearly optimal size–depth–ancilla tradeoffs for quantum oracles of three Boolean-function families under a constant-size, constant-width gate set (e.g. Clifford+T). For total functions f:{0,1}^n→{0,1}^b and 1≤m≤Θ(2^n/n) ancilla it achieves size O(b 2^n/log(n+m)) and depth O(b 2^n/(n+m)) (Theorem 1), with a corollary for reversible maps. For partial oracles of effective support d it gives size O(n log d+bd) and a matching depth–ancilla tradeoff for Θ(log d)≤m≤Θ(d) (Theorem 3). For sparse oracles with |f^{-1}(1)|=d it gives size O(n² log d + nd/log(log d+m/n)) and depth O(n² log n log d/(n+m)+log n+nd/m) for Θ(log n+log d)≤m≤Θ(nd/log d), with a further logarithmic improvement when Θ(n) extra ancilla are available (Theorems 4 and 34). Matching Shannon-style counting and light-cone lower bounds (Theorems 15–17) show the bounds are asymptotically tight up to logarithmic factors in the stated ancilla regimes. Constructions combine Lupanov regrouping, conditionally clean ancilla, linear hashing (including JKZ25 max-load), decision-tree parallelization, and X-separating hash families with batched membership checks.","tokens_in":17187,"tokens_out":1485,"duration_ms":34937,"significance":"Boolean oracles and QROM are recurring bottlenecks in Hamiltonian simulation, cryptanalysis, and data-intensive quantum algorithms; worst-case size/depth/ancilla tradeoffs with matching lower bounds have been incomplete. The work essentially closes the general-total and reversible cases over a broad ancilla range (improving on folklore, Lupanov translations, and Zakablukov’s reversible bounds), and substantially extends the sparse/partial regimes of ZLY22/ZY24 down to near-logarithmic ancilla. Strengths include independent counting lower bounds, fully constructive upper bounds built from standard primitives (fan-out/fan-in, log-depth n-Toffoli), and explicit comparison tables. Results are non-uniform (hash matrices exist by the probabilistic method and are hardwired), which is standard for this complexity model and does not undercut the asymptotic claims. If the stated tradeoffs hold, they are directly usable as black-box resource estimates in algorithm design.","major_comments":[{"comment":"Abstract and Theorem 4 claim size/depth are “asymptotically optimal up to logarithmic factors” over the full stated ancilla range. The matching lower bound (Theorem 17) is Ω(d(n−log d)/log min{W,d(n−log d)}). When d=o(n) the leading upper-bound term O(n² log d) from computing κ=n+1 hash maps (proof of Theorem 4, §6.1) does not match this lower bound; the paper itself notes near-optimality “when d=Ω(n)” only in related work (§1.2). The abstract, Theorem 4 statement, and the optimality sentence after Theorem 34 should restrict the “nearly optimal” claim to d=Ω(n), or quantify the gap for smaller d.","section":"Abstract; Theorem 4; §1.2; §6.1"},{"comment":"In the m<n case of Theorem 1 (§4.3), the construction computes σ_S, conditionally zeros the first p inputs via fan-out, runs f_S treating those wires as ancilla, then writes A∧B into the target. The write-up does not spell out uncomputation of f_S and restoration of the p input wires on the A=0 path. A standard compute–U–write–U† sandwich works (U† restores dirty ancilla when A=0), but this should be written explicitly so that clean-ancilla semantics (Definition 8) and the claimed size/depth are verified rather than left implicit.","section":"§4.3, proof of Theorem 1"}],"minor_comments":[{"comment":"Abstract opening: “the study focusing at quantum circuit optimization of such oracle is yet closed” is ungrammatical; intended meaning is that the question remains open. Same sentence appears in the introduction.","section":"Abstract; §1"},{"comment":"Fact 9 claims 0-ancilla O(log n)-depth fan-out. Standard dirty-target constructions need a clean workspace or recursive doubling with temporary space; since all main theorems have m≥1 this is harmless, but the fact should state the precise ancilla model or cite the 1-ancilla log-depth version.","section":"§2.2, Fact 9"},{"comment":"Table 1 header “Fourier expansion∗ / Not full reversible logic” is easy to miss; a short footnote clarifying that the O(2^n) Fourier circuit is not a standard clean oracle would help.","section":"Table 1"},{"comment":"Lemma 31 (sequential AND of oracles) is a useful primitive; a one-line remark that it is essentially a low-width “OR of zeros” counter would aid readers implementing it.","section":"§6.1, Lemma 31"},{"comment":"Several “we omit here” constant-factor and log b depth improvements (§4.3 end, §5.2 end) are fine for asymptotics but could be collected in a short appendix remark for implementers.","section":"§4.3; §5.2"},{"comment":"Typos/notation: “tradeoffs” consistently vs “tradeoffs”; “effective” hyphenation; Corollary 2 ancilla “n+1≤m” vs table “n<m”; arXiv ID line “30 Jul 2026” looks like a placeholder year.","section":"Throughout; Corollary 2; Table 2"}],"recommendation":"minor_revision","confidential_remarks":"The technical core is sound and the contribution is real for quant-ph algorithm-resource estimation. Non-uniform hashes are not a defect in this model. I would not block on the sparse d=o(n) gap if the authors simply qualify the optimality language. Fit for a solid theory/algorithms venue is good; borderline “accept” vs “minor revision” depends on how strictly the journal polices claim precision in abstracts."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This is the clean resource-tradeoff paper the Boolean-oracle literature has needed. For general total functions they give, across the whole window 1 ≤ m ≤ Θ(2^n/n), size O(b 2^n / log(n+m)) and depth O(b 2^n/(n+m)), matching the Shannon-style counting lower bounds up to logs; the same style of nearly-tight surface is pushed down to logarithmic ancilla for partial and sparse oracles. Tables 1–2 make the comparison with Lupanov, Zakablukov, ZLY22/ZY24 explicit, so you can see exactly what was missing.\n\nWhat is new is the complete surface, not any single trick. They glue Lupanov regrouping to the conditionally-clean-ancilla idea from their own NZS24 Toffoli work for the m < n regime, linear hashing plus parallel decision-tree bins for partial functions, and X-separating hashes plus batched membership plus a low-width sequential AND for sparse functions. The lower-bound lemmas are standard counting plus light-cone and are specialized correctly. I walked the recurrences at the asymptotic level; they close.\n\nSoft spots are real but proportionate. The hash matrices (Lemmas 24–25, 28–29) are non-uniform existence statements via the probabilistic method; the circuits do not construct them. That is normal non-uniform circuit complexity and does not break the claims, but anyone who needs explicit hashes will pay a load penalty. Theorem 34 is only a sketch, constant-factor cleanup is omitted, and the “nearly optimal” slogan for sparse oracles is fully tight only when d = Ω(n)—which the paper already notes. Fact 9’s 0-ancilla fan-out is slightly loose for dirty targets, but m ≥ 1 is always present in the main theorems so the log-depth bound is restored. None of these overturn the central asymptotics.\n\nThis is for people who actually budget Toffoli/T depth and ancilla inside QROM, SELECT, or Hamiltonian simulation. Citation pattern is honest; self-cites supply primitives, not the target tradeoff. I would send it to referees without hesitation and would cite the general and sparse statements myself.","headline":"Solid constructive paper that actually closes the size–depth–ancilla surface for Boolean oracles; asymptotics check out and the gaps are ordinary for the genre.","tokens_in":17858,"tokens_out":552,"would_cite":true,"duration_ms":9868,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","81P68"],"pacs":[],"model":"grok-4.5","headline":"Any Boolean function has a quantum oracle whose size and depth nearly match information-theoretic limits once you dial the ancilla count.","keywords":["quantum circuits","Boolean oracles","ancilla tradeoff","QROM","partial Boolean functions","sparse Boolean functions","circuit depth","reversible computing"],"falsifier":"Exhibit a concrete family of n-bit Boolean functions (or a sparse/partial instance) whose minimal quantum-oracle size or depth, for some m in the claimed range and a fixed constant-width gate set, exceeds the stated upper bound by more than a polylog factor, or prove a matching lower bound that already includes those logs.","tokens_in":17859,"feed_emoji":"⚛️","tokens_out":931,"duration_ms":20659,"temperature":0.7,"pith_summary":"Quantum algorithms often need a classical Boolean function wired into a reversible circuit, and the cost of that wiring can dominate the whole algorithm. This paper shows how to build those oracles so that size, depth, and spare qubits trade off nearly optimally for three standard families: fully general functions, functions that only matter on a small support, and functions that are 1 on only a few inputs. For a general n-bit function the size drops like 2^n over log of the ancilla budget, and the depth drops like 2^n over the total width; matching lower bounds say you cannot do much better. The same style of tradeoff is given for partial and sparse oracles down to only logarithmic ancilla. The constructions are meant to be drop-in subroutines for QROM, lookup tables, and any quantum algorithm that must embed classical data.","feed_headline":"Quantum Boolean oracles hit near-optimal size and depth","feed_subtitle":"Dial the spare qubits and the circuit cost tracks the information-theoretic floor up to logs","key_machinery":"Lupanov-style regrouping of the algebraic normal form (compute every small Boolean function once, then fan it out) combined with linear hashing that shortens or separates the effective support, plus conditionally clean ancilla so that input wires can be reused as workspace.","core_discovery":"With m ancilla qubits in the stated ranges, any total Boolean map {0,1}^n to {0,1}^b admits a quantum oracle of size O(b 2^n / log(n+m)) and depth O(b 2^n /(n+m)); partial maps of effective support d and sparse maps of true-input size d admit analogous nearly tight size-depth-ancilla tradeoffs. All upper bounds match simple counting lower bounds up to logarithmic factors inside those ancilla windows.","pith_inferences":["If explicit constructions of the linear hashes with the same load bounds become available, the partial and sparse circuits become fully uniform without changing the asymptotics.","The same batching-plus-conditionally-clean-ancilla pattern should apply to other classical subroutines (sorting networks, arithmetic) that must run inside a quantum circuit.","When T-count is already near-optimal, the remaining Clifford volume is now the quantity these tradeoffs directly shrink."],"forward_implications":["QROM and classical lookup tables can be compiled with asymptotically smaller Toffoli/T depth once spare qubits are available.","Reversible n-bit permutations inherit the same nearly optimal size O(n 2^n / log(n+m)) and depth O(n 2^n /(n+m)) for n < m ≤ Θ(2^n/n).","Hamiltonian-simulation and cryptanalysis routines that treat the oracle as a black box can now budget concrete size-depth-ancilla numbers instead of worst-case folklore circuits.","With only Θ(log d) ancilla a partial oracle of support d still has linear size in n log d + b d, so low-ancilla regimes remain usable."],"fun_headline_variants":["Near-optimal size-depth-ancilla tradeoffs for quantum Boolean oracles","Quantum Boolean oracles match counting lower bounds up to logs","Ancilla windows yield nearly tight circuits for Boolean quantum oracles","Total partial and sparse Boolean maps get near-optimal quantum oracles","Dial ancillas and quantum Boolean oracle cost tracks the information floor"],"cache_read_input_tokens":128,"weakest_assumption_plain":"The partial and sparse constructions assume linear hash matrices with the claimed collision and load bounds are already known; the circuit size does not pay for finding them.","fun_headline_variants_meta":{"raw":{"variants":["Near-optimal size-depth-ancilla tradeoffs for quantum Boolean oracles","Quantum Boolean oracles match counting lower bounds up to logs","Ancilla windows yield nearly tight circuits for Boolean quantum oracles","Total partial and sparse Boolean maps get near-optimal quantum oracles","Dial ancillas and quantum Boolean oracle cost tracks the information floor"]},"model":"grok-4.5","effort":"low","cost_usd":0.005823,"raw_usage":{"total_tokens":1677,"prompt_tokens":951,"num_sources_used":0,"completion_tokens":92,"cost_in_usd_ticks":58228000,"prompt_tokens_details":{"text_tokens":951,"audio_tokens":0,"image_tokens":0,"cached_tokens":256},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":634,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":951,"tokens_out":92,"duration_ms":11804,"temperature":1.0,"reasoning_tokens":634,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-31T08:26:57.364758+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"Exhibit a concrete family of n-bit Boolean functions (or a sparse/partial instance) whose minimal quantum-oracle size or depth, for some m in the claimed range and a fixed constant-width gate set, exceeds the stated upper bound by more than a polylog factor, or prove a matching lower bound that already includes those logs.","supporting_citations":[],"review_version":1}