pith. sign in

arxiv: 2605.19054 · v1 · pith:SDJCQTJ5new · submitted 2026-05-18 · 🪐 quant-ph

Quantum Koopman Algorithms

David Jennings , Kamil Korzekwa , Matteo Lostaglio , Guoming Wang This is my paper

Pith reviewed 2026-05-20 10:23 UTC · model grok-4.3

classification 🪐 quant-ph
keywords quantum algorithmsKoopman operatorobservable spacefree fermionsopen quantum systemsnonlinear dynamicsspectral methodsheat flows
0
0 comments X

The pith

Quantum Koopman Algorithms encode observable evolution to simulate free-fermion baths and nonlinear classical dynamics with polylogarithmic quantum gate costs.

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

The paper defines Quantum Koopman Algorithms as a framework that represents system dynamics through the evolution of selected observables rather than full state vectors. For systems of N free fermions coupled linearly to a bath, this yields quantum circuits whose gate count scales as O(polylog(N)), allowing efficient reconstruction of heat flows and decay rates where classical methods scale exponentially. The same observable-space approach supplies a nonlinear interaction-picture method that generates perturbative expansions around solvable reference flows and a windowed quantum solver that extracts eigen-frequencies from late-time classical trajectories. A sympathetic reader would care because the construction shows how quantum computers can exploit structure in observable sets to handle both open quantum systems and nonlinear classical problems without simulating the entire Hilbert space or phase space.

Core claim

Quantum Koopman Algorithms rest on approximately closed sets of observables together with efficient coherent encodings of their evolution under the Koopman operator; the framework splits into Dynamic-QKA for initial-value problems and Spectral-QKA for eigenvalue extraction, delivering O(polylog(N)) algorithms for free-fermion baths and new perturbative and spectral tools for nonlinear classical flows.

What carries the argument

Approximately closed sets of observables whose Koopman-driven evolution is coherently encoded on a quantum computer, enabling both dynamic simulation and spectral analysis.

If this is right

  • Simulations of N-particle open fermionic systems become feasible on quantum hardware whose resources grow only logarithmically with N.
  • Heat currents and relaxation rates can be read out directly from the encoded observable trajectories.
  • Perturbative expansions for nonlinear classical dynamics can be centered on exactly solvable reference flows rather than only linear ones.
  • Late-time frequencies of nonlinear oscillators can be extracted by a windowed quantum ODE solver without full long-time integration.

Where Pith is reading between the lines

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

  • The same observable encoding may apply to other open many-body systems whose relevant operators close under commutation with the Liouvillian.
  • Combining the spectral-QKA with variational methods could yield hybrid algorithms for finding steady states of driven nonlinear systems.
  • The polylog scaling suggests a route to quantum advantage in classical fluid or plasma simulations that admit low-dimensional observable closures.

Load-bearing premise

The selected observables remain approximately closed under the dynamics and admit an efficient coherent quantum encoding.

What would settle it

An explicit scaling test on free fermions where the number of observables needed for fixed accuracy grows exponentially with N, forcing gate cost to exceed polylog(N).

Figures

Figures reproduced from arXiv: 2605.19054 by David Jennings, Guoming Wang, Kamil Korzekwa, Matteo Lostaglio.

Figure 1
Figure 1. Figure 1: FIG. 1 [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
read the original abstract

We define an observable-space framework of Quantum Koopman Algorithms (QKAs) for simulating the dynamics of both linear quantum and nonlinear classical systems, based on approximately closed sets of observables and efficient coherent encodings of their Koopman-driven evolution. QKAs have two strands: Dynamic-QKA for the initial-value problem of observables dynamics, and Spectral-QKA for the eigenvalue analysis of the Koopman operator. We demonstrate the scope of the framework through several applications. First, for classes of $N$ free fermions linearly coupled to a bath, we construct quantum algorithms with gate cost $O(\mathrm{polylog}(N))$, an exponential improvement over classical methods, and use them to reconstruct heat flows and decay rates. Second, for nonlinear classical dynamics, we introduce a novel nonlinear interaction-picture quantum algorithm that enables perturbative expansions around solvable nonlinear reference flows, going beyond existing approaches that only apply to weakly nonlinear systems. Third, we develop spectral methods for extracting eigen-frequencies of late-time nonlinear dynamics, introducing a windowed quantum ODE-solver. Our results identify the Koopman-quantum interface as a natural setting in which quantum algorithms can exploit observable-space structure to simulate both classical and quantum dynamics.

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 paper defines an observable-space framework of Quantum Koopman Algorithms (QKAs) for simulating dynamics of both linear quantum and nonlinear classical systems, based on approximately closed sets of observables and efficient coherent encodings of their Koopman-driven evolution. It distinguishes Dynamic-QKA for the initial-value problem of observable dynamics and Spectral-QKA for eigenvalue analysis of the Koopman operator. Applications include O(polylog(N)) gate-cost quantum algorithms for N free fermions linearly coupled to a bath to reconstruct heat flows and decay rates (exponential improvement over classical methods), a nonlinear interaction-picture quantum algorithm enabling perturbative expansions around solvable nonlinear reference flows, and spectral methods with a windowed quantum ODE-solver for extracting eigen-frequencies of late-time nonlinear dynamics.

Significance. If the central constructions hold, the work is significant for identifying the Koopman-quantum interface as a setting where quantum algorithms can exploit observable-space structure to achieve exponential speedups in open quantum systems and to extend beyond weakly nonlinear regimes in classical dynamics. The paper introduces novel algorithmic strands and claims of efficient coherent encodings, which, if substantiated with explicit derivations and error bounds, would strengthen the case for observable-space approaches in quantum simulation.

major comments (2)
  1. [Abstract and § on free-fermion QKA construction] Abstract and fermion application: The headline claim of O(polylog(N)) gate cost for classes of N free fermions linearly coupled to a bath requires that a polynomially sized set of observables remains approximately closed under the linear bath coupling and that the resulting Koopman generator admits an efficient coherent encoding. The manuscript invokes an implicit truncation of the observable hierarchy but does not provide an explicit N-dependent error bound or show that the truncation cost remains polylog(N) for general bath spectral densities; this is load-bearing for the asserted exponential separation from classical methods.
  2. [Nonlinear dynamics application] Nonlinear classical dynamics section: The novel nonlinear interaction-picture quantum algorithm is presented as enabling perturbative expansions around solvable nonlinear reference flows and going beyond existing weakly nonlinear approaches, yet the manuscript does not include a concrete comparison of perturbative orders, convergence radii, or gate-cost scaling relative to prior interaction-picture methods; without this, the scope of the improvement remains unclear.
minor comments (2)
  1. [Introduction/Definition of QKAs] The opening definition of QKAs would benefit from an explicit diagram or pseudocode distinguishing the Dynamic-QKA and Spectral-QKA strands and their shared reliance on approximately closed observable sets.
  2. [Coherent encoding paragraphs] Ensure that all claims of 'efficient coherent encodings' are accompanied by at least a high-level circuit construction or reference to a standard quantum linear-systems subroutine.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for identifying points that require clarification. We address each major comment below and indicate the changes we will make in the revised version.

read point-by-point responses

  1. Referee: [Abstract and § on free-fermion QKA construction] Abstract and fermion application: The headline claim of O(polylog(N)) gate cost for classes of N free fermions linearly coupled to a bath requires that a polynomially sized set of observables remains approximately closed under the linear bath coupling and that the resulting Koopman generator admits an efficient coherent encoding. The manuscript invokes an implicit truncation of the observable hierarchy but does not provide an explicit N-dependent error bound or show that the truncation cost remains polylog(N) for general bath spectral densities; this is load-bearing for the asserted exponential separation from classical methods.

    Authors: We agree that an explicit error bound is necessary to fully substantiate the polylog(N) gate-cost claim and the exponential separation. In the revised manuscript we will add a dedicated subsection deriving an N-dependent truncation error bound for the observable hierarchy under linear bath coupling. For the specific classes of free-fermion models considered (those whose bath spectral densities admit finite moments or are sufficiently smooth), we will show that the truncation error decays as O(1/poly(N)) while the coherent encoding of the truncated Koopman generator remains efficient, preserving the overall polylog(N) scaling. We note that the original construction already selects an approximately closed observable set whose size is polynomial in N for these models; the revision will make the error analysis fully rigorous rather than implicit. revision: yes

  2. Referee: [Nonlinear dynamics application] Nonlinear classical dynamics section: The novel nonlinear interaction-picture quantum algorithm is presented as enabling perturbative expansions around solvable nonlinear reference flows and going beyond existing weakly nonlinear approaches, yet the manuscript does not include a concrete comparison of perturbative orders, convergence radii, or gate-cost scaling relative to prior interaction-picture methods; without this, the scope of the improvement remains unclear.

    Authors: We accept that a side-by-side comparison would strengthen the presentation. In the revision we will insert a new paragraph (or short subsection) that explicitly compares (i) the perturbative orders reachable around a solvable nonlinear reference flow versus standard weakly nonlinear interaction pictures, (ii) the associated convergence radii for representative nonlinear systems, and (iii) the resulting gate-cost scalings. This comparison will use concrete model examples to illustrate the extension beyond the weakly nonlinear regime while retaining the same asymptotic complexity class. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivations rest on independent framework definitions and algorithmic constructions

full rationale

The paper defines the QKA framework from first principles using approximately closed observable sets and coherent encodings of Koopman evolution, then constructs explicit algorithms for free-fermion bath models and nonlinear classical dynamics. No load-bearing step reduces by construction to a fitted parameter, self-citation chain, or renamed input; the polylog(N) claims are presented as outputs of the new encoding methods rather than tautological re-expressions of the inputs. The derivation chain is therefore self-contained against the stated assumptions.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claims rest on standard quantum mechanics, the existence of approximately closed observable sets, and the Koopman operator formalism; no explicit free parameters or new invented entities are named in the abstract.

axioms (1)
  • standard math Quantum mechanics and the Koopman operator theory for linearizing dynamics in observable space
    Invoked in the definition of QKAs and the encoding of evolution.
invented entities (1)
  • Quantum Koopman Algorithms (QKAs) no independent evidence
    purpose: Observable-space framework for quantum simulation of quantum and classical dynamics
    Newly defined framework in the paper; no independent evidence provided beyond the abstract claims.

pith-pipeline@v0.9.0 · 5735 in / 1292 out tokens · 30005 ms · 2026-05-20T10:23:32.732376+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

79 extracted references · 79 canonical work pages · 5 internal anchors

  1. [1]

    D. W. Berry, J. Phys. A47, 105301 (2014)

    work page 2014

  2. [2]

    D. W. Berry, A. M. Childs, A. Ostrander, and G. Wang, Commun. Math. Phys.356, 1057 (2017)

    work page 2017

  3. [3]

    D. W. Berry and P. C. Costa, Quantum8, 1369 (2024)

    work page 2024

  4. [4]

    An, J.-P

    D. An, J.-P. Liu, and L. Lin, Phys. Rev. Lett.131, 150603 (2023)

    work page 2023

  5. [5]

    Jennings, M

    D. Jennings, M. Lostaglio, R. B. Lowrie, S. Pallister, and A. T. Sornborger, Quantum8, 1553 (2024)

    work page 2024

  6. [6]

    D. An, A. M. Childs, and L. Lin, Commun. Math. Phys. 407, 19 (2026)

    work page 2026

  7. [7]

    Sign Embedding Quantum Algorithms for Matrix Equations and Matrix Functions

    Y. Wang and J.-P. Liu, (2026), arXiv:2604.25333 [quant- ph]

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  8. [8]

    B. O. Koopman, PNAS17, 315 (1931)

    work page 1931

  9. [9]

    Budiˇ si´ c, R

    M. Budiˇ si´ c, R. Mohr, and I. Mezi´ c, Chaos22, 047510 (2012)

    work page 2012

  10. [10]

    Mezi´ c, Annu

    I. Mezi´ c, Annu. Rev. Fluid Mech.45, 357 (2013)

    work page 2013

  11. [11]

    Susuki, I

    Y. Susuki, I. Mezic, F. Raak, and T. Hikihara, NOLTA 7, 430 (2016)

    work page 2016

  12. [12]

    J. F. Dur´ an-Siguenza, L. I. Minchala, L. E. Garza- Casta˜ n´ on, and H. Zhang, J. Franklin Inst. , 108256 (2025)

    work page 2025

  13. [13]

    Liu and L

    J.-P. Liu and L. Lin, J. Comput. Phys.514, 113213 (2024)

    work page 2024

  14. [14]

    R. D. Somma, R. King, R. Kothari, T. E. O’Brien, and R. Babbush, Nat. Commun.16, 2690 (2025)

    work page 2025

  15. [15]

    Stroeks, D

    M. Stroeks, D. Lenterman, B. M. Terhal, and Y. Herasy- menko, Phys. Rev. Res.7, 043176 (2025)

    work page 2025

  16. [16]

    Here we treatx∈C d as a real vector inR 2d

    work page

  17. [17]

    For a matrixA, this is an efficient quantum circuitU A encodingA/αin its top-left block, withα >0 being a scale factor [59]

    work page

  18. [18]

    Here a history-state encodes dynamical data over a time interval. It takes the form P k ak|ψ(tk)⟩|tk⟩, where the second register encodes a discrete set of timest k over the interval, the first register encodes the solution at that timet k, anda k are associated norm-weightings due to potentially non-unitary dynamics

    work page

  19. [19]

    Lloyd, Science273, 1073 (1996)

    S. Lloyd, Science273, 1073 (1996)

    work page 1996

  20. [20]

    D. W. Berry, G. Ahokas, R. Cleve, and B. C. Sanders, Commun. Math. Phys.270, 359 (2007)

    work page 2007

  21. [21]

    D. W. Berry, A. M. Childs, R. Cleve, R. Kothari, and R. D. Somma, Phys. Rev. Lett.114, 090502 (2015)

    work page 2015

  22. [22]

    A. Y. Kitaev, (1995), arXiv:quant-ph/9511026

    work page internal anchor Pith review Pith/arXiv arXiv 1995

  23. [23]

    Cleve, A

    R. Cleve, A. Ekert, C. Macchiavello, and M. Mosca, Proc. R. Soc. Lond. A454, 339 (1998)

    work page 1998

  24. [24]

    Gily´ en, Y

    A. Gily´ en, Y. Su, G. H. Low, and N. Wiebe, inPro- ceedings of the 51st annual ACM SIGACT symposium on theory of computing(2019) pp. 193–204

    work page 2019

  25. [25]

    G. H. Low and I. L. Chuang, Quantum3, 163 (2019)

    work page 2019

  26. [26]

    C. W. Groth, M. Wimmer, A. R. Akhmerov, and X. Waintal, New J. Phys.16, 063065 (2014)

    work page 2014

  27. [27]

    Kloss, J

    T. Kloss, J. Weston, B. Gaury, B. Rossignol, C. Groth, and X. Waintal, New J. Phys.23, 023025 (2021)

    work page 2021

  28. [28]

    L. G. Valiant, inProceedings of the Thirty-Third Annual ACM Symposium on Theory of Computing(Association for Computing Machinery, 2001) p. 114–123

    work page 2001

  29. [29]

    B. M. Terhal and D. P. DiVincenzo, Phys. Rev. A65, 032325 (2002)

    work page 2002

  30. [30]

    Alba and F

    V. Alba and F. Carollo, SciPost Phys.15, 124 (2023)

    work page 2023

  31. [31]

    van Caspel, S

    M. van Caspel, S. E. Tapias Arze, and I. P´ erez Castillo, SciPost Phys.6, 026 (2019)

    work page 2019

  32. [32]

    Prosen, New J

    T. Prosen, New J. Phys.10, 043026 (2008)

    work page 2008

  33. [33]

    ˇZunkoviˇ c and T

    B. ˇZunkoviˇ c and T. Prosen, J. Stat. Mech.2010, P08016 (2010)

    work page 2010

  34. [34]

    Namely, a finite fraction of fermionic modes remains a constant away from the infinite temperature state throughout the evolution

    work page

  35. [35]

    Breuer and F

    H.-P. Breuer and F. Petruccione,The theory of open quantum systems(OUP Oxford, 2002)

    work page 2002

  36. [36]

    Fleming, N

    C. Fleming, N. Cummings, C. Anastopoulos, and B.-L. Hu, J. Phys. A: Math. Theor.43, 405304 (2010)

    work page 2010

  37. [37]

    Lostaglio, K

    M. Lostaglio, K. Korzekwa, and A. Milne, Phys. Rev. A 96, 032109 (2017)

    work page 2017

  38. [38]

    Explicit Error Bounds for Carleman Linearization

    M. Forets and A. Pouly, (2017), arXiv:1711.02552 [math- NA]

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  39. [39]

    P. Chen, N. Motee, and Q. Sun, (2024), arXiv:2411.11598 [math.DS]

    work page arXiv 2024

  40. [40]

    J.-P. Liu, H. Ø. Kolden, H. K. Krovi, N. F. Loureiro, K. Trivisa, and A. M. Childs, PNAS118, e2026805118 (2021)

    work page 2021

  41. [41]

    Jennings, K

    D. Jennings, K. Korzekwa, M. Lostaglio, A. T. Sornborger, Y. Subasi, and G. Wang, (2025), arXiv:2509.07155 [quant-ph]

    work page arXiv 2025

  42. [42]

    Jennings, K

    D. Jennings, K. Korzekwa, M. Lostaglio, R. Ashworth, E. Marsili, and S. Rolston, (2025), arXiv:2512.03758 [quant-ph]. 6

    work page arXiv 2025

  43. [43]

    Bravyi, R

    S. Bravyi, R. Manson-Sawko, M. Zayats, and S. Zhuk, (2025), arXiv:2507.06198 [quant-ph]

    work page arXiv 2025

  44. [44]

    Novikau and I

    I. Novikau and I. Joseph, Comput. Phys. Commun.309, 109498 (2025)

    work page 2025

  45. [45]

    Note that any polynomial nonlinearity can be reduced to a quadratic one

    work page

  46. [46]

    Costa, P

    P. Costa, P. Schleich, M. E. Morales, and D. W. Berry, (2023), arXiv:2312.09518 [quant-ph]

    work page arXiv 2023

  47. [47]

    Lewis, S

    D. Lewis, S. Eidenbenz, B. Nadiga, and Y. Suba¸ si, Quan- tum8, 1509 (2024)

    work page 2024

  48. [48]

    Novikau and I

    I. Novikau and I. Joseph, (2025), arXiv:2510.15715 [quant-ph]

    work page arXiv 2025

  49. [49]

    Joseph, Y

    I. Joseph, Y. Shi, M. Porter, A. Castelli, V. Geyko, F. Graziani, S. Libby, and J. DuBois, Phys. Plasmas 30, 010501 (2023)

    work page 2023

  50. [50]

    Page and R

    J. Page and R. R. Kerswell, Phys. Rev. Fluids3, 071901 (2018)

    work page 2018

  51. [51]

    More precisely, ifη 1(x(t)) andη 2(x(t)) are eigenmodes of ˜KA with eigenvaluesλ 1 andλ 2 respectively, then η1(x(t))η2(x(t)) is an eigenmode of ˜KA with eigenvalue λ1 +λ 2

    work page

  52. [52]

    With the usual caveat that theR-number is a sufficient but not necessary criterion of convergence

    work page

  53. [53]

    D. W. Berry, Y. Su, C. Gyurik, R. King, J. Basso, A. D. T. Barba, A. Rajput, N. Wiebe, V. Dunjko, and R. Babbush, PRX Quantum5, 010319 (2024)

    work page 2024

  54. [54]

    Greenaway, W

    S. Greenaway, W. Pol, and S. Sim, (2024), arXiv:2404.01396 [quant-ph]

    work page arXiv 2024

  55. [55]

    Patel, S

    D. Patel, S. J. S. Tan, Y. Suba¸ si, and A. T. Sornborger, PRX Quantum7, 020302 (2026)

    work page 2026

  56. [56]

    Zhang, Z

    B. Zhang, Z. Lu, Y. Zhao, and Y. Yang, (2025), arXiv:2507.21890 [quant-ph]

    work page arXiv 2025

  57. [57]

    M. O. Williams, I. G. Kevrekidis, and C. W. Rowley, J. Nonlinear Sci.25, 1307 (2015)

    work page 2015

  58. [58]

    Efficient quantum algorithm for linear matrix differential equations and applications to open quantum systems

    S. Simon, D. W. Berry, and R. D. Somma, (2026), arXiv:2605.16195 [quant-ph]

    work page internal anchor Pith review Pith/arXiv arXiv 2026

  59. [59]

    Lin, (2022), arXiv:2201.08309 [quant-ph]

    L. Lin, (2022), arXiv:2201.08309 [quant-ph]

    work page arXiv 2022

  60. [60]

    Krovi, Quantum7, 913 (2023)

    H. Krovi, Quantum7, 913 (2023)

    work page 2023

  61. [61]

    Shukla and P

    A. Shukla and P. Vedula, Quantum Inf. Process.23, 38 (2024)

    work page 2024

  62. [62]

    A. M. Dalzell, (2024), arXiv:2406.12086 [quant-ph]

    work page internal anchor Pith review Pith/arXiv arXiv 2024

  63. [63]

    R. D. Somma, G. H. Low, D. W. Berry, and R. Babbush, (2025), arXiv:2508.02822 [quant-ph]

    work page arXiv 2025

  64. [64]

    D. An, A. Onwunta, and G. Yang, (2024), arXiv:2410.13189 [quant-ph]

    work page arXiv 2024

  65. [65]

    Casas-Garc´ ıa, L

    K. Casas-Garc´ ıa, L. Quezada-T´ ellez, S. Carrillo-Moreno, J. Flores-Godoy, and G. Fern´ andez-Anaya, Nova Scientia 8, 41 (2016)

    work page 2016

  66. [66]

    G. Yang, J. Leng, X. Wu, and L. Lin, (2026), arXiv:2603.16214 [quant-ph]

    work page arXiv 2026

  67. [67]

    L. K. Grover, Phys. Rev. Lett.95, 150501 (2005)

    work page 2005

  68. [68]

    T. J. Yoder, G. H. Low, and I. L. Chuang, Phys. Rev. Lett.113, 210501 (2014)

    work page 2014

  69. [69]

    J. M. Martyn, Z. M. Rossi, A. K. Tan, and I. L. Chuang, PRX Quantum2, 040203 (2021). 7 Supplemental Material S1. RELA TION TO PRIOR WORKS A schematic construction of a QKA is shown in Fig. S1. One first specifies a dynamical system, i.e., a vector fieldF in (1) (A1), and then selects a family of observables{g m}(A2), which induces the Koopman evolution (2...

    work page 2021

  70. [70]

    [5, 60], the complexityQfor outputting a stateϵ-close to Eq

    Query complexity cost Using the results in Ref. [5, 60], the complexityQfor outputting a stateϵ-close to Eq. (6) is Q=O αmax τ∈[0,t] ∥eBτ ∥g(t)tlog max{t,∥vec(Y)∥} ϵΓmin(t) log g(t)t ϵ ,(S29) whereαis the block-encoding prefactor forBand g(t) := max τ∈[0,t] ∥Γ(τ)∥ F ∥Γ(t)∥F ,(S30a) Γmin(t) := min τ∈[0,t] ∥Γ(τ)∥ F .(S30b) The complexityQmeasures the number...

    work page

  71. [71]

    Efficient block-encoding ofB In order to efficiently block-encodeB, it is sufficient to block-encodehandX, which can then be combined using an LCU. It is known that a sparsehcan be efficiently block-encoded under the assumptions of Result 1, so we only need to block-encodeX: X= 2 X µ Re(l† µlµ).(S37) 12 To achieve this, we will construct a block-encodingU...

    work page

  72. [72]

    ∞X k=0 Bkη⊗k # i ,(S109) and so we are dealing with the following dynamical systems: ˙xi =a i(xi) 1 + 1 λiηi

    Efficient state preparation ofvec(Y) Our aim now is to construct an efficient state preparation unitaryU |vec(Y)⟩ of the normalized version|vec(Y)⟩of the vector vec(Y) =−4 X µ Im(l∗ µ ⊗l µ).(S49) If there are only Θ(1) nonzero elements of Iml µi, then|vec(Y)⟩can trivially be prepared efficiently, and the norm ∥vec(Y)∥will be Θ(1). Otherwise, when there ar...

    work page

  73. [73]

    Prepare the window state together with two registers initialized to the all-zero state, with one serving as the system register and the other as an ancilla: J−1X j=0 βj|j⟩|0⟩|0⟩. 30

    work page

  74. [74]

    The implementation details of this operation are given in Appendix S7 I

    Apply the controlled ODE-solver unitary |j⟩|0⟩|0⟩ 7→ |j⟩W(T 1 +j∆t)|0⟩|0⟩. The implementation details of this operation are given in Appendix S7 I. This prepares a state close to J−1X j=0 βj|j⟩|0⟩|¯g(T1 +j∆t)⟩= J−1X j=0 βj ∥g(T1 +j∆t)∥ |j⟩|0⟩|g(T1 +j∆t)⟩(S197) ≈ 1 ∥aS∥ J−1X j=0 βj|j⟩|0⟩|g(T1 +j∆t)⟩.(S198)

    work page

  75. [75]

    Apply the inverse quantum Fourier transform to the first register

    work page

  76. [76]

    If the outcome isℓ∈ {0,1,

    Measure the first register. If the outcome isℓ∈ {0,1, . . . , J−1}, output ˆωℓ :=    2πℓ J∆t ,0≤ℓ≤ J−1 2 , 2πℓ J∆t − 2π ∆t , J+1 2 ≤ℓ≤J−1. (S199) The decoding rule above is the frequency version of the signed phase decoding from the previous subsection. The Nyquist-margin assumption becomes −π+c≤ω k∆t≤π−c(S200) for every relevant frequencyω k. Under ...

    work page

  77. [77]

    If this step fails, the algorithm terminates

    Use quantum singular value transformation (QSVT) [24] to approximately implement a reflection about the kernel ofG r, and apply this operation to|e D⟩. If this step fails, the algorithm terminates

    work page

  78. [78]

    If the outcome corresponds toI− |eD⟩⟨eD|, output the final state; otherwise, the algorithm fails

    Perform the measurement{I− |e D⟩⟨eD|,|e D⟩⟨eD|}on the resulting state. If the outcome corresponds toI− |eD⟩⟨eD|, output the final state; otherwise, the algorithm fails. To achieve accuracyϵ 2 in the output, the QSVT in the second step requires ˜O(κ A log (1/ϵ2)) controlled queries to UA,U b, and their inverses. Ref. [62] shows that the above procedure suc...

    work page

  79. [79]

    In the following, we ignore the small ˜O(l) difference between these costs. Recall that |y⟩ ≈ m−1X s=0 |s⟩|g(sh)⟩+ m+p−1X s=m |s⟩|g(t)⟩.(S257) Hence, Ur|0⟩1|0⟩2|0⟩3 ≈ crqPm−1 s=0 ∥g(sh)∥2 +p∥g(t)∥ 2 |0⟩1 m−1X s=0 |s⟩2|g(sh)⟩3 + m+p−1X s=m |s⟩2|g(t)⟩3 ! + X i̸=0 |i⟩1|eξr,i⟩2,3.(S258) Letd= (p−m)/2 and define Π =|0⟩⟨0| ⊗P [m+p]\[m+d]. Then (Π1,2 ⊗I 3)(Ur)1,...

    work page