{"id":"4644ae2c-5f85-4c0c-bd98-d506d7c59172","arxiv_id":"2507.00908","paper_version":4,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A quantum algorithm with one ancilla prepares normalized imaginary-time evolved states using an adaptive normalization factor, with provably polynomial gate and measurement cost in evolution time.","lead":"This paper presents a quantum algorithm that prepares imaginary-time evolved quantum states with a cost that grows polynomially with the evolution time, instead of exponentially. It uses an adaptively chosen normalization factor and targets ground-state and open-system simulation, which are key building blocks for quantum chemistry and many-body physics.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Central Theorem 2 is plausible; the load-bearing gap is the unproved error-propagation step in Theorem 7, which underpins the advertised open-system results.","rationale":"The reader's conditional verdict already flags the open-system error-propagation simplification and the heuristic Assumption (x). My stress-test agrees that this is the most concrete unsupported step in the manuscript. I do not find a comparable flaw in Theorem 2: the adaptive-normalization idea, the use of QPP for the exponential transformation, and the gamma-dependence of the success probability are internally consistent, and the claimed polynomial-in-tau resource scaling survives scrutiny aside from standard caveats about the vagueness of Assumption (iv) and the 'with probability 1' phrasing. The gamma-overlap assumption identified by the reader is standard and affects only the polynomial-in-n corollary, not the central polynomial-in-time claim, so I weight the open-system gap as the more load-bearing concern. The verdict should remain CONDITIONAL.","tokens_in":46566,"tokens_out":20498,"duration_ms":257957,"concrete_test":"Independently re-derive the error recurrence in Appendix E without the simplification in Eq. (E.20): compute the worst-case Lipschitz constant of the normalized QPP map V on the subspace reachable under the alternating U_Hc and V steps, as a function of tau, N, and the state overlap with the ground subspace of H. If the constant is O(1), Theorems 7 and 8 stand; if it scales with tau, the advertised O(t^3/epsilon) Lindbladian cost is unsupported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of Theorem 7 (Appendix E, Eq. E.18-E.23) reduces the per-step recurrence of the error between the algorithm output |phi_k> and the ideal state |zeta_k> to ||V[|phi_k>]-V[|zeta_k>]|| approx |||phi_k>-|zeta_k>||. This is asserted with the words 'by assuming |phi_k> and |zeta_k> are mainly differed by their components in ground-state subspace of H'. That assumption is not established: the coherent step U_Hc can rotate the state out of the ground-state subspace of H, and the QPP map V is not a contraction because its polynomial approximation has Lipschitz constant O(tau) near the spectrum. If the per-step gain is O(tau), the error recurrence can grow exponentially in the number of steps N, invalidating the claimed O(t^2/(mu N) + N epsilon) bound and hence Theorems 7 and 8. The closed-system Theorem 2 does not depend on this simplification, so the central imaginary-time-evolution claim itself is not affected; the gap is in the paper's broader Lindbladian-simulation claims.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a QPP-based quantum algorithm for preparing normalized imaginary-time-evolved states, with an adaptive normalization parameter λ that keeps the post-selection success probability bounded away from zero over long evolution times. The central claim, Theorem 2, states that under overlap and oracle assumptions one can prepare the ITE state to fidelity 1 − O(poly(τ^{-1})) with probability 1, using Õ(γ^{-2}τ) queries and one ancilla. Theorem 3 extends this to a Trotterized Pauli-form setting. The paper then applies the ITE primitive to ground-state preparation/energy estimation (Algorithm 1, Theorem 6) and to Lindbladian simulation (Algorithm 2, Theorems 7 and 8), with numerical experiments for τ up to 50. The core adaptive-normalization idea is original and the QPP construction is appropriate, but several load-bearing proof steps in the appendices are not established as written, so the formal claims currently exceed what is proven.","tokens_in":46830,"tokens_out":18615,"duration_ms":222183,"significance":"If the central Theorem 2 holds, this is a meaningful conceptual advance: it would provide the first provably polynomial-in-τ ITE algorithm, complementing the usual polynomial-in-n scaling and addressing a real gap in the literature. The adaptive normalization idea is elegant, the numerical experiments are relevant, and the comparison tables are useful. The paper also gives credit to the field by making the QPP machinery a central tool and by sharing code for the numerics. However, the significance is currently limited by the fact that the proof of Theorem 2 relies on an unproved degree-scaling step in Theorem S4 and on an asymptotic simplification in Lemma 1; and the open-system application rests on an explicitly unproved error-propagation assumption in Theorem 7. These are fixable in principle, so the work is worth serious revision rather than dismissal.","major_comments":[{"comment":"Theorem 2 states that the ITE state is prepared 'with probability 1', but the proof invokes Theorem S5, which returns an estimate of |λ0| with failure probability e^{-τ}. If that phase-estimation subroutine fails, the chosen λ may violate λ ≥ |λ0|, and the guarantees of Lemma 1 no longer apply. No amplification to failure probability zero is described, and a finite number of repetitions cannot achieve exact probability 1. The theorem should either state success probability 1 − e^{-τ} (or 1 − δ with a stated boosting cost) or explicitly condition on the success of the QPE subroutine.","section":"Section II.D, Theorem 2 and Appendix C.1"},{"comment":"The fidelity proof asserts ∥e^{-τH/2}|φ⟩∥² = O(γ² e^{-τλ0}) and ∥e^{-τH}|φ⟩∥² = O(γ² e^{-2τλ0}) directly from Assumption (iv). These bounds require that the excited-state contributions be of order γ², i.e. (1−γ²)e^{-τΔ} = O(γ²), which is not among Assumptions (i,iv,v). Without such a condition the ratio a(τ) can be larger by a factor γ^{-2}, so the claimed fidelity lower bound 1 − O(α^{-1}ε e^C) and the fidelity guarantee in Theorem 2 do not follow as stated. The lemma needs an explicit γ-dependence or an additional spectral-gap/overlap assumption.","section":"Lemma 1, Appendix C, Eq. (C.29)"},{"comment":"The proof claims that a trigonometric polynomial of degree L = O(τ) approximates f with error O(poly(τ^{-1})) by applying Jackson's theorem with a constant C_l that is treated as independent of τ. For g(x) = ρ(x) e^{τ(x−λ−μ)} the l-th derivative is O(τ^l), so the constant in Jackson's bound must scale as O(τ^l); then the construction L = C_l^{1/l}τ gives L = O(τ²), not O(τ), unless a new τ-independent constant is proved. Since Theorem 2's query depth and gate counts depend on the degree bound L = O(τ), the resource statement is not established. The proof should be repaired, e.g. by an analytic Chebyshev approximation argument, or the resource counts in Theorems 2 and 3 should be revised.","section":"Theorem S4, Appendix B.1"},{"comment":"The per-step error recurrence replaces ∥V[|φ_k⟩] − V[|ζ_k⟩]∥ by ∥|φ_k⟩ − |ζ_k⟩∥, justified only by 'assuming |φ_k⟩ and |ζ_k⟩ are mainly differed by their components in ground-state subspace of H'. This is not proved. The map V includes a normalization factor (Eq. 6) and is therefore nonlinear, and the coherent rotation U_{Hc} can move population out of the ground-state subspace of H, so the effective Lipschitz constant of V is uncontrolled. Consequently the bound O(kα^{-1}ε) and the final O(t²/µN + Nε) in Theorem 7 do not follow, and Theorem 8 inherits the gap. The authors' own admission in Section III.B that no general success-probability bound is available underscores that this step is load-bearing. Please prove the simplification or explicitly restrict Theorem 7 to a setting where Hc approximately preserves the relevant subspace.","section":"Theorem 7, Appendix E, Eqs. (E.18)–(E.20)"},{"comment":"Theorem 6 and Algorithm 1 are conditioned on Assumption (x), which states that a known B with γ²|λ0| ≥ e²B > 0 is available. The authors explicitly call this a heuristic step, and the numerical verification uses a fixed B = 1/5000 for three small Heisenberg chains; no theoretical method for obtaining B or sensitivity analysis is given. The formal complexity guarantee is therefore instance-specific and weaker than the theorem statement suggests. The assumption should appear prominently in the theorem statement, and the paper should either provide a procedure for choosing B or state the result as conditional on that promise.","section":"Section III.A, Assumption (x) and Theorem 6"}],"minor_comments":[{"comment":"There are numerous typos and grammatical errors, e.g. 'theorectical', 'trignometric', 'postivie', 'gurantees', 'hvae', and 'sine the product'. A careful proofreading pass is needed.","section":"Throughout"},{"comment":"The row for Theorem 3 lists expected circuit runs O(poly(n)), but the theorem statement says O(poly(n)) copies of |φ⟩; please clarify what 'circuit runs' means and whether the overall success probability is meant to be high probability rather than exactly 1.","section":"Table I"},{"comment":"The caption states that 'cost' counts queries including post-selection repetitions, but the main text says 'average resource cost' without specifying the estimator. Please define the plotted cost precisely in the caption.","section":"Section III.B.1, Figure 3(c)"},{"comment":"The notation H_≈ is used without local definition; it should be reintroduced in Appendix E or a pointer to Theorem 3's definition should be given.","section":"Appendix E, Eq. (E.35)"},{"comment":"The step 'the operator norm of the difference of the real-time evolutions implies ∥H − H_≈∥∞ < ϵ' is stated without proof; because the logarithm is multi-valued, a short Davis–Kahan-style argument for eigenphases should be supplied.","section":"Appendix C.2, Proposition S14"}],"recommendation":"major_revision","confidential_remarks":"The paper is a serious contribution with a genuinely promising central idea, and the numerical work is a positive feature. However, the formal proofs contain several gaps that are directly load-bearing for the advertised theorems: the 'probability 1' statement in Theorem 2 is not supported by the probabilistic QPE subroutine, Lemma 1's fidelity bound hides a γ^{-2} contribution, Theorem S4's degree scaling is not proved by the Jackson argument as written, and Theorem 7's error recurrence uses an explicit unproved subspace assumption. These are fixable with additional analysis or by weakening the claims, but they are too central for the paper to be accepted in its current form. I recommend major revision."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read the paper. The main result—adaptive normalization gives provably polynomial-in-tau resources for normalized imaginary-time evolution—holds up on my reading. The proof of Theorem 2 is a coherent chain (Jackson approximation, QPP realization, QPE-based lambda estimation), I don't see circularity, and the numerical checks are honest. That is a real advance over the exponentially decaying success probabilities of prior QSP-based ITE schemes.\n\nThe weak spot is the open-system section. Theorem 7's proof in Appendix E contains a step the authors themselves concede is an assumption: to bound ||V[|phi_k>]-V[|zeta_k>]||, they write that |phi_k> and |zeta_k> \"are mainly differed by their components in ground-state subspace of H\" and reduce the contraction to an identity. That is not established. The coherent step U_Hc can rotate the state out of the ground-state subspace, and V is not a contraction because its polynomial approximation has Lipschitz constant O(tau) near the spectrum. The per-step gain could be O(tau), making the error recurrence exponential in N. The paper also explicitly says it has no general post-selection success bound for Algorithm 2. So the advertised Lindbladian-simulation guarantee is not proven; it is a heuristic direction. This does not touch Theorem 2, but it means the paper's broadest claims are ahead of the proofs.\n\nMinor soft spots: Assumption (x) in Algorithm 1 is explicitly heuristic; the numerical evidence is supportive but not decisive; no machine-checked proofs, though the code and data are on GitHub and are reproducible in principle. None of these change my take on the core.\n\nWho this is for: anyone working on ground-state preparation, QSP/QPP, or early fault-tolerant quantum simulation. The central ITE result deserves a serious referee. The referee report should push hard on Theorem 7 and ask for either a real proof or a much more circumspect statement of the open-system results. I'd accept it for peer review and would cite the main theorem (not the Lindbladian one) in my own work.","headline":"Core ITE polynomial-resource result is solid and worth refereeing; the Lindbladian extension has an unproved error-propagation step and should be treated as heuristic.","tokens_in":47305,"tokens_out":2078,"would_cite":true,"duration_ms":25360,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","68Q12"],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"A quantum algorithm prepares imaginary-time-evolved states with polynomial resource scaling in evolution time, using one ancilla qubit and an adaptive normalization factor.","keywords":["imaginary-time evolution","quantum algorithm","quantum phase processing","ground-state preparation","Lindbladian simulation","polynomial resource scaling","success probability","early fault-tolerant quantum computing"],"falsifier":"Simulate the algorithm on a Hamiltonian with a known ground state, for example an antiferromagnetic Heisenberg chain, at $\\tau=100$ with $\\lambda$ chosen in $[|\\lambda_0|,|\\lambda_0|+\\tau^{-1}]$, and measure the post-selection success probability and output fidelity. If the success probability falls below $\\alpha^2\\gamma^2-\\epsilon$ or the infidelity fails to reach $O(\\tau^{-1})$ with $\\epsilon=O(\\tau^{-2})$, Lemma 1 and hence Theorem 2 would be contradicted.","tokens_in":46358,"feed_emoji":"⚛️","tokens_out":9660,"duration_ms":105599,"temperature":0.7,"pith_summary":"This paper claims that quantum imaginary-time evolution, the standard operation that turns a state into a low-energy state by exponentiating the Hamiltonian, can be simulated on a quantum computer with resources growing polynomially in the evolution time. The core move is an adaptive normalization factor chosen slightly above the ground-state energy, which keeps the post-selection success probability near $\\alpha^2\\gamma^2$ instead of letting it decay as $e^{-2\\tau}$. With that stabilization, the algorithm approximates the normalized evolved state to fidelity $1-O(\\operatorname{poly}(\\tau^{-1}))$ using $\\widetilde{O}(\\gamma^{-2}\\tau)$ controlled queries to the evolution oracle and one ancilla qubit; if the initial overlap $\\gamma$ is inverse-polynomial in system size, the whole cost is polynomial in both time and qubit number. The same primitive is then applied to ground-state preparation and energy estimation, where it shortens circuit depth by a factor $\\gamma^{-1}$ at the price of more measurements, and to Lindbladian simulation, where circuit depth no longer grows with the number of dissipative terms.","feed_headline":"Provable polynomial cost for imaginary-time evolution","feed_subtitle":"A single ancilla and an adaptive normalization factor keep success probability stable for long evolution times.","key_machinery":"The object that carries the argument is an adapted target function $f_{\\tau,\\lambda}(x)=\\alpha e^{\\tau(x-\\lambda)}$ on $x\\in[-1,\\lambda]$, extended by a smooth bounded function on $(\\lambda,1]$, with $\\alpha\\in(e^{-1/2},1]$. A trigonometric polynomial $F$ of degree $O(\\tau)$ approximates $f_{\\tau,\\lambda}$ with error $\\epsilon=O(\\operatorname{poly}(\\tau^{-1}))$ via Jackson's theorem, and a quantum phase processing (QPP) circuit $V^\\epsilon_f(U_H)$ implements $F(U_H)$ by interleaving controlled calls to $U_H$ and its inverse with single-qubit ancilla rotations. Post-selecting the ancilla on $|0\\rangle$ applies $F(U_H)$ to the input, approximating $e^{-\\tau H}$. Choosing $\\lambda$ in the comfort region $[|\\lambda_0|,|\\lambda_0|+\\tau^{-1}]$ makes the constant $C=\\tau(\\lambda-|\\lambda_0|)$ at most $1$, so the ground-state amplitude factor $\\alpha e^{-C}$ stays bounded away from zero and the success probability is stabilized at order $\\alpha^2\\gamma^2$.","core_discovery":"The paper's central assertion is Theorem 2: given a normalized Hamiltonian with negative ground-state energy, access to controlled-$U_H=e^{-iH}$ and its inverse, and an initial state with overlap $\\gamma>0$ on the ground state, one can prepare the normalized imaginary-time evolved state $|\\phi(\\tau)\\rangle$ up to fidelity $1-O(\\operatorname{poly}(\\tau^{-1}))$ with overall success probability $1$, using $\\widetilde{O}(\\gamma^{-2}\\tau)$ queries to controlled-$U_H$, $O(\\gamma^{-2})$ copies of the initial state, $\\widetilde{O}(\\tau)$ maximal query depth, and one ancilla qubit. The normalization parameter $\\lambda$ is set inside $[|\\lambda_0|,|\\lambda_0|+\\tau^{-1}]$, where $\\lambda_0$ is the ground-state energy; this keeps the success-probability lower bound at $\\alpha^2\\gamma^2-\\epsilon$ rather than $e^{-2\\tau}$. When the oracle is replaced by a Trotterized Pauli decomposition and $\\gamma=\\Omega(\\mathrm{poly}(n^{-1}))$, the cost becomes polynomial in both $n$ and $\\tau$. The authors then build on this ITE primitive to give a ground-state preparation and energy-estimation algorithm with query depth reduced by a factor $\\gamma^{-1}$ relative to phase-estimation-based methods, and an open-system simulation algorithm whose circuit depth is independent of the number of jump operators.","pith_inferences":["The depth-versus-measurements tradeoff suggests that on devices where depth is the scarce resource, this ITE route to ground-state problems may be preferable even when its total query count is larger; the paper notes that circuits can be run in parallel.","Since Theorem 2 inherits the $\\widetilde{O}(\\gamma^{-2}\\tau)$ cost from the ground-state-energy estimation subroutine, any future improvement in spectral estimation would automatically improve ITE; the paper hints at, but does not prove, a computational equivalence between the two problems.","The favourable numerical success probabilities in the Lindbladian setting suggest there may exist a provable post-selection bound under a condition weaker than preserving the ground-state subspace of the dissipative Hamiltonian; finding such a condition is a concrete open problem."],"forward_implications":["Imaginary-time evolution can now be used as a rigorously analyzed subroutine in quantum algorithms, replacing heuristic Trotter or variational steps in tasks where long evolution times are needed.","Ground-state preparation and ground-state energy estimation can be carried out with query depth reduced by a factor $O(\\gamma^{-1})$ compared with phase-estimation-based methods, at the cost of more measurement shots.","Lindbladian simulation in Liouville space can be implemented with circuit depth that does not grow with the number of jump operators, provided the Pauli sparsity stays fixed.","When the initial state has inverse-polynomial overlap with the ground state, preparing imaginary-time evolved states costs $\\mathrm{poly}(n,\\tau)$ gates, making long-time many-body simulation accessible in principle on early fault-tolerant hardware."],"supporting_citations":[{"why":"Quantum phase processing: the circuit framework used to implement polynomial transformations of $U_H$ with one ancilla and controlled queries.","marker":"[18]"},{"why":"Ground-state energy estimation via quantum eigenvalue transformation; supplies the $\\lambda$ estimate with $\\widetilde{O}(\\gamma^{-2}\\tau)$ queries needed by Theorem 2.","marker":"[34]"},{"why":"Quantum singular value transformation: the generalized framework that motivates polynomial eigenvalue transformations and provides an alternate block-encoding route.","marker":"[17]"},{"why":"Original quantum signal processing: establishes single-qubit polynomial transformations on which the multi-qubit extension rests.","marker":"[16]"},{"why":"First Trotter-based quantum imaginary-time evolution algorithm; the heuristic baseline that Table I compares against.","marker":"[3]"},{"why":"Open-system simulation in Liouville space using imaginary-time evolution; Algorithm 2 replaces its heuristic subroutine with the rigorously analyzed ITE circuit.","marker":"[30]"},{"why":"Jackson's theorem: guarantees the exponential function on $[-1,\\lambda]$ is approximated by a degree-$O(\\tau)$ trigonometric polynomial with superpolynomial error decay.","marker":"[92]"},{"why":"Davis-Kahan theorem: bounds ground-state subspace mismatch when the oracle is replaced by a Trotter approximation, used in Theorem 3.","marker":"[94]"},{"why":"Hoeffding's inequality: gives the measurement-shot bounds for expectation-value estimation in Algorithm 1 and Theorem 6.","marker":"[95]"}],"fun_headline_variants":["First provable polynomial-cost ITE algorithm","Adaptive normalization stabilizes long-time imaginary evolution","Polynomial quantum resources for imaginary-time evolution","ITE with provable polynomial scaling in time and system size"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The result collapses if the initial state's overlap $\\gamma=|\\langle\\phi|\\psi_0\\rangle|$ with the ground state is exponentially small in the number of qubits, because then the guaranteed success probability scale $\\alpha^2\\gamma^2$ and the $O(\\gamma^{-2})$ repetitions in Theorem 2 become exponentially large.","fun_headline_variants_meta":{"raw":{"variants":["First provable polynomial-cost ITE algorithm","Adaptive normalization stabilizes long-time imaginary evolution","Polynomial quantum resources for imaginary-time evolution","ITE with provable polynomial scaling in time and system size"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000611,"raw_usage":{"total_tokens":2914,"prompt_tokens":1084,"completion_tokens":1830,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":700,"completion_tokens_details":{"reasoning_tokens":1771}},"tokens_in":700,"tokens_out":1830,"duration_ms":15132,"temperature":1.0,"reasoning_tokens":1771,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T21:05:31.390556+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the algorithm on a Hamiltonian with a known ground state, for example an antiferromagnetic Heisenberg chain, at $\\tau=100$ with $\\lambda$ chosen in $[|\\lambda_0|,|\\lambda_0|+\\tau^{-1}]$, and measure the post-selection success probability and output fidelity. If the success probability falls below $\\alpha^2\\gamma^2-\\epsilon$ or the infidelity fails to reach $O(\\tau^{-1})$ with $\\epsilon=O(\\tau^{-2})$, Lemma 1 and hence Theorem 2 would be contradicted.","supporting_citations":[{"cited_title":"Über die Genauigkeit der Annäherung stetiger Funktionen durch ganze rationale Funktionen gegebe- nen Grades und trigonometrische Summen gegebener Ordnung","cited_arxiv_id":null,"evidence_quote":"Jackson's theorem: guarantees the exponential function on $[-1,\\lambda]$ is approximated by a degree-$O(\\tau)$ trigonometric polynomial with superpolynomial error decay."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Davis-Kahan theorem: bounds ground-state subspace mismatch when the oracle is replaced by a Trotter approximation, used in Theorem 3."},{"cited_title":"Probability inequalities for sums of bounded random variables","cited_arxiv_id":null,"evidence_quote":"Hoeffding's inequality: gives the measurement-shot bounds for expectation-value estimation in Algorithm 1 and Theorem 6."}],"review_version":1}