{"id":"f79871ef-81f8-4269-b1d9-343d49db5055","arxiv_id":"2608.13533","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Quantum algorithms simulate linear Volterra integro-differential equations exponentially faster in system size when memory is weak (M<1), with a matching hardness result for strong memory and efficient handling of sum-of-exponentials kernels.","lead":"This paper designs quantum algorithms for simulating non-Markovian dynamical systems described by Volterra integro-differential equations, where the future depends on the whole past. It offers exponential speedups under a weak-memory condition, a hardness result for strong-memory general kernels, and efficient algorithms for special exponential-based kernels.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The abstract's 'structured kernels' overstates Definition 6.1: the M≥1 Markovianization results apply only to scalar K=-k(x)I with positive real exponentials and b=0, excluding matrix-valued kernels such as the Mori–Zwanzig kernel.","rationale":"The reader's weakest assumption identifies the same load-bearing concern: Definition 6.1 restricts structured kernels to scalar K=-k(x)I with positive real exponentials, while the abstract omits this restriction. I agree this is the main scope limitation of the central claim. The Markovianization construction and the Lyapunov bound in Claim 6.5 genuinely require the off-diagonal blocks to be multiples of the identity; matrix-valued kernels of the form appearing in the Mori–Zwanzig equation (Eq. 302) are therefore excluded. The homogeneous b=0 restriction in Theorem 6.2 is also unmentioned in the abstract. These are not internal inconsistencies—within Definition 6.1 the proofs appear coherent—but they materially narrow the 'structured kernels' claim. I did not find a rejection-level flaw: the condition-number proof in Theorem 4.10 has a repairable inequality slip, and the use of the external ODE solver theorem is a dependency rather than a demonstrated error. Since the reader already rated the paper CONDITIONAL for this reason, my read does not change the verdict.","tokens_in":49273,"tokens_out":43398,"duration_ms":452525,"concrete_test":"Check the extension to a non-scalar sum-of-exponentials kernel: let A=-I and K(x)=e^{-gamma x} diag(1,2) (or K(x)=e^{-gamma x}B with B not proportional to I), build the Markovianized matrix A = [[A,-B],[I,-gamma I]], and test whether any block-diagonal P=diag(P0,P1)>0 satisfies PA + A^dagger P <= 0. If no such P exists even when C(A) is finite, Claim 6.5 relies essentially on K=-kI, confirming that the abstract must be revised to 'scalar structured kernels.'","verdict_should_be":"UNCHANGED","load_bearing_attack":"The structured-kernel results (Theorems 6.2, 6.10, 6.14) rely on Definition 6.1, which requires K(x)=-k(x)I with k real and approximated by positive real exponentials; Theorem 6.2 also sets b=0. The abstract instead promises 'structured kernels which admit concise decompositions over exponentials' without the scalar qualifier. This is load-bearing because the Markovianization ODE (Eq. 251) has off-diagonal blocks -sqrt(w_j)I that are multiples of the identity, and Claim 6.5 uses this to construct the Lyapunov transformation P^{1/2}AP^{-1/2} without changing off-diagonal blocks. For a matrix-valued kernel K(x)=sum_j B_j e^{-gamma_j x}, the corresponding off-diagonal blocks are B_j, which are not simultaneously reduced by a block-diagonal P; the proof of C(A) <= Clp(A) fails. The Mori–Zwanzig kernel in Eq. 302 is exactly matrix-valued, so the structured algorithm does not apply there; only the M<1 general-kernel algorithm of Section 4 does. The homogeneous restriction b=0 is likewise omitted from the abstract. These are scope limitations rather than internal inconsistencies: within Definition 6.1 the proofs are consistent. But the headline claim is materially narrower than the abstract suggests.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops quantum algorithms for linear convolution Volterra integro-differential equations (VIDEs) of the form du/dt = Au + integral_0^t K(t-tau)u(tau)d tau + b. It defines a memory-strength parameter M and proves a stability bound for M<1. It then discretizes the VIDE into a block lower-triangular linear system and applies a quantum linear system algorithm, obtaining history-state and final-state algorithms whose complexity is polynomial in T, ||A||, 1/epsilon, and derivative norms of K, and whose condition number is shown to grow linearly in the number of time steps. A state-discrimination argument gives an exponential-in-T lower bound for general-kernel final-state simulation when M>=1. For structured kernels K=-k I with k approximated by positive real exponentials, the paper introduces Markovianization into a larger linear ODE and applies quantum ODE solvers, including a power-law kernel specialization. It closes with an application to the linear Mori-Zwanzig formalism using the general-kernel algorithm.","tokens_in":49532,"tokens_out":11236,"duration_ms":115539,"significance":"The technical core is substantial and appears internally consistent. The stability lemma (Lemma 3.2), the discretization error bound (Lemma 4.7), the condition-number bound (Theorem 4.10), and the lower-bound construction (Lemma 5.2 and Theorem 5.3) are detailed and check out. The Markovianization analysis for scalar sum-of-exponentials kernels is a useful addition to the quantum differential-equation toolkit, and the paper is careful to state many of its hypotheses in the technical sections. The principal weakness is that the advertised scope of the structured-kernel results is broader than the proven statements: the algorithms require scalar kernels, positive real exponential weights, and a homogeneous right-hand side, while the abstract and the informal results do not carry these qualifications. Because the proofs rest on the scalar structure, this is not merely a wording issue, but it is fixable within the paper's framework.","major_comments":[{"comment":"The structured-kernel algorithms are restricted to scalar kernels K(x)=-k(x)I with positive real exponential weights and rates and to the homogeneous case b=0, but the abstract and Section 1.2 describe them as 'structured kernels which admit concise decompositions over exponentials' without these qualifiers. This is load-bearing: the off-diagonal blocks in the Markovianized ODE, Eq. (251), are -sqrt(w_j)I, and Claim 6.5's argument that P^{1/2} A P^{-1/2} has negative-semidefinite Hermitian part relies on those blocks being scalar multiples of the identity. For a matrix-valued kernel K(x)=sum_j B_j e^{-gamma_j x}, the analogous blocks are B_j, which are not simultaneously reduced by a block-diagonal P, and the bound C(A) <= Clp(A) need not hold. The Mori-Zwanzig kernel in Eq. (302), K(x)=L_{M\\bar M} e^{L_{\\bar M\\bar M} x} L_{\\bar M M}, is generically matrix-valued, so Section 6's Markovianization does not apply to it; Section 7 correctly falls back on the Section 4 algorithm, but the abstract's wording invites the contrary reading. The abstract, Results 1.6–1.7, and Theorem 6.2 should state the scalar, positive-real-exponential, and b=0 hypotheses explicitly.","section":"§6.1.2–§6.2 (Definition 6.1, Eq. (251), Claim 6.5, Theorems 6.2, 6.10, 6.14)"},{"comment":"Theorem 6.2 is stated for K(x)=-k(x)I and b=0, and the power-law results (Theorem 6.14 and Corollary 6.15) inherit the homogeneous restriction. Neither the abstract nor Results 1.6 and 1.7 mention this restriction. The proofs of Claims 6.8 and 6.9 use the homogeneous evolution y(t)=e^{At}y(0) to bound post-selection probabilities; replacing b=0 by a nonzero forcing term changes both the norm bounds and the success-probability estimates, so the extension is not immediate. The paper should state the b=0 restriction in the abstract and in the informal main results.","section":"Theorem 6.2 and §6.2.5"}],"minor_comments":[{"comment":"Claim 6.7 uses p := floor(p(epsilon_soe)), whereas Definition 6.1 and Theorem 6.2 define p := ceil(p(epsilon_soe)); the floor should be a ceiling to avoid a contradiction in the order parameter.","section":"§6.2.3, Claim 6.7"},{"comment":"For K(x)=e^{-gamma x}B with arbitrary matrix B, the Markovianized off-diagonal blocks should be +I and +B, or the sign convention should be written as K=-e^{-gamma x}B; as printed, the signs in Eq. (245) do not match the preceding warm-up derivation.","section":"§6.1.1, Eq. (245)"},{"comment":"The definition of epsilon_max in Theorem 4.1 uses alpha and beta, but these parameters are not introduced in the theorem statement; they should be defined there or the statement should refer explicitly to Lemma 4.4.","section":"Theorem 4.1"},{"comment":"Definition 6.1 reuses m for the number of exponentials after m was used for the number of time steps elsewhere; this notational collision can confuse the reader and would be worth removing.","section":"Definition 6.1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript's technical content is likely publishable after revision. The main request is to align the abstract and informal results with the scalar, positive-real-exponential, homogeneous assumptions of Section 6, and to make clear that the Mori-Zwanzig application falls under the Section 4 general-kernel algorithm rather than the Markovianization results. I see no grounds for rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things before reading this one. First, the core algorithmic results are real: the QLSA-based algorithm for general convolution kernels under the M<1 short-memory condition, the state-discrimination lower bound for M≥1, and the Markovianization construction for scalar sum-of-exponentials kernels are all new and the proofs hold together internally. Second, the abstract promises more than the structured-kernel section delivers. The Markovianization theorems (6.2, 6.10, 6.14) only apply to scalar kernels of the form K(x)=-k(x)I with k approximated by positive real exponentials, and the main theorem also sets b=0. The abstract says 'structured kernels which admit concise decompositions over exponentials,' which reads as much broader. That matters: the Mori–Zwanzig kernel in Eq. (302) is genuinely matrix-valued, so the structured-kernel algorithm does not apply there—only the M<1 general-kernel algorithm of Section 4 does. The paper actually handles that distinction correctly in Section 7, but the abstract and the opening of Section 6 blur it.\n\nWhat the paper does well: The stability analysis under M<1 (Lemma 3.2), the condition number bound O(m) for the discretized linear system (Theorem 4.10), and the discretization error bounds are careful and check out. The lower bound (Theorem 5.3) is a clean application of state-discrimination impossibility, and it fills a real gap: nobody had shown hardness for generic kernels with M≥1. The Markovianization analysis for scalar SOE kernels is also sound within its stated assumptions—the Lyapunov transformation in Claim 6.5 works specifically because the off-diagonal blocks are multiples of the identity, and the paper doesn't pretend otherwise except in the abstract.\n\nSoft spots, in proportion: The scalar restriction and b=0 are the main ones; they are scope limitations rather than errors. There is also a minor typo in Claim 6.7 (floor vs ceiling in the definition of p). The structured-kernel results lean on the self-cited quantum ODE solver theorem [DCTK26] without independent verification; that's a reliance, not a flaw, but it does mean the structured-kernel complexity inherits whatever caveats that theorem carries. The complexity statements themselves are heavy with parameters (C(A), Clp(A), g, g0), but that is normal for this literature.\n\nWho this is for: anyone working on quantum algorithms for differential equations, especially non-Markovian or integro-differential systems. The general-kernel algorithm and the lower bound are the parts I'd point people to. The structured-kernel section is more specialized but still worth engaging with after the scope is clarified.\n\nRecommendation: This deserves a serious referee. I would accept it with revisions that tighten the abstract, explicitly state the scalar and homogeneous restrictions in the structured-kernel theorems, and either verify or clearly flag the dependence on the ODE solver theorem. The math is solid enough that these are presentational and scoping fixes, not structural ones.","headline":"Solid quantum-algorithm paper for non-Markovian VIDEs: the general-kernel results and the lower bound are genuine, but the abstract overstates the structured-kernel scope.","tokens_in":50120,"tokens_out":1310,"would_cite":true,"duration_ms":15681,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["65R20","81P68"],"pacs":[],"model":"deepseek-v4-flash","headline":"For linear Volterra integro-differential equations, weak memory gives exponential quantum speedup, strong memory is provably hard, and structured kernels bypass the barrier via Markovianization.","keywords":["quantum simulation","Volterra integro-differential equations","non-Markovian dynamics","memory kernel","quantum linear systems algorithms","quantum lower bounds","Mori-Zwanzig formalism","sum of exponentials"],"falsifier":"Take the two-state VIDE from Lemma 5.2 but replace the scalar kernel with a matrix-valued kernel $K(x)=e^{-\\gamma x}B$ with $B$ not proportional to $I$, and run the Markovianization of Eq. (251). The claim to check is whether the enlarged ODE operator still satisfies the Lyapunov inequality $PA+A^\\dagger P\\preceq0$; for generic $B$ the off-diagonal blocks are not simultaneously diagonalized by the similarity transformation, so one should search for a concrete $B$ where no such $P$ exists — that would falsify the structured-kernel branch as stated.","tokens_in":49025,"feed_emoji":"🧠","tokens_out":10755,"duration_ms":103019,"temperature":0.7,"pith_summary":"This paper claims that quantum computers can efficiently simulate linear Volterra integro-differential equations, the standard model of dynamics with memory, and it maps the boundary of what is tractable. The authors introduce a dimensionless memory strength $\\mathsf M = \\frac{1}{|\\mu(A)|}\\int_0^\\infty \\|K(x)\\|\\,dx$; when $\\mathsf M<1$ (the short-term memory regime), the discretized VIDE becomes a well-conditioned linear system solvable by a quantum linear-system algorithm with complexity polynomial in $T$, $\\|A\\|$, and $1/\\varepsilon$ — an exponential speedup in the system dimension over classical solvers. When $\\mathsf M\\ge 1$, they prove a matching obstruction: for a family of generic kernels, any bounded-error quantum simulator needs $e^{\\Omega(T)}$ copies of the initial condition, because the dynamics itself amplifies the distinguishability of nearly identical states. The obstruction disappears for structured kernels $K(x)=-k(x)I$ that are $L^1$-approximable by positive real exponentials: Markovianization replaces the history integral by auxiliary ODE variables, and existing quantum ODE solvers run efficiently even with $\\mathsf M\\ge1$, including for the singular power-law kernel $x^{-\\beta}$. This matters for systems with memory in open quantum dynamics, viscoelasticity, epidemiology, and reduced-order modeling, where classical time-stepping must couple every step to all previous ones.","feed_headline":"Quantum speedup for memory systems, with a wall when memory dominates","feed_subtitle":"Weak-memory equations get exponential speedup; when memory dominates, efficient simulation needs structured kernels.","key_machinery":"The load-bearing objects are the memory strength $\\mathsf M$ and the Markovianized ODE operator. $\\mathsf M<1$ is what makes the VIDE stable (Lemma 3.2) and makes the discretized matrix $L$ well conditioned (Theorem 4.10), turning the whole trajectory into a QLSA instance. Markovianization is the named mechanism for structured kernels: if $k(x)\\approx\\sum_{j=1}^{s} w_j e^{-\\gamma_j x}$ with $w_j,\\gamma_j>0$, the auxiliary variables $y_j(t)=\\sqrt{w_j}\\int_0^t e^{-\\gamma_j(t-\\tau)}u(\\tau)\\,d\\tau$ satisfy first-order ODEs, so the VIDE becomes $dy/dt=\\mathcal{A}y+c$ with a block matrix as in Eq. (251). The scalar structure is what makes the similarity-transformed Hermitian part negative semidefinite (Claim 6.5), giving the exponential-norm bound $C(\\mathcal{A})\\le C_{\\mathrm{Lp}}(A)$ that feeds all structured-kernel complexity estimates.","core_discovery":"The paper's central claim is that linear convolution Volterra integro-differential equations $\\frac{du}{dt} = Au + \\int_0^t K(t-\\tau)u(\\tau)\\,d\\tau + b$ are quantumly simulable exactly in the regime fixed by the memory strength $\\mathsf M = \\frac{1}{|\\mu(A)|}\\int_0^\\infty \\|K(x)\\|\\,dx$. For $\\mathsf M<1$ and $A$ dissipative, forward-Euler time stepping plus a left Riemann sum gives the recurrence $u_{j+1}=(I+Ah)u_j+h^2\\sum_{k<j}K((j-k)h)u_k+hb$, which is a block lower-triangular linear system $Ly=c$ whose solution is the full history state; Theorem 4.10 bounds $\\kappa(L)\\le 3(m+p+1)$, so a QLSA prepares the history or final states with polynomial complexity (Theorems 4.1 and 4.2). For $\\mathsf M\\ge1$, Theorem 5.3 shows that a two-dimensional example with kernel $e^{-\\gamma x}\\,\\mathrm{diag}(0,1)$ separates $1-\\epsilon$-overlapping initial states to constant distance in $O(\\log(1/\\epsilon))$ time, forcing $e^{\\Omega(T)}$ copies of the initial condition in any bounded-error simulation. The escape route is Theorem 6.2: for scalar kernels $K(x)=-k(x)I$ with $k$ approximated by $s$ positive real exponentials, introducing one auxiliary variable per exponential turns the VIDE into a linear ODE of dimension $(s+1)N$ whose exponential growth is controlled by a Lyapunov-stability constant; applying a quantum ODE solver yields polynomial complexity for the power-law kernel $k(x)=x^{-\\beta}$, $0<\\beta<1$, even though this kernel has $\\mathsf M=\\infty$.","pith_inferences":["If the scalar restriction on structured kernels were relaxed to matrix-valued kernels, the Lyapunov analysis of Claim 6.5 would stop working: off-diagonal blocks $\\sqrt{w_j}B$ no longer commute with the similarity transformation. A direct test is to search for the positive definite $P$ in Claim 6.5 when $B$ is not proportional to $I$; this is an extension the paper does not make.","The $\\mathsf M<1$ condition is structurally parallel to the convergence condition for linearizing nonlinear ODEs (ratio of nonlinearity to dissipation), suggesting a broader principle: quantum speedups for dissipative dynamics depend on a weakness ratio, and memory or nonlinearity that amplifies state distinguishability is what triggers hardness.","The paper's outlook explicitly identifies complex-exponential decompositions as the next step, so the natural extension is to test whether $\\gamma_j$ with $\\mathrm{Re}\\,\\gamma_j>0$ but nonzero imaginary parts preserve the Hermitian-part bound; the Gaussian kernel, common in non-Markovian models, would be the first target.","Because the lower-bound construction is only two-dimensional and analytically solvable, the same distinguishability-amplification mechanism may transfer to bilinear Volterra equations, yielding lower bounds analogous to those for quadratically nonlinear ODEs."],"forward_implications":["For every VIDE with $\\mathsf M<1$ and efficient oracles for $A$, $K$, $u_0$, and $b$, the paper's algorithm prepares the history state with $O\\left((\\Lambda+\\Xi T)^2 T^4\\, g^{-2}\\,\\log(1/\\varepsilon)/\\varepsilon^2\\right)$ queries and the final state with an additional $g/q$ factor, an exponential speedup in system dimension over classical solvers.","The $\\mathsf M\\ge1$ lower bound uses only a two-dimensional example, so any future general algorithm for strong memory must either exploit kernel structure or consume exponentially many copies of the initial condition.","Structured scalar kernels, including the weakly singular power-law kernel $x^{-\\beta}$ with $\\beta\\in(0,1)$, are efficiently simulable with complexity polynomial in $T$, $\\|A\\|$, $1/\\varepsilon$, and $1/(1-\\beta)$ for fixed $\\beta$, despite having $\\mathsf M=\\infty$.","In the Mori-Zwanzig coarse-graining application, the derived VIDE satisfies the short-term memory condition whenever the coupling between resolved and unresolved blocks is small: $\\|L_{M\\bar M}\\|\\,\\|L_{\\bar M M}\\|/(|\\mu_M\\mu_{\\bar M}|)<1$ (Claim 7.1), so the general-kernel algorithm applies directly."],"supporting_citations":[{"why":"Supplies the quantum linear-system algorithm that solves the discretized $Ly=c$ system with $O(\\kappa\\log(1/\\varepsilon))$ oracle calls.","marker":"[CAS+22]"},{"why":"Gives the sparse block-encoding tools used to encode the banded matrix $L$ and the right-hand-side vector.","marker":"[GSLW19]"},{"why":"Provides the state-discrimination lower bound (their Lemma 7) that the $\\mathsf M\\ge1$ hardness proof contradicts.","marker":"[LKK+21]"},{"why":"Provides the sum-of-exponentials approximation for the power-law kernel $x^{-\\beta}$ and bounds its order.","marker":"[Li10]"},{"why":"Supplies the quantum ODE solver applied to the Markovianized system.","marker":"[Kro23]"},{"why":"States the explicit block-encoding error and complexity guarantees of the ODE solver used in Theorems 6.2 and 6.14.","marker":"[DCTK26]"},{"why":"Amplifies the post-selection probability in final-state preparation.","marker":"[BHMT02]"}],"fun_headline_variants":["Quantum memory speedup: exponential until a cliff, then structured only","Non-Markovian quantum simulation: exponential speedup for weak memory","For memory equations, quantum gives exponential speedup until memory wins","Markovianization lets quantum sims handle memory-heavy kernels","Quantum sims: exponential speedup for weak-memory equations, wall for strong"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"For the algorithms that work when memory is not weak, the kernel must be scalar ($K(x)=-k(x)I$) and $k$ must be well approximated by a few positive real exponentials; if the true kernel is matrix-valued, these algorithms no longer apply.","fun_headline_variants_meta":{"raw":{"variants":["Quantum memory speedup: exponential until a cliff, then structured only","Non-Markovian quantum simulation: exponential speedup for weak memory","For memory equations, quantum gives exponential speedup until memory wins","Markovianization lets quantum sims handle memory-heavy kernels","Quantum sims: exponential speedup for weak-memory equations, wall for strong"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001458,"raw_usage":{"total_tokens":6012,"prompt_tokens":1230,"completion_tokens":4782,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":846,"completion_tokens_details":{"reasoning_tokens":4689}},"tokens_in":846,"tokens_out":4782,"duration_ms":34734,"temperature":1.0,"reasoning_tokens":4689,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T04:47:34.770222+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the two-state VIDE from Lemma 5.2 but replace the scalar kernel with a matrix-valued kernel $K(x)=e^{-\\gamma x}B$ with $B$ not proportional to $I$, and run the Markovianization of Eq. (251). The claim to check is whether the enlarged ODE operator still satisfies the Lyapunov inequality $PA+A^\\dagger P\\preceq0$; for generic $B$ the off-diagonal blocks are not simultaneously diagonalized by the similarity transformation, so one should search for a concrete $B$ where no such $P$ exists — that would falsify the structured-kernel branch as stated.","supporting_citations":[],"review_version":1}