REVIEW 2 major objections 4 minor 21 references
Fast quantum imaginary time evolution
T0 review · 2 major / 4 minor · reviewed 2026-08-27 · deepseek-v4-flash
Pith's one-line read A single $n$-qubit imaginary-time Trotter step costs $O(n^2)$ operations, not $O(2^{2n})$.
desk verdict The paper's central reduction is unsound: Eq. (16) cannot hold for entangled states, so the O(n^2) Fast QITE claim collapses; the idea is novel but the main result does not go through. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing mechanism is a one-qubit QITE identity: for any Pauli operator $\sigma_{a_1}$ and input state $|\psi\rangle$, there is a real vector $x=(x_0,x_1,x_2,x_3)$ such that $i\tau\sum_{b_1} x_{b_1}\sigma_{b_1}|\psi\rangle = \tau(\sigma_{a_1}-\langle\psi|\sigma_{a_1}|\psi\rangle)|\psi\rangle$ to first order in $\tau$. Multiplying this identity by $h_a\bigotimes_{i=2}^n \sigma_{a_i}$ and rearranging converts $e^{\tau H_a}|\psi\rangle$ into a smaller imaginary-time step on $n-1$ qubits applied after the unitary $U_{a_1}$. Iterating this recurrence $n$ times yields Eq. 24 and is exactly what removes the exponential operator-space dimension: at each level the free parameters are only the four single-qubit coefficients $x_{b_1}$, rather than the $4^n$ Pauli coefficients appearing in standard QITE.
What would settle it
Take a single qubit in a generic state such as $(|0\rangle+e^{i\phi}|1\rangle)/\sqrt{2}$ and a Pauli operator $\sigma_{a_1}$, and solve the equation $i\tau\sum_{b_1} x_{b_1}\sigma_{b_1}|\psi\rangle = \tau(\sigma_{a_1}-\langle\psi|\sigma_{a_1}|\psi\rangle)|\psi\rangle$ for real $x_0,x_1,x_2,x_3$; if any $\phi$ gives no real solution, the first reduction step of Fast QITE is invalid and the $O(n^2)$ per-step scaling no longer follows.
Extended reading notes
Core claim
The paper's central claim is that an $n$-qubit QITE Trotter step $e^{\tau H_a}|\psi\rangle$ can be replaced, to first order in $\tau$, by $e^{\tau h_a\langle\psi|\sigma_{a_1}|\psi\rangle \bigotimes_{i=2}^n \sigma_{a_i}} U_{a_1}|\psi\rangle$, where $U_{a_1}$ is a real-time evolution generated by a sum of only four Pauli strings. Repeating this step peels off one qubit at a time, so after at most $n$ rounds the original step equals $U_{a_n}\cdots U_{a_1}|\psi\rangle = e^{\tau H_a}|\psi\rangle/\sqrt{c_a}$ (Eq. 24). Because each $U_{a_j}$ is a Hamiltonian evolution over $O(1)$ Pauli terms, each can be implemented with $O(n)$ gates and the full Trotter step with $O(n^2)$. This replaces the standard QITE requirement of sampling an operator space of size $O(2^{2n})$ and solving the associated linear system, and it is the basis for the paper's claimed quantum advantage in sampling diagonal elements of matrix exponentials.
Load-bearing premise
The whole method rests on an unproved assumption that, for every possible quantum state and every single-qubit Pauli operator, the equation $i\tau\sum_b x_b\sigma_b|\psi\rangle = \tau(\sigma_{a_1}-\langle\psi|\sigma_{a_1}|\psi\rangle)|\psi\rangle$ has a real solution $x$; if that ever fails, the step-by-step shrinking of the problem cannot proceed.
Editorial extensions
If this is right
- For a general Pauli Hamiltonian term on $n$ qubits, each Trotter step costs $O(n^2)$ instead of $O(2^{2n})$, and a full imaginary-time evolution for an arbitrary $2^n \times 2^n$ Hamiltonian costs $O(2^{2n}n^2)$ instead of $O(2^{4n})$.
- For $k$-local Hamiltonians the per-step cost is $O(k^2)$, an exponential improvement in $k$ over the $O(2^{O(k)})$ of standard QITE, which makes long-range interaction terms easier to handle.
- Sampling diagonal entries of $e^H$ for an $H$ with polynomially many Pauli terms can be done in polynomial time, which the paper argues is exponentially faster than standard QITE and than any classical algorithm, whose output size is at least $2^n$.
- Finite-temperature expectation values under a $k$-local Hamiltonian can be estimated by Monte Carlo sampling with per-sample cost $O(\beta n k^3)$ when the observable eigenbasis is known, and $O(\beta n^2 k^4)$ when a METTS-style sampling over a $k$-local observable is used.
Reading between the lines
- The unproved solvability of the single-qubit relation in Eq. (16) is the natural pressure point: a numeric search over single-qubit states and Pauli operators would settle the recurrence, and if counterexamples exist the reduction might be repaired by choosing the order of Pauli factors adaptively instead of fixing it.
- The $O(n^2)$ cost counts gate operations for known parameters, but estimating the expectation values that set those parameters adds sampling overhead; for large $n$ that measurement cost, not the unitary count, could dominate and would need to be included in a fair resource comparison.
- The claimed quantum advantage is for a sampling task on the state $e^H|\psi\rangle$; it does not carry over to computing individual matrix elements or the whole matrix $e^H$, which may remain exponentially hard, so the advantage is tied to the observable-driven sampling formulation.
- A direct extension would apply the same one-qubit-peeling recurrence to higher-order Trotter steps or to non-Pauli generators expanded in a Pauli basis, potentially reducing QITE costs for molecular Hamiltonians with long Pauli strings.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes "Fast QITE," a variant of the quantum imaginary time evolution algorithm that aims to reduce the cost of each Trotter step from O(2^{2n}) to O(n^2) for a Pauli term acting on n qubits. The key idea is to iteratively reduce an n-qubit imaginary-time evolution to an (n-1)-qubit problem using a single-qubit linear relation (Eq. 16). The manuscript then uses this speedup to claim a quantum advantage in sampling diagonal elements of a matrix exponential and analyzes finite-temperature simulation costs. The core reduction, however, rests on a linear equation that is not solvable for general (entangled) states; this invalidates the central O(n^2) claim. The quantum advantage argument additionally ignores an exponentially small projection probability.
Significance. If the central reduction were correct, the O(n^2) per-Trotter-step cost would be a major practical improvement to QITE and would open a plausible route to quantum advantage for matrix-exponential sampling. The recursive reduction idea is creative and the paper is clearly structured. However, the failure of Eq. (16) means the claimed exponential speedup is unsupported, and the quantum advantage claim also omits a necessary 1/p measurement overhead. The paper contains no numerical demonstrations or machine-checked proofs, and the algebraic derivation is not reproducible because the central step is mathematically false for generic states.
major comments (2)
- [III. Fast QITE] Eq. (16) is not solvable for general input states, and the entire n→(n-1) reduction depends on it. The equation asserts the existence of a real vector x with i Σ_b x_b σ_{b1} |ψ> = (σ_{a1} − <ψ|σ_{a1}|ψ>)|ψ>. For the two-qubit state |ψ> = (|00>+|11>)/√2 and a1 = Z, we have <Z>=0 and the equation becomes i(x0+x3)|00>/√2 + i(x0−x3)|11>/√2 + (i x1−x2)|10>/√2 + (i x1+x2)|01>/√2 = (|00>−|11>)/√2. This requires i(x0+x3)=1 and i(x0−x3)=−1, so x3=−i, which is impossible for real x. Equivalently, the Schmidt decomposition shows that the equality on the two Schmidt branches forces σ_{a1}−<σ_{a1}> to be a multiple of the identity on the first qubit, which does not hold when the reduced state is mixed. Consequently, Eqs. (23) and (24) do not follow from the derivation, and the O(n^2) per-Trotter-step claim in Section IV is unsupported for the entangled states QITE is designed to evolve.
- [V. Sampling Diagonal Elements of Matrix Exponentials] The claimed polynomial-time cost of sampling a diagonal element ignores the probability of the projective measurement. The algorithm prepares e^H|ψ>/√c_H and projects onto |ψ>, which succeeds with probability p = |<ψ|e^H|ψ>|^2/c_H. This probability can be exponentially small: for |ψ> = |0^n> and H = λ Σ_i X_i, one has p = cosh^{2n}(λ)/cosh^n(2λ) ≈ 2^{-n} for large λ. The paper does not describe amplitude estimation or any other technique to overcome this 1/p overhead, so the stated O(poly(n)) cost for sampling a diagonal element is not established. The same issue propagates into the finite-temperature Monte Carlo estimates in Section VI, where each proposed sample requires computing a diagonal element by this projection method.
minor comments (4)
- [IV. Computational Cost of Fast QITE] The statement that the full evolution e^H|ψ>/√c_H costs O(2^{2n} n^2) for fixed precision omits the number of Trotter repetitions 1/τ required to control the Trotter error; the error of the product formula in Eq. (1) is stated as O(τ^2) but the accumulated error over 1/τ steps is O(τ). This does not change the relative comparison with standard QITE, but it makes the absolute cost claim imprecise.
- [V. Sampling Diagonal Elements of Matrix Exponentials] The classical lower bound of Ω(2^n) is argued from the size of the vector e^H|ψ>, but a classical algorithm that only needs one diagonal element need not write down the full vector; the claim of a polynomial-time quantum advantage therefore also requires a more careful classical comparison.
- [VI. Finite Temperature Simulation with Fast QITE] The METTS cost estimate jumps from O(β n k^3) for generating the state to O(β n^2 k^4) for the overall Monte Carlo step; the extra factor of n k appears to multiply rather than add the measurement cost and should be justified.
- [I–VII (throughout)] The typesetting of equations is heavily corrupted in the manuscript under review (for example, '/summationtext', '/productdisplay', '/bardblex', '∝vecx'), which makes the algebra hard to follow; the final version should be carefully typeset.
Circularity Check
No significant circularity: the Fast QITE derivation is self-contained, and the main caveat is an unproved existence assumption in Eq. (16), which is a correctness issue rather than a circular one.
full rationale
The paper's derivation chain is not circular. Standard QITE is defined by solving the linear system M x + r = 0 in the full 4^n Pauli basis, with M and r given by expectation values in Eqs. (7), (8), and (11). Fast QITE's central step is Eq. (16), which asserts the existence of a real four-component vector x such that iτ Σ_{b1} x_{b1} σ_{b1} |ψ⟩ = τ(σ_{a1} − ⟨ψ|σ_{a1}|ψ⟩)|ψ⟩ to first order. This is an assumption about representability of a particular vector in the full Hilbert space by a single-qubit operator; it is not obtained by fitting a parameter to the same quantity that is later called a prediction, nor is any result defined in terms of the conclusion it is supposed to establish. The reduction from n qubits to (n−1) qubits in Eqs. (17)–(23) is a direct algebraic consequence of Eq. (16), and the O(n²) cost bound in Section IV follows from counting the unitaries U_{a1}, ..., U_{an} and their Pauli decompositions. The cited QITE papers [8] and [18] provide the background formalism and sampling formulas, but the central derivation does not reduce to a self-citation chain: even if those references were removed, the logical structure of the paper would be unchanged, though unsupported at Eq. (16). The genuine weakness flagged by the skeptic is that Eq. (16) may have no real solution for entangled states, so the reduction could fail; that is a correctness or rigor concern, not circularity. There are no fitted inputs relabeled as predictions, no importation of a uniqueness theorem, no ansatz smuggled in via citation, and no renaming of a known result as a new derivation. The conclusion is therefore not equivalent to its inputs by construction.
Assumptions & free parameters
assumptions (4)
- standard math Trotter product formula: e^H = (∏_a e^{τH_a})^{1/τ} + O(τ^2)
- domain assumption For any normalized state and any single-qubit Pauli σ_a, there is a real vector x with iτ Σ_b x_b σ_b |ψ⟩ = τ(σ_a − ⟨σ_a⟩)|ψ⟩ + O(τ^2)
- domain assumption Expectation values of Pauli operators can be measured at unit cost
- standard math A Hamiltonian that is a sum of four Pauli strings of length n can be simulated with O(n) gates
Cite this review
Pith. "Pith review of Fast quantum imaginary time evolution." pith.science (2026). https://pith.science/paper/LZWQFVBU
@misc{pith2026200912239,
author = {Pith},
title = {Pith review of: Fast quantum imaginary time evolution},
year = {2026},
howpublished = {\url{https://pith.science/paper/LZWQFVBU}},
note = {Machine review of arXiv:2009.12239}
}
read the original abstract
A fast implementation of the quantum imaginary time evolution (QITE) algorithm called Fast QITE is proposed. The algorithmic cost of QITE typically scales exponentially with the number of particles it nontrivially acts on in each Trotter step. In contrast, a Fast QITE implementation reduces this to only a linear scaling. It is shown that this speed up leads to a quantum advantage when sampling diagonal elements of a matrix exponential, which cannot be achieved using the standard implementation of the QITE algorithm. Finally the cost of implementing Fast QITE for finite temperature simulations is also discussed.
Reference graph
Works this paper leans on
-
[1]
B. M. Terhal, and D. P. DiVincenzo, Phys. Rev. A 61, 022301 (2000)
work page 2000
- [2]
- [3]
- [4]
- [5]
- [6]
-
[7]
Y . Ge, A. Molnár, and J. I. Cirac, Phys. Rev. Lett. 116, 080503 (2016)
work page 2016
- [8]
Show all 21 references
-
[9]
Preskill, Quantum 2, 79 (2018)
J. Preskill, Quantum 2, 79 (2018)
2018
-
[10]
P. J. J. O’Malley et al., Phys. Rev. X 6, 031007 (2016)
2016
-
[11]
N. M. Linke, D. Maslov, M. Roetteler, S. Debnath, C. Figgatt, K. A. Landsman, K. Wright, and C. Monroe, Proc. Natl. Acad. Sci. USA 114, 3305 (2017)
2017
-
[12]
Kandala, A
A. Kandala, A. Mezzacapo, K. Temme, M. Takita, M. Brink, J. M. Chow, and J. M. Gambetta, Nature 549, 242 (2017)
2017
-
[13]
E. F. Dumitrescu, A. J. McCaskey, G. Hagen, G. R. Jansen, T. D. Morris, T. Papenbrock, R. C. Pooser, D. J. Dean, and P. Lougovski, Phys. Rev. Lett. 120, 210501 (2018)
2018
-
[14]
N. Klco, E. F. Dumitrescu, A. J. McCaskey, T. D. Morris, R. C. Pooser, M. Sanz, E. Solano, P. Lougovski, and M. J. Savage, Phys. Rev. A 98, 032331 (2018)
2018
-
[15]
J. I. Colless, V . V . Ramasesh, D. Dahlen, M. S. Blok, M. E. Kimchi-Schartz, J. R. McClean, J. Carter, W. A. de Jong, and I . Siddiqi, Phys. Rev. X 8, 011021 (2018)
2018
-
[16]
G. C. Wick, Phys. Rev. 96, 1124 (1954)
1954
-
[17]
Y eter-Aydeniz, R
K. Y eter-Aydeniz, R. C. Pooser, and G. Siopsis, npj Quant. In f. 6, 63 (2020)
2020
-
[18]
S.-N. Sun, M. Motta, R. N. Tazhigulov, A. T. K. Tan, G. K.-L. Chan, and A. J. Minnich, arXiv:2009.03542
2009 arXiv
-
[19]
Berry, A
D. Berry, A. Childs, R. Cleve, R. Kothary, and R. Somma, Phys. Rev. Lett. 114, 090502 (2015)
2015
-
[20]
Moler, and C
C. Moler, and C. V . Loan, SIAM Rev. 45, 3 (2003)
2003
-
[21]
Stoudenmire, and S
E.M. Stoudenmire, and S. R. White New J. Phys. 12, 055026 (2010)
2010
Reviewed August 27, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.