Pith. sign in

REVIEW 3 major objections 3 minor 68 references

A Dequantized Algorithm for the Guided Local Hamiltonian Problem

T0 review · 3 major / 3 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 This paper claims that a classical algorithm can solve the guided local Hamiltonian problem for general k-local Hamiltonians without an operator-norm constraint, reaching limited constant accuracy generally and arbitrary constant accuracy…

desk verdict The paper has a real idea—dequantizing imaginary-time evolution to remove the operator-norm constraint—but the main theorem's parameter range is too broad and the proof has a load-bearing gap that looks fixable. read the letter →

arxiv 2411.16163 v2 pith:BELQPAPN submitted 2024-11-25 quant-ph

Yukun Zhang , Yusen Wu , Xiao Yuan This is my paper · ORCID
classification quant-ph MSC 68Q1281P68 PACS 03.67.Ac03.67.-a
keywords guidedlocalHamiltonianground-stateenergyestimationdequantizationrandomizedquantumimaginary-timeevolutionclusterexpansionanalyticcontinuationspectralgapadvantage
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

The paper tries to establish that the guided local Hamiltonian problem, a ground-state energy estimation task that is BQP-complete when a good guiding state is supplied, can often be solved by a classical computer. Its vehicle is a dequantized, and therefore classically simulatable, version of a randomized quantum imaginary-time evolution algorithm. The key move is to evaluate the relevant partition function with cluster expansion, which removes the constant operator-norm constraint that made earlier dequantizations inapplicable to physically realistic Hamiltonians. The results give polynomial-time classical solutions when the required accuracy sits above a constant threshold $\epsilon_{*} = 2e^{2}d(d+1)$, and when the guiding state has overlap at least $1/\sqrt{2}$, analytic continuation extends the accuracy to any constant. If the claims hold, the boundary between classical and quantum computational power for ground-state problems shifts, with quantum advantage surviving only in more restricted regimes.

What carries the argument

The load-bearing object is the shifted imaginary-time partition function $D_{\beta}(H-x)=\langle\psi_I|e^{-\beta(H-x)}|\psi_I\rangle$, which equals a convolution of the guiding state's spectral function with the filter $e^{\beta x}$. The residue function $R(x)=D_{\beta}(H-x)-D_{2\beta}(H-x)$ falls monotonically as $x$ approaches the ground-state energy and serves as the termination threshold. Classically, this quantity is computed through a cluster expansion of $\log\langle y|e^{-\beta(H-x)}|x\rangle$: terms factor over connected clusters of the Hamiltonian's interaction graph, and the graph degree $d$ controls the convergence radius $\beta_{*}=(2e^{2}d(d+1))^{-1}$. For the arbitrary-accuracy result, the map $\beta\mapsto\beta\phi(z)$ with $\phi(z)=\log(1-z/\nu)/\log(1-1/\nu')$ performs analytic continuation, and the zero-free region $\mathrm{Re}(\beta)>0$ guaranteed when $\gamma\ge 1/\sqrt{2}$ makes $\log D_{\beta}(H)$ analytic so that the complex Taylor approximation applies.

What would settle it

Compute the cluster-expansion truncation error for a concrete k-local Hamiltonian at $\beta$ just below $\beta_{*}=(2e^{2}d(d+1))^{-1}$: if the error exceeds $|S|(2e^{2}d(d+1)|\beta|)^{M+1}/(1-2e^{2}d(d+1)|\beta|)$, the classical estimator fails. Alternatively, search numerically for a zero of $D_{\beta}(H)$ with $\mathrm{Re}(\beta)>0$ for a guiding state with overlap $\gamma^2\ge1/2$; finding one would disprove the zero-free lemma on which the arbitrary-constant-accuracy result rests.

Watch

Extended reading notes

Core claim

The central claim is that there is a classical algorithm that solves the ground-state energy estimation problem for general k-local Hamiltonians, with no bound on the operator norm of $H$, provided the spectral gap is not too small compared with the desired accuracy and the guiding state has a semiclassical form that is classically accessible. The algorithm estimates the shifted partition function $D_{\beta}(H-x)=\langle\psi_I|e^{-\beta(H-x)}|\psi_I\rangle$ by cluster-expanding its logarithm, and uses the residue $R(x)=D_{\beta}(H-x)-D_{2\beta}(H-x)$ as a monotone termination test to locate $E_0$. Cluster expansion converges when $\beta<\beta_{*}=(2e^{2}d(d+1))^{-1}$, giving accuracy $\epsilon>\epsilon_* = 2e^{2}d(d+1)$ with runtime $R^2|S|/\epsilon$ times a factor polynomial in $(|S|/(\gamma^2\beta\epsilon[1-\beta/\beta_*]))^{\log(\beta_*/\beta)}$. When the guiding state has overlap $\gamma\ge 1/\sqrt{2}$, the logarithm of the partition function has no zeros for $\mathrm{Re}(\beta)>0$, so analytic continuation extends the imaginary time to an arbitrary constant and yields arbitrary constant accuracy, at the cost of a runtime of order $(e^{2\pi\beta/\beta_*}/(\beta\epsilon^2)\mathrm{poly}(|S|))^{e^{2\pi\beta/\beta_*}}$. Normalizing the Hamiltonian improves the accuracy threshold to $\epsilon > \epsilon_*/\|H\|$.

Load-bearing premise

The whole construction depends on the gap-to-accuracy condition $\Delta/\epsilon \ge \ln(\gamma^{-2}\epsilon^{-1})$, which keeps the imaginary-time parameter $\beta$ small enough that $\beta\epsilon\le1$ and the cluster expansion converges; if the gap is smaller or the accuracy demand is tighter, the dequantized algorithm loses its efficiency guarantee.

Editorial extensions

If this is right

  • For classically accessible guiding states, exponential quantum advantage is not expected when only constant accuracy above $\epsilon_*$ is required; the problem is classically solvable in time polynomial in the system size for fixed gap and accuracy.
  • Removing the operator-norm constraint makes the method applicable to realistic Hamiltonians with $\|H\|=\mathrm{poly}(n)$, such as Ising-type models; normalizing $H$ further relaxes the accuracy threshold to $\epsilon_*/\|H\|$.
  • With overlap at least $1/\sqrt{2}$, the classical algorithm reaches arbitrary constant accuracy, though its runtime has an exponent that grows doubly exponentially with the inverse gap.
  • The BQP-hardness of the guided local Hamiltonian problem depends on demanding arbitrarily small inverse-polynomial accuracy; for the classically accessible instances considered here, constant accuracy is not enough to guarantee quantum advantage.
  • The accuracy threshold $\epsilon_* = 2e^{2}d(d+1)$ is determined by the interaction-graph degree, so sparser Hamiltonians admit tighter accuracies before the cluster expansion breaks down.

Reading between the lines

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

  • An implicit corollary of the accuracy threshold is that the real boundary for quantum advantage may be set by the required precision relative to the spectral gap, not by the Hamiltonian's norm; a matching hardness result for $\epsilon\le\epsilon_*$ would make this crisp.
  • The $\gamma=1/\sqrt2$ overlap threshold is where the zero-free proof becomes tight, so a natural test is whether overlaps just below $1/\sqrt2$ make constant-accuracy estimation classically hard, possibly by locating zeros of the partition function.
  • The method's dependence on Assumption 1 suggests testing it on molecular systems with known large gaps; if the gap-to-accuracy condition fails in practice, a resummed or higher-order cluster expansion would be needed to extend the approach.
  • For guiding states prepared by deeper circuits, the similarity-transformed Hamiltonian's interaction degree $d'$ grows and the accuracy threshold worsens; quantifying this growth on concrete circuit families would show how far the analytic-continuation route can go.
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 / 3 minor

Summary. The paper proposes a classical dequantized algorithm for the guided local Hamiltonian (GLH) problem, based on a randomized quantum imaginary-time evolution (RQITE) scheme. The main result, Theorem 2/8, claims a classical algorithm solving the ground state energy estimation problem for general k-local Hamiltonians without the operator-norm constraint, for limited accuracy ε > ε* = 2e²d(d+1), with runtime polynomial in the system parameters up to a log-type exponent in 1/(1−β/β*). A second result, Theorem 3/10, claims arbitrary constant accuracy when the guiding state has overlap γ = 1/√2 and is prepared by a constant-depth circuit, using analytic continuation and a zero-free-region argument. The paper also gives corollaries for normalized Hamiltonians and discusses the boundary between classical and quantum computational power.

Significance. If the technical gaps were repaired, the cluster-expansion dequantization would be a meaningful advance: it provides an explicit classical algorithm for an interesting regime of the GLH problem, with concrete runtime formulas and a clear comparison to prior dequantized QSVT approaches. The paper correctly identifies the role of the cluster-expansion threshold β* and connects the limitations to hardness results for Gibbs-state partition functions. Strengths include a reasonably detailed cluster-expansion derivation following Ref. [30], explicit dependence on the Hamiltonian interaction degree d, and a serious discussion of prior work. However, as written, the central termination and parameter-range arguments contain load-bearing errors, so the main theorems are not established in their stated form.

major comments (3)
  1. [Appendix C.1, Lemma 2 (Eqs. C8–C9)] The stopping rule in Lemma 2 does not separate the two energy regimes. For x∈[Emax,E0−ε] the lemma only proves R(x)>p0βε, while the threshold is Ξ=(β/2+1)p0ε = p0ε + (p0/2)βε. Under Assumption 1 one has βε≤1, so Ξ is strictly larger than the lower bound p0βε; for example, with βε=0.1, R(E0−ε)≈p0(e^{−0.1}−e^{−0.2})≈0.086p0, whereas Ξ≈0.105p0. The condition R(x)<Ξ can therefore be satisfied at grid points several ε below E0, so the RQITE algorithm can terminate before its output is within ε of E0. This invalidates the termination protocol used by Theorem 5 and inherited by Theorems 2 and 8.
  2. [Appendix E.1, Theorem 8; main-text Eq. (4) and Theorem 2] The theorem's parameter range includes β≤0. With β=Δ^{-1} ln(γ^{-2}ε^{-1}) (Eq. C7), β is positive only when γ²ε<1. Assumption 1 as stated in Eq. C6 is vacuous when γ²ε>1 because the right-hand side is negative, and Theorem 2/8 allows ε>ε* without any condition on γ²; e.g. γ=1/√2 and ε=20 give β=−ln10/Δ<0. In that regime e^{−β(H−x)} is not trace non-increasing, every term in R(x)=Dβ−D2β is non-positive for x≤E0, and the positive threshold Ξ causes immediate termination at the first grid point, outputting an energy not within ε of E0. The theorem must either explicitly assume β>0 (e.g., γ²ε<1) and handle x∈[Ea,Emax], or replace Lemma 2 with a termination rule valid for β≤0. The proof also states 'we know that βϵ ≥ 1', which contradicts Assumption 1/Lemma 2, where βϵ≤1; the claimed accuracy threshold ε>ε* is not derived by the argument given.
  3. [Main text, Corollary 1] The normalization corollary appears to invert the accuracy threshold. Applying Theorem 8 to ~H=H/‖H‖ with relative accuracy ε>ε* gives an absolute error ‖H‖ε for the original problem, i.e. a threshold ε_abs>‖H‖ε*, not ε_abs>ε*/‖H‖. To reach ε_abs>ε*/‖H‖ one would need relative accuracy ε*/‖H‖², which is inverse-polynomial and outside the theorem's range. As stated, Table I and Corollary 1 claim a stronger result than the proof supports.
minor comments (3)
  1. [Appendix C.1, Eq. (C16)] The text says 'e^{-β(H-x)} ≼ 0 is a trace non-increasing operator'; the semidefinite notation is wrong, and the intended meaning appears to be that e^{-β(H-x)} is positive semidefinite and trace non-increasing for x≤E0.
  2. [Appendix E.2, proof of Theorem 9] The proof says zero points of the partition function are determined by 'the second part in the last line of Eq. (C10)', but the relevant expression Sβ(H) is defined in Eq. (E4), not Eq. (C10); the cross-reference should be corrected.
  3. [Main text, around Eq. (3) and Fig. 1] There are several presentation typos, including 'decades monotonically' for 'decays monotonically', 'Hamdard test circuit' for 'Hadamard test circuit', and 'the algorithm outputs the estimation E′0 when R(x) decays below the termination threshold' where the sentence structure is repetitive.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; the dequantized RQITE results are derived from stated gap/overlap inputs and external cluster-expansion bounds, not from their own conclusions.

full rationale

The derivation chain is self-contained. Equation (C2) defines D_beta(H-x) as a spectral expectation value, and R(x) is defined in Eq. (C5) as a difference of two such expectation values. Lemma 2 fixes beta and the termination threshold Xi from the input lower bounds gamma and Delta and the requested accuracy epsilon (Eqs. C6-C9); the threshold is not extracted from the algorithm's output. The dequantized estimator in Theorem 6 approximates D_beta(H-x) via cluster expansion, whose convergence radius beta* = 1/(2e^2 d(d+1)) comes from Proposition 9 of the external Ref. [30], and the analytic-continuation step uses Lemma 5 of Ref. [30]. The zero-free region needed for arbitrary constant accuracy is proved in Theorem 9 from p0 >= 1/2 without invoking the paper's own conclusions. The authors' prior work, Ref. [29], is cited for context and for a 2D variant, but the proofs of Theorems 2 and 3 do not rest on it, and no uniqueness claim is imported from a self-citation. No parameter is fitted to the data the algorithm is supposed to predict: gamma, Delta, and epsilon are inputs, and the accuracy threshold epsilon > epsilon* follows algebraically from beta < beta* together with Assumption 1. The separate concern that the stated range can include beta <= 0 when gamma^2 epsilon > 1 is a correctness gap in the parameter regime, not a circular reduction, so it does not raise the circularity score.

Assumptions & free parameters 0 free parameters · 4 assumptions · 0 invented entities

No free parameters are fitted to data; beta and beta* are derived quantities, not empirical fits. No new particles, forces, or mediators are introduced. The load-bearing input assumptions are the spectral-gap condition, the semiclassical classically accessible guiding state, and the large-overlap constant-depth circuit condition used for arbitrary constant accuracy.

assumptions (4)
  • domain assumption Assumption 1: the spectral gap satisfies Delta/epsilon >= ln(gamma^{-2} epsilon^{-1}).
    Used to set beta = ln(gamma^{-2} epsilon^{-1})/Delta and to enforce beta epsilon <= 1. Stated as Eq. (4) in the main text and as Assumption 1 in Appendix C. It is an unproven restriction on the physical system.
  • domain assumption The guiding state is semiclassical and classically accessible: |psi_c> = sum_{j=1}^R a_j |x_j> with R = O(poly(n)) and product states |x_j>.
    Required for the cluster expansion of D_beta(H-x) in Eq. (7). The authors note BQP-hardness survives for semiclassical guiding states, so the assumption is standard for this line of work, but it is an assumed input model.
  • domain assumption For arbitrary constant accuracy: overlap gamma = 1/sqrt(2), guiding state prepared by a constant-depth circuit U, and H defined on an O(1)-dimensional lattice (Theorem 3).
    These conditions guarantee the zero-free region for log D_beta(H) and keep the similarity-transformed Hamiltonian H' = U^dagger H U local with bounded degree d'. Without them the analytic continuation argument does not go through.
  • standard math Cluster expansion convergence for beta < beta* = 1/(2e^2 d(d+1)), using Lemma 4 from Ref. [30] and the bound |G_m| <= |S| (ed)^m.
    The classical algorithm approximates log d_{x,y,beta}(H) by truncating a connected-cluster expansion. The validity relies on external results from the literature, treated as black-box lemmas.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Dequantized Algorithm for the Guided Local Hamiltonian Problem." pith.science (2026). https://pith.science/paper/BELQPAPN

@misc{pith2026241116163,
  author       = {Pith},
  title        = {Pith review of: A Dequantized Algorithm for the Guided Local Hamiltonian Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BELQPAPN}},
  note         = {Machine review of arXiv:2411.16163}
}
read the original abstract

The local Hamiltonian (LH) problem, the quantum analog of the classical constraint satisfaction problem, is a cornerstone of quantum computation and complexity theory. It is known to be QMA-complete, indicating that it is challenging even for quantum computers. Interestingly, the guided local Hamiltonian (GLH) problem -- an LH problem with a guiding state that has a non-trivial overlap with the ground state -- can be efficiently solved on a quantum computer and is proved to be BQP-complete. This makes the GLH problem a valuable framework for exploring the fundamental separation between classical and quantum computation. Remarkably, the quantum algorithm for solving the GLH problem can be `dequantized' (i.e., made classically simulatable) under certain conditions, such as when only constant accuracy is required and when the Hamiltonian satisfies an unrealistic constant operator norm constraint. In this work, we relieve these restrictions by introducing a dequantized classical algorithm for a randomized quantum imaginary-time evolution quantum algorithm. We demonstrate that it achieves either limited or arbitrary constant accuracy, depending on whether the guiding state's overlap is general or exceeds a certain threshold. Crucially, our approach eliminates the constant operator norm constraint on the Hamiltonian, opening its applicability to realistic problems. Our results advance the classical solution of the GLH problem in practical settings and provide new insights into the boundary between classical and quantum computational power.

Figures

Figures reproduced from arXiv: 2411.16163 by the authors.

Figure 1
Figure 1. FIG. 1. (a) Sketch of the [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

68 extracted references · 51 canonical work pages

  1. [30]

    Dequantizing algorithms to understand quantum advantage in machine learning

    Ewin Tang. Dequantizing algorithms to understand quantum advantage in machine learning. Nature Reviews Physics , 4(11):692–693, 2022

    work page 2022

  2. [1]

    A key requirement for the algorithm is that the spectral gap is larger than the accuracy. The rationale is that around x = E0, the effect of the first-excited state component in R(x) can be controlled by e−β∆ so that it will not affect the determination of E′ 0 dramatically. Specifically, we assume that ∆ ε ≥ ln(γ−2ε−1), (4) a requirement that is satisfia...

    work page

  3. [2]

    Let the similarity-transformed Hamiltonian H ′ = U †HU and the maximum degree of its corresponding interaction graph be denoted as d′

    Suppose H representing a k-local Hamiltonian defined on a O(1)-dimensional lattice. Let the similarity-transformed Hamiltonian H ′ = U †HU and the maximum degree of its corresponding interaction graph be denoted as d′. Then, if the condition in Eq. (4) holds, there exists a classical algorithm that solves the GSEE problem with a run time e2πβ/β ∗ βε2 poly...

    work page

  4. [3]

    Superconducting magnets

    Martin N Wilson. Superconducting magnets. 1983

    work page 1983

  5. [4]

    Experimental properties of superfluid he 3

    John C Wheatley. Experimental properties of superfluid he 3. Reviews of modern physics , 47(2):415, 1975

    work page 1975

  6. [5]

    Topological orders and edge excitations in fractional quantum hall states

    Xiao-Gang Wen. Topological orders and edge excitations in fractional quantum hall states. Advances in Physics, 44(5):405– 473, 1995

    work page 1995

  7. [6]

    Z 2 topological order and the quantum spin hall effect

    Charles L Kane and Eugene J Mele. Z 2 topological order and the quantum spin hall effect. Physical review letters , 95(14):146802, 2005. 7

    work page 2005

  8. [7]

    Quantum chromodynamics at high energy

    Yuri V Kovchegov and Eugene Levin. Quantum chromodynamics at high energy . Cambridge University Press, 2013

    work page 2013

Show all 68 references
  1. [8]

    Quantum chemistry , volume 6

    Ira N Levine, Daryle H Busch, and Harrison Shull. Quantum chemistry , volume 6. Pearson Prentice Hall Upper Saddle River, NJ, 2009

    2009

  2. [9]

    Quantum chemistry in the age of quantum computing

    Yudong Cao, Jonathan Romero, Jonathan P Olson, Matthias Degroote, Peter D Johnson, M´ aria Kieferov´ a, Ian D Kivlichan, Tim Menke, Borja Peropadre, Nicolas PD Sawaya, et al. Quantum chemistry in the age of quantum computing. Chemical reviews, 119(19):10856–10915, 2019

    2019

  3. [10]

    The complexity of the local hamiltonian problem.Siam journal on computing, 35(5):1070–1097, 2006

    Julia Kempe, Alexei Kitaev, and Oded Regev. The complexity of the local hamiltonian problem.Siam journal on computing, 35(5):1070–1097, 2006

    2006

  4. [11]

    Quantum hamiltonian complexity

    Sevag Gharibian, Yichen Huang, Zeph Landau, Seung Woo Shin, et al. Quantum hamiltonian complexity. Foundations and Trends® in Theoretical Computer Science , 10(3):159–282, 2015

    2015

  5. [12]

    Classical and quantum computation

    Alexei Yu Kitaev, Alexander Shen, and Mikhail N Vyalyi. Classical and quantum computation . Number 47. American Mathematical Soc., 2002

    2002

  6. [13]

    The bose-hubbard model is qma-complete

    Andrew M Childs, David Gosset, and Zak Webb. The bose-hubbard model is qma-complete. In Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I 41, pages 308–319. Springer, 2014

    2014

  7. [14]

    Electronic structure in a fixed basis is qma-complete

    Bryan O’Gorman, Sandy Irani, James Whitfield, and Bill Fefferman. Electronic structure in a fixed basis is qma-complete. arXiv preprint arXiv:2103.08215 , 2021

    2021 arXiv

  8. [15]

    Quantum np-a survey

    Dorit Aharonov and Tomer Naveh. Quantum np-a survey. arXiv preprint quant-ph/0210077 , 2002

    2002 arXiv

  9. [16]

    Reducibility among combinatorial problems

    Richard M Karp. Reducibility among combinatorial problems . Springer, 2010

    2010

  10. [17]

    Guest column: the quantum pcp conjecture

    Dorit Aharonov, Itai Arad, and Thomas Vidick. Guest column: the quantum pcp conjecture. Acm sigact news, 44(2):47–79, 2013

    2013

  11. [18]

    Near-optimal ground state preparation

    Lin Lin and Yu Tong. Near-optimal ground state preparation. Quantum, 4:372, 2020

    2020

  12. [19]

    Ground-state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices

    Yulong Dong, Lin Lin, and Yu Tong. Ground-state preparation and energy estimation on early fault-tolerant quantum computers via quantum eigenvalue transformation of unitary matrices. PRX Quantum , 3(4):040305, 2022

    2022

  13. [20]

    Heisenberg-limited ground-state energy estimation for early fault-tolerant quantum computers

    Lin Lin and Yu Tong. Heisenberg-limited ground-state energy estimation for early fault-tolerant quantum computers. PRX Quantum, 3(1):010318, 2022

    2022

  14. [21]

    Randomized quantum algorithm for statistical phase estimation

    Kianna Wan, Mario Berta, and Earl T Campbell. Randomized quantum algorithm for statistical phase estimation. Physical Review Letters, 129(3):030503, 2022

    2022

  15. [22]

    Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision

    Guoming Wang, Daniel Stilck Fran¸ ca, Ruizhe Zhang, Shuchen Zhu, and Peter D Johnson. Quantum algorithm for ground state energy estimation using circuit depth with exponentially improved dependence on precision. Quantum, 7:1167, 2023

    2023

  16. [23]

    Even shorter quantum circuit for phase estimation on early fault-tolerant quantum computers with applications to ground-state energy estimation

    Zhiyan Ding and Lin Lin. Even shorter quantum circuit for phase estimation on early fault-tolerant quantum computers with applications to ground-state energy estimation. PRX Quantum , 4(2):020331, 2023

    2023

  17. [24]

    On low-depth algorithms for quantum phase estimation

    Hongkang Ni, Haoya Li, and Lexing Ying. On low-depth algorithms for quantum phase estimation. Quantum, 7:1165, 2023

    2023

  18. [25]

    Dequantizing the quantum singular value transformation: hardness and applications to quantum chemistry and the quantum pcp conjecture

    Sevag Gharibian and Fran¸ cois Le Gall. Dequantizing the quantum singular value transformation: hardness and applications to quantum chemistry and the quantum pcp conjecture. In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing , pages 19–32, 2022

    2022

  19. [26]

    Improved hardness results for the guided local hamiltonian problem

    Chris Cade, Marten Folkertsma, Sevag Gharibian, Ryu Hayakawa, Fran¸ cois Le Gall, Tomoyuki Morimae, and Jordi Wegge- mans. Improved hardness results for the guided local hamiltonian problem. arXiv preprint arXiv:2207.10250 , 2022

    2022 arXiv

  20. [27]

    Complexity of the guided local hamiltonian problem: Improved parameters and extension to excited states

    Chris Cade, Marten Folkertsma, and Jordi Weggemans. Complexity of the guided local hamiltonian problem: Improved parameters and extension to excited states. arXiv preprint arXiv:2207.10097 , 2022

    2022 arXiv

  21. [28]

    Classical algorithms for constant approximation of the ground state energy of local hamiltonians

    Fran¸ cois Le Gall. Classical algorithms for constant approximation of the ground state energy of local hamiltonians. arXiv preprint arXiv:2410.21833, 2024

    2024 arXiv

  22. [29]

    Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

    Andr´ as Gily´ en, Yuan Su, Guang Hao Low, and Nathan Wiebe. Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing , pages 193–204, 2019

    2019

  23. [31]

    An efficient classical algorithm for simulating short time 2d quantum dynamics

    Yusen Wu, Yukun Zhang, and Xiao Yuan. An efficient classical algorithm for simulating short time 2d quantum dynamics. arXiv preprint arXiv:2409.04161 , 2024

    2024

  24. [32]

    Classical simulation of short-time quantum dynamics

    Dominik S Wild and ´Alvaro M Alhambra. Classical simulation of short-time quantum dynamics. PRX Quantum , 4(2):020340, 2023

    2023

  25. [33]

    Polynomial-time classical sampling of high-temperature quantum gibbs states

    Chao Yin and Andrew Lucas. Polynomial-time classical sampling of high-temperature quantum gibbs states. arXiv preprint arXiv:2305.18514, 2023

    2023 arXiv

  26. [34]

    Algorithmic cluster expansions for quantum problems

    Ryan L Mann and Romy M Minko. Algorithmic cluster expansions for quantum problems. PRX Quantum , 5(1):010305, 2024

    2024

  27. [35]

    High-temperature gibbs states are unentangled and efficiently preparable

    Ainesh Bakshi, Allen Liu, Ankur Moitra, and Ewin Tang. High-temperature gibbs states are unentangled and efficiently preparable. arXiv preprint arXiv:2403.16850 , 2024

    2024 arXiv

  28. [36]

    The computational hardness of counting in two-spin models on d-regular graphs

    Allan Sly and Nike Sun. The computational hardness of counting in two-spin models on d-regular graphs. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science , pages 361–369. IEEE, 2012

    2012

  29. [37]

    The complexity of approximating complex-valued ising and tutte partition functions

    Leslie Ann Goldberg and Heng Guo. The complexity of approximating complex-valued ising and tutte partition functions. computational complexity, 26:765–833, 2017

    2017

  30. [38]

    Learning quantum hamiltonians from high-temperature gibbs states and real-time evolutions

    Jeongwan Haah, Robin Kothari, and Ewin Tang. Learning quantum hamiltonians from high-temperature gibbs states and real-time evolutions. Nature Physics, pages 1–5, 2024. 8

    2024

  31. [39]

    Quantum hamiltonian complexity in thermal equilibrium

    Sergey Bravyi, Anirban Chowdhury, David Gosset, and Pawel Wocjan. Quantum hamiltonian complexity in thermal equilibrium. Nature Physics, 18(11):1367–1370, 2022

    2022

  32. [40]

    Qma with subset state witnesses

    Alex Bredariol Grilo, Iordanis Kerenidis, and Jamie Sikora. Qma with subset state witnesses. In International Symposium on Mathematical Foundations of Computer Science , pages 163–174. Springer, 2015

    2015

  33. [41]

    Statistical theory of equations of state and phase transitions

    Tsung-Dao Lee and Chen-Ning Yang. Statistical theory of equations of state and phase transitions. ii. lattice gas and ising model. Physical Review, 87(3):410, 1952

    1952

  34. [42]

    M.E. Fisher. The Nature of Critical Points . University of Colorado Press, 1965

    1965

  35. [43]

    Combinatorics and complexity of partition functions , volume 30

    Alexander Barvinok. Combinatorics and complexity of partition functions , volume 30. Springer, 2016

    2016

  36. [44]

    Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems

    Aram W Harrow, Saeed Mehraban, and Mehdi Soleimanifar. Classical algorithms, correlation decay, and complex zeros of partition functions of quantum many-body systems. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages 378–386, 2020

    2020

  37. [45]

    Inapproximability of the partition function for the antiferromagnetic ising and hard-core models

    Andreas Galanis, Daniel ˇStefankoviˇ c, and Eric Vigoda. Inapproximability of the partition function for the antiferromagnetic ising and hard-core models. Combinatorics, Probability and Computing , 25(4):500–559, 2016

    2016

  38. [46]

    Peps as unique ground states of local hamiltonians

    David Perez-Garcia, Frank Verstraete, J Ignacio Cirac, and Michael M Wolf. Peps as unique ground states of local hamiltonians. arXiv preprint arXiv:0707.2260 , 2007

    2007 arXiv

  39. [47]

    Circuit-to-hamiltonian from tensor networks and fault tolerance

    Anurag Anshu, Nikolas P Breuckmann, and Quynh T Nguyen. Circuit-to-hamiltonian from tensor networks and fault tolerance. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing , pages 585–595, 2024

    2024

  40. [48]

    Computational complexity of isometric tensor network states

    Daniel Malz and Rahul Trivedi. Computational complexity of isometric tensor network states. arXiv preprint arXiv:2402.07975, 2024

    2024 arXiv

  41. [49]

    Sequential generation of projected entangled-pair states

    Zhi-Yuan Wei, Daniel Malz, and J Ignacio Cirac. Sequential generation of projected entangled-pair states. Physical Review Letters, 128(1):010607, 2022

    2022

  42. [50]

    Preparing projected entangled pair states on a quantum computer

    Martin Schwarz, Kristan Temme, and Frank Verstraete. Preparing projected entangled pair states on a quantum computer. Physical review letters , 108(11):110502, 2012

    2012

  43. [51]

    Rapid adiabatic preparation of injective projected entangled pair states and gibbs states

    Yimin Ge, Andr´ as Moln´ ar, and J Ignacio Cirac. Rapid adiabatic preparation of injective projected entangled pair states and gibbs states. Physical review letters , 116(8):080503, 2016

    2016

  44. [52]

    Dalzell, Ashutosh Kumar, Phillip Helms, Johnnie Gray, Zhi-Hao Cui, Wenyuan Liu, Michael Kastoryano, Ryan Babbush, John Preskill, David R

    Seunghoon Lee, Joonho Lee, Huanchen Zhai, Yu Tong, Alexander M. Dalzell, Ashutosh Kumar, Phillip Helms, Johnnie Gray, Zhi-Hao Cui, Wenyuan Liu, Michael Kastoryano, Ryan Babbush, John Preskill, David R. Reichman, Earl T. Camp- bell, Edward F. Valeev, Lin Lin, and Garnet Kin-Lic...

    1952

  45. [53]

    A quantum-inspired classical algorithm for recommendation systems

    Ewin Tang. A quantum-inspired classical algorithm for recommendation systems. In Proceedings of the 51st annual ACM SIGACT symposium on theory of computing , pages 217–228, 2019

    2019

  46. [54]

    Classical algorithms for quantum mean values

    Sergey Bravyi, David Gosset, and Ramis Movassagh. Classical algorithms for quantum mean values. Nature Physics , 17(3):337–341, 2021

    2021

  47. [55]

    Quantum-enhanced measurements: beating the standard quantum limit

    Vittorio Giovannetti, Seth Lloyd, and Lorenzo Maccone. Quantum-enhanced measurements: beating the standard quantum limit. Science, 306(5700):1330–1336, 2004

    2004

  48. [56]

    Linear combination of hamiltonian simulation for nonunitary dynamics with optimal state preparation cost

    Dong An, Jin-Peng Liu, and Lin Lin. Linear combination of hamiltonian simulation for nonunitary dynamics with optimal state preparation cost. Physical Review Letters, 131(15):150603, 2023

    2023

  49. [57]

    Error-resilient monte carlo quantum simulation of imaginary time

    Mingxia Huo and Ying Li. Error-resilient monte carlo quantum simulation of imaginary time. Quantum, 7:916, 2023

    2023

  50. [58]

    The fast intersection transform with applications to counting paths

    Andreas Bj ¨orklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. The fast intersection transform with applications to counting paths. arXiv preprint arXiv:0809.2489 , 2008

    2008 arXiv

  51. [59]

    More on reverse triangle inequality in inner product spaces

    Arsalan Hojjat Ansari, Mohammad Sal Moslehian, et al. More on reverse triangle inequality in inner product spaces. International journal of mathematics and mathematical sciences , 2005:2883–2893, 2005. 9 Appendix A: Comparison with existing results This section discusses the d...

    2005

  52. [60]

    (B2) given by the exponential function

    The randomized quantum imaginary-time evolution algorithm In this section, we propose a nascent algorithm, dubbed randomized quantum imaginary-time evolution (RQITE), with the filter (projection) function in Eq. (B2) given by the exponential function. Let us first define the f...

  53. [61]

    We use the results from Ref

    Complexity of the RQITE algorithm In this section, we analyze the complexity of our RQITE algorithm in both maximal and total evolution times for the RQITE algorithm to solve the GSEE problem. We use the results from Ref. [20] for the sample complexity and refer the readers to...

  54. [62]

    A local Hamiltonian is composed of linear combinations of Hermitian operators hX which nontrivially acts on the qubit subset X ∈ S with the corresponding coefficient λX

    Cluster and Interaction Graph Definition 3 (Local Hamiltonian). A local Hamiltonian is composed of linear combinations of Hermitian operators hX which nontrivially acts on the qubit subset X ∈ S with the corresponding coefficient λX . Here, the coefficients satisfy |λX | ≤1 an...

  55. [63]

    Using the Taylor expansion formula, we have e−βH = X m≥0 βm m! ∂me−βH ∂β m β=0

    Classical Algorithm for small β We first consider the cluster expansion of Dβ(H) = ⟨ψI |e−βH |ψI ⟩. Using the Taylor expansion formula, we have e−βH = X m≥0 βm m! ∂me−βH ∂β m β=0 . (D3) Recall that H = P X λX hX , then we define ZX = −βλX and Z = (ZX1 , ZX2 , · · ·). As a resu...

  56. [64]

    Extend the inverse temperature β to a general constant Following the analytic continuation method given by Ref. [30], we consider the map β 7→ βϕ(z), where the complex variable function ϕ(z) = log(1 − z/ν ) log(1 − 1/ν′) 20 satisfies (i) ϕ(0) = 0, (ii) ϕ(1) = 1 and (iii) ϕ(z) ...

  57. [65]

    (D27) 22 Let log ⟨0n|e−βϕ(1)H ′ |0n⟩ = P∞ l=0 Alβl and ϕ(z) = P∞ l=0 ϕlzl

    Classical Algorithm and Complexity Analysis Here, we provide technical details in evaluating the function f (1) = log Dβϕ(1)(H) = log ⟨0n|e−βϕ(1)H ′ |0n⟩ . (D27) 22 Let log ⟨0n|e−βϕ(1)H ′ |0n⟩ = P∞ l=0 Alβl and ϕ(z) = P∞ l=0 ϕlzl. According to the Taylor series in the complex ...

  58. [66]

    The fact that cluster expansion only allows a limited imaginary evolution time will constrain the accuracy we can reach, which is summarized in the following

    Classical algorithm for solving the GSEE problem with limited accuracy We are now in place to describe the dequantized RQITE algorithm. The fact that cluster expansion only allows a limited imaginary evolution time will constrain the accuracy we can reach, which is summarized ...

  59. [67]

    As mentioned at the beginning of Sec

    Analytic regions for initial state with large enough overlap Now, we extend the dequantization of the GSEE algorithm to arbitrary constant accuracy by utilizing tools of analytic continuation to extend β to an arbitrary constant in the cluster expansion. As mentioned at the be...

  60. [68]

    Our construction follows from the deduction in Sec

    Classical algorithm for solving the GSEE problem with general constant accuracy We provide details on the classical method for dequantization of the RQITE algorithm for arbitrary constant accuracy. Our construction follows from the deduction in Sec. D 3 and D 4 for the cluster...

Pith tools

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