{"id":"da745ae0-a0c3-4a78-9c02-3945ac26536f","arxiv_id":"2608.06703","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Constant-depth quantum Fourier transform is possible iff constant-depth fanout is possible.","lead":"This paper proves a conditional equivalence: constant-depth quantum circuits can approximate the quantum Fourier transform only if they can also perform fanout, a qubit-copying gate. The result answers a 2006 open question and links constant-depth Shor-style circuits to the fanout resource.","discovery_kind":"unification","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. (2.18)-(2.23) drops the identity term of R_b; for exact QFT the two terms cancel and the claimed Omega(delta^2) felinity bound is false. Theorem 1.1's proof is incomplete even before relying on [GGJ26a].","rationale":"The paper's intended goal is clear: to show QFT_q in QAC^0 iff FANOUT_n in QAC^0 via a felinity reduction. The Hoyer-Spalek forward direction and the local Shor-case lemma are not the issue here. The load-bearing step is the proof of Theorem 1.1. On careful expansion, Eqs. (2.18)-(2.23) are not merely missing a bound; the leading terms cancel exactly in the ideal case. Since the proof must handle gQFT with delta arbitrarily close to 1, a construction that vanishes in that limit cannot yield a uniform Omega(delta^2) lower bound. This is an internal correctness risk independent of whether [GGJ26a] is true. The reader's weakest assumption, the unpublished felinity-to-fanout theorem, is also real and would need to be supplied, but the more immediate blocker is the written reduction itself. A conditional acceptance is still plausible because the flaw appears fixable by changing the reflection to 2P_b - I and rechecking the constants, and the overall strategy may be sound. Therefore I recommend keeping the reader's CONDITIONAL verdict rather than moving to accept or reject, but the conditions should explicitly require correcting the reflection step and making [GGJ26a] publicly verifiable.","tokens_in":6544,"tokens_out":21591,"duration_ms":198460,"concrete_test":"Symbolically expand Eq. (2.20) for b=0 with gQFT = QFT, q = 2^n, phi_y0 = QFT^dag|0>, and psi_q as in Lemma 2.1. Keep the identity term of R_0: the left side of Eq. (2.18) computes to 0, whereas Eq. (2.23) predicts >= 0.11. Run the same numerical check for n = 2 and n = 3 to confirm the cancellation. If the authors instead intend R'_b = 2P'_b - I, recompute Eqs. (2.18)-(2.23) with that sign and verify the lower bound; if it holds, the theorem may be repairable, but the current text is not.","verdict_should_be":"UNCHANGED","load_bearing_attack":"With R_b = I - 2|phi_yb><phi_yb|_A tensor |+_b><+_b|_{w1,w2}, the exact amplitude after QFT on the probe is <z_b|QFT R_b(|psi_q>|EPR>) = (1/sqrt(2))(<y_b|QFT|psi_q> - <y_b|QFT|phi_yb><phi_yb|psi_q>) = 0 because QFT|phi_yb> = |y_b>. Eq. (2.20) keeps only the 2P part of R_b and silently discards the identity term, which cancels it. This is not a small error: the two terms have the same O(1) magnitude, so the triangle-inequality step in Eqs. (2.19)-(2.23) is invalid. For gQFT arbitrarily close to QFT (delta near 1), the same cancellation can make the true amplitude arbitrarily small, contradicting the claimed uniform bound >= 0.11 sqrt(delta). The subsequent F_n >= Omega(delta^2) therefore does not follow from the written construction. This is the central mechanism connecting a delta-approximate QFT gate to felinity; without a corrected reflection (e.g., 2P_b - I) or a different branch-marking argument, Theorem 1.1 is unproven. The companion-paper dependency [GGJ26a] noted by the reader is a second independent gap, but the sign/cancellation error in this manuscript is more elementary and load-bearing.","agreement_with_reader":"partial"},"referee_report":null,"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe headline is that this note proves QFT_q in QAC^0 iff FANOUT_n in QAC^0, resolving the Fang et al. open question, and the proof is more believable than the stress-test suggests. The specific objection about Eq. (2.18)-(2.23) does not hold up: the identity term in R_b vanishes because the measured w-register state |1-b,b> is orthogonal to the EPR state. So the step from (2.19) to (2.20) is exact, not a dropped term. The algebra from there to the Omega(delta^2) felinity bound checks out.\n\nWhat's genuinely new: the reduction from a delta-approximate QFT gate to a non-negligible felinity state is a nice trick, and the companion result that high felinity implies fanout is the engine. The note also gives a clean local approximation of fanout for power-of-two moduli (Lemma 2.3), which is a useful addition for the NISQ discussion. The writing is clear and the logic is coherent.\n\nThe soft spot is exactly what the reader flagged: the engine is cited to [GGJ26a] (felinity-to-fanout) and the reflection/amplification tools to [GGJ26b]. Both are unpublished companion papers by the same group. Nothing in this note independently verifies those claims. That makes the result conditional rather than self-contained. It is not a fatal flaw in the reduction itself, but it means a referee cannot check the central step without the companions.\n\nMinor points: the notion of 'non-negligible fidelity' is weaker than the usual approximation, which is fine but should be explicit (it is). The appendix's exact QFT from fanout is a sketch, not a full proof. And the acknowledgement of ChatGPT is not an issue.\n\nBottom line: this is a serious paper worth a serious referee. If the companions are posted or their key theorems proven in the paper, I would accept it. As it stands, I would send it out but require the authors to make the dependencies publicly available.\n\nRecommendation: send to peer review, not desk reject. The stress-test's main objection is wrong.","headline":"Resolves the 2006 QFT/fanout question with a clean reduction, but the core felinity-to-fanout engine is in an unpublished companion paper; the stress-test's cancellation objection is wrong.","tokens_in":7407,"tokens_out":9252,"would_cite":true,"duration_ms":73218,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q12","81P68"],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"Constant-depth QFT exists only if fanout does.","keywords":["Shor's algorithm","Quantum Fourier transform","Fanout gate","QAC^0","Constant-depth quantum circuits","Felinity","Quantum complexity theory","NISQ"],"falsifier":"Produce a $\\mathsf{QAC}^0$ circuit family that approximates $\\mathsf{QFT}_q$ for some $q$ to non-negligible fidelity and, with the same techniques, a proof that $\\mathsf{FANOUT}_n\\notin\\mathsf{QAC}^0$; the paper's Theorem 1.1 says these two objects cannot coexist. A smaller-scale check is to simulate Lemma 2.3's circuit with an ideal $\\mathsf{QFT}_{2^n}$ on $n$ qubits and verify that the output fidelity to $|1\\cdots1\\rangle$ reaches $1-4^{1-k}$; a shortfall would show the circuit analysis is wrong.","tokens_in":6337,"feed_emoji":"⚛️","tokens_out":7870,"duration_ms":65840,"temperature":0.7,"pith_summary":"This paper establishes that an approximate constant-depth circuit for the quantum Fourier transform ($\\mathsf{QFT}_q$) can be converted, for any $n$-qubit modulus $q$, into a constant-depth circuit for the $n$-qubit fanout gate. Since the opposite direction was already known, the paper concludes that $\\mathsf{QFT}_q$ belongs to the constant-depth class $\\mathsf{QAC}^0$ if and only if $\\mathsf{FANOUT}_n$ does, resolving a 2006 open question about whether fanout is really necessary for constant-depth Fourier transforms. For the power-of-two modulus used by Shor's algorithm, the paper gives an explicit circuit: a single QFT on $2^n$ qubits plus $O(1)$ two-qubit local gates approximate fanout to arbitrary fixed precision. The result matters because it locates the genuine bottleneck for shallow quantum computation in the fanout operation rather than in the Fourier transform itself.","feed_headline":"Constant-depth QFT exists only if fanout does","feed_subtitle":"A short equivalence proof settles a 2006 question and ties Shor's NISQ feasibility to the fanout gate.","key_machinery":"The felinity functional $F_n(\\rho)=2\\sum_{y\\in\\{0,1\\}^n}\\langle y|\\rho|y\\rangle\\langle y|X^{\\otimes n}\\rho X^{\\otimes n}|y\\rangle$, which measures how much weight a state spreads between complementary bit strings, is the quantity that carries the argument. The proof engineers a state whose QFT has constant amplitude on two complementary frequencies, so after the approximate gate the state has non-negligible felinity; the cited bridge result then converts non-negligible felinity into constant-depth fanout. Two concrete pieces of machinery do the constructing: the Dirichlet kernel identity $D_q(L)=e^{i\\pi(L-1)/q}\\sin(L\\pi/q)/\\sin(\\pi/q)$, which gives the constant amplitudes, and, for $q=2^n$, a truncated version of the known constant-depth decrement gate, implemented with controlled-phase gates, which approximates fanout directly.","core_discovery":"The paper's central claim is Theorem 1.1: for any $q$ and $n=\\lceil\\log_2 q\\rceil$, if a $\\mathsf{QAC}^0$ circuit approximates $\\mathsf{QFT}_q$ to non-negligible fidelity $\\delta$ (at least a polynomial inverse in $n$), then $\\mathsf{FANOUT}_n$ is in $\\mathsf{QAC}^0$. Because the reverse direction—fanout to constant-depth QFT—is already known, the corollary is the equivalence $\\mathsf{QFT}_q\\in\\mathsf{QAC}^0\\iff\\mathsf{FANOUT}_n\\in\\mathsf{QAC}^0$. The proof constructs a product state whose ideal QFT has constant amplitude on two frequencies whose binary forms are complementary ($2^n-1$ and $2^n$), runs the approximate QFT alongside reflections about Fourier basis states, and extracts a state with felinity $\\Omega(\\delta^2)$; a cited companion result asserts that any $\\mathsf{QAC}^0$ circuit preparing an $n$-qubit state with felinity at least $n^{-c}$ implies $\\mathsf{FANOUT}_n\\in\\mathsf{QAC}^0$. For the Shor modulus $q=2^n$, Lemma 2.3 gives a depth-$k+2$ circuit that uses $\\mathsf{QFT}_{2^n}^\\dagger$, Hadamards, and $k$ controlled-phase gates to approximate $\\mathsf{FANOUT}_n$ to fidelity at least $1-4^{1-k}$.","pith_inferences":["If the cited felinity-to-fanout theorem is eventually proven, the same construction likely yields a quantitative tradeoff: a QFT approximation with fidelity $\\delta$ produces fanout with parameters controlled by $\\delta$, so hardware noise thresholds for the two operations should track each other.","The $\\Omega(\\delta^2)$ felinity bound could be tested numerically on small registers by applying the construction to simulated noisy QFT circuits; finding a faster decay would suggest the bound is loose.","A natural extension is to replace $\\mathsf{QFT}_q$ by more general constant-depth channels that approximate it, and ask whether the felinity-to-fanout implication survives under depolarizing or dephasing noise—this would give a NISQ-era 'requires fanout' statement per device.","Because the Shor-case circuit uses one QFT plus $O(1)$ gates, an experimental demonstration on a small register comparing the output fidelity to $1-4^{1-k}$ would directly expose whether a device's QFT gate is faithful enough to serve as fanout hardware."],"forward_implications":["If any constant-depth approximate QFT circuit exists, then constant-depth fanout exists, so quantum circuit lower bounds for fanout would immediately become lower bounds for approximate QFT.","For Shor's power-of-two modulus, a single $\\mathsf{QFT}_{2^n}$ plus $O(1)$ local two-qubit gates gives fanout to fidelity $1-4^{1-k}$, meaning NISQ devices with good constant-depth QFTs already have the raw material for fanout.","The approximation needed is only non-negligible fidelity $\\delta\\ge n^{-O(1)}$, far weaker than the standard $(1-\\varepsilon)$ approximation, so the equivalence covers very noisy QFT implementations.","The 2006 question of whether fanout is necessary for constant-depth QFT is answered affirmatively, conditional on the cited felinity-to-fanout theorem."],"supporting_citations":[{"why":"Supplies the load-bearing implication that QAC^0 preparation of a state with felinity at least $n^{-c}$ yields FANOUT_n in QAC^0; the proof's final step relies on it.","marker":"[GGJ26a]"},{"why":"Establishes the forward direction that fanout gives constant-depth QFT and provides the decrement-gate construction adapted in Lemma 2.3.","marker":"[HS05]"},{"why":"Makes the forward QFT-with-fanout construction exact by removing phase-estimation error, as detailed in Appendix A.","marker":"[MZ03]"},{"why":"Introduced the question of whether FANOUT_n belongs to QAC^0; the paper's equivalence targets this problem.","marker":"[Moo99]"},{"why":"Posed the open question of whether fanout is necessary for constant-depth QFT, which Theorem 1.1 answers.","marker":"[FFG+06]"},{"why":"Gives the logarithmic-depth lower bound for QFT with local gates, the contrasting baseline that motivates constant-depth approximations.","marker":"[CW00]"},{"why":"Provides the QAC^0 reflection and amplitude-amplification facts used in Lemma 2.2 and in the proof of Theorem 1.1.","marker":"[GGJ26b]"}],"fun_headline_variants":["Fanout is unavoidable for constant-depth QFT","Shor's algorithm needs the fanout gate","QFT and fanout are equivalent in constant depth","2006 QFT question answered: fanout required"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is an unpublished result from a companion paper: any constant-depth circuit that prepares a state with 'felinity' at least a polynomial inverse in $n$ can be converted into a constant-depth fanout circuit; if that conversion fails, the main equivalence collapses.","fun_headline_variants_meta":{"raw":{"variants":["Fanout is unavoidable for constant-depth QFT","Shor's algorithm needs the fanout gate","QFT and fanout are equivalent in constant depth","2006 QFT question answered: fanout required"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000629,"raw_usage":{"total_tokens":3004,"prompt_tokens":1136,"completion_tokens":1868,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":752,"completion_tokens_details":{"reasoning_tokens":1807}},"tokens_in":752,"tokens_out":1868,"duration_ms":15817,"temperature":1.0,"reasoning_tokens":1807,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T04:15:29.923706+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Produce a $\\mathsf{QAC}^0$ circuit family that approximates $\\mathsf{QFT}_q$ for some $q$ to non-negligible fidelity and, with the same techniques, a proof that $\\mathsf{FANOUT}_n\\notin\\mathsf{QAC}^0$; the paper's Theorem 1.1 says these two objects cannot coexist. A smaller-scale check is to simulate Lemma 2.3's circuit with an ideal $\\mathsf{QFT}_{2^n}$ on $n$ qubits and verify that the output fidelity to $|1\\cdots1\\rangle$ reaches $1-4^{1-k}$; a shortfall would show the circuit analysis is wrong.","supporting_citations":[],"review_version":2}