{"id":"e75d8dc0-b3ff-47e7-ba4f-2140010dc26c","arxiv_id":"2509.25345","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"All-to-all Hamiltonians can simulate any two-qubit gate in about 1/N time and any depth-D circuit in about D/√N time, with polynomially small error.","lead":"This paper proves that all-to-all interacting qubit Hamiltonians can implement quantum gates up to N times faster and general circuits up to √N times faster than the naive circuit-based estimate. The results set speed limits for quantum information spreading in long-range interacting systems and connect to the fast scrambling conjecture.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 1/N gate protocol depends on K-local interactions whose generation from 2-local Hamiltonians is explicitly left open in SM §7.1; the √N circuit speedup is unaffected.","rationale":"The reader's weakest assumption is the same load-bearing issue I would flag. The K-local Hamiltonian model is well-defined and the internal proof structure—Holstein-Primakoff bosonization, squeezed-state encoding, polynomial potential stabilization—is coherent; the √N randomized protocol is 2-local and its error analysis appears sound. The fragile step is the bridge from the K-local theorem to the pairwise-interaction framing of the abstract, and the paper explicitly disclaims this bridge in Section 7.1. This is a genuine limitation statement that must be weighed in the verdict, not an artifact of the review pipeline. My proposed check targets exactly that bridge: verify that a concrete 2-local Floquet drive produces the required K-body terms with the correct N^{2-k} normalization. Since the concern is acknowledged and does not affect the second main result, the existing conditional verdict remains appropriate; I do not recommend moving it further.","tokens_in":47685,"tokens_out":38702,"duration_ms":351866,"concrete_test":"Fix K=4 and simulate the two-body Floquet sequence proposed in SM §7.1, e^{-iT X^2} e^{-iT Y^2} with T=1/N, on N=32,64,128 qubits. Numerically compute the Floquet–Magnus effective Hamiltonian (or the stroboscopic unitary) and extract the coefficient of a representative 3-body term such as X_i Y_j Z_k; check whether the per-coupling coefficient scales as N^{-1} = N^{2-k}. Then check whether truncating at order 4 reproduces the H_S, H_CD, and H_DCZ gadgets used in Theorem 3.1 with per-gate error decaying as 1/poly(N). If the coefficients scale differently, or the expansion fails to converge before the required order, the physical realizability of the O(1/N) protocol by 2-local all-to-all interactions is not established.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The headline O(1/N) two-qubit-gate speedup (Theorem 1 / SM Theorem 3.1) is proven for K-local all-to-all Hamiltonians of the form (1.2), with K a sufficiently large constant. The abstract frames the result as applying under 'each pair of qubits interacts with O(1) strength,' but the paper does not prove that the required K-body terms, with the specific N^{2-k} normalization, can be generated from pairwise 2-local couplings. SM §7.1 gives only a heuristic Floquet/Magnus argument: Eq. (7.1)–(7.2) suggest convergence at constant order for T≤c'/N, and then state verbatim that 'it is unclear whether the desired form of K-local Hamiltonians like in Theorem 3.1 could be generated by a 2-local protocol.' If this generation fails, the 1/N two-qubit gate, the multiply-controlled Toffoli/GHZ/W corollaries, and the tight-Lieb-Robinson saturation result do not apply to pairwise all-to-all platforms (trapped ions, cavities), which is the physical motivation of the abstract. The √N circuit speedup (Theorem 5) is 2-local and does not inherit this fragility. A secondary presentation issue is that Theorem 1 states 'any K≥2' while the error (3.2) is not polynomially small until K is chosen large relative to 1/δ_T; the large-K caveat appears only in prose after Eq. (2).","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the computational power of time-dependent all-to-all Hamiltonians. Its first main result (Theorem 1) claims that any two-qubit gate can be simulated in time O(1/N) up to an N^δ factor with polynomially small error, using K-local all-to-all Hamiltonians with a specific N^{2-k} normalization; corollaries include fast preparation of GHZ and W states, fast multiply-controlled Toffoli gates, and saturation of Lieb-Robinson bounds for strongly long-range interactions. Its second main result (Theorem 5) proves that any depth-D quantum circuit can be simulated in time O(D/√N) with constant space overhead and polynomially small average error, using only 2-local interactions and randomized on-site fields. The proofs in the Supplemental Material are detailed and self-contained, including explicit error estimates, truncation bounds for the Holstein-Primakoff mapping, and normalization checks for the Hamiltonians.","tokens_in":48022,"tokens_out":4787,"duration_ms":44968,"significance":"If the central results hold in the form stated, they would establish a polynomial speedup of Hamiltonian evolution over circuit depth for all-to-all architectures, which is a significant conceptual advance in Hamiltonian complexity. The paper's strengths include unusually detailed and self-contained proofs, explicit polynomial error bounds for the 1/N protocol, a fully 2-local randomized √N-speedup protocol, an exact Mølmer-Sørensen-type two-qubit gate in O(1/√N) time, and a tightness argument for a known Lieb-Robinson bound. However, the headline 1/N result is proved only for K-local Hamiltonians with K sufficiently large, and the generation of such K-local terms from 2-local pairwise interactions is explicitly left open in the Supplemental Material. The √N result is 2-local and does not inherit this fragility, so the paper contains a substantial robust contribution even if the 1/N claims are restricted.","major_comments":[{"comment":"The O(1/N) two-qubit-gate result is proved only for K-local all-to-all Hamiltonians of the form (1.2), with K a sufficiently large constant, and not for pairwise 2-local Hamiltonians. SM §7.1 explicitly states: \"it is unclear whether the desired form of K-local Hamiltonians like in Theorem 3.1 could be generated by a 2-local protocol.\" Since the abstract and introduction frame the result as applying when \"each pair of qubits interacts with O(1) strength,\" there is a load-bearing gap: Corollaries 2, 3, and 4, together with the Lieb-Robinson saturation claim, inherit this unresolved assumption. The authors should either prove that the assumed K-local terms can be generated from pairwise couplings with the same normalization, or restrict all O(1/N) claims to the K-local model and state clearly that the pairwise-interaction case remains open.","section":"Abstract; SM §7.1, Eq. (1.2)"},{"comment":"The statement of Theorem 1, \"For any constants δ_T∈(0,1) and locality K≥2,\" is incompatible with the displayed error bound ε = N^{2−δ_T(√K−1)/2}. For fixed K such as K=2 and small δ_T, the exponent is positive and the error grows with N, so the bound is not polynomially small. The text after Eq. (2) acknowledges that a sufficiently large K is needed, but this condition is absent from the theorem statement and from the abstract. The theorem should be restated with the explicit condition that K is chosen large enough relative to δ_T (or the claim should be weakened accordingly).","section":"Theorem 1; SM Theorem 3.1, Eqs. (2) and (3.2)"}],"minor_comments":[{"comment":"The notation Z_i for a Fourier-transformed data-qubit operator conflicts with the notation Z_i for the i-th ancilla qubit in other parts of the paper; using a different symbol would improve readability.","section":"Eq. (6.29)"},{"comment":"In the bound of Lemma 2.2, the condition |α|>5e^{|ζ|} is stated, but the proof text occasionally suppresses the dependence of constants on |ζ|; making the constant dependence explicit would help the reader verify the uniformity claimed in later uses.","section":"SM §2.2, Lemma 2.2"},{"comment":"The phrase \"polynomially small error\" is used in Theorem 1 and Corollaries without always specifying whether the exponent is uniform in the other parameters; this should be made uniform and explicit, especially because the error exponent in (3.2) depends on K.","section":"Throughout"},{"comment":"The space-for-time tradeoff claims that the time T can be made to vanish by choosing N≫N_d, but the normalization (1.2) depends on N_tot; the sentence could acknowledge that fixing the total qubit count and increasing N necessarily reduces N_d, so the statement is an asymptotic tradeoff rather than a literal vanishing time for fixed N_tot.","section":"Corollary 3"}],"recommendation":"major_revision","confidential_remarks":"The paper is carefully written and the proofs appear unusually detailed, but the abstract and Theorem 1 currently overclaim the 1/N speedup for pairwise all-to-all systems. The authors themselves acknowledge the K-locality generation problem in SM §7.1. This is fixable by reframing the claims or resolving the generation question, and the 2-local √N result is a solid independent contribution. I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here is my take. This is a serious, unusually detailed theory paper. The genuinely new thing is that all-to-all Hamiltonians beat the naive circuit-depth simulation by a polynomial factor: O(1/N) for a CZ gate (up to N^δ) and O(D/√N) for arbitrary circuits. Prior work on global gates reached constant time or O(log N), so these are real improvements, and the √N speedup uses only 2-local Hamiltonians, which makes it the cleanest result in the paper.\n\nThe paper earns credit for the supplemental material: the proofs are self-contained, with explicit error bounds, and the derivations do not reduce to the author's earlier heuristic protocol. The Lieb-Robinson tightness corollary is a nice byproduct. The citation pattern is fine; the earlier heuristic is cited as motivation and the formal proofs stand independently.\n\nNow the soft spots. The abstract says 'assuming each pair of qubits interacts with O(1) strength,' but the O(1/N) gate simulation (Theorem 1 / SM Theorem 3.1) needs K-local all-to-all Hamiltonians with the specific N^{2-k} normalization. The paper does not prove that those K-body terms can be generated from 2-local couplings; SM §7.1 sketches a Floquet/Magnus argument and then says explicitly it is unclear. That is a genuine gap for the physical platforms named in the abstract (trapped ions, cavities), which are pairwise. The √N speedup does not inherit this problem, and I would say the central scaling claims are likely correct under the stated assumptions.\n\nTwo smaller presentation issues. Theorem 1 states 'any K≥2' but the displayed error is only polynomially small once K is large relative to 1/δ_T; the large-K caveat appears only in prose after the theorem. And the abstract's phrase about an 'operational proof of the fast scrambling conjecture' oversells what is proven: the paper gives a constructive saturation of known bounds, not a general proof of the conjecture.\n\nWho is this for: researchers in Hamiltonian complexity, quantum simulation, and long-range interacting systems. A reader interested in the √N speedup can trust that part; a reader planning to use the 1/N gate speedup should check whether their platform can realize the required K-local terms.\n\nMy recommendation: yes, this deserves a serious referee. I would send it to review with the expectation of revision: make the abstract and Theorem 1 match the K-locality caveat, and clearly separate the 2-local circuit speedup from the K-local gate speedup. The core ideas and proofs are strong enough that these issues are fixable.","headline":"Serious, detailed theory paper with two real speedups; the √N circuit speedup is solid, while the 1/N gate result needs a clear caveat about K-local realizability.","tokens_in":48547,"tokens_out":2736,"would_cite":true,"duration_ms":24692,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"All-to-all Hamiltonians can simulate any two-qubit gate in O(1/N) time and any depth-D circuit in O(D/√N), polynomially beating circuit-by-circuit simulation.","keywords":["all-to-all Hamiltonians","quantum circuit simulation","Holstein-Primakoff transformation","Mølmer-Sørensen scheme","Lieb-Robinson bounds","fast scrambling","Hamiltonian quantum computation"],"falsifier":"Simulate or derive the effective Hamiltonian of a Floquet/Magnus sequence built from 2-local couplings and check whether its K-body coefficients obey the $N^{{2-k}}$ normalization with a constant K; if the required K-local Hamiltonian cannot be generated this way, then Theorem 3.1's O(1/N) gate protocol does not apply to pairwise-coupled platforms. A complementary numerical test is to implement the Theorem 3.1 pulse sequence for N≈$10^{3}$ to $10^{4}$ with locality K=4 or 6 and verify that the error follows the claimed $N^{{-δ_T(√K-1)/2}}$ decay rather than saturating at a constant.","tokens_in":47459,"feed_emoji":"⚛️","tokens_out":9452,"duration_ms":77428,"temperature":0.7,"pith_summary":"The paper argues that programmable all-to-all Hamiltonians, in which every pair of qubits can interact with O(1) strength, can process quantum information far faster than the standard circuit simulation, where each gate takes O(1) time. Its first result shows that a two-qubit gate can be realized in O(1/N) time on N qubits, up to an N^δ overhead and with polynomially small error, by using K-local couplings and treating the ancilla ensemble as a squeezed bosonic mode. This immediately yields O(1/N)-time generation of GHZ states, W states, and multiply-controlled Toffoli gates, and shows that a known Lieb-Robinson speed limit for strongly long-range interactions is tight. Its second result shows that any depth-D circuit can be simulated in O(D/√N) time by a randomized 2-local Hamiltonian protocol with constant space overhead, giving an operational proof of fast scrambling for dense Hamiltonians. If correct, the paper establishes that interaction time, not circuit depth, is the right complexity measure for all-to-all platforms.","feed_headline":"All-to-all Hamiltonians run gates in 1/N time","feed_subtitle":"One two-qubit gate costs O(1/N) evolution time; any depth-D circuit runs in O(D/√N).","key_machinery":"The central object is the Dicke manifold of the N ancilla qubits: the permutation-symmetric subspace behaves as a large semiclassical spin, and near its north pole the Holstein-Primakoff transformation maps it to a boson mode with position x̂=(B+B†)/√2. The 1/N protocol squeezes this boson, displaces it conditionally on a data qubit, reverses the squeezing to amplify the signal, and then applies a potential V(x̂) that is flat at the two displaced wavepackets, imprinting a π/2 phase in time ~1/N; truncating the boson operators to polynomial order K produces the K-local Hamiltonian. The √N protocol uses a Mølmer-Sørensen-style sequence (a four-pulse trapped-ion scheme in which qubits acquire a geometric phase from a shared bosonic mode) whose phase-space trajectory returns the ancillae to their initial state while accumulating a geometric phase proportional to Z0Z−1, and a Fourier transform of the ancilla operators focuses O($N^{2}$) weak couplings into O(N) couplings of strength √N. Suzuki product formulas upgrade the primitive to polynomially small error, and a worst-case-to-average-case reduction with random on-site Pauli rotations removes the restriction to typical inputs.","core_discovery":"On the paper's own terms, the central discovery is that all-to-all Hamiltonians are polynomially stronger than all-to-all quantum circuits per unit time. Theorem 3.1 proves that a controlled-Z gate (and hence any two-qubit gate) can be simulated with error $N^{{2-δ_T(√K-1)/2}}$ in time T≤$N^{{-1+δ_T}}$ using K-local all-to-all interactions with the normalization $N^{{2-k}}$ per k-body term; Theorem 5 proves that any depth-D circuit is simulated with error $cD^{2}$ $N^{{-2κ}}$ in time T≤ĉ $N^{{-1/2+δ_T}}$ D using 2-local interactions and random on-site fields. From these follow O(1/N)-time preparation of GHZ and W states and the multiply-controlled Toffoli gate, a matching of the strongly long-range Lieb-Robinson bound T=Ω($N^{{α/d-1}}$), and an operational proof of the fast-scrambling conjecture for dense Hamiltonian ensembles. The proofs rely on non-commuting Hamiltonians rather than on parallelizing commuting gates: squeezing, controlled displacement, geometric phases, and Fourier focusing of spin-wave modes.","pith_inferences":["Inference: If pairwise-only platforms cannot realize the required K-local terms, the 1/N speedup might still survive heuristically through 2-local squeezing protocols like the author's earlier GHZ encoding; a direct numerical test on ~10^3 qubits would distinguish a genuine scaling advantage from a proof artifact.","Inference: The space-for-time tradeoff suggests a general resource theory for Hamiltonian computation in which ancillary qubits function as a clock or bus; this may be relevant for error correction or near-term devices where decoherence sets a hard time budget.","Inference: The Fourier-focusing trick is not tied to circuit simulation and could be adapted to other distributed tasks, such as preparing graph states or implementing non-local gates in modular quantum processors, though the paper does not explore these applications.","Inference: The fast-scrambling implication is testable in current all-to-all platforms by measuring out-of-time-ordered correlators at times ~1/√N or ~1/N; if the predicted scrambling times are observed, the paper's model of Hamiltonian computation would be validated experimentally."],"forward_implications":["GHZ states, W states, and multiply-controlled Toffoli gates can be produced in O(1/N) time with constant space overhead, roughly N times faster than previous global-gate constructions.","Any depth-D circuit can be simulated in O(D/√N) time using only 2-local all-to-all couplings plus randomness, so a Shor-style factoring computation would run in Hamiltonian time ~√N rather than circuit depth Θ(N).","The strongly long-range Lieb-Robinson bound for α