Pith. sign in

REVIEW 3 major objections 4 minor 7 references

Polynomial time and space quantum algorithm for the simulation of non-Markovian quantum dynamics

T0 review · 3 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A quantum algorithm simulates non-Markovian dynamics, avoiding exponential memory cost.

desk verdict Nice circuit construction, but the polynomial scaling claim collapses because the all-zeros readout probability is exponentially small. read the letter →

arxiv 2411.18168 v1 pith:KGWIXE2P submitted 2024-11-27 quant-ph

Avin Seneviratne , Peter L. Walters , Fei Wang This is my paper · ORCID
classification quant-ph MSC 81P6881S40 PACS 03.67.Lx03.65.Yz
keywords non-Markovianquantumdynamicspathintegralformulationsimulationalgorithmopensystemsinfluencefunctionalspin-bosonmodelunitarydilationWalshseriescircuits
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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<N$. The authors present two variants: one that minimizes qubit count and one that concentrates all measurement statistics into a single ancilla qubit via a multi-controlled Toffoli gate. They validate both against a tensor-network path-integral benchmark on the spin-boson model, reporting agreement for both weak and strong system-bath coupling.

Load-bearing premise

The algorithm's efficiency rests on the assumption that the final all-zeros measurement occurs with non-negligible probability, so that the path sum can be read out with polynomially many shots; if that probability decays exponentially with the number of time steps, the polynomial-time claim collapses.

Editorial extensions

If this is right

  • Non-Markovian open-system dynamics for a system coupled to a harmonic bath could be simulated on a quantum computer with polynomial resource scaling, avoiding the exponential path-counting cost of classical methods.
  • The algorithm's efficiency is claimed to be independent of temporal entanglement, so strongly non-Markovian regimes that defeat tensor-network approaches become tractable.
  • Because each operator acts on only a few qubits, the circuit is shallow enough to run on near-term devices for moderate propagation times, and the one-qubit measurement variant reduces shot noise.
  • The construction extends naturally to multi-level systems by encoding each system level in $\log_2 n$ qubits, giving a unified framework for simulating non-Markovian dynamics.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Inference: The paper asserts that oblivious amplitude amplification can boost the final all-zeros amplitude 'without changing the time and space complexity,' but if that amplitude is exponentially small in $N$, amplification would require exponentially many calls; resolving this requires analyzing the success probability as a function of $N$.
  • Inference: A concrete test would measure the all-zero outcome probability for the spin-boson model at strong coupling (e.g., $\xi = 1.2$) for increasing $N$; if it decays as $e^{-cN}$, polynomial readout fails without additional assumptions.
  • Inference: The finite-memory assumption ($L<N$) is critical to linear scaling; for baths with very long memory the quadratic $O(N^2)$ resources return, so an extension that adaptively truncates memory could trade accuracy for scalability.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

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.

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 (3)
  1. [§III.C, §III.D] 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.
  2. [§IV, last paragraph] 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.
  3. [§III.B] 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.
minor comments (4)
  1. [Throughout] There are numerous typographical errors, including 'autors', 'spce', 'propapationg', 'Algorihtm', 'otained', 'Wash' for Walsh, and 'complexty'; a careful proofreading pass is needed.
  2. [§III.B, Eq. (3.8)] 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.
  3. [§III.D, Eq. (3.20)] 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).
  4. [§IV, Table I] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the algorithm is a direct circuit implementation of the standard Feynman-Vernon path integral, with no fitted inputs and no prediction that reduces to an input by construction.

full rationale

The derivation starts from the standard Feynman-Vernon influence functional (Eqs. 2.5-2.7) and the Makri-Makarov tensor product decomposition (Eq. 3.3). The circuit encodes the path sum sum_i A_i |i> as a product of diagonal influence-functional factors and bare propagators; the Hadamard aggregation step is literally the summation in Eq. (3.5). Agreement with the path integral is therefore by construction, not because a parameter was fitted to the comparison data. The only normalization is the dilation rescaling in Section III.B, and the paper cancels it by forming ratios of populations from two endpoint preparations (Figures 4 and 5), then normalizes with the trace identity; this is not a fitted input. Numerical benchmarks use an independent tensor-network path integral method (Ref. 48), which does not supply any parameter to the quantum circuit. The self-citations to the authors' prior work (Refs. 22, 23, 24) describe earlier frameworks and are not used to justify the present derivation's correctness. The Section IV claim that oblivious amplitude amplification can boost the readout without changing complexity is a performance/correctness concern, not a circularity: it rests on an incorrect estimate of the all-zeros measurement success probability, but the algorithm's output is not defined in terms of that amplification. No result in the paper is equivalent to its input by definition, and no fitted parameter is relabeled as a prediction.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

The derivation is built on standard path integral and diagonal-unitary techniques. The main unstated premise is that the output readout probability is not exponentially small, which is not an axiom but an omission addressed in the scores and red flags.

free parameters (2)
  • Trotter time step Δt
    Discretization step for the path integral; chosen by the user to balance accuracy and circuit size, not fitted to data.
  • Dilation rescaling factor (largest singular value of I_C)
    Introduced in Section III.B to ensure |σ_j|<1; cancels when taking ratios of populations, so it is not a fitted parameter but a normalization.
assumptions (5)
  • domain assumption The environment is a harmonic bath linearly coupled to the system, producing a Gaussian influence functional.
    Section II, equations (2.1)-(2.4); the influence functional (2.6) is exact for this model, and the paper argues via the central limit theorem that many condensed-phase environments fit this form.
  • domain assumption The memory of the bath correlation function is finite, LΔt, so the influence functional factorizes into pairwise two-time tensors.
    Equation (3.3) and Section III.D; this is the Makri-Makarov finite-memory truncation, required for the O(NL) complexity claims.
  • domain assumption The system propagator and influence functional tensors are diagonal in the multi-time path basis, allowing implementation as diagonal unitaries.
    Section III.A, 'the short time unitary propagator K and the influence functional tensor I are diagonal in this basis'; this is true only after grouping all index dependencies as diagonal phases on joint registers.
  • standard math The Walsh-series construction of Welch et al. exactly implements any diagonal unitary with 2^{M+1}-3 native gates.
    Section III.B, equations (3.10)-(3.16), cited from reference [42].
  • standard math The unitary dilation from Schlimgen et al. (Section III.B, eq. 3.7-3.9) correctly embeds the non-unitary diagonal I into a unitary with one ancilla.
    Given in ref [41], used to implement the diagonal operators.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Polynomial time and space quantum algorithm for the simulation of non-Markovian quantum dynamics." pith.science (2026). https://pith.science/paper/KGWIXE2P

@misc{pith2026241118168,
  author       = {Pith},
  title        = {Pith review of: Polynomial time and space quantum algorithm for the simulation of non-Markovian quantum dynamics},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/KGWIXE2P}},
  note         = {Machine review of arXiv:2411.18168}
}
read the original abstract

In this work, we developed an efficient quantum algorithm for the simulation of non-Markovian quantum dynamics, based on the Feynman path integral formulation. The algorithm scales polynomially with the number of native gates and the number of qubits, and has no classical overhead. It demonstrates the quantum advantage by overcoming the exponential cost on classical computers. In addition, the algorithm is efficient regardless of whether the temporal entanglement due to non-Markovianity is low or high, making it a unified framework for simulating non-Markovian dynamics in open quantum system.

Figures

Figures reproduced from arXiv: 2411.18168 by the authors.

Figure 1
Figure 1. Non-Markovian temporal coupling. This tensor-product structure forms the basis for the following quantum algorithm development. We can create equal superposition states that represent all the possible paths. For instance, to propagate one timestep, a two-state system (denoted by the eigenvalues, e.g. 0 and 1, of the position-like states) has the possible forward-backward paths of (00;00), (00;01), (00;10), (00;11), … view at source ↗
Figure 2
Figure 2. [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Circuit for 2 time steps evolution. The way it stands, the circuit can be made more compact by combining the two-qubit operators with the four qubit operators, as long as they operate on the same qubits. For instance, for the propagation up to 2∆𝑡, we can define the combined operator 𝐼 𝐶 as 𝐼01 𝐶 = 𝑈 × 𝑈 † × 𝐼00 × 𝐼01 (3.17) 𝐼12 𝐶 = 𝑈 × 𝑈 † × 𝐼11 × 𝐼12 (3.18) [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: Compact circuit for 2 time steps evolution for population |0⟩. One subtlety is that since rescaling might be needed for the dilation (explained at the beginning of Section B), the measurement statistics of |00 ⋯ 00⟩ could be the rescaled value of |⟨0|𝜌(𝑁∆𝑡)|0⟩| 2 . Ins…
Figure 5
Figure 5. Figure 5: Compact circuit for 2 time steps evolution for population |1⟩. (b) Algorithm II To alleviate the measurement overhead, we further construct the multiple-controlled-NOT gate, i.e., the Toffoli gate, to transfer the outcome of |00 ⋯ 00⟩ into one qubit,43 and the measurem…
Figure 7
Figure 7. Figure 7: One-qubit measurement scheme for 2 time steps evolution for population |1⟩. The pros and cons for each of the algorithms are transparent. Algorithm I uses less number of qubibts whereas Algorithm II does less measurement. Indeed, for Algorithm II, only one qubit is mea…
Figure 10
Figure 10. Figure 10: Representative Gaussian distribution. Figure (a) is from the noisy simulation of Algorith I at 𝑇 = ∆𝑡 with parameters Ω = 1, 𝜉 = 0.1, 𝜔𝑐 = 7.5, 𝛽 = 5, 20K shots and 100 runs. Figure (b) is from the ideal simulation of Algorith I at 𝑇 = 3∆𝑡 with parameters Ω = 1, 𝜉 = 1…
Figure 11
Figure 11. Figure 11: Standard deviation comparison for both algorithms with 100 runs. Figure (a) with parememeters Ω = 1, 𝜉 = 0.1, 𝜔𝑐 = 7.5, 𝛽 = 5 and Figure (b) with parameters Ω = 1, 𝜉 = 1.2, 𝜔𝑐 = 2.5, 𝛽 = 0.2 [PITH_FULL_IMAGE:figures/full_fig_p014_11.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

7 extracted references · 1 canonical work pages

  1. [1]

    (1) Proceedings / 35th Annual Symposium on Foundations of Computer Science, November 20 - 22, 1994, Santa Fe, New Mexico; Goldwasser, S., IEEE Computer Society, Eds.; IEEE Computer Society Press: Los Alamitos, Calif.,

    work page 1994

  2. [4]

    (44) Bullock, S

    https://doi.org/10.1017/CBO9780511976667. (44) Bullock, S. S.; Markov, I. L. Smaller Circuits for Arbitrary N -Qubit Diagonal Computations

    doi:10.1017/cbo9780511976667

  3. [1994]

    (2) Shor, P. W. Polynomial -Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM J. Comput. 1997, 26 (5), 1484 –1509. https://doi.org/10.1137/S0097539795293172. (3) Grover, L. K. A Fast Quantum Mechanical Algorithm for Database Search. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - ...

    arXiv 1997

  4. [2003]

    (45) Light, J

    https://doi.org/10.48550/ARXIV .QUANT-PH/0303039. (45) Light, J. C.; Hamilton, I. P.; Lill, J. V . Generalized Discrete Variable Approximation in Quantum Mechanics. J. Chem. Phys. 1985, 82 (3), 1400–1409. https://doi.org/10.1063/1.448462. (46) Harris, D. O.; Engerholm, G. G.; Gwinn, W. D. Calculation of Matrix Elements for One-Dimensional Quantum-Mechanic...

    doi:10.48550/arxiv.quant-ph/0303039 1985

  5. [2012]

    (29) Rätsep, M.; Cai, Z

    https://doi.org/10.1142/8334. (29) Rätsep, M.; Cai, Z. -L.; Reimers, J. R.; Freiberg, A. Demonstration and Interpretation of Significant Asymmetry in the Low-Resolution and High-Resolution Q y Fluorescence and Absorption Spectra of Bacteriochlorophyll a. J. Chem. Phys. 2011, 134 (2), 024506. https://doi.org/10.1063/1.3518685. (30) Walters, P. L.; Allen, T...

    doi:10.1142/8334

  6. [2021]

    (49) Berry, D

    https://doi.org/10.48550/ARXIV .2106.12523. (49) Berry, D. W.; Childs, A. M.; Cleve, R.; Kothari, R.; Somma, R. D. Exponential Improvement in Precision for Simulating Sparse Hamiltonians. In Proceedings of the forty -sixth annual ACM symposium on Theory of computing ; ACM: New York New York, 2014; pp 283 –292. https://doi.org/10.1145/2591796.2591854. (50)...

    arXiv doi:10.48550/arxiv.2106.12523

  7. [2023]

    2023, 60 (1), 46–47

    IEEE Spectr. 2023, 60 (1), 46–47. https://doi.org/10.1109/MSPEC.2023.10006669. (51) Malinowski, M.; Allcock, D. T. C.; Ballance, C. J. How to Wire a 1000 -Qubit Trapped-Ion Quantum Computer. PRX Quantum 2023, 4 (4), 040313. https://doi.org/10.1103/PRXQuantum.4.040313. (52) De Leon, N. P.; Itoh, K. M.; Kim, D.; Mehta, K. K.; Northup, T. E.; Paik, H.; Palme...

    arXiv 2023

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.