pith. sign in

arxiv: 2606.30396 · v1 · pith:RFEYHY5Inew · submitted 2026-06-29 · 🪐 quant-ph

Provable Quantum Advantage for Dynamical Phase Transition

Jue Xu , Xiao Yuan , Qi Zhao This is my paper

Pith reviewed 2026-06-30 06:24 UTC · model grok-4.3

classification 🪐 quant-ph
keywords dynamical quantum phase transitionsquantum computational advantageBQP-completenessHamiltonian dynamicsmulti-time estimationnonequilibrium criticalityquantum algorithms
0
0 comments X

The pith

Deciding whether a subsystem exhibits a dynamical quantum phase transition is as hard as simulating generic quantum circuits.

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

The paper shows that estimating dynamical quantum phase transitions to a certain precision remains intractable even for quantum computers. In contrast, the decision problem for a subsystem variant of these transitions is proven to be computationally as difficult as simulating generic quantum circuits. This establishes a provable exponential quantum advantage for the decision task. The work also presents a quantum algorithm that provides a quadratic speedup for locating critical times in local DQPTs through efficient multi-time observable estimation.

Core claim

Estimating full DQPT is intractable for quantum computers, but deciding subsystem DQPT matches the hardness of quantum circuit simulation, allowing exponential quantum advantage. A quadratically faster quantum algorithm estimates observables of Hamiltonian dynamics at multiple times with Heisenberg-limited precision and sublinear scaling in time points. Encoding classical evolution into quantum dynamics enables broader speedups for classical anomalous phenomena.

What carries the argument

The reduction establishing equivalence between subsystem DQPT decision and generic quantum circuit simulation, which proves the quantum advantage.

If this is right

  • Quantum computers can decide subsystem DQPT instances exponentially faster than classical computers.
  • Critical times for local DQPTs can be searched with quadratic quantum speedup.
  • Quantum algorithms can detect anomalous phenomena in classical systems via encoding into quantum dynamics.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The multi-time estimation method may apply to other problems involving repeated sampling of quantum dynamics.
  • This hardness result could inspire similar proofs for other nonequilibrium phenomena.
  • Practical implementations might require specific Hamiltonian forms not restricted in the reduction.

Load-bearing premise

The reduction from quantum circuit simulation to the subsystem DQPT decision problem is valid without unstated restrictions.

What would settle it

A classical algorithm that solves the subsystem DQPT decision problem in polynomial time would disprove the claimed quantum advantage.

Figures

Figures reproduced from arXiv: 2606.30396 by Jue Xu, Qi Zhao, Xiao Yuan.

Figure 1
Figure 1. Figure 1: FIG. 1. Illustration of practical quantum advantage for DQPT. (a) Estimating rate function is [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2. The local version of rate function for the Ising [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3. Search for local DQPT critical times and the [PITH_FULL_IMAGE:figures/full_fig_p004_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: FIG. 4. The quantum circuit for one round of adaptive snapshots estimation (Alg. [PITH_FULL_IMAGE:figures/full_fig_p005_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: FIG. 5. The compute–hold–uncompute palindromic circuit construction (Section [PITH_FULL_IMAGE:figures/full_fig_p018_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: FIG. 6. The two promise conditions on the rate function, for the [PITH_FULL_IMAGE:figures/full_fig_p021_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: FIG. 7. Probability oracle [PITH_FULL_IMAGE:figures/full_fig_p029_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: FIG. 8. One round of the adaptive gradient estimation protocol for [PITH_FULL_IMAGE:figures/full_fig_p030_8.png] view at source ↗
read the original abstract

The universal scaling of critical behavior in phase transitions is a cornerstone of physics. Dynamical quantum phase transitions (DQPTs) are their nonequilibrium analogues: abrupt nonanalyticities that emerge as a quantum system evolves in time. Yet the hardness and cost of detecting this phenomenon remain largely unexplored. We prove that estimating DQPT to a certain precision is intractable even for quantum computers, whereas deciding a subsystem variant of DQPT is as hard as simulating generic quantum circuits, implying a provable exponential quantum advantage. Furthermore, to search for critical times of local DQPTs, we show a quadratically faster quantum algorithm that estimates observables of Hamiltonian dynamics at multiple time points with Heisenberg-limited precision and sublinear scaling in the number of time points. Moreover, through encoding classical evolution into quantum dynamics, our framework enables broader quantum speedups for detecting anomalous phenomena in classical systems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript claims to prove that estimating a dynamical quantum phase transition (DQPT) to a fixed precision is intractable even for quantum computers, while deciding the presence of a non-analyticity in a subsystem variant of the Loschmidt echo is BQP-hard via a polynomial-time reduction from arbitrary quantum-circuit simulation. This is presented as establishing a provable exponential quantum advantage. The paper further gives a quantum algorithm that estimates observables of Hamiltonian dynamics at multiple times with Heisenberg-limited precision and sublinear scaling in the number of times, yielding a quadratic speedup for locating critical times of local DQPTs, and sketches an encoding that transfers the framework to certain classical dynamical systems.

Significance. A valid BQP-hardness reduction for a physically motivated decision problem would constitute a concrete, falsifiable example of exponential quantum advantage outside the usual circuit-simulation setting. The multi-time estimation routine, if it achieves the stated scaling without hidden logarithmic factors, would also be of independent algorithmic interest. The classical-system extension is noted but appears secondary to the main quantum-complexity claims.

major comments (2)
  1. [Hardness reduction (reduction from circuit simulation to subsystem DQPT)] The central exponential-advantage claim rests on a polynomial-time reduction showing that the subsystem-DQPT decision problem is BQP-hard. The construction must map arbitrary circuits to Hamiltonians and initial states that satisfy exactly the same locality, time-independence, and state-preparation restrictions used in the definition of DQPT elsewhere in the manuscript; any implicit narrowing of the input class would confine the hardness result to a subclass and undermine the stated implication for generic quantum-circuit simulation.
  2. [Intractability of DQPT estimation] The claim that estimating the (non-subsystem) DQPT to fixed precision lies outside BQP requires an explicit error analysis and a reduction that preserves the precision parameter; without the intermediate steps showing how the Loschmidt-echo non-analyticity encodes the output bit, it is impossible to confirm that the intractability statement is not an artifact of the chosen observable or normalization.
minor comments (2)
  1. [Preliminaries] Notation for the Loschmidt echo and its subsystem variant should be introduced with explicit equations before the hardness statements are invoked.
  2. [Quantum algorithm for critical-time search] The sublinear scaling in the number of time points for the multi-time estimation algorithm should be stated with the precise dependence on the number of times (e.g., O(√ T) or better) and any polylog factors made explicit.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful review and constructive comments on the manuscript. We address each major comment below with references to the relevant sections and proofs, confirming that the reductions satisfy the stated restrictions and include the required error analyses.

read point-by-point responses

  1. Referee: [Hardness reduction (reduction from circuit simulation to subsystem DQPT)] The central exponential-advantage claim rests on a polynomial-time reduction showing that the subsystem-DQPT decision problem is BQP-hard. The construction must map arbitrary circuits to Hamiltonians and initial states that satisfy exactly the same locality, time-independence, and state-preparation restrictions used in the definition of DQPT elsewhere in the manuscript; any implicit narrowing of the input class would confine the hardness result to a subclass and undermine the stated implication for generic quantum-circuit simulation.

    Authors: The reduction in the proof of Theorem 3 constructs time-independent, geometrically local Hamiltonians on a lattice together with product initial states directly from arbitrary quantum circuits via a standard encoding (detailed in Appendix B). This matches exactly the locality, time-independence, and efficient state-preparation conditions used to define the subsystem DQPT decision problem in Section 2; no subclass restriction is introduced. revision: no

  2. Referee: [Intractability of DQPT estimation] The claim that estimating the (non-subsystem) DQPT to fixed precision lies outside BQP requires an explicit error analysis and a reduction that preserves the precision parameter; without the intermediate steps showing how the Loschmidt-echo non-analyticity encodes the output bit, it is impossible to confirm that the intractability statement is not an artifact of the chosen observable or normalization.

    Authors: Section 2 gives the complete reduction from circuit simulation to DQPT estimation, including the intermediate error analysis (Lemma 2) that shows how the non-analyticity of the Loschmidt-echo rate function encodes the output bit while preserving the fixed precision up to polynomial factors. The observable and normalization are the standard ones from the DQPT literature, so the intractability is not an artifact. revision: no

Circularity Check

0 steps flagged

No significant circularity in hardness reduction or DQPT claims

full rationale

The paper's core argument is a complexity reduction showing BQP-hardness of a subsystem DQPT decision problem via polynomial-time mapping from generic quantum circuit simulation. This is a standard external reduction technique that does not rely on self-definitional equations, fitted parameters renamed as predictions, or load-bearing self-citations. No equations or ansatzes in the provided abstract reduce the result to its inputs by construction, and the framework for quantum algorithms and classical encoding is presented as independent. The derivation chain remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review provides no explicit free parameters, axioms, or invented entities; all details of the hardness reductions and algorithm are absent.

pith-pipeline@v0.9.1-grok · 5667 in / 1024 out tokens · 30415 ms · 2026-06-30T06:24:11.542550+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

64 extracted references · 61 canonical work pages · 26 internal anchors

  1. [1]

    Sachdev ,\ @noop title Quantum Phase Transitions ,\ edition second edition \ ed.\ ( publisher Cambridge University Press ,\ address Cambridge ; New York ,\ year 2011 ) NoStop

    author author S. Sachdev ,\ @noop title Quantum Phase Transitions ,\ edition second edition \ ed.\ ( publisher Cambridge University Press ,\ address Cambridge ; New York ,\ year 2011 ) NoStop

    2011

  2. [2]

    Dynamical Quantum Phase Transitions in the Transverse Field Ising Model

    author author M. Heyl , author A. Polkovnikov ,\ and\ author S. Kehrein ,\ https://doi.org/10.1103/PhysRevLett.110.135704 journal journal Phys. Rev. Lett. \ volume 110 ,\ pages 135704 ( year 2013 ) ,\ https://arxiv.org/abs/1206.2505 arXiv:1206.2505 NoStop

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevlett.110.135704 2013

  3. [3]

    Dynamical quantum phase transitions: a review

    author author M. Heyl ,\ https://doi.org/10.1088/1361-6633/aaaf9a journal journal Rep. Prog. Phys. \ volume 81 ,\ pages 054001 ( year 2018 ) ,\ https://arxiv.org/abs/1709.07461 arXiv:1709.07461 NoStop

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1088/1361-6633/aaaf9a 2018

  4. [4]

    Dynamics of Loschmidt echoes and fidelity decay

    author author T. Gorin , author T. Prosen , author T. H. \ Seligman ,\ and\ author M. Znidaric ,\ https://doi.org/10.1016/j.physrep.2006.09.003 journal journal Physics Reports \ volume 435 ,\ pages 33 ( year 2006 ) ,\ https://arxiv.org/abs/quant-ph/0607050 arXiv:quant-ph/0607050 NoStop

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1016/j.physrep.2006.09.003 2006

  5. [5]

    Dynamical quantum phase transitions: scaling and universality

    author author M. Heyl ,\ https://doi.org/10.1103/PhysRevLett.115.140602 journal journal Phys. Rev. Lett. \ volume 115 ,\ pages 140602 ( year 2015 ) ,\ https://arxiv.org/abs/1505.02352 arXiv:1505.02352 NoStop

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevlett.115.140602 2015

  6. [6]

    Dynamical quantum phase transitions in systems with broken-symmetry phases

    author author M. Heyl ,\ https://doi.org/10.1103/PhysRevLett.113.205701 journal journal Phys. Rev. Lett. \ volume 113 ,\ pages 205701 ( year 2014 ) ,\ https://arxiv.org/abs/1403.4570 arXiv:1403.4570 NoStop

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevlett.113.205701 2014

  7. [7]

    Van Damme , author J.-Y

    author author M. Van Damme , author J.-Y. \ Desaules , author Z. Papi \'c ,\ and\ author J. C. \ Halimeh ,\ https://doi.org/10.1103/PhysRevResearch.5.033090 journal journal Phys. Rev. Research \ volume 5 ,\ pages 033090 ( year 2023 ) ,\ https://arxiv.org/abs/2210.02453 arXiv:2210.02453 NoStop

    work page doi:10.1103/physrevresearch.5.033090 2023

  8. [8]

    Dynamical Quantum Phase Transitions in Spin Chains with Long-Range Interactions: Merging different concepts of non-equilibrium criticality

    author author B. Zunkovic , author M. Heyl , author M. Knap ,\ and\ author A. Silva ,\ https://doi.org/10.1103/PhysRevLett.120.130601 journal journal Phys. Rev. Lett. \ volume 120 ,\ pages 130601 ( year 2018 ) ,\ https://arxiv.org/abs/1609.08482 arXiv:1609.08482 NoStop

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevlett.120.130601 2018

  9. [9]

    author author J. C. \ Budich \ and\ author M. Heyl ,\ https://doi.org/10.1103/PhysRevB.93.085416 journal journal Phys. Rev. B \ volume 93 ,\ pages 085416 ( year 2016 ) ,\ https://arxiv.org/abs/1504.05599 arXiv:1504.05599 NoStop

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevb.93.085416 2016

  10. [10]

    Dynamical quantum phase transitions: Role of topological nodes in wavefunction overlaps

    author author Z. Huang \ and\ author A. V. \ Balatsky ,\ https://doi.org/10.1103/PhysRevLett.117.086802 journal journal Phys. Rev. Lett. \ volume 117 ,\ pages 086802 ( year 2016 ) ,\ https://arxiv.org/abs/1604.04698 arXiv:1604.04698 NoStop

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevlett.117.086802 2016

  11. [11]

    Dynamical Quantum Phase Transitions: A Geometric Picture

    author author J. Lang , author B. Frank ,\ and\ author J. C. \ Halimeh ,\ https://doi.org/10.1103/PhysRevLett.121.130603 journal journal Phys. Rev. Lett. \ volume 121 ,\ pages 130603 ( year 2018 ) ,\ https://arxiv.org/abs/1804.09179 arXiv:1804.09179 NoStop

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevlett.121.130603 2018

  12. [12]

    author author T. V. \ Zache , author N. Mueller , author J. T. \ Schneider , author F. Jendrzejewski , author J. Berges ,\ and\ author P. Hauke ,\ https://doi.org/10.1103/PhysRevLett.122.050403 journal journal Phys. Rev. Lett. \ volume 122 ,\ pages 050403 ( year 2019 ) ,\ https://arxiv.org/abs/1808.07885 arXiv:1808.07885 NoStop

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevlett.122.050403 2019

  13. [13]

    Hamazaki ,\ https://doi.org/10.1038/s41467-021-25355-3 journal journal Nat Commun \ volume 12 ,\ pages 5108 ( year 2021 ) NoStop

    author author R. Hamazaki ,\ https://doi.org/10.1038/s41467-021-25355-3 journal journal Nat Commun \ volume 12 ,\ pages 5108 ( year 2021 ) NoStop

    work page doi:10.1038/s41467-021-25355-3 2021

  14. [14]

    De Nicola , author A

    author author S. De Nicola , author A. A. \ Michailidis ,\ and\ author M. Serbyn ,\ https://doi.org/10.1103/PhysRevLett.126.040602 journal journal Phys. Rev. Lett. \ volume 126 ,\ pages 040602 ( year 2021 ) ,\ https://arxiv.org/abs/2008.04894 arXiv:2008.04894 NoStop

    work page doi:10.1103/physrevlett.126.040602 2021

  15. [15]

    Detecting equilibrium and dynamical quantum phase transitions in Ising chains via out-of-time-ordered correlators

    author author M. Heyl , author F. Pollmann ,\ and\ author B. D \'o ra ,\ https://doi.org/10.1103/PhysRevLett.121.016801 journal journal Phys. Rev. Lett. \ volume 121 ,\ pages 016801 ( year 2018 ) ,\ https://arxiv.org/abs/1801.01684 arXiv:1801.01684 NoStop

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevlett.121.016801 2018

  16. [16]

    Direct observation of dynamical quantum phase transitions in an interacting many-body system

    author author P. Jurcevic , author H. Shen , author P. Hauke , author C. Maier , author T. Brydges , author C. Hempel , author B. P. \ Lanyon , author M. Heyl , author R. Blatt ,\ and\ author C. F. \ Roos ,\ https://doi.org/10.1103/PhysRevLett.119.080501 journal journal Phys. Rev. Lett. \ volume 119 ,\ pages 080501 ( year 2017 ) ,\ https://arxiv.org/abs/1...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevlett.119.080501 2017

  17. [17]

    Observation of a Many-Body Dynamical Phase Transition with a 53-Qubit Quantum Simulator

    author author J. Zhang , author G. Pagano , author P. W. \ Hess , author A. Kyprianidis , author P. Becker , author H. Kaplan , author A. V. \ Gorshkov , author Z.-X. \ Gong ,\ and\ author C. Monroe ,\ https://doi.org/10.1038/nature24654 journal journal Nature \ volume 551 ,\ pages 601 ( year 2017 ) ,\ https://arxiv.org/abs/1708.01044 arXiv:1708.01044 NoStop

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1038/nature24654 2017

  18. [18]

    Mueller , author J

    author author N. Mueller , author J. A. \ Carolan , author A. Connelly , author Z. Davoudi , author E. F. \ Dumitrescu ,\ and\ author K. Yeter-Aydeniz ,\ https://doi.org/10.1103/PRXQuantum.4.030323 journal journal PRX Quantum \ volume 4 ,\ pages 030323 ( year 2023 ) ,\ https://arxiv.org/abs/2210.03089 arXiv:2210.03089 NoStop

    work page doi:10.1103/prxquantum.4.030323 2023

  19. [19]

    De , author P

    author author A. De , author P. Cook , author M. Ali , et al. ,\ https://doi.org/10.1038/s41467-025-63398-y journal journal Nat Commun \ volume 16 ,\ pages 7939 ( year 2025 ) ,\ https://arxiv.org/abs/2309.10856 arXiv:2309.10856 NoStop

    work page doi:10.1038/s41467-025-63398-y 2025

  20. [20]

    Xu , author Z.-H

    author author K. Xu , author Z.-H. \ Sun , author W. Liu , et al. ,\ https://doi.org/10.1126/sciadv.aba4935 journal journal Sci. Adv. \ volume 6 ,\ pages eaba4935 ( year 2020 ) NoStop

    work page doi:10.1126/sciadv.aba4935 2020

  21. [21]

    Probing many-body dynamics on a 51-atom quantum simulator

    author author H. Bernien , author S. Schwartz , author A. Keesling , et al. ,\ https://doi.org/10.1038/nature24622 journal journal Nature \ volume 551 ,\ pages 579 ( year 2017 ) ,\ https://arxiv.org/abs/1707.04344 arXiv:1707.04344 NoStop

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1038/nature24622 2017

  22. [22]

    Simulating dynamic quantum phase transitions in photonic quantum walks

    author author K. Wang , author X. Qiu , author L. Xiao , author X. Zhan , author Z. Bian , author W. Yi ,\ and\ author P. Xue ,\ https://doi.org/10.1103/PhysRevLett.122.020501 journal journal Phys. Rev. Lett. \ volume 122 ,\ pages 020501 ( year 2019 ) ,\ https://arxiv.org/abs/1806.10871 arXiv:1806.10871 NoStop

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevlett.122.020501 2019

  23. [23]

    Observation of a dynamical topological phase transition

    author author N. Fl \"a schner , author D. Vogel , author M. Tarnowski , author B. S. \ Rem , author D.-S. \ L \"u hmann , author M. Heyl , author J. C. \ Budich , author L. Mathey , author K. Sengstock ,\ and\ author C. Weitenberg ,\ https://doi.org/10.1038/s41567-017-0013-8 journal journal Nature Phys \ volume 14 ,\ pages 265 ( year 2018 ) ,\ https://ar...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1038/s41567-017-0013-8 2018

  24. [24]

    Tian , author H.-X

    author author T. Tian , author H.-X. \ Yang , author L.-Y. \ Qiu , author H.-Y. \ Liang , author Y.-B. \ Yang , author Y. Xu ,\ and\ author L.-M. \ Duan ,\ https://doi.org/10.1103/PhysRevLett.124.043001 journal journal Phys. Rev. Lett. \ volume 124 ,\ pages 043001 ( year 2020 ) NoStop

    work page doi:10.1103/physrevlett.124.043001 2020

  25. [25]

    Nie , author B.-B

    author author X. Nie , author B.-B. \ Wei , author X. Chen , et al. ,\ https://doi.org/10.1103/PhysRevLett.124.250601 journal journal Phys. Rev. Lett. \ volume 124 ,\ pages 250601 ( year 2020 ) ,\ https://arxiv.org/abs/1912.12038 arXiv:1912.12038 NoStop

    work page doi:10.1103/physrevlett.124.250601 2020

  26. [26]

    Lloyd ,\ https://doi.org/10.1126/science.273.5278.1073 journal journal Science \ volume 273 ,\ pages 1073 ( year 1996 ) NoStop

    author author S. Lloyd ,\ https://doi.org/10.1126/science.273.5278.1073 journal journal Science \ volume 273 ,\ pages 1073 ( year 1996 ) NoStop

    work page doi:10.1126/science.273.5278.1073 1996

  27. [27]

    author author R. P. \ Feynman ,\ https://doi.org/10.1007/BF02650179 journal journal Int J Theor Phys \ volume 21 ,\ pages 467 ( year 1982 ) NoStop

    work page doi:10.1007/bf02650179 1982

  28. [28]

    author author A. J. \ Daley , author I. Bloch , author C. Kokail , author S. Flannigan , author N. Pearson , author M. Troyer ,\ and\ author P. Zoller ,\ https://doi.org/10.1038/s41586-022-04940-6 journal journal Nature \ volume 607 ,\ pages 667 ( year 2022 ) NoStop

    work page doi:10.1038/s41586-022-04940-6 2022

  29. [29]

    \ Zhang , author Y

    author author X.-M. \ Zhang , author Y. Zhang , author W. He ,\ and\ author X. Yuan ,\ https://doi.org/10.1103/3n8f-k8pl journal journal Phys. Rev. Lett. \ volume 135 ,\ pages 140601 ( year 2025 ) ,\ https://arxiv.org/abs/2401.12091 arXiv:2401.12091 NoStop

    work page doi:10.1103/3n8f-k8pl 2025

  30. [30]

    \ Chen , author H.-Y

    author author C.-F. \ Chen , author H.-Y. \ Huang , author J. Preskill ,\ and\ author L. Zhou ,\ https://doi.org/10.1038/s41567-025-02781-4 journal journal Nat. Phys. \ volume 21 ,\ pages 654 ( year 2025 ) NoStop

    work page doi:10.1038/s41567-025-02781-4 2025

  31. [31]

    author author L. G. \ Valiant ,\ https://doi.org/10.1016/0304-3975(79)90044-6 journal journal Theoretical Computer Science \ volume 8 ,\ pages 189 ( year 1979 ) NoStop

    work page doi:10.1016/0304-3975(79)90044-6 1979

  32. [32]

    Aaronson \ and\ author A

    author author S. Aaronson \ and\ author A. Arkhipov ,\ in\ https://doi.org/10.1145/1993636.1993682 booktitle Proc. Forty-Third Annu . ACM Symp . Theory Comput . ,\ series and number STOC '11 \ ( publisher Association for Computing Machinery ,\ address New York, NY, USA ,\ year 2011 )\ pp.\ pages 333--342 ,\ https://arxiv.org/abs/1011.3245 arXiv:1011.3245 NoStop

    work page doi:10.1145/1993636.1993682 2011

  33. [33]

    author author M. J. \ Bremner , author A. Montanaro ,\ and\ author D. J. \ Shepherd ,\ https://doi.org/10.1103/PhysRevLett.117.080501 journal journal Phys. Rev. Lett. \ volume 117 ,\ pages 080501 ( year 2016 ) ,\ https://arxiv.org/abs/1504.07999 arXiv:1504.07999 NoStop

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevlett.117.080501 2016

  34. [34]

    Karch , author S

    author author S. Karch , author S. Bandyopadhyay , author Z.-H. \ Sun , et al. ,\ https://doi.org/10.48550/arXiv.2501.16995 title Probing quantum many-body dynamics using subsystem Loschmidt echos ( year 2025 ),\ https://arxiv.org/abs/2501.16995 arXiv:2501.16995 NoStop

    work page doi:10.48550/arxiv.2501.16995 2025

  35. [35]

    author author C. H. \ Bennett , author E. Bernstein , author G. Brassard ,\ and\ author U. Vazirani ,\ https://doi.org/10.1137/S0097539796300933 journal journal SIAM J. Comput. \ volume 26 ,\ pages 1510 ( year 1997 ) ,\ https://arxiv.org/abs/quant-ph/9701001 arXiv:quant-ph/9701001 NoStop

    work page doi:10.1137/s0097539796300933 1997

  36. [36]

    Babbush , author D

    author author R. Babbush , author D. W. \ Berry , author R. Kothari , author R. D. \ Somma ,\ and\ author N. Wiebe ,\ https://doi.org/10.1103/PhysRevX.13.041041 journal journal Phys. Rev. X \ volume 13 ,\ pages 1041 ( year 2023 ) ,\ https://arxiv.org/abs/2303.13012 arXiv:2303.13012 NoStop

    work page doi:10.1103/physrevx.13.041041 2023

  37. [37]

    Bravyi , author R

    author author S. Bravyi , author R. Manson-Sawko , author M. Zayats ,\ and\ author S. Zhuk ,\ https://doi.org/10.48550/arXiv.2507.06198 title Quantum simulation of a noisy classical nonlinear dynamics ( year 2025 ),\ https://arxiv.org/abs/2507.06198 arXiv:2507.06198 NoStop

    work page doi:10.48550/arxiv.2507.06198 2025

  38. [38]

    Jin , author N

    author author S. Jin , author N. Liu ,\ and\ author Y. Yu ,\ https://doi.org/10.1103/PhysRevLett.133.230602 journal journal Phys. Rev. Lett. \ volume 133 ,\ pages 230602 ( year 2024 ) ,\ https://arxiv.org/abs/2212.13969 arXiv:2212.13969 NoStop

    work page doi:10.1103/physrevlett.133.230602 2024

  39. [39]

    An , author J.-P

    author author D. An , author J.-P. \ Liu ,\ and\ author L. Lin ,\ https://doi.org/10.1103/PhysRevLett.131.150603 journal journal Phys. Rev. Lett. \ volume 131 ,\ pages 150603 ( year 2023 ) ,\ https://arxiv.org/abs/2303.01029 arXiv:2303.01029 NoStop

    work page doi:10.1103/physrevlett.131.150603 2023

  40. [40]

    author author M. J. \ Bremner , author R. Jozsa ,\ and\ author D. J. \ Shepherd ,\ https://doi.org/10.1098/rspa.2010.0301 journal journal Proc. R. Soc. A. \ volume 467 ,\ pages 459 ( year 2011 ) ,\ https://arxiv.org/abs/1005.1407 arXiv:1005.1407 NoStop

    work page doi:10.1098/rspa.2010.0301 2010

  41. [41]

    author author J. C. \ Halimeh , author D. Trapin , author M. Van Damme ,\ and\ author M. Heyl ,\ https://doi.org/10.1103/PhysRevB.104.075130 journal journal Phys. Rev. B \ volume 104 ,\ pages 075130 ( year 2021 ) ,\ https://arxiv.org/abs/2010.07307 arXiv:2010.07307 NoStop

    work page doi:10.1103/physrevb.104.075130 2021

  42. [42]

    Bandyopadhyay , author A

    author author S. Bandyopadhyay , author A. Polkovnikov ,\ and\ author A. Dutta ,\ https://doi.org/10.1103/PhysRevLett.126.200602 journal journal Phys. Rev. Lett. \ volume 126 ,\ pages 200602 ( year 2021 ) ,\ https://arxiv.org/abs/2011.03906 arXiv:2011.03906 NoStop

    work page doi:10.1103/physrevlett.126.200602 2021

  43. [43]

    note See Supplementary Materials for more details NoStop

  44. [44]

    Vajna \ and\ author B

    author author S. Vajna \ and\ author B. D \'o ra ,\ https://doi.org/10.1103/PhysRevB.91.155127 journal journal Phys. Rev. B \ volume 91 ,\ pages 155127 ( year 2015 ) NoStop

    work page doi:10.1103/physrevb.91.155127 2015

  45. [45]

    Optimizing quantum optimization algorithms via faster quantum gradient computation

    author author A. Gily \'e n , author S. Arunachalam ,\ and\ author N. Wiebe ,\ in\ https://doi.org/10.1137/1.9781611975482.87 booktitle SODA \ ( year 2019 )\ https://arxiv.org/abs/1711.00465 arXiv:1711.00465 NoStop

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1137/1.9781611975482.87 2019

  46. [46]

    author author W. J. \ Huggins , author K. Wan , author J. McClean , author T. E. \ O'Brien , author N. Wiebe ,\ and\ author R. Babbush ,\ https://doi.org/10.1103/PhysRevLett.129.240501 journal journal Phys. Rev. Lett. \ volume 129 ,\ pages 240501 ( year 2022 ) ,\ https://arxiv.org/abs/2111.09283 arXiv:2111.09283 NoStop

    work page doi:10.1103/physrevlett.129.240501 2022

  47. [47]

    Wada , author N

    author author K. Wada , author N. Yamamoto ,\ and\ author N. Yoshioka ,\ https://doi.org/10.1103/PRXQuantum.6.020308 journal journal PRX Quantum \ volume 6 ,\ pages 020308 ( year 2025 ) ,\ https://arxiv.org/abs/2406.03306 arXiv:2406.03306 NoStop

    work page doi:10.1103/prxquantum.6.020308 2025

  48. [48]

    van Apeldoorn ,\ in\ https://doi.org/10.4230/LIPIcs.TQC.2021.9 booktitle 16th Conf

    author author J. van Apeldoorn ,\ in\ https://doi.org/10.4230/LIPIcs.TQC.2021.9 booktitle 16th Conf . Theory Quantum Comput . Commun . Cryptogr . TQC 2021 ,\ series Leibniz International Proceedings in Informatics ( LIPIcs ) , Vol.\ volume 197 ,\ editor edited by\ editor M.-H. \ Hsieh \ ( publisher Schloss Dagstuhl -- Leibniz-Zentrum f\"ur Informatik ,\ a...

    work page doi:10.4230/lipics.tqc.2021.9 2021

  49. [49]

    Dagum , author R

    author author P. Dagum , author R. Karp , author M. Luby ,\ and\ author S. Ross ,\ https://doi.org/10.1137/S0097539797315306 journal journal SIAM J. Comput. \ volume 29 ,\ pages 1484 ( year 2000 ) NoStop

    work page doi:10.1137/s0097539797315306 2000

  50. [50]

    Quantum circuits and low-degree polynomials over F_2

    author author A. Montanaro ,\ https://doi.org/10.1088/1751-8121/aa565f journal journal J. Phys. A: Math. Theor. \ volume 50 ,\ pages 084002 ( year 2017 ) ,\ https://arxiv.org/abs/1607.08473 arXiv:1607.08473 NoStop

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1088/1751-8121/aa565f 2017

  51. [51]

    author author L. A. \ Goldberg \ and\ author H. Guo ,\ https://doi.org/10.1007/s00037-017-0162-2 journal journal comput. complex. \ volume 26 ,\ pages 765 ( year 2017 ) ,\ https://arxiv.org/abs/1409.5627 arXiv:1409.5627 NoStop

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1007/s00037-017-0162-2 2017

  52. [52]

    Quantum Commuting Circuits and Complexity of Ising Partition Functions

    author author K. Fujii \ and\ author T. Morimae ,\ https://doi.org/10.1088/1367-2630/aa5fdb journal journal New J. Phys. \ volume 19 ,\ pages 033003 ( year 2017 ) ,\ https://arxiv.org/abs/1311.2128 arXiv:1311.2128 NoStop

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1088/1367-2630/aa5fdb 2017

  53. [53]

    author author S. A. \ Fenner , author L. J. \ Fortnow ,\ and\ author S. A. \ Kurtz ,\ https://doi.org/10.1016/S0022-0000(05)80024-8 journal journal Journal of Computer and System Sciences \ volume 48 ,\ pages 116 ( year 1994 ) NoStop

    work page doi:10.1016/s0022-0000(05)80024-8 1994

  54. [54]

    Perfect state transfer in quantum spin networks

    author author M. Christandl , author N. Datta , author A. Ekert ,\ and\ author A. J. \ Landahl ,\ https://doi.org/10.1103/PhysRevLett.92.187902 journal journal Phys. Rev. Lett. \ volume 92 ,\ pages 187902 ( year 2004 ) ,\ https://arxiv.org/abs/quant-ph/0309131 arXiv:quant-ph/0309131 NoStop

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevlett.92.187902 2004

  55. [55]

    author author D. W. \ Berry , author A. M. \ Childs , author R. Cleve , author R. Kothari ,\ and\ author R. D. \ Somma ,\ in\ https://doi.org/10.1145/2591796.2591854 booktitle Proc. Forty-Sixth Annu . ACM Symp . Theory Comput . \ ( publisher ACM ,\ address New York New York ,\ year 2014 )\ pp.\ pages 283--292 ,\ https://arxiv.org/abs/1312.1414 arXiv:1312....

    work page doi:10.1145/2591796.2591854 2014

  56. [56]

    author author A. M. \ Childs , author Y. Su , author M. C. \ Tran , author N. Wiebe ,\ and\ author S. Zhu ,\ https://doi.org/10.1103/PhysRevX.11.011020 journal journal Phys. Rev. X \ volume 11 ,\ pages 011020 ( year 2021 ) ,\ https://arxiv.org/abs/1912.08854 arXiv:1912.08854 NoStop

    work page doi:10.1103/physrevx.11.011020 2021

  57. [57]

    Zhao , author Y

    author author Q. Zhao , author Y. Zhou ,\ and\ author A. M. \ Childs ,\ https://doi.org/10.1038/s41567-025-02945-2 journal journal Nat. Phys. \ volume 21 ,\ pages 1338 ( year 2025 ) ,\ https://arxiv.org/abs/2406.02379 arXiv:2406.02379 NoStop

    work page doi:10.1038/s41567-025-02945-2 2025

  58. [58]

    author author G. H. \ Low \ and\ author I. L. \ Chuang ,\ https://doi.org/10.1103/PhysRevLett.118.010501 journal journal Phys. Rev. Lett. \ volume 118 ,\ pages 010501 ( year 2017 ) ,\ https://arxiv.org/abs/1606.02685 arXiv:1606.02685 NoStop

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevlett.118.010501 2017

  59. [59]

    Gily \'e n , author Y

    author author A. Gily \'e n , author Y. Su , author G. H. \ Low ,\ and\ author N. Wiebe ,\ https://doi.org/10.1145/3313276.3316366 journal journal Proc. 51st Annu. ACM SIGACT Symp. Theory Comput. \ ,\ pages 193 ( year 2019 b ) ,\ https://arxiv.org/abs/1806.01838 arXiv:1806.01838 NoStop

    work page doi:10.1145/3313276.3316366 2019

  60. [60]

    author author D. W. \ Berry , author G. Ahokas , author R. Cleve ,\ and\ author B. C. \ Sanders ,\ https://doi.org/10.1007/s00220-006-0150-x journal journal Commun. Math. Phys. \ volume 270 ,\ pages 359 ( year 2007 ) ,\ https://arxiv.org/abs/quant-ph/0508139 arXiv:quant-ph/0508139 NoStop

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1007/s00220-006-0150-x 2007

  61. [61]

    author author D. W. \ Berry , author A. M. \ Childs ,\ and\ author R. Kothari ,\ in\ https://doi.org/10.1109/FOCS.2015.54 booktitle 2015 IEEE 56th Annu . Symp . Found . Comput . Sci . \ ( year 2015 )\ pp.\ pages 792--809 ,\ https://arxiv.org/abs/1501.01715 arXiv:1501.01715 NoStop

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1109/focs.2015.54 2015

  62. [62]

    author author S. P. \ Jordan ,\ https://doi.org/10.1103/PhysRevLett.95.050501 journal journal Phys. Rev. Lett. \ volume 95 ,\ pages 050501 ( year 2005 ) ,\ https://arxiv.org/abs/quant-ph/0405146 arXiv:quant-ph/0405146 NoStop

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1103/physrevlett.95.050501 2005

  63. [63]

    author author J. M. \ Varah ,\ https://doi.org/10.1016/0024-3795(75)90112-3 journal journal Linear Algebra and its Applications \ volume 11 ,\ pages 3 ( year 1975 ) NoStop

    work page doi:10.1016/0024-3795(75)90112-3 1975

  64. [64]

    author author A. B. \ Tsybakov ,\ @noop title Introduction to Nonparametric Estimation ,\ edition 1st \ ed.\ ( publisher Springer Publishing Company, Incorporated ,\ year 2008 ) NoStop

    2008