{"id":"0f0ee54e-4795-417e-85b1-bba33df9019c","arxiv_id":"2504.14841","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Provable (sub)exponential quantum-classical query separation for discrete and continuous optimization, achieved by compiling the GHV adiabatic separation into plain adiabatic evolution and quantum Hamiltonian descent.","lead":"This paper constructs families of discrete and continuous optimization problems where every classical algorithm needs exponentially many queries, yet simple quantum algorithms (plain adiabatic evolution and quantum Hamiltonian descent) find the optimum in polynomial time. It compiles a known quantum-classical separation for adiabatic quantum computing into standalone objective functions, giving provable (sub)exponential quantum speedup for optimization in the oracle model.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Continuous extension rests on Claim 10.6 imported from overlapping preprint ZLLW24; if its λ-uniform splitting, reflection, and concentration bounds fail, Lemma 10.5 and Theorem 10.2 collapse.","rationale":"The reader's verdict of CONDITIONAL is caused by the same load-bearing assumption I would flag: the continuous separation imports Claim 10.6 from [ZLLW24], a preprint with overlapping authorship, and the entire error analysis of Lemma 10.5 and Theorem 10.2 rests on its quantitative bounds. I checked the internal reductions for the discrete theorem and found them explicit and carefully parameterized; the perturbative lemmas (Sections 5–9) are worked out in sufficient detail to be auditable, and the classical-hardness reduction via oracle simulation is sound. The continuous construction's bD analysis is detailed and the use of reflection symmetry and concentration is internally consistent, but only conditional on Claim 10.6. I do not see a new independent flaw that would move the verdict away from CONDITIONAL: the concern is exactly the one identified by the reader, so no change to the verdict is warranted. A positive resolution would require a standalone verification of Claim 10.6; absent that, CONDITIONAL is the appropriate status.","tokens_in":60935,"tokens_out":11652,"duration_ms":105843,"concrete_test":"Independently re-derive Claim 10.6 from first principles (or extract and audit the proof of [ZLLW24, Theorem 4.22]) and check that the following hold uniformly for all λ≥c log n: (a) µ1(bX)-µ0(bX)=2/Λ with Λ=e^{λ/6(1±o(1))}; (b) the reflection identity (10.44); (c) ⟨b0|b0⟩_{[-1,w]}≤O(Λ^{-2/3}) for some fixed w∈(0,1/2). A complementary computational check: for λ=2^k with k up to about 30, solve the two-endpoint boundary-value problem for bX on [-1,1] by a high-order finite-difference or spectral method, compute Λ=2/(µ1-µ0) and the wrong-well probability, and verify the scaling exponents −1/6 and −2/3 to within a few percent. If the exponents are weaker, redo the parameter choice (10.29)–(10.30) to see whether δ(λ)≥1/poly(n) and ε≤δ/n^{Ω(1)} still admit λ0=Θ(log n).","verdict_should_be":"UNCHANGED","load_bearing_attack":"The discrete Theorem 4.1 is a self-contained reduction from the GHV oracle separation, with all perturbative steps explicitly proved in Sections 5–9. The continuous Theorem 10.2, however, depends on Lemma 10.5, which in turn depends on Claim 10.6, imported from [ZLLW24, Theorem 4.22]. Three quantitative properties are load-bearing: (i) the spectral gap of bX(λ)=-d²/dξ²+λ²f_dw is 2/Λ with Λ=e^{λ/6(1±o(1))}; (ii) the exact reflection symmetry (10.44) of |b0⟩,|b1⟩; (iii) the concentration bound ⟨b0|b0⟩_{[-1,w]}≤O(Λ^{-2/3}) in (10.45). These feed Claims 10.7 and 10.8, which control the block decomposition of bH and give ε≤O(√nΛ^{-1/6}∥D∥) in Lemma 10.5. The parameter regime λ0=Θ(log n) in (10.29)–(10.30) is chosen so that ε and the exponentially small 1/Λ terms are below 1/poly(n); if any of the exponents or constants in Claim 10.6 have hidden λ- or n-dependencies, the spectral-gap lower bound δ(λ)≥1/poly(n) and the closeness n^{-Ω(1)} in Theorem 10.2(ii) may fail. Because [ZLLW24] is an overlapping-author preprint with no formal verification or independent implementation, this is the least secure step in the chain. The rest of the continuous proof, including the construction of bD and the reduction from f-queries to D-queries, appears consistent once Claim 10.6 is granted.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper constructs oracle-based families of optimization problems for which it claims provable exponential quantum-classical query separation. For discrete optimization, Theorem 4.1 reduces the GHV stoquastic adiabatic separation to a linear Hamiltonian path H(t)=(1-t)H_TFI+tD, where H_TFI is a transverse-field Ising Hamiltonian and D is diagonal, and shows that plain adiabatic evolution solves the problem in poly(n) time while any classical algorithm needs exp(n^{Ω(1)}) queries. The proof is a sequence of perturbative reductions: sparse stoquastic paths to hypercube paths (Lemma 4.3), hypercube paths to TFD paths (Lemma 4.4), piecewise-linear interpolation (Lemma 4.5), a toy TFI ground-state shifter (Lemma 4.6), linearization via a clock register (Lemma 4.7), and a tilt-and-extension step (Lemma 4.8). For continuous optimization, Theorem 10.2 embeds the discrete construction into Schrödinger operators H(t)=-Δ+ν(t)g(x)+t f(x), with ν(t)=e^{-Θ(√t)}, yielding a Quantum Hamiltonian Descent speedup. The continuous proof depends on Lemma 10.5, whose error analysis in turn depends on Claim 10.6, a set of spectral, symmetry, and concentration properties of the double-well operator bX(λ), imported from the overlapping preprint [ZLLW24].","tokens_in":61289,"tokens_out":15945,"duration_ms":148528,"significance":"If the results are correct, this is a substantial contribution: it provides the first provable exponential quantum-classical separation for optimization in the oracle model using the plain adiabatic algorithm and QHD, with hardness inherited from the GHV separation. The discrete part is a significant technical achievement: the perturbative reductions in Sections 5–9 are explicit, preserve an inverse-polynomial spectral gap, preserve classical hardness, and are stated in reusable form in Propositions B.1 and B.2. The paper also ships detailed proofs rather than relying on numerical experiment. The main caveat is that the continuous result is not self-contained at a load-bearing point: Claim 10.6 is taken from an overlapping-author preprint, and the current manuscript does not prove the quantitative bounds that feed Lemma 10.5 and Theorem 10.2. With that claim supplied or independently verified, the significance is high; as it stands, the continuous theorem is conditional on an external source.","major_comments":[{"comment":"The continuous half of the paper rests on Claim 10.6, which is imported from [ZLLW24, Theorem 4.22] rather than proved in this manuscript. The three quantitative properties in the claim—the spectral gap 2/Λ with Λ satisfying (10.16), the reflection identity (10.44), and the concentration bound (10.45)—are exactly the inputs to Claims 10.7 and 10.8, and they control the error ε≤O(√nΛ^{-1/6}∥D∥) in Lemma 10.5 and hence the gap and fidelity statements in Theorem 10.2(ii). If any of these bounds carries a hidden λ- or n-dependence, the estimates δ(λ)≥1/poly(n) and the n^{-Ω(1)} closeness in Theorem 10.2(ii) may fail. Because [ZLLW24] is an overlapping-author preprint, this is not an independent verification. Please include a self-contained proof of Claim 10.6, or state it from a peer-reviewed source with explicit uniform-in-λ constants for λ≥λ0=Θ(log n). As written, Theorem 10.2 is valid only conditionally on that external claim.","section":"§10.3, Claim 10.6 and Lemma 10.5"},{"comment":"The displayed estimate for ⟨bx|bDp|bx⟩ reads \"≤⟨x|D|x⟩⟨ex|ex⟩−2∥˚x∥∥D∥\"; this inequality is not implied by the preceding line, since the two cross terms can have either sign and the triangle inequality gives an upper bound with a plus sign, not a minus sign. The final O(√nΛ^{-1/3}∥D∥) bound is still recoverable by applying the triangle inequality to obtain both upper and lower bounds, but the proof as printed is mathematically incorrect. Please correct the inequality and explicitly state both bounds.","section":"§10.4, proof of Claim 10.10(i)"}],"minor_comments":[{"comment":"The notation d^kΛ/dλ^k = (e^{λ/6})^{1±o_k(1)} for k∈N is not a well-defined definition of Λ; please state precisely what is assumed for each fixed k, whether the o_k(1) terms are uniform in the regime λ≥λ0, and how these derivative bounds are used in the estimates for ν(t), ν̇(t), and ν̈(t).","section":"§10.3, Eq. (10.16)"},{"comment":"The first sentence contains the typo \"impiclitly\"; it should read \"implicitly\".","section":"Appendix B"},{"comment":"Weyl's inequality is cited to a Wikipedia article [Wik25]; please use a standard textbook or published reference for this classical result.","section":"References"},{"comment":"The informal Theorem 1.2 states T,t_f=poly(n), while the formal Theorem 10.2 states t_f=poly(n,1/η); please align the two statements.","section":"Theorem 1.2 vs Theorem 10.2"},{"comment":"The text calls the reflection symmetry in (10.44) a \"newfound symmetry property,\" but Claim 10.6 attributes it to [ZLLW24, Theorem 4.22]; please clarify what is new in this paper versus what is imported.","section":"§2.6"}],"recommendation":"major_revision","confidential_remarks":"The overlap with [ZLLW24] is substantive: two authors overlap, and Claim 10.6 is stated as being taken from that preprint. I recommend asking the authors to either include a full proof of Claim 10.6 or to point to a peer-reviewed version, as this is the least secure step in the continuous theorem. The discrete result, conditional on the cited GHV separation, appears technically sound and is the stronger contribution as written."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know: the discrete half of this paper looks like a genuine advance. Leng, Wu, Wu, and Zheng take the GHV oracle separation and compile it, through a chain of explicit perturbative reductions, into a standalone optimization problem solved by the plain adiabatic algorithm. That was not in GHV, and the technical machinery here—edge-subdivision gadgets, linearization via a clock register, path tilt and extension—is new and mostly well argued. The spectral gap and hardness preservation steps in Sections 5–9 are coherent, and the discrete result is anchored to the external GHV benchmark rather than to the authors' own prior work.\n\nThe continuous half is also real, but it is conditional in a specific place. The reduction from TFD Hamiltonians to Schrödinger operators relies on Lemma 10.5, which in turn imports Claim 10.6 from ZLLW24, an overlapping-author preprint. Three quantitative facts are load-bearing: the 2/Λ spectral gap of the double-well operator, the exact reflection symmetry of |b0⟩ and |b1⟩, and the O(Λ^{-2/3}) concentration bound. If any of these has a hidden λ- or n-dependence, the ε ≤ O(√n Λ^{-1/6}‖D‖) estimate in Lemma 10.5 collapses and Theorem 10.2 does not follow. The paper does not re-prove these bounds, and the stress-test note identifies exactly this as the least secure step. That is the correct concern, and it is the reason a referee rather than a desk rejection is needed.\n\nEverything else in the continuous part appears consistent once Claim 10.6 is granted. The bD construction and the new error analysis that avoids the trivial 2^n Λ^{-1/3} bound are a genuinely nice piece of work. The classical-hardness argument in Theorem 10.2(i) is compressed, but the query-to-query reduction is straightforward and I would not call that a soft spot.\n\nOne minor note: no code or machine-checked proofs, which is normal for a theory paper, and the self-citation of ZLLW24 is not itself a flaw—but it does mean the load-bearing claim lacks independent verification.\n\nWho this is for: researchers in quantum algorithms and complexity, especially anyone working on adiabatic optimization, oracle separations, or QHD. It deserves a serious referee. My recommendation: send it to peer review, assign a referee who knows the ZLLW24 inner-workings, and ask that referee to verify Claim 10.6 and the bD error analysis before accepting.\n\nI would bring this to a reading group and cite it in my own work. Not because I'm fully convinced of the continuous half, but because the discrete result alone is a notable step and the continuous framework is worth engaging with even if the imported lemma needs patching.","headline":"Discrete half is a genuine reduction-based advance; continuous half is a real but conditional result resting on an unproved claim imported from an overlapping preprint—worth refereeing with that flag.","tokens_in":61830,"tokens_out":1636,"would_cite":true,"duration_ms":17722,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","68Q12","90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that two plain quantum optimization algorithms — adiabatic evolution and quantum Hamiltonian descent — can have (sub)exponential query advantage over any classical algorithm.","keywords":["quantum adiabatic optimization","oracle separation","exponential quantum speedup","quantum Hamiltonian descent","transverse field Ising Hamiltonian","Schrödinger operator encoding","perturbative gadgets","continuous optimization"],"falsifier":"Compute the two lowest eigenvalues of $-\\frac{d^2}{d\\xi^2}+\\lambda^2(\\xi^2-1/4)^2$ on $[-1,1]$ with vanishing boundary conditions for large $\\lambda$ and check that the gap is $2/\\Lambda$ with $\\Lambda=e^{\\lambda/6(1\\pm o(1))}$ and that $\\langle b_0|b_0\\rangle_{[-1,w]}\\le O(\\Lambda^{-2/3})$; failure of any of these at increasing $\\lambda$ would invalidate the error estimate $\\varepsilon\\le O(\\sqrt{n}\\,\\Lambda^{-1/6}\\|D\\|)$ in Lemma 10.5.","tokens_in":60731,"feed_emoji":"⚛️","tokens_out":7329,"duration_ms":61768,"temperature":0.7,"pith_summary":"This paper tries to establish that optimization, both discrete and continuous, is a setting where quantum computation can provably beat every classical algorithm by an exponential gap in the oracle-query model. It constructs families of objective functions whose global minimum is hard for any classical method to find, yet is reached in polynomial time by the plain adiabatic algorithm (discrete case) and by quantum Hamiltonian descent (continuous case). If the construction is right, it settles the open question of whether such separations exist in optimization, and it does so without exotic modifications of the algorithms: only the natural linear Hamiltonian path and the Schrödinger operator evolution are used.","feed_headline":"Provable (sub)exponential quantum speedup for optimization","feed_subtitle":"Adiabatic and QHD find optima in poly time where classical methods need exponential queries.","key_machinery":"The argument is carried by a chain of perturbative reductions. Starting from a stoquastic sparse adiabatic path with inverse-polynomial spectral gap, edge-subdivision gadgets embed its interaction graph into a hypercube, and then a second-order reduction maps it to a transverse-field diagonal Hamiltonian of the form $-\\sum_i a_i X_i + D(t)$; a toy TFI Hamiltonian acting as a unary clock linearizes the path, and a small tilt extends it so that it starts as a pure TFI Hamiltonian and ends diagonal. For the continuous setting, the key object is the double-well operator $\\hat X(\\lambda)=-\\frac{d^2}{d\\xi^2}+\\lambda^2(\\xi^2-1/4)^2$, whose first two eigenstates form symmetric/antisymmetric pairs $|b_0\\rangle,|b_1\\rangle$ concentrated on one side of the well; the new error analysis shows that a diagonal Hamiltonian $D$ can be represented as a continuous function $\\hat D$ over the box with error $\\mathrm{poly}(n)\\Lambda^{-\\Omega(1)}$ rather than the naive $\\Theta(2^n)$ bound.","core_discovery":"The central claim is Theorem 4.1: for every $n$ there is an $n$-qubit transverse-field Ising Hamiltonian $H_{\\mathrm{TFI}}$ and a family of diagonal Hamiltonians $D$ such that the linear path $H(t)=(1-t)H_{\\mathrm{TFI}}+tD$ has exponential quantum advantage. Any classical algorithm must use $\\exp(n^{\\Omega(1)})$ queries to find the diagonal entry $u$ minimizing $\\langle u|D|u\\rangle$, while the path keeps spectral gap $n^{\\Omega(1)}$ and norm $\\mathrm{poly}(n)$, and simulating the Schrödinger dynamics for $T=\\mathrm{poly}(n)$ yields a state $n^{-\\Omega(1)}$-close to $|u\\rangle$ with $\\mathrm{poly}(n)$ queries and gates. The continuous analogue (Theorem 10.2) transfers the same separation to functions $f$ on a bounded box, where the QHD-type dynamics $H(t)=-\\Delta+t f(x)+\\nu(t)g(x)$ with $\\nu(t)=e^{-\\Theta(\\sqrt{t})}$ finds the minimizer in polynomial time while classical query algorithms require exponentially many queries.","pith_inferences":["Because the separation is oracle-based, converting it into an unconditional complexity-class separation would require additional structure; removing the oracle is a natural next test of the framework.","The continuous construction suggests that QHD's advantage in this setting is driven by the adiabatic gap and the concentration of the double-well encoding, not by non-adiabatic higher-energy exploration; this could be tested by replacing $\\hat X$ with other spectrally similar operators and checking whether the speedup persists.","The linearization gadget is essentially a quantum tunneling chain through a clock register; this may be reusable to turn other walk-based quantum speedups into optimization speedups.","The continuous result inherits the cited double-well spectral bounds; an independent re-derivation of Claim 10.6 with explicit $\\lambda$-dependencies would make the error analysis self-contained and easier to verify."],"forward_implications":["Any classical query algorithm for the constructed discrete family needs $\\exp(n^{\\Omega(1)})$ queries even to reach $1/\\mathrm{poly}(n)$ accuracy, so no classical black-box method can match the adiabatic algorithm on these instances.","The plain linear-path adiabatic evolution suffices for the speedup; the construction needs only the standard mixer $D$ plus a fixed TFI starting Hamiltonian, not problem-specific or nonlocal mixers.","The continuous construction gives the first provable super-polynomial quantum-classical separation for continuous optimization, carried by quantum Hamiltonian descent dynamics.","The reductions preserve an inverse-polynomial spectral gap and polynomial norms throughout, so the quantum evolutions are implementable by standard digital simulation in polynomial time.","The modular chain — sparse to hypercube to TFD to linear to Schrödinger — is a reusable template for compiling other adiabatic oracle separations into optimization separations."],"supporting_citations":[{"why":"Supplies the original (sub)exponential adiabatic oracle separation that this paper compiles into optimization instances.","marker":"[GHV21]"},{"why":"Provides the perturbative reduction lemmas (first and second order) used to transform sparse stoquastic Hamiltonians into TFD form.","marker":"[BH17]"},{"why":"Establishes the correspondence between TFI Hamiltonians and Schrödinger operators, including the double-well bound imported as Claim 10.6.","marker":"[ZLLW24]"},{"why":"Supplies the unary embedding and clock construction used to linearize the Hamiltonian path.","marker":"[LLPW24]"},{"why":"Defines Quantum Hamiltonian Descent, the continuous algorithm whose dynamics the constructed Schrödinger path follows.","marker":"[LHLW23]"},{"why":"Introduced adiabatic quantum optimization, the paradigm the discrete speedup instantiates.","marker":"[FGGS00]"}],"fun_headline_variants":["Provable exponential quantum speedup for optimization","Adiabatic and QHD achieve provable exponential speedups","Quantum optimization beats classical by exponential queries","Subexponential quantum advantage shown in optimization","Exponential query separation for quantum optimization"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The continuous part of the construction imports a spectral-gap and concentration bound for the double-well operator from prior work; if that bound has hidden parameter dependencies or errors, the continuous separation does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Provable exponential quantum speedup for optimization","Adiabatic and QHD achieve provable exponential speedups","Quantum optimization beats classical by exponential queries","Subexponential quantum advantage shown in optimization","Exponential query separation for quantum optimization"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000296,"raw_usage":{"total_tokens":1683,"prompt_tokens":876,"completion_tokens":807,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":492,"completion_tokens_details":{"reasoning_tokens":739}},"tokens_in":492,"tokens_out":807,"duration_ms":7141,"temperature":1.0,"reasoning_tokens":739,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:39:56.886519+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the two lowest eigenvalues of $-\\frac{d^2}{d\\xi^2}+\\lambda^2(\\xi^2-1/4)^2$ on $[-1,1]$ with vanishing boundary conditions for large $\\lambda$ and check that the gap is $2/\\Lambda$ with $\\Lambda=e^{\\lambda/6(1\\pm o(1))}$ and that $\\langle b_0|b_0\\rangle_{[-1,w]}\\le O(\\Lambda^{-2/3})$; failure of any of these at increasing $\\lambda$ would invalidate the error estimate $\\varepsilon\\le O(\\sqrt{n}\\,\\Lambda^{-1/6}\\|D\\|)$ in Lemma 10.5.","supporting_citations":[],"review_version":1}