{"id":"e0c07dd2-df5d-474b-896d-a6271d9ce379","arxiv_id":"2411.18168","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"high","formal_verification":"none","parameter_count":2,"one_line_summary":"A path-integral quantum simulation algorithm that encodes non-Markovian dynamics as diagonal unitaries claims polynomial scaling, but its measurement success probability decays exponentially with the number of time steps.","lead":"This paper proposes a quantum circuit algorithm for simulating non-Markovian open quantum dynamics using Feynman path integrals, claiming polynomial qubit and gate counts with no classical overhead. It is notable because it would address an exponentially hard classical simulation problem, but the final measurement step gives an exponentially small success probability that the complexity analysis ignores.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The final all-zeros readout probability is exponentially small in the number of time steps, and the proposed oblivious amplitude amplification cannot restore polynomial scaling.","rationale":"The reader's weakest assumption correctly identifies the decisive flaw: the final readout success probability is exponentially small in the number of time steps, and the paper's invocation of oblivious amplitude amplification does not fix it. I find no other concern that is more load-bearing. The path-integral tensor-product decomposition and the unitary dilation construction are plausible, and the small-N ideal simulations provide some evidence that the circuit implements the intended propagator for N up to 5. However, the paper's central claim of polynomial time complexity requires estimating the population from the all-zeros measurement with polynomially many shots, which fails because p = |rho|^2 / D^2 decays as 4^{-2N} (for a two-level system). The complexity analysis in Section III.D counts gates and qubits but not shots, and Section IV's statement that amplitude amplification boosts the amplitude without changing complexity is incorrect; the required number of amplification rounds is exponential. The reader's REJECT verdict is therefore appropriate, and my stress-test does not change it.","tokens_in":14380,"tokens_out":8702,"duration_ms":83458,"concrete_test":"Run the Algorithm I circuit for the spin-boson model of Fig. 8 with N=10 time steps on an ideal simulator, using 10^6 shots and the same operator construction as Section III.C. Count the number of all-zeros outcomes. The expected count is 10^6 * |rho_00(10 dt)|^2 / 4^{2(N-1)} ≈ 10^6 * 0.1 / 4^18 ≈ 4e-4, so the run should yield zero counts with high probability, whereas a polynomial-time algorithm would need a reliable estimate of rho_00. This directly tests whether the final readout is exponentially suppressed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim of polynomial time and space complexity rests on the ability to read out the path sum from the circuit. In Section III.C, the Hadamard aggregation step leaves an amplitude (1/D) sum_i A_i on the all-zeros component, where D is the number of paths in the equal superposition. For an n-level system propagated for N time steps with fixed endpoints, D = n^{2(N-1)} (for the two-level examples, D = 4^{N-1}). Thus the probability of measuring all zeros is p = |sum_i A_i|^2 / D^2 = |rho_target|^2 / D^2, which is exponentially small in N because rho_target is a population between 0 and 1. The paper's complexity analysis in Section III.D counts qubits and gates but omits the number of shots or repetitions needed for this readout. The statement in Section IV that oblivious amplitude amplification can boost the amplitude 'without changing the time and space complexity' is incorrect: amplitude amplification to constant success probability requires O(1/sqrt(p)) = O(D) iterations, each invoking the full circuit, making the total cost exponential. Reference [49]'s oblivious amplitude amplification applies to block-encoded operators with singular values near 1; it cannot amplify a non-unitary path-sum coefficient whose magnitude is exponentially small. The same exponential suppression also affects the postselection on dilation ancillas: the non-unitary influence-functional tensors are implemented by conditioning on ancilla |0> states, and the joint success probability is the same exponentially small factor. The small-N ideal simulations (N up to 5) agree with exact benchmarks but use up to 300,000 shots; for N=10 the required shots would be on the order of 4^{18} ~ 6.9e10, contradicting the claimed polynomial scaling. Therefore the load-bearing assumption of a non-negligible readout probability fails, and the central claim is unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a quantum algorithm for simulating non-Markovian open-system dynamics based on the Feynman-Vernon influence functional. The algorithm encodes all forward-backward paths in an equal superposition, implements the influence functional and bare propagators through unitary dilations of diagonal operators, and then uses Hadamard gates to aggregate path amplitudes into the final reduced density matrix population. The authors claim polynomial scaling in the number of qubits and native gates, no classical overhead, and uniform efficiency regardless of temporal entanglement. They demonstrate the circuits on a two-level spin-boson model for up to five time steps, benchmarking ideal simulations against an exact tensor-network path integral method and also reporting noisy-simulator results.","tokens_in":14585,"tokens_out":2739,"duration_ms":26184,"significance":"If the polynomial-time and polynomial-space claims were correct, the algorithm would be a significant advance, potentially enabling quantum advantage for non-Markovian open-system dynamics where classical tensor-network methods scale exponentially with memory. The paper does provide a concrete circuit construction, explicit gate counts based on Walsh-series decompositions, and numerical benchmarks against a separate exact method; these are genuine strengths. However, the central complexity claim is invalid because the algorithm's readout success probability is exponentially small in the propagation time, and the proposed amplitude-amplification fix does not restore polynomial scaling. The results are therefore limited to very short propagation times, as the paper's own Table I reflects with rapidly increasing shot counts.","major_comments":[{"comment":"The final aggregation step leaves the target population with amplitude (1/D)Σ_i A_i in the |0...0⟩ component, where D is the number of paths in the superposition. For fixed initial and final endpoints, D = n^{2(N-1)} for an n-level system propagated over N steps. The success probability of measuring all zeros is therefore |ρ_target|^2 / D^2, which is exponentially small in N. The complexity analysis in §III.D counts qubits and gates but omits the number of shots or repetitions required for this readout, so the claimed polynomial time complexity does not hold.","section":"§III.C, §III.D"},{"comment":"The statement that oblivious amplitude amplification can boost the all-zeros amplitude 'without changing the time and space complexity' is incorrect. Amplitude amplification to constant success probability requires O(1/√p) = O(D) = O(n^{2(N-1)}) iterations, each involving a full execution of the circuit, which is exponential in N. Reference [49]'s oblivious amplitude amplification applies to block-encoded operators with singular values close to 1; it cannot amplify a non-unitary path-sum coefficient whose magnitude is exponentially small by construction.","section":"§IV, last paragraph"},{"comment":"The unitary dilation of each influence-functional tensor succeeds only when the dilation ancilla is measured in |0⟩, with probability |σ_j|^2 for each tensor element. The algorithms contain O(N^2) compact coupling operators (or O(NL) with finite memory), so the joint success probability of all dilation ancillas is the product of the individual |σ_j|^2. This postselection overhead is not accounted for in the complexity analysis in §III.D and compounds the exponential suppression from the path-sum readout.","section":"§III.B"}],"minor_comments":[{"comment":"There are numerous typographical errors, including 'autors', 'spce', 'propapationg', 'Algorihtm', 'otained', 'Wash' for Walsh, and 'complexty'; a careful proofreading pass is needed.","section":"Throughout"},{"comment":"The notation σ_j is used both for the elements of the influence functional and the singular values in the previous sentence; please use distinct symbols to avoid confusion.","section":"§III.B, Eq. (3.8)"},{"comment":"The expression '(N+1)N/2' is unambiguous but would be clearer as 'N(N+1)/2'; the same comment applies to the gate-count formula in Eq. (3.22).","section":"§III.D, Eq. (3.20)"},{"comment":"The table shows that the number of shots increases substantially with time step (e.g., from 20K to 300K in Figure 10), which the text interprets via 'more terms populating... making the amplitude relatively smaller.' This is precisely the exponential readout problem identified in the major comments, and it would be helpful to state this explicitly.","section":"§IV, Table I"}],"recommendation":"reject","confidential_remarks":"The paper's numerical demonstrations are limited to very short propagation times (up to N=5), and the authors' own data show that the required number of shots grows rapidly with N. This is consistent with the exponential readout overhead that invalidates the central complexity claim. The circuit construction and benchmarking methodology are reasonable, but the fundamental flaw in the resource analysis means that the claimed polynomial-time, no-classical-overhead result is not established. A major revision would require a fundamentally different readout scheme or a different algorithmic approach, so rejection is appropriate."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe one thing worth knowing about this paper is that the circuit construction is genuine but the central complexity claim is unsupported. The concrete new step is combining Walsh-series diagonal unitaries with unitary dilation to implement the Feynman-Vernon influence functional without classical eigendecomposition. That is a real improvement over their earlier path-integral algorithm, and the ideal-simulator results for N up to 5 match the exact tensor-network benchmarks. For short-time proof-of-principle simulations, this part is solid.\n\nThe soft spot is the readout. The aggregation step in Section III.C leaves the target population amplitude as (1/D) Σ_i A_i in the |0...0⟩ component, with D = n^{2(N-1)} for an n-level system. The success probability is |Σ_i A_i|^2 / D^2, exponentially small in the number of time steps. The complexity analysis in Section III.D counts qubits and gates but omits the number of shots. Section IV says oblivious amplitude amplification can boost the amplitude 'without changing the time and space complexity.' That is incorrect: boosting an exponentially small amplitude to constant success probability needs O(D) circuit repetitions, and the cited reference (Berry et al. on truncated Taylor series) applies to block-encoded operators with singular values near 1, not to a path-sum coefficient that can be arbitrarily small. Algorithm II's one-qubit measurement does not change the underlying amplitude, so it suffers the same problem.\n\nI checked the stress-test arithmetic and it holds. For N=10, the required shots would be around 4^18 ≈ 7×10^10, which is not polynomial. This is a load-bearing flaw, not a minor inefficiency.\n\nThe paper deserves a serious referee because the construction is explicit and the error is instructive. But as it stands, the main claim is not established. I would not cite it as evidence of polynomial scaling. If the authors can design a readout that extracts the path sum without exponential overhead, the circuit idea may be salvageable, but this version does not meet that bar. Recommendation: reject in current form; ask for a rigorous sampling-complexity analysis before resubmission.","headline":"Nice circuit construction, but the polynomial scaling claim collapses because the all-zeros readout probability is exponentially small.","tokens_in":15276,"tokens_out":4100,"would_cite":false,"duration_ms":35324,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","81S40"],"pacs":["03.67.Lx","03.65.Yz"],"model":"deepseek-v4-flash","headline":"A quantum algorithm simulates non-Markovian dynamics, avoiding exponential memory cost.","keywords":["non-Markovian quantum dynamics","path integral formulation","quantum simulation algorithm","open quantum systems","influence functional","spin-boson model","unitary dilation","Walsh series circuits"],"falsifier":"Compute the success probability of the all-zero outcome, $|\\sum_i A_i|^2 / D^2$ where $D$ is the number of path amplitudes, for the spin-boson model with strong coupling ($\\xi=1.2$) and increasing $N$, using the circuits described for Algorithms I and II. If this probability falls exponentially with $N$ (e.g., as $c^{-N}$), then the claim that the path sum can be extracted with polynomial measurement overhead is falsified, and the assertion that oblivious amplitude amplification restores polynomial complexity would require exponentially many calls for that amplification.","tokens_in":14097,"feed_emoji":"⚛️","tokens_out":7714,"duration_ms":61054,"temperature":0.7,"pith_summary":"This paper claims to solve a hard simulation problem: tracking the evolution of a quantum system that remembers its past (non-Markovian dynamics). The authors construct a quantum circuit based on the path-integral formulation of open quantum systems, encoding all possible forward-backward paths as amplitudes in a superposition. They argue the circuit uses a polynomial number of qubits and native gates, has no classical precomputation overhead, and remains efficient whether the non-Markovian memory is weak or strong. If correct, this would replace exponential classical cost with polynomial quantum cost across a broad range of condensed-phase and biological charge/energy transfer problems.","feed_headline":"Quantum algorithm simulates non-Markovian dynamics in polynomial time","feed_subtitle":"Path-integral circuits avoid the exponential memory cost of classical methods, even for strong memory.","key_machinery":"The load-bearing object is the tensor-product decomposition of the path integral into short-time unitary propagators $K(s_{k+1}^\\pm, s_k^\\pm)$ and influence functional tensors $I_{k,k'}$, each coupling at most two timepoints. Those tensors are non-unitary, so each compact operator $I_{k,k'}^C = U U^\\dagger I_{kk} I_{kk'}$ is implemented by a unitary dilation that embeds the diagonal non-unitary matrix into a larger diagonal unitary $U_\\Sigma$ with elements $I_\\pm^j = \\sigma_j \\pm i\\sqrt{1-|\\sigma_j|^2/|\\sigma_j|^2}\\,\\sigma_j$ (rescaling if needed). The diagonal unitary itself is implemented in $R_z$ and CNOT gates through the Walsh series representation, which expresses any diagonal unitary as a product of exponentials of tensor products of Pauli $Z$ operators. This combination of tensor-product path sums, unitary dilation, and Walsh-series circuits is what reduces the simulation to polynomial qubit and gate counts.","core_discovery":"The paper's central discovery is that the reduced density matrix of a system coupled to a harmonic bath can be computed as a single path sum encoded in a quantum state, with every non-unitary influence functional factor implemented as a diagonal unitary via unitary dilation. The resulting circuit applies only local two-timepoint operators, so the gate count for an $n$-level system propagated for $N\\Delta t$ is $O(n^4 N^2)$ in the general case and $O(n^4 N)$ when the bath memory is limited to $L\\Delta t$ with $L