Kernel-weighted combination of unitary propagators

What it fills

• Recast a non-Hermitian generator as Hamiltonian evolution

  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.

When it applies

Requires $L(t) = (A(t)+A(t)^†)/2 ⪰ 0$ throughout the interval; without a shift the identity does not apply when the Hermitian part has a negative eigenvalue anywhere on $[0,T]$. That restriction is the whole of what this construction demands, and it is a real one — it is the linear-layer analogue of Carleman's dissipativity requirement. What it does not require is anything the alternatives do: no dilated linear system, and no spectral mapping theorem of the kind QSVT-based approaches rest on.

Requires

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

Example

An, Liu and Lin (arXiv:2303.01029) contain no numerical experiment at all: the single figure is a contour used to prove a lemma, and no device, simulator or software is named. An, Childs and Lin (arXiv:2312.03916) do compute, but Section 2.2's Figure 2 measures how fast a different kernel decays, and this record's Cauchy kernel appears there only as the baseline the new one is drawn against.

given  A(t) on [0,T]

# 1. split into Hermitian and anti-Hermitian parts
L(t) = (A(t) + A(t)^dagger) / 2
H(t) = (A(t) - A(t)^dagger) / (2i)

# 2. the identity requires L(t) >= 0 on the whole interval
if L(t) is not positive semidefinite somewhere on [0,T]:
    c = - min_{t in [0,T]} lambda_min( L(t) )
    substitute u(t) = e^{ct} v(t)
    # v solves  d_t v = -( L(t) + cI + iH(t) ) v + e^{-ct} b(t),   and L(t) + cI >= 0

# 3. every member of the one-parameter family is Hermitian by construction
#      for each k in R:   H(t) + k L(t)  is Hermitian
#      so  V(t; ik) = T exp( -i int_0^t ( H(s) + k L(s) ) ds )  is unitary

# 4. the identity -- an equality, not an approximation
#      T exp( - int_0^t A(s) ds )  =  int_R  1/(pi (1 + k^2))  V(t; ik)  dk

# 5. hand downstream: the family { H(t) + k L(t) }_k, and the kernel
#    1/(pi (1 + k^2)) whose decay rate fixes how many members survive
#    truncation and quadrature of the k-integral
return  { H(t) + k L(t) }_k,  kernel 1/(pi (1 + k^2))

Cost, as the source states it

The count this construction hands downstream is the number of unitary propagators surviving truncation and discretization of the $k$-integral, and that number is set by how fast the kernel decays — which is why the kernel is the thing later work changed rather than the identity. The original Cauchy kernel $1/(\pi(1+k²))$ decays quadratically; An, Childs and Lin's $f(z) = 1/(C_\beta e^{(1+iz)^\beta})$ decays at a near-exponential $e^{-c|k|^\beta}$. The end-to-end query bounds those two produce are stated on `lchs-route` and `lchs-improved-kernel`, where the papers state them, and are not restated here.

Implementations

• LCU over a truncated quadrature grid, with product-formula Hamiltonian simulation

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

  The paper's own first implementation, and the one it calls the simplest: the identity is made finite by truncating and discretizing the $k$-integral, each surviving propagator is realized by a product formula, and the whole weighted sum is run as one LCU circuit that prepares the solution coherently in a quantum register. The problem statement is $\frac{d}{dt}u(t) = -A(t)u(t) + b(t)$ with $u(0) = u_0$ and $A(t)$ time-dependent and in general non-Hermitian, and the output is an $\varepsilon$-approximation of the state $|u(T)\rangle$ with $\Omega(1)$ success probability and a flag indicating success.

  The integral of Theorem 1 is truncated to $[-K,K]$ with $K = c/\varepsilon$, justified by $\int_K^\infty \frac{1}{1+k^2}\,dk = \pi - 2\arctan K = O(K^{-1})$, and discretized by the trapezoidal rule on $M+1$ points: $k_j = -K + 2jK/M$, $w_j = (2 - 1_{j=0,M})K/M$ and $c_j = w_j/(\pi(1+k_j^2))$. Each $U_j(T) = \mathcal{T}e^{-i\int_0^T (H(s)+k_jL(s))\,ds}$ is then realized by a $p$-th order product formula with a fixed number of steps $r$, the same $r$ for every $j$, giving Eq. (8) as a product over the $\Xi_p$ exponentials of the formula and over the $r$ steps. The LCU itself is standard: from the binary representation of $j$ a select oracle $\mathrm{SEL}_L(s,\tau) = \sum_j |j\rangle\langle j| \otimes e^{-iL(\tau)k_js}$ is built with $O(\log M)$ queries to $O_L$; then $O_{\mathrm{coef}} \otimes O_{\mathrm{prep}}$ is applied, then $\mathrm{SEL}_L(\alpha_lT/r, (l'+\gamma_l)T/r)$ and $O_H(\beta_lT/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. A source term is carried by Duhamel's principle, Eq. (7); its double integral over $k$ and $s$ is discretized by a multidimensional trapezoidal rule with coefficients $\tilde c_{j,j'} = v_{j'}w_j\lVert b(s_{j'})\rVert/(\pi(1+k_j^2))$ at the times $s_{j'} = j'T/M_t$, and the homogeneous and inhomogeneous states are joined by an outer LCU on one extra ancilla qubit with a single-qubit rotation. Measuring every ancilla register and reading all zeros is the success flag. When $A(t) \equiv A$ is time-independent the coherent time encoding is dropped: the select oracles are built from $O_L(s) = e^{-iLs}$ and $O_H(s) = e^{-iHs}$ at $O(\log(M)\log(M_t))$ cost, and the smoothness parameter $\Gamma_p = \max_{0 \le q \le p,\,\tau \in [0,T]} (\lVert H^{(q)}(\tau)\rVert + \lVert L^{(q)}(\tau)\rVert)^{1/(q+1)}$ is replaced by the commutator quantity $\Lambda_p = (\sum_{H_q \in \{H,L\}} \lVert [H_p,\dots,[H_1,H_0]]\rVert)^{1/(p+1)}$, which is never larger, while the order of $K$ in the Trotter error drops by one.

  Oracles only, and the paper instantiates none of them: the state preparation oracle $O_{\mathrm{prep}} : |0\rangle \to |u_0\rangle$, the Hamiltonian simulation oracles $O_L(s,\tau) = e^{-iL(\tau)s}$ for $|s| \le 1/\lVert L\rVert$ and $O_H(s,\tau) = e^{-iH(\tau)s}$ for $|s| \le 1/\lVert H\rVert$, and the coefficient oracle $O_{\mathrm{coef}} : |0\rangle \to \frac{1}{\sqrt{\lVert c\rVert_1}}\sum_j \sqrt{c_j}\,|j\rangle$. With a source term there are also $O_b : |j'\rangle|0\rangle \to |j'\rangle|b(s_{j'})\rangle$ and the time-dependent variants $O_L'$ and $O_H'$, which encode evolutions of different lengths for different $j'$ and are extensions of the time-dependent input model of Low and Wiebe (arXiv:1805.00675). The analysis assumes $H(t)$ and $L(t)$ are $C^1$-smooth and $b(t)$ is $C^2$-smooth, and it needs $L(t) \succeq 0$, which the shift $u(t) = e^{ct}v(t)$ of Eq. (4) always secures.

  A complexity statement, not a run. Theorem 2 gives $\widetilde{O}\!\left(\left(\frac{\lVert u_0\rVert + \lVert b\rVert_{L^1}}{\lVert u(T)\rVert}\right)^{2+2/p} \frac{\Gamma_p^{1+1/p}T^{1+1/p}}{\varepsilon^{1+2/p}}\right)$ queries to the input models of $H$ and $L$, $O\!\left(\frac{\lVert u_0\rVert + \lVert b\rVert_{L^1}}{\lVert u(T)\rVert}\right)$ queries to $O_{\mathrm{prep}}$ and $O_b$, $O(\log(\Gamma_1\lVert b\rVert_{C^2}T/\varepsilon))$ ancilla qubits and the same number of additional one-qubit gates. The paper reads its own bill: the $\Gamma_p^{1+1/p}T^{1+1/p}/\varepsilon^{1/p}$ part is the number of Trotter steps, the extra $1/\varepsilon$ is the truncation $K = O(\varepsilon^{-1})$, and the remaining state-norm factor comes from bounding the relative Trotter error. For time-independent $A$ and $b = 0$, Theorem 15 gives $\widetilde{O}\!\left(\Lambda_p^{1+1/p}\left(\frac{\lVert u_0\rVert}{\lVert u(T)\rVert}\right)^{2+1/p}\frac{T^{1+1/p}}{\varepsilon^{1+1/p}}\right)$, and Theorem 16 the inhomogeneous counterpart. No numerics are reported for any of it, and no device, simulator or software is named.

• Interaction-picture LCHS with the truncated Dyson series, for a complex absorbing potential

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

  The construction the paper builds for one named physical problem, and the one that carries its near-optimal claim. The complex absorbing potential method replaces the real potential by a complex one, so the Schrödinger equation becomes $i\partial_t u(r,t) = \left(-\frac{1}{2}\Delta_r + V_R(r,t) - iV_I(r)\right)u(r,t)$, with $-iV_I$ the damping potential, $V_I$ bounded and non-negative and usually time-independent. It is discussed for single-particle dynamics and the paper says it generalizes to multi-particle dynamics and to other boundary treatments such as the perfectly matched layer. The regime of interest is before the scattering wave leaves the region of interest, so that $\lVert u(T)\rVert^2$ is not too small, a condition also met if $u_0$ is a near-resonance state.

  The spatial variable is discretized on $N$ equidistant grid points with the Laplacian taken by the central difference formula, which puts the problem in the form this record's identity applies to: $H(t) = -\frac{1}{2}\Delta_r + V_R(t)$ is the ordinary Hamiltonian with $\lVert H(t)\rVert = O(N^2 + \max_t\lVert V_R(t)\rVert)$, and $L = V_I$ is time-independent and positive semidefinite. The point of the application is that $e^{-ikLt}$ is fast-forwardable — it can be performed at a cost independent of $k$, $t$ and $\lVert L\rVert$ — so the Hamiltonian simulation is done in the interaction picture with the truncated Dyson series method, which is what removes the overhead the cutoff $K$ would otherwise impose. The identity is then used in the form $\mathcal{T}e^{-\int_0^t A(s)\,ds} \approx \sum_j c_j\, e^{-iLk_jt}\, \mathcal{T}e^{-i\int_0^t H_I(s;k_j)\,ds}\, e^{iLk_jt}$ with $H_I(s;k) = e^{iLks}H(s)e^{-iLks}$, and combined by LCU; the derivative of $H_I$ still scales linearly in $K$, but the truncated Dyson cost depends on it only logarithmically. The Supplemental Materials assemble the oracles explicitly: $\mathrm{HAM}\text{-}T_{H_I,m} = (I \otimes \mathrm{SEL}_{L,m}')(I \otimes \mathrm{HAM}\text{-}T_{H,m})(I \otimes \mathrm{SEL}_{L,m})$ at $O(\log(M_H)\log(M))$ queries to $O_{V_I}$ and $O_{V_R}$, a select oracle $\mathrm{SEL}_W$ whose blocks satisfy $\lVert W_j - \mathcal{T}e^{-i\int_0^T H_I(s;k_j)\,ds}\rVert \le \varepsilon'$, and finally $\mathrm{SEL}_U = \mathrm{SEL}_L(T)\,\mathrm{SEL}_W\,\mathrm{SEL}_L(-T)$ as the select oracle of the LCU step. The error is split into a quadrature part and a simulation part and closed by choosing $M = \lVert V_I\rVert T/\varepsilon^2$ and $\varepsilon' = \varepsilon\lVert u(T)\rVert/(4\lVert c\rVert_1\lVert u_0\rVert)$.

  Oracles again, and no potential is ever written down: $O_{V_I} : |r\rangle|0\rangle \to |r\rangle|V_I(r)\rangle$, $O_{V_R} : |r\rangle|s\rangle|0\rangle \to |r\rangle|s\rangle|V_R(r,s)\rangle$, and the state preparation oracle $O_{\mathrm{prep}}$ for the initial condition. $V_R$, $V_I$, the grid size $N$ and the horizon $T$ stay symbols throughout, so no molecular scattering, photodissociation or nanotransport instance is set up even though those are the problems the section names as motivation.

  Theorem 3: $\widetilde{O}\!\left(\frac{\lVert u_0\rVert}{\lVert u(T)\rVert}\,T\,(\max_t\lVert H(t)\rVert)\,\mathrm{poly}\log\frac{\max_t\lVert V_R'(t)\rVert\,\lVert V_I\rVert}{\varepsilon}\right)$ queries to $O_{V_I}$ and $O_{V_R}$ and $O(\lVert u_0\rVert/\lVert u(T)\rVert)$ queries to $O_{\mathrm{prep}}$, with $\max_t\lVert H(t)\rVert = O(N^2 + \max_t\lVert V_R(t)\rVert)$, for an $\varepsilon$-approximation of $|u(T)\rangle$ with $\Omega(1)$ success probability and a flag indicating success. This is the paper's near-optimal-in-all-parameters result, and it is remarked to hold more generally whenever $H(t)$ is an arbitrary time-dependent Hamiltonian and $L$ is time-independent and fast-forwardable. Nothing is computed: no potential is instantiated, no grid size is chosen, and no device or simulator is named. The paper's own discussion records the price this construction pays, that interaction-picture Hamiltonian simulation may be difficult to implement, and says the more desirable fix would be a faster-decaying kernel — which is the record `lchs-improved-kernel`.

• Hybrid quantum-classical estimation of an observable

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

  The same identity read for a different output. When only an observable $u(t)^*Ou(t)$ is wanted rather than the solution state, the linear combination need not be coherent at all: the paper offers this variant to facilitate the computation of observables on early fault-tolerant quantum computers, and it never prepares $|u(T)\rangle$.

  Because the $U_j$ are unitary, the observable factorizes as $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$. Each correlation function is estimated on the quantum computer by the non-unitary Hadamard test, which differs from the ordinary Hadamard test only in replacing the controlled unitary by the controlled block encoding: multiplying $\widetilde U_{k'}(t)$, $U_O$ and $\widetilde U_k^\dagger(t)$ gives an $(\alpha_O,0)$-block-encoding of $\widetilde U_k^\dagger(t)O\widetilde U_{k'}(t)$, so the scaled expectation value is read from the probability of measuring $0$ on the ancilla, and amplitude estimation sharpens it. The sum is then done classically by Monte Carlo: for $j = 1,\dots,J$ sample the pair $(k,k')$ with probability $c_kc_{k'}/\lVert c\rVert_1^2$ — legitimate because every $c_j$ is a positive real and $\sum_{k,k'}c_kc_{k'} = \lVert c\rVert_1^2$ — estimate $\langle u_0|U_{k(j)}^\dagger(t)OU_{k'(j)}(t)|u_0\rangle$ by the Hadamard test, and return $\lVert c\rVert_1^2 X$ with $X$ the sample mean. Absent error, $\mathbb{E}X$ is exactly $u(t)^*Ou(t)$; the Hamiltonian simulation error is set to $\varepsilon_{\mathrm{HS}} = O(\varepsilon/\lVert O\rVert)$, and $\varepsilon_{\mathrm{HS}} = \varepsilon/(4\lVert O\rVert)$ suffices for a single pair.

  The state preparation oracle $O_{\mathrm{prep}}$ for $|u_0\rangle$, an $(\alpha_O,0)$-block-encoding $U_O$ of the observable with $\alpha_O \ge \lVert O\rVert$, and quantum circuits $\widetilde U_k(t)$ approximating $U_k(t)$ to error $\varepsilon_{\mathrm{HS}}$ for every $k$. No observable and no initial state is instantiated.

  Theorem 9 estimates $u(t)^*Ou(t)$ to precision $\varepsilon$ with probability at least $1-\delta$ using $O\!\left(\frac{\lVert O\rVert^2}{\varepsilon^2}\log\frac{1}{\delta}\right)$ samples, each circuit using $O\!\left(\frac{\alpha_O}{\varepsilon}\log\frac{\alpha_O}{\varepsilon}\log\frac{\lVert O\rVert\log(1/\delta)}{\delta\varepsilon}\right)$ queries to $O_{\mathrm{prep}}$, $U_O$ and $\widetilde U_k(t)$. The $1/\varepsilon^2$ is the price of the classical sampling and is the difference between this variant and the coherent one. No sampling experiment is run, on hardware or in simulation.

What it needs

Nothing below this — it bottoms out here.

Other ways to fill the same slot

Different approaches

• Warped phase transformation

  Introduce one extra variable and change to it, so that a linear ODE or PDE system becomes a system of Schrödinger equations in real time — which a simulator runs as it stands. The original solution lives in the auxiliary dimension and is recovered from it afterwards.

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
• Quantum algorithm for linear non-unitary dynamics with near-optimal dependence on all parameters↗Dong An, Andrew M. Childs, Lin Lin · 2023theory yes · simulation yes · hardware no