LCHS — linear combination of Hamiltonian simulation

What it fills

• Solve a linear ODE du/dt = A(t)u + b(t)

  Given block-encoding access to $A(t)$ and $b(t)$ and a preparation unitary for $u_0$, output a normalized state $\varepsilon$-close to $u(T)/||u(T)||$. Matrix-query and state-preparation-query counts are stated separately, because methods here differ in them independently.

When it applies

Requires the decomposition $A(t) = L(t) + iH(t)$ with $L(t) = (A(t)+A(t)^†)/2$ the Hermitian part, and $L(t) ⪰ 0$ throughout the interval. Without a shift it does not apply when the Hermitian part has a negative eigenvalue anywhere on the interval — this is a real restriction, and the analogue at the linear layer of Carleman's dissipativity requirement. It does not rely on converting the problem into a dilated linear system problem, or on the spectral mapping theorem that underpins QSVT-based approaches, which is what substantiates the bypass rather than merely asserting it.

Requires

Every step this method names moves its route along, so there is nothing it needs alongside them.

Example

An, Liu and Lin's contribution is analytical throughout: Theorem 1 is the kernel identity, Theorems 2 and 3 are query-complexity theorems and Theorem 9 is a sampling-complexity theorem for the hybrid variant. A full-text read including the Supplemental Materials found no numerical experiment, no simulator and no hardware run. The improved-kernel paper cited under Refinements does carry numerics, but they measure that kernel's truncation and belong to `lchs-improved-kernel`.

given  A(t) = L(t) + iH(t)  with L(t) >= 0 on [0,T],  b(t),  u_0,  tolerance eps
       O_prep : |0> -> |u_0>
       O_L(s,tau) = e^{-iL(tau)s},  O_H(s,tau) = e^{-iH(tau)s}
       O_coef : |0> -> (1/sqrt(||c||_1)) sum_j sqrt(c_j) |j>
       O_b    : |j'>|0> -> |j'>|b(s_j')>

# 1. truncate and discretize the k-integral of the LCHS identity
K   = c/eps                          # remainder pi - 2 arctan K = O(1/K) = O(eps)
k_j = -K + 2jK/M,   w_j = (2 - 1_{j=0,M}) K/M,   c_j = w_j / (pi (1 + k_j^2))
M   = O(||L|| T / eps^2)             # trapezoidal-rule error

# 2. each surviving term is one Hamiltonian simulation problem
#      U_j(T) = T exp(-i int_0^T (H(s) + k_j L(s)) ds)
#    implemented by a p-th order product formula with the SAME step count r for all j

# 3. homogeneous part, by LCU
apply O_coef (x) O_prep
for l' = 0 ... r-1:
    for l = 0 ... Xi_p - 1:
        apply SEL_L(alpha_l T/r, (l'+gamma_l) T/r)   # sum_j |j><j| (x) e^{-iL(tau) k_j s};
                                                     # O(log M) queries to O_L
        apply O_H(beta_l T/r, (l'+delta_l) T/r)
apply O_coef^dagger on the ancilla register

# 4. inhomogeneous part: the same construction over a two-dimensional trapezoidal
#    rule in (k,s), with O_b loading |b(s_j')>
# 5. combine the two with one extra ancilla qubit and a single-qubit rotation
#    (an outer LCU)

# 6. measure ALL the ancilla registers; if every outcome is 0 the state
#    approximately encodes u(T).  One shot succeeds with probability
#    (||T|psi>|| / ||alpha||_1)^2; amplitude amplification raises it to Omega(1)
#    at O(||alpha||_1 / ||T|psi>||) queries.

Cost, as the source states it

An, Liu and Lin price the solver in Theorem 2, for the implementation combining LCU with a $p$-th order product formula: $\tilde{O}( ((||u_0|| + ||b||_{L^1})/||u(T)||)^{2+2/p} \Gamma_p^{1+1/p} T^{1+1/p} / \varepsilon^{1+2/p} )$ queries to the input models of $H$ and $L$, where $\Gamma_p$ collects the sizes of the first $p$ derivatives of $H$ and $L$, together with $O( (||u_0|| + ||b||_{L^1})/||u(T)|| )$ queries to the state-preparation oracle and the source input. The second count is the title's claim: it matches the $\Omega(||u_0||/||u(T)||)$ lower bound the paper cites, so no differential-equation solver can query the initial state fewer times. The matrix-query count is not optimal, and the paper says why: the Cauchy kernel $1/(\pi(1+k^2))$ decays only quadratically, forcing the truncation $K = O(1/\varepsilon)$ and an extra $\varepsilon^{-1}$ factor of circuit depth — the limitation the improved kernel recorded under Refinements was built to remove.

Implementations

• Coherent LCU with a $p$-th order product formula

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

  The paper's own "simplest implementation of LCHS", and the one Theorem 2 prices. It solves Eq. (1), $\partial_t u(t) = -A(t)u(t) + b(t)$ with $u(0) = u_0$, by preparing the solution directly in a quantum register rather than reading an observable off it: the linear combination "can also be coherently implemented to prepare the solution directly in a quantum register and to reduce the complexity", and it is in this case that the authors claim the cost of LCHS is optimal in terms of state preparation, which they say is useful when the initial state $u_0$ is difficult to prepare. The Implementation section frames the choice as one of several — LCHS "can be implemented in a gate-efficient way by combining LCU with any Hamiltonian simulation algorithms" — and this entry is the product-formula option; the truncated Dyson series option is the interaction-picture entry beside it.

  The $k$-integral of Theorem 1 is first truncated to $[-K,K]$ and discretized by a trapezoidal rule on $M+1$ grid points $k_j = -K + 2jK/M$, with weights $w_j = (2-1_{j=0,M})K/M$ and coefficients $c_j = w_j/(\pi(1+k_j^2))$. Each surviving propagator $U_j(T) = \mathcal{T}e^{-i\int_0^T (H(s)+k_j L(s))\,ds}$ is then implemented by a $p$-th order product formula with a fixed number of steps $r$ shared by all $j$, which is Eq. (8): $\mathcal{T}e^{-\int_0^T A(s)\,ds}u_0 \approx \sum_{j=0}^{M} c_j v_j$ with $v_j = \prod_{l'=0}^{r-1}\prod_{l=0}^{\Xi_p-1} e^{-iH\left(\frac{(l'+\delta_l)T}{r}\right)\frac{\beta_l T}{r}} e^{-iL\left(\frac{(l'+\gamma_l)T}{r}\right)\frac{\alpha_l k_j T}{r}} u_0$, where $\Xi_p$ is the number of exponentials in the product formula, $\alpha_l$ and $\beta_l$ are its coefficients, and $\gamma_l$ and $\delta_l$ fix the discrete times at which the time-dependent Hamiltonians are evaluated. The circuit is the standard LCU: apply $O_{\mathrm{coef}} \otimes O_{\mathrm{prep}}$, then apply $\mathrm{SEL}_L(\alpha_l T/r, (l'+\gamma_l)T/r)$ and $O_H(\beta_l T/r, (l'+\delta_l)T/r)$ in sequence for $l \in [\Xi_p]$ and $l' \in [r]$, and finally $O_{\mathrm{coef}}^{\dagger}$ on the ancilla register. The family is indexed rather than enumerated: from the binary representation of $j$, the select oracle $\mathrm{SEL}_L(s,\tau) = \sum_{j=0}^{M}|j\rangle\langle j| \otimes e^{-iL(\tau)k_j s}$ is built with $O(\log M)$ queries to $O_L(s,\tau)$. The source term is handled by the same Trotterization and LCU over a multidimensional trapezoidal rule in $k$ and $s$, with coefficients $\tilde{c}_{j,j'} = v_{j'}w_j\|b(s_{j'})\|/(\pi(1+k_j^2))$, $v_{j'} = (2-1_{j'=0,M})T/(2M_t)$ and $s_{j'} = j'T/M_t$. The two parts are joined by appending one extra ancilla qubit, preparing both states controlled on it, and running LCU again at the outer loop with a single-qubit rotation. All ancilla registers are then measured, and the all-zeros outcome is the flag: "if all the outcomes are 0, then the resulting state approximately encodes the solution $u(t)$ of the ODE". For the special case $A(t) \equiv A$ the paper simplifies the same implementation — the coherent encoding of the time evolution is no longer needed, the select oracles can be constructed from $O_L(s) = e^{-iLs}$ and $O_H(s) = e^{-iHs}$ at $O(\log(M)\log(M_t))$ cost, and $\Gamma_p$ improves to commutator scalings between $H$ and $L$.

  Stated against oracles rather than a data set. The state preparation oracle is $O_{\mathrm{prep}} : |0\rangle \to |u_0\rangle$; the Hamiltonian simulation oracles are $O_L(s,\tau) = e^{-iL(\tau)s}$ for $|s| \le 1/\|L\|$ and $O_H(s,\tau) = e^{-iH(\tau)s}$ for $|s| \le 1/\|H\|$; the LCU coefficient oracle is $O_{\mathrm{coef}} : |0\rangle \to \frac{1}{\sqrt{\|c\|_1}}\sum_{j=0}^{M}\sqrt{c_j}\,|j\rangle$. With a source term present the evolution times of the different Hamiltonians vary, so the input models are assumed to encode evolutions of different lengths coherently: $O'_L(s,\tau_0,\tau_1) = \sum_{j'=0}^{M_t}|j'\rangle\langle j'| \otimes e^{-iL(\tau_0 j' + \tau_1(M_t-j'))s(M_t-j')}$ and the matching $O'_H$ for $|s|M_t \le 1/\|H\|$, with the source itself entering as $O_b : |j'\rangle|0\rangle \to |j'\rangle|b(s_{j'})\rangle$. The paper states that all of these oracles are an extension of the time-dependent encoding proposed by Low and Wiebe.

  What came out is Theorem 2, and no execution. The theorem states that the algorithm prepares an $\varepsilon$-approximation of $|u(T)\rangle$ with $\Omega(1)$ success probability and a flag indicating success. Its two query counts are quoted in this record's cost field; the two counts that are not are $O(\log(\Gamma_1\|b\|_{C^2}T/\varepsilon))$ ancilla qubits, with $\|b\|_{C^2} = \sum_{q=0}^{2}\max_{\tau\in[0,T]}\|b^{(q)}(\tau)\|$, and $O((\|u_0\|+\|b\|_{L^1})/\|u(T)\|)$ additional one-qubit gates. The authors attribute the small state-preparation count to the fact that each run of the LCU procedure only requires $O(1)$ uses of such oracles, so that the overall complexity relates only to the success probability. No instance of this implementation was run: the paper names no simulator and no hardware, reports no numerics, and its only figure is the contour used to prove Lemma 4. The Discussion names the implementation's own limitation instead, that the spectral radius of the Hermitian part $L$ is multiplied by a factor up to the frequency cutoff $K = O(1/\varepsilon)$, which "increases the maximal circuit depth by a factor $\varepsilon^{-1}$".

• Hybrid quantum-classical estimation of observables

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

  The ending for a reader who wants an observable rather than the state, and the one the authors put forward for early fault-tolerant machines: the linear combination "can be implemented in a hybrid quantum-classical fashion to compute observables related to the solution, using a small amount of quantum resources". Because each $U_j$ is unitary, an observable of the solution splits into correlation functions, which is Eq. (6): $u(t)^*Ou(t) \approx \sum_{k,k'} c_k^* c_{k'}\langle u_0|U_k^{\dagger}(t)OU_{k'}(t)|u_0\rangle$. The quantum computer therefore never has to hold the whole linear combination at once, and the same expression is available for the inhomogeneous case. This is the second ending the atlas records but does not draw as a route.

  The quantum computer evaluates the correlation functions $\langle u_0|U_k^{\dagger}(t)OU_{k'}(t)|u_0\rangle$ by the non-unitary Hadamard test together with amplitude estimation, and the summation is performed on a classical computer by Monte Carlo sampling. The non-unitary Hadamard test is the ordinary one — an ancilla qubit, a Hadamard gate, a controlled operation, a second Hadamard gate, and a measurement whose probability of outcome 0 carries the real part — with the controlled unitary replaced by the controlled block encoding of the non-unitary target; the imaginary part follows with a slight modification. Here the target is assembled as an $(\alpha_O,0)$-block-encoding of $\tilde{U}_k^{\dagger}(t)O\tilde{U}_{k'}(t)$ by multiplying $\tilde{U}_{k'}$, $U_O$ and $\tilde{U}_k^{\dagger}$ with additional ancilla qubits. The classical loop has three steps: for each $j = 1,\dots,J$ sample a pair $(k,k')$ independently with probability $c_k c_{k'}/\|c\|_1^2$; estimate $\langle u_0|U_{k(j)}^{\dagger}(t)OU_{k'(j)}(t)|u_0\rangle$ by the non-unitary Hadamard test and call the successful estimator $X_j$; then report $\|c\|_1^2\bar{X}$ with $\bar{X} = \frac{1}{J}\sum_{j=1}^{J}X_j$. If there were no error in implementing $U_k(t)$ or in the Hadamard test, $\mathbb{E}\bar{X}$ would be exactly $u(t)^*Ou(t)$; the implementation error is absorbed by taking $\varepsilon_{HS} = O(\varepsilon/\|O\|)$, and the sampling error is bounded by Hoeffding's inequality. The estimate is of the possibly unnormalized $u(t)^*Ou(t)$, which the paper calls the natural setup for classical non-unitary dynamics; estimating $\langle u(t)|O|u(t)\rangle$ for the normalized solution instead means dividing by $\|u(t)\|^2$, which tightens the tolerance to $\varepsilon\|u(t)\|^2$ and needs a separate algorithm to estimate $\|u(t)\|$ when it is not known in advance.

  Again oracles rather than a data set: the state preparation oracle $O_{\mathrm{prep}}$ of $|u_0\rangle$, a unitary $U_O$ that is an $(\alpha_O,0)$-block-encoding of the observable with $\alpha_O \ge \|O\|$, and a quantum circuit $\tilde{U}_k(t)$ approximating $U_k(t)$ with error smaller than $\varepsilon_{HS}$ for any $k$. The sampling distribution is the quadrature's own coefficient vector $c = (c_k)$ with $c_k = w_j/(\pi(1+k_j^2))$: these are all positive reals, they satisfy $\sum_{k,k'}c_k c_{k'} = \|c\|_1^2$, and $\|c\|_1 = O(1)$ because they come from the numerical approximation of $\int \frac{dk}{\pi(1+k^2)}$.

  What came out is Theorem 9, and no execution. Choosing $\varepsilon_{HS} = O(\varepsilon/\|O\|)$, the procedure estimates $u(t)^*Ou(t)$ to precision $\varepsilon$ with probability at least $1-\delta$; the number of samples is $O\left(\frac{\|O\|^2}{\varepsilon^2}\log\frac{1}{\delta}\right)$ and each circuit with sampled value $(k,k')$ uses $O\left(\frac{\alpha_O}{\varepsilon}\log\frac{\alpha_O}{\varepsilon}\log\frac{\|O\|\log(1/\delta)}{\delta\varepsilon}\right)$ queries to $O_{\mathrm{prep}}$, $U_O$ and $\tilde{U}_k(t)$. The authors add that the final complexity in terms of the input models for $A(t)$ still depends on how $\tilde{U}_k(t)$ is actually implemented, so a low-order method such as the first-order Trotter formula introduces extra overhead, while a high-order Trotter formula or the truncated Dyson series method makes it almost linear in $t$, $k$ and certain norms of $A$ with $1/\varepsilon_{HS}^{o(1)}$ dependence. In the worst case the circuit's query complexity is still almost linear in $K$, but they remark that on average that $K$ dependence improves, because a circuit with larger $k$ and $k'$ is sampled with a probability that decays quadratically as $\sim 1/(k^2k'^2)$. No instance of this hybrid procedure was run: Supplemental §IV is a proof section, and the paper reports no numerics anywhere.

• Interaction-picture LCHS with a complex absorbing potential

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

  The paper's application, and the source of the abstract's claim of "near-optimal dependence on all parameters". Problems in quantum dynamics such as molecular scattering, photodissociation and nanotransport are defined in an infinite space, and replacing that space by a finite box can introduce significant errors along extended dimensions, so boundary conditions have to be designed to balance accuracy against cost. In its simplest form the complex absorbing potential method, widely used in quantum chemistry, replaces the real potential by a complex one, and the time-dependent Schrödinger equation becomes Eq. (10), $i\partial_t u(r,t) = \left(-\frac{1}{2}\Delta_r + V_R(r,t) - iV_I(r)\right)u(r,t)$, where $V_R$ is the real time-dependent external potential and $-iV_I$ is the absorbing potential, which can often be chosen time-independent and can be taken bounded and non-negative; the minus sign reflects that it damps. The discussion is confined to single-particle dynamics for simplicity, and the authors say the formulation generalizes to multi-particle dynamics and to other boundary treatments such as the perfectly matched layer method. The regime of interest is before the scattering wave leaves the region of interest, so that $\|u(T)\|^2 = \int|u(r,T)|^2dr$ is not too small — a condition also satisfied when $u_0$ is a near-resonance state.

  The spatial variable is discretized on $N$ equidistant grid points with the Laplace operator taken by the central difference formula, which puts the problem in the form of Eq. (1) with Hermitian part $H(t) = -\frac{1}{2}\Delta_r + V_R(t)$, of norm $\|H(t)\| = O(N^2 + \max_t\|V_R(t)\|)$, and non-Hermitian part $L = V_I$, a time-independent positive semi-definite matrix. Because $e^{-ikLt}$ can be fast-forwarded, in the sense that it can be performed at a cost independent of $k$, $t$ and $\|L\|$, the Hamiltonian simulation is carried out in the interaction picture with the truncated Dyson series method, which avoids the overhead the cutoff $K$ otherwise brings: the derivative of $H_I$ still scales linearly in $K$, but the cost of the truncated Dyson series method scales only logarithmically with respect to that derivative. The identity becomes Eq. (11), $\mathcal{T}e^{-\int_0^t A(s)\,ds} \approx \sum_{j=0}^{M} c_j e^{-iLk_j t}\left(\mathcal{T}e^{-i\int_0^t H_I(s;k_j)\,ds}\right)e^{iLk_j t}$ with $H_I(s;k) = e^{iLks}H(s)e^{-iLks}$, and is implemented directly by LCU. In the proof, $V_I$ is diagonal, so $O_L(s) = e^{-iLs}$ is constructed fast-forwardly with a single use of $O_{V_I}$ for any $s$, and $\mathrm{SEL}_L(s) = \sum_{j=0}^{M}|j\rangle\langle j| \otimes e^{-iLk_j s}$ with $O(\log M)$ queries to it. A HAM-T oracle block encoding $H(t)$ over each interval $[mh,(m+1)h]$ costs $O(1)$ uses of $O_{V_R}$, with $\alpha_H = O(N^2+\max_t\|V_R(t)\|)$ and $M_H$ the number of grid points per step of the truncated Dyson series method. Conjugating it by the two select oracles, $\mathrm{HAM\text{-}T}_{H_I,m} = (I_{n_a}\otimes \mathrm{SEL}'_{L,m})(I_{\log(M)}\otimes \mathrm{HAM\text{-}T}_{H,m})(I_{n_a}\otimes \mathrm{SEL}_{L,m})$, gives the input model of $H_I(t;k)$ at $O(\log(M_H)\log(M))$ queries to $O_{V_I}$ and $O_{V_R}$. Low and Wiebe's Corollary 4 then yields a select oracle $\mathrm{SEL}_W = \sum_j |j\rangle\langle j|\otimes W_j$ with $\|W_j - \mathcal{T}e^{-i\int_0^T H_I(s;k_j)\,ds}\| \le \varepsilon'$, and $\mathrm{SEL}_U = \mathrm{SEL}_L(T)\,\mathrm{SEL}_W\,\mathrm{SEL}_L(-T)$ is the select oracle of the LCU step. Splitting the final error $\||u(T)\rangle - |\tilde{u}\rangle\|$ into a quadrature part and a simulation part fixes $M = \|V_I\|T/\varepsilon^2$ and $\varepsilon' = \varepsilon\|u(T)\|/(4\|c\|_1\|u_0\|)$, and amplitude amplification then needs $O(\|c\|_1\|u_0\|/\|\tilde{u}\|) = O(\|u_0\|/\|u(T)\|)$ repeats to reach a success.

  The oracles are $O_{V_I} : |r\rangle|0\rangle \to |r\rangle|V_I(r)\rangle$ and the sparse input oracle $O_{V_R} : |r\rangle|s\rangle|0\rangle \to |r\rangle|s\rangle|V_R(r,s)\rangle$, where $|r\rangle$ and $|s\rangle$ encode discrete indices after spatial discretization and $|s\rangle$ may vary on different sub-intervals, together with the state preparation oracle $O_{\mathrm{prep}}$ for the initial condition. Both potentials enter as data through those oracles rather than as matrices: $V_I$ and $V_R$ are diagonal, and $-\Delta_r/2$ after spatial discretization is tridiagonal with diagonal entries $1/N^2$ and off-diagonal entries $-1/(2N^2)$.

  What came out is Theorem 3, and no execution. The algorithm prepares an $\varepsilon$-approximation of $|u(T)\rangle$ with $\Omega(1)$ success probability and a flag indicating success, using $\tilde{O}\left(\frac{\|u_0\|}{\|u(T)\|}T\left(\max_t\|H(t)\|\right)\mathrm{poly}\log\frac{\max_t\|V_R'(t)\|\|V_I\|}{\varepsilon}\right)$ queries to $O_{V_I}$ and $O_{V_R}$ and $O(\|u_0\|/\|u(T)\|)$ queries to $O_{\mathrm{prep}}$, where $\max_t\|H(t)\| = O(N^2 + \max_t\|V_R(t)\|)$. The authors describe this as achieving near-optimal scaling in all parameters, and remark that the result also holds in the more general case where $H(t)$ is an arbitrary time-dependent Hamiltonian and $L$ is a time-independent fast-forwardable Hamiltonian. The Discussion states the price this variant charges in exchange: Hamiltonian simulation in the interaction picture "may be difficult to implement", and the authors name a fast-decaying replacement for the kernel $(1+k^2)^{-1}$ as the more desirable solution — the direction the improved-kernel record beside this one took. Nothing was run here either: Supplemental §VIII is the proof of Theorem 3 and reports no numerics.

What it needs

1. Recast a non-Hermitian generator as Hamiltonian evolution 2 methods

   Given a generator $A(t)$ whose evolution is not unitary, produce a Hermitian generator — or a quadrature-indexed family of them — on a space at least as large, whose unitary evolution reproduces the original dynamics, together with the map that recovers the original solution. Both halves are required: a construction that reaches a Hamiltonian and cannot get back is not a route.

2. Simulate Hamiltonian evolution 3 methods

   Implement $e^{-iHt}$ to error $\varepsilon$ given some access model for $H$. It is an application in its own right and also the engine inside phase estimation and several linear-system solvers.

Slots it makes unnecessary

These do not fill the slot. They replace the span it belongs to, so this layer is not on their path at all.

• Quantum linear solve

  Given access to a matrix $A$ and a unitary that prepares $|b>$, produce a flagged quantum state that is $\varepsilon$-close in $l2$ to the normalised $A^{-1}b$. The deliverable is a state, not a classical vector.

• Choose a time discretization or propagator approximation

  Reduce continuous evolution over $[0,T]$ to a finite algebraic object — a banded linear system, a product of step propagators, or a spectral coefficient system — with a stated truncation error. When a linear system is formed, a conditioning bound is stated with it.

Other ways to fill the same slot

Different approaches

• Linear multistep method, all-at-once encoding

  The first quantum algorithm for general linear ODEs. Discretize with a high-order linear multistep method, lay every time step out at once against a clock register so that one state $\sum_j |t_j\rangle|x_j\rangle$ holds the whole history, and solve the resulting sparse linear system with a quantum linear system algorithm. Going high-order is what buys the $\Delta t$ scaling: plain Euler costs at least $O(\Delta t^4)$ here.

• Taylor propagator, all-at-once encoding

  Encode a truncated Taylor series of the propagator into a single sparse linear system approximating the whole evolution, then solve it with a quantum linear system algorithm. This is what brought the precision dependence down to polynomial in $\log(1/\varepsilon)$.

• Chebyshev spectral method, global collocation

  The route that brought $\mathrm{poly}(\log(1/\varepsilon))$ precision to linear ODEs with **time-dependent** coefficients, which is what its abstract says was missing: "no such algorithm was previously known for differential equations with time-dependent coefficients". It does it by not stepping. The solution is approximated globally by a truncated Chebyshev series, the coefficients are fixed by collocating the differential equation at Chebyshev nodes, and the resulting sparse system goes to a high-precision quantum linear system algorithm. The exponential precision is bought by smoothness rather than by the solver: it is the $C^{\infty}$ convergence of the Chebyshev series that makes the series length logarithmic in $1/\varepsilon$.

• Krovi's reanalysis of the all-at-once encoding a narrower version of Taylor propagator, all-at-once encoding

  Reanalyses the all-at-once propagator encoding and shows that the norm of the matrix exponential, rather than the eigenvector condition number, characterizes the run time. It still forms a global linear system and still calls a quantum linear solver.

• Dyson propagator, all-at-once encoding

  Encode the Dyson series in a system of linear equations and solve it via the optimal quantum linear equation solver, extending the all-at-once approach to genuinely time-dependent generators.

• Time-marching with uniform singular value amplification

  Propagate the solution one step at a time and defeat the exponentially vanishing success probability by repeatedly invoking uniform singular value amplification, improved further by a compression gadget lemma. Fang, Lin and Tong present it explicitly as a design path alternative to solvers based on quantum linear systems algorithms.

• Schrödingerisation (linear PDEs as Schrödinger equations)

  A simple change of variable — the warped phase transformation, which introduces one extra variable — recasts any linear PDE or ODE system into a system of Schrödinger equations in real time, which ordinary Hamiltonian simulation then runs. The original solution is recovered from the auxiliary dimension.

Narrower versions of this one

• LCHS with the improved kernel a narrower version of LCHS — linear combination of Hamiltonian simulation

  A family of identities expressing non-unitary evolution as a linear combination of unitary evolutions, built on the kernel $f(z) = 1/(C_β e^{(1+iz)^β})$ with $β ∈ (0,1)$ and $C_β = 2π e^{-2^β}$. The kernel decays at a near-exponential rate $e^{-c|k|^β}$, replacing the original Cauchy kernel's quadratic decay and exponentially enhancing accuracy.

In the Atlas

• Linear combination of unitaries

  A block-encoding primitive that turns a weighted sum of unitary operations into one larger unitary circuit.

Sources

• Linear combination of Hamiltonian simulation for nonunitary dynamics with optimal state preparation cost↗Dong An, Jin-Peng Liu, Lin Lin · 2023theory yes · simulation no · hardware no