It surpasses existing QLSA-based solvers in three respects stated by the authors: $A(t)$ need not be diagonalizable; $A(t)$ may be non-smooth and is only required to be of bounded variation; and it can use fewer queries to the initial state. It needs no global linear solve, which is what makes the bypass real rather than rhetorical. The trade is in matrix queries: An, Childs and Lin's comparison table gives time-marching a worse dependence on $\alpha_A T$ than the LCHS family while crediting it with the same initial-state-preparation advantage.

A block-encoding of $A(t)$ with a normalization $\alpha_A \ge \max_t \lVert A(t)\rVert$, preparation unitaries for $u_0$ and $b$, the evolution time $T$, and an error tolerance $\varepsilon$.

1. Linear ODE system → Linear system Ax = bChoose a time discretization or propagator approximation runs once per time step, with an amplification at every one

   What this slot returns on this route is a product of step propagators rather than a global system: the mesh is chosen so that $t_l - t_{l-1} \le (2\alpha)^{-1}$ with $\alpha = \sup_t \|A(t)\|$, hence $L = \Theta(\alpha T)$ segments, and each segment contributes a block encoding of the short-time propagator $\Xi_l = \mathcal{T} e^{\int_{t_{l-1}}^{t_l} A(t)\,dt}$. approximation: The Dyson series is truncated at order $K$, with error at most $(\int_a^b \|A(s)\|\,ds)^K / K!$; the segment is cut short precisely so that $\int_a^b \|A(s)\|\,ds = O(1)$ and a few terms already give high accuracy. assumption: Each step's integrator $\bar{\Xi}_l$ must be consistent with $\Xi_l$ to $\|\Xi_l - \bar{\Xi}_l\| \le \varepsilon_l \|\Xi_l\|$ — a precision relative to $\|\Xi_l\|$ and not an absolute one — and the composition theorem additionally needs $\sum_l \varepsilon_l \le 1/2$ across the whole mesh. Section 5 pairs the same marching with a first-order truncated Magnus step $\bar{\Xi} = e^{\frac{b-a}{M}\sum_{k=0}^{M-1} A(a + k(b-a)/M)}$ instead, which is equivalent to dropping the time-ordering operator and needs no time-clocking quantum control logic.

   approximationassumption

   The loop stays coherent: nothing is measured between turns. The preparation may still be reapplied every turn — what the loop never pays is a readout and a restart from classical data. The price is depth, and a success probability that multiplies down the chain. Fang, Lin and Tong's method is the repetition stated as the design: propagate one step at a time, and defeat the exponentially vanishing success probability by repeatedly invoking uniform singular value amplification. Nothing is measured between turns — the decay is a coherent one and it is bought back coherently — which is why the cost lands on the amplification ratio rather than on a shot count. The authors prove that linear dependence attains the query-complexity lower bound, so this repetition cannot be made cheaper in the worst case; it can only be avoided by not marching.

   Open this step

2. Linear system Ax = b → Answer about the solutionamplify each step, then post-select

   Each step's block encoding $U_l$ carries a subnormalization $\alpha_l \ge \|\Xi_l\|$, so post-selecting through all $L$ steps succeeds with probability $\|\Xi_L \cdots \Xi_1 |\psi(0)\rangle\|^2 / (\alpha_1 \alpha_2 \cdots \alpha_L)^2$; for the Euler step $\alpha_l = 1 + \|A\|T/L$, and that costs $e^{2\|A\|T} \| |\psi(0)\rangle \|^2 / \| |\psi(T)\rangle \|^2$ trials. Uniform singular value amplification rebuilds each $U_l$ as a $(\|\Xi_l\|/(1-\delta),\, m_l+1,\, \varepsilon'\|\Xi_l\|)$-block encoding at $O\!\left(\frac{\alpha_l}{\delta\|\Xi_l\|}\log\frac{\alpha_l}{\|\Xi_l\|\varepsilon'}\right)$ uses of $U_l$, and it is oblivious to the state it acts on, so no earlier step is ever re-prepared; with $\delta = 1/L$ one has $(1-\delta)^L = \Omega(1)$, the denominator becomes $\|\Xi_L\|^2 \cdots \|\Xi_1\|^2$, and the success probability is $\Omega(Q^{-2})$ for $Q = \prod_l \|\Xi_l\| / \| |\psi(T)\rangle \|$. approximation: The amplifying odd polynomial only has to agree with $\gamma' x$, $\gamma' = \alpha_l/\|\bar{\Xi}_l\|$, on $[-\gamma'^{-1}, \gamma'^{-1}]$; because the target is discontinuous there, the Gibbs phenomenon forces it to approximate $(1-\delta)$ times that target in order to keep $|p(x)| \le 1$ on $[-1,1]$, and the $1/(1-\delta)$ left in the subnormalization is what that costs. A counter register of $\lceil \log_2 L \rceil + 1$ qubits, started in $|L\rangle$ and decremented by a controlled $\mathrm{ADD}^{\dagger}$ at each successful step, keeps the whole chain coherent, so amplitude amplification runs without duplicating the ancilla register and the $Q$ dependence drops from $O(Q^2)$ to $O(Q)$. assumption: Every one of the $L$ steps must have succeeded — the procedure post-selects on the counter register to ensure exactly that, and success is flagged by the measurement result of a single qubit.

   approximationassumption

A state proportional to $u(T)$, or a history state, together with separately stated matrix-query and initial-state-query complexity.

The only numerical experiment in arXiv:2208.06941 — Section 2.3 with Figure 2, and Appendix C — measures the degree of the odd polynomial that uniform singular value amplification hands to QSVT, and nothing else. No differential equation is integrated, no quantum state is prepared, and no value of the problem's own parameters enters anywhere.

given  A(t) on [0,T] with alpha = sup_t ||A(t)||,  Uinit preparing |psi(0)>,  tolerance eps

choose the mesh 0 = t_0 < ... < t_L = T  with  t_l - t_{l-1} <= 1/(2 alpha)
    # so L = Theta(alpha T) segments

for l = 1 ... L:                    # once per time step
    # the time-discretization slot, invoked per segment, not once for the whole horizon
    U_l <- block encoding of  Xi_l = T-ordered exp( int_{t_{l-1}}^{t_l} A(t) dt )
           # truncated Dyson series (Sec 3.1), or the first-order Magnus step (Sec 5)
           # consistent to ||Xi_l - Xibar_l|| <= eps_l ||Xi_l||, with sum_l eps_l <= 1/2

    # the amplification, at every turn: subnormalization alpha_l -> ||Xi_l||/(1-delta)
    Utilde_l <- uniform singular value amplification of U_l, delta = 1/L
                # oblivious to the state, so no earlier step is re-prepared

# no all-at-once system is assembled and no quantum linear solve is called

counter <- |L>  on ceil(log2 L) + 1 qubits
apply Utilde_1, ..., Utilde_L in order, each decrementing counter by controlled ADD-dagger
    # coherent: nothing is measured between turns

post-select counter = |0>              # succeeds with probability Omega(Q^-2)
amplitude-amplify, O(Q) rounds        # Q = prod_l ||Xi_l|| / |||psi(T)>||
return the state on the flagged branch

The complexity depends linearly on the amplification ratio, which quantifies the deviation from a unitary dynamics; that linear dependence is proved to attain the query complexity lower bound and thus cannot be improved in the worst case.

• Time-marching paired with the high-order truncated Dyson series (Theorem 8)

  • Time-marching based quantum solvers for time-dependent linear differential equations

    Di Fang, Lin Lin, Yu Tong · 2022

  About

  The paper's headline algorithm, and the one its optimality result is about. The problem is Equation (1): prepare the solution of $\frac{d}{dt}|\psi(t)\rangle = A(t)|\psi(t)\rangle$ at time $T$, for a coefficient matrix $A$ of bounded variation on $[0,T]$, given a unitary circuit $U_{\mathrm{init}}$ with $U_{\mathrm{init}}|0^n\rangle = |\psi(0)\rangle$. Fang, Lin and Tong present it as a design route alternative to solvers built on quantum linear systems algorithms rather than as an improvement inside one.

  Methods

  The mesh satisfies $t_l - t_{l-1} \le (2\alpha)^{-1}$ for every segment, and each segment carries a time-dependent matrix encoding $\mathrm{MAT}_l$, an $(n_q, m, t_{l-1}, t_l, \alpha, \varepsilon'')$-MAT in the sense of the paper's Definition 1 with $\varepsilon'' < \varepsilon/(2TQ)$, out of which a block encoding of the high-order truncated Dyson series approximation to $\Xi_l$ is built. Every step's block encoding is then rebuilt by uniform singular value amplification at $\delta = 1/L$, the whole chain is made coherent by the compression gadget of Lemma 3 so that the ancilla register need not be duplicated $L$ times, and $O(Q)$ rounds of amplitude amplification lift the $\Omega(Q^{-2})$ success probability to at least $2/3$.

  Data

  None found yet.

  Code

  None found yet.

  Results

  What the theorem proves, rather than anything measured: $O\!\left(\alpha^2 T^2 Q \log(\alpha TQ)\, \frac{\log(\alpha TQ\varepsilon^{-1})}{\log\log(\alpha TQ\varepsilon^{-1})}\right)$ queries to all $\mathrm{MAT}_l$ and $O(Q)$ applications of controlled-$U_{\mathrm{init}}$ and its inverse, using $O(n + m + \mathrm{polylog}(V_0^T(A)\alpha TQ\varepsilon^{-1}))$ qubits and $\tilde{O}(\alpha^2 T^2 Q (m + \mathrm{polylog}(V_0^T(A)\alpha TQ\varepsilon^{-1})))$ additional elementary gates, preparing a state within $O(\varepsilon)$ of the normalized solution with probability at least $2/3$, success flagged by the measurement result of a single qubit. The authors report no execution of this algorithm on hardware or on a simulator.

• Time-marching paired with the first-order truncated Magnus integrator (Section 5, Theorem 14)

  • Time-marching based quantum solvers for time-dependent linear differential equations

    Di Fang, Lin Lin, Yu Tong · 2022

  About

  Section 5's simplified implementation. Implementing the high-order truncated Dyson series requires complicated quantum control logic for handling time-ordering operators, so the authors pair the same marching with the cheapest integrator that avoids that logic entirely: $\bar{\Xi} = \exp\left(\int_{t_j}^{t_{j+1}} A(s)\,ds\right)$, the first-order truncated Magnus series, which is the time-ordered propagator with the time-ordering operator simply dropped. In Hamiltonian simulation the same step is the quantum highly oscillatory protocol of An, Fang and Lin, and it carries commutator scaling in the high-precision limit. When $A(t)$ commutes with itself at any pair of times the step is exact, and the precision dependence of the query complexity becomes polylogarithmic.

  Methods

  The integral over a segment is approximated by a Riemann sum with $M = 2^{n_q}$ quadrature points, $\int_a^b A(s)\,ds \approx \frac{b-a}{M}\sum_{k=0}^{M-1} A(a + k(b-a)/M)$, and that sum is block encoded by applying a Hadamard on each of the $n_q$ quadrature qubits, then $\mathrm{MAT}_j$, then uncomputing the Hadamards. The resulting time-independent matrix exponential is then applied through the contour integral $e^A = \frac{1}{2\pi i}\oint_{\Gamma} e^z (z - A)^{-1}\,dz$, discretized by numerical quadrature into a linear combination of resolvents $(z_j - A)^{-1}$ each implemented with QSVT. The contour route is what the non-normal case forces: for a general $A$ the singular value transformation no longer agrees with the eigenvalue transformation, so the exponential cannot be applied by transforming singular values directly. Everything around the step, the amplification at each turn, the compression gadget and the $O(Q)$ rounds of amplitude amplification, is unchanged from the Dyson pairing.

  Data

  None found yet.

  Code

  None found yet.

  Results

  Theorem 14 states the general query count in terms of $\max\{\alpha_{\mathrm{comm}}T^2Q/\varepsilon,\ \alpha T\}$, where $\alpha_{\mathrm{comm}} := \sup_{s,\tau \in [0,T]}\|[A(s), A(\tau)]\|$. In the high-precision limit with a non-zero $\alpha_{\mathrm{comm}}$ it simplifies to $O\!\left(\frac{\alpha_{\mathrm{comm}}^2 T^4 Q^3}{\varepsilon^2}\log^2\frac{\max\{\alpha_{\mathrm{comm}}, \alpha\}TQ}{\varepsilon}\right)$ queries to all $\mathrm{MAT}_l$, together with $O(Q)$ applications of controlled-$U_{\mathrm{init}}$ and its inverse, on $O(n + m + \mathrm{polylog}(V_0^T(A)\alpha TQ\varepsilon^{-1}))$ qubits, with success flagged by the measurement result of a single qubit. When $\alpha_{\mathrm{comm}} = 0$ the authors note this first-order implementation has the same complexity scaling as the high-order truncated Dyson series. These are proved bounds; no run is reported.

• Sparse-matrix input model (Corollary 9)

  • Time-marching based quantum solvers for time-dependent linear differential equations

    Di Fang, Lin Lin, Yu Tong · 2022

  About

  The Theorem 8 algorithm re-costed on sparse access rather than on a supplied time-dependent matrix encoding. Fang, Lin and Tong give it because that input model is the one other quantum-linear-systems-based differential equation solvers and time-dependent Hamiltonian simulation algorithms are stated in, which is what makes a comparison against them a like-for-like one.

  Methods

  Gilyén, Su, Low and Wiebe's Lemma 48 builds the $(n_q, m, a, b, \alpha, \varepsilon)$-MAT that Theorem 8 needs out of those three oracles, at a single query each to $U_{\mathrm{row}}$ and $U_{\mathrm{col}}$ and two queries to $U_{\mathrm{val}}$. The precision $\varepsilon$ can be made arbitrarily small, and holding the error below it costs $O(n + \log^{5/2}(d\varepsilon^{-1}))$ additional elementary gates and $O(n_b + \log^{5/2}(d\varepsilon^{-1}))$ additional ancilla qubits, where $n_b$ is the number of bits encoding $A_{jk}(t)$; those ancillas can be reused. Nothing in the marching itself changes.

  Data

  $A(t)$ is $d$-sparse with $\|A(t)\| \le 1$, and the locations of its non-zero elements do not move with time. Access is three oracles: $U_{\mathrm{row}}|j,s\rangle = |j, \mathrm{row}(j,s)\rangle$, $U_{\mathrm{col}}|j,s\rangle = |j, \mathrm{col}(j,s)\rangle$ and $U_{\mathrm{val}}|t,j,k,z\rangle = |t,j,k,z \oplus A_{jk}(t)\rangle$, where $\mathrm{row}(j,s)$ is the row index of the $s$-th non-zero element in the $j$-th column and $\mathrm{col}(j,s)$ the column index of the $s$-th non-zero element in the $j$-th row.

  Code

  None found yet.

  Results

  Corollary 9's proved cost: $O\!\left(d^2 T^2 Q \log(dTQ)\, \frac{\log(dTQ\varepsilon^{-1})}{\log\log(dTQ\varepsilon^{-1})}\right)$ applications of controlled-$U_{\mathrm{row}}$, $U_{\mathrm{col}}$, $U_{\mathrm{val}}$ and their inverses, and $O(Q)$ applications of controlled-$U_{\mathrm{init}}$ and its inverse, on $O(n + \mathrm{polylog}(V_0^T(A)dTQ\varepsilon^{-1}))$ qubits with $\tilde{O}(d^2 T^2 Q(n + \mathrm{polylog}(V_0^T(A)dTQ\varepsilon^{-1})))$ additional elementary gates, at success probability at least $2/3$, flagged by the measurement result of a single qubit. Proved, not measured.

• Convex-optimization construction of the amplifying polynomial (Appendix C)

  • Time-marching based quantum solvers for time-dependent linear differential equations

    Di Fang, Lin Lin, Yu Tong · 2022

  About

  A replacement for the polynomial the amplification lemma is quoted from. Gilyén, Su, Low and Wiebe's construction approximates $(1-\delta)\,\mathrm{XRect}(x)$, and because $\mathrm{XRect}(x) = \gamma' x\,\mathrm{Rect}(x)$ is discontinuous at $x = \gamma'^{-1}$ the Gibbs phenomenon forces the $(1-\delta)$ factor and leaves a large preconstant, hence high degrees even at moderate $\alpha$, $\delta$ and $\varepsilon$. Fang, Lin and Tong observe that the amplification never needed that: it only needs a polynomial agreeing with $\gamma' x$ on $I = [-\gamma'^{-1}, \gamma'^{-1}]$, and outside $I$ the value may be anything the norm constraint $|p(x)| \le 1$ on $[-1,1]$ allows. Dropping the requirement to vanish outside $I$ is the whole of the idea.

  Methods

  The odd polynomial of degree $d$ is written in odd Chebyshev polynomials as $F(x) = \sum_{k=0}^{(d-1)/2} T_{2k+1}(x) c_k$, the interval $[-1,1]$ is discretized at $M$ grid points $x_j = -\cos\frac{j\pi}{M-1}$, and the coefficient matrix is $A_{jk} = T_{2k+1}(x_j)$. The coefficients then solve $\min_{\{c_k\}} \max_{x_j \in [0,\gamma'^{-1}]} |F(x_j) - (1-\delta)\gamma' x_j|$ subject to $|F(x_j)| \le c$ at every grid point, which is a convex problem. The norm constraint is imposed at the sampled points only, so $|F(x)| \le 1$ is relaxed to $|F(x_j)| \le c$ with $c$ chosen close to $1$, for instance $c = \max\{0.9999,\ 1 - 0.1\delta\}$, to absorb the slight overshoot possible between grid points. Because the program approximately solves a min-max problem, it is near-optimal in the $L^\infty$ sense by definition, in the asymptotic and the pre-asymptotic regime alike.

  Data

  None found yet.

  Code

  The convex program is solved with CVX, Grant and Boyd's Matlab software for disciplined convex programming, version 2.1. The resulting Chebyshev coefficients are then fed to QSPPACK, at https://github.com/qsppack/QSPPACK, which finds the phase factors using the optimization-based method of Dong, Meng, Whaley and Lin. Both are named in Appendix C; the paper publishes no repository of its own for the solver.

  Results

  At $\gamma' = 5$, $\delta = 0.05$, $\varepsilon = 0.01$ the construction returns degree 21, against 2001 for the polynomial approximating $(1-\delta)\,\mathrm{XRect}(x)$ at the same parameters. Figure 2 draws both polynomials in panels (a) and (b) and their errors on $I$ in panels (c) and (d); panel (e) sweeps the degree at fixed $\gamma'$ and $\delta$ and reports the $L^\infty$ error $\max_{x \in I}|p(x) - (1-\delta)\,\mathrm{XRect}(x)|$, showing both converge exponentially in the degree while the convex-optimization rate is significantly faster, which the authors say reduces the number of queries to each $U_l$ by orders of magnitude. This is a classical numerical construction and no hardware or quantum simulator is named for it; it measures the polynomial, not the solver.