Requires a block-encoding of the Hamiltonian, a reasonable lower bound on the spectral gap, and an initial state with non-trivial overlap with the target eigenstate. Stated for a $d$-sparse $A$ whose singular values lie in $[1/\kappa, 1]$ — the theorems are about singular values, not eigenvalues. Lin and Tong give two ways of supplying the starting state, one seeded by time-optimal adiabatic evolution and one that walks a Zeno path of intermediate Hamiltonians.

An access model for $A$ — sparse row/column entry oracles, or a block-encoding; a unitary preparing $\lvert b\rangle$; a known upper bound $\kappa$ on the condition number; the normalisation $\lVert A\rVert \le 1$; and a target state error $\varepsilon$.

1. Linear system Ax = b → Block-encodingBlock-encode a matrix

   The sparse-access oracles $O_{A,1}$, $O_{A,2}$ give a $(d, n+2, 0)$-block-encoding of $A$, the oracle $O_B$ gives a $(1,1,0)$-block-encoding of $Q_b = I - |b><b|$, and applying $O_B$, $O_{A,1}$, $O_{A,2}$ twice gives a $(d, n+4, 0)$-block-encoding $U_{H_1}$ of $H_1 = |0><1| \otimes AQ_b + |1><0| \otimes Q_bA$. The subnormalisation this hop returns is $\alpha = d$, and Theorem 3 counts the filter in $O((\alpha/\Delta)\log(1/\varepsilon))$ applications of the block-encoding — so this $\alpha$ is where the $d$ in the route's $O(d\kappa\log(1/\varepsilon))$ comes from. assumption: $A$ is $d$-sparse with singular values in $[1/\kappa, 1]$, so $\kappa$ is an upper bound on the condition number rather than the condition number itself. assumption: the block-encoding is taken to be exact — Theorem 1' is stated for an $(\alpha, m, 0)$-block-encoding, and Lin and Tong assume exactness for simplicity.

   assumption

   Open this step

2. Block-encoding → Block-encoding of f(A)Matrix function

   The filter is the degree-$2\ell$ polynomial $R_\ell(x;\Delta) = T_\ell(-1 + 2(x^2-\Delta^2)/(1-\Delta^2)) / T_\ell(-1 + 2(-\Delta^2)/(1-\Delta^2))$, and Lemma 2(i) shows it solves the minimax problem $\min_{p \in P_{2\ell}[x], p(0)=1} \max_{x \in D_\Delta} |p(x)|$ on $D_\Delta = [-1,-\Delta] \cup [\Delta,1]$ — the best compression ratio of the unwanted components among all polynomials of degree up to $2\ell$. approximation: the spectral projector $P_\lambda$ is replaced by $R_\ell$ applied to $\tilde H = (H - \lambda I)/(\alpha+|\lambda|)$, with $||R_\ell(\tilde H;\tilde\Delta) - P_\lambda|| \le 2e^{-\sqrt{2}\ell\tilde\Delta}$ by Lemma 2(ii). Because $R_\ell$ is even and $|R_\ell(x;\tilde\Delta)| \le 1$ on $[-1,1]$, Theorem 1' implements it by quantum signal processing, and Theorem 3 gives a $(1, m+2, \varepsilon)$-block-encoding of $P_\lambda$ from $O((\alpha/\Delta)\log(1/\varepsilon))$ applications of controlled-$U_H$ and $U_H^\dagger$. assumption: $\lambda$ is known exactly and separated from the rest of the spectrum by a gap at least $\Delta$, so that $0$ is separated from the rest of the spectrum of $\tilde H$ by $\tilde\Delta = \Delta/(\alpha+|\lambda|) \ge \Delta/(2\alpha)$.

   approximationassumption

   Open this step

3. Block-encoding of f(A) → Solution as a statefilter out the orthogonal part

   The linear system becomes an eigenvalue problem: the null space of $H_1 = |0><1| \otimes AQ_b + |1><0| \otimes Q_bA$, with $Q_b = I - |b><b|$, is spanned by $|0>|x>$ and $|1>|b>$, and the rest of the spectrum is separated from $0$ by a gap $1/\kappa$. Along the path $H(f) = (1-f)H_0 + fH_1$ with $H_0 = \sigma_x \otimes Q_b$ that gap is bounded below by $\Delta_*(f) = 1 - f + f/\kappa$, so time-optimal AQC(p) supplies $|\tilde x_0>$; one application of the filter removes $|\perp>$, and measuring the first qubit and obtaining $0$ leaves $|0>|x> + O(\varepsilon)$. approximation: AQC(p) is run only to constant precision, which is all $|\gamma_0| = \Omega(1)$ requires, so its $O(1/\varepsilon)$ runtime never enters — and $\gamma_1$ comes entirely from the error of the time-dependent Hamiltonian simulation, since AQC itself keeps the state orthogonal to $|1>|b>$. Because the filter approximates a projector, $||P|| = 1$ and its block-encoding needs subnormalisation only $O(1)$, so the success probability is already $\Omega(1)$ — whereas a block-encoding of $A^{-1}$ requires subnormalisation at least $\kappa$, hence worst-case success $\Omega(\kappa^{-2})$ and $O(\kappa)$ rounds of amplitude amplification. assumption: a lower bound on the gap along the path, that is an upper bound on $\kappa$, is known; $A$ is taken Hermitian positive definite here, the indefinite and non-Hermitian cases being handled by matrix dilation.

   approximationassumption

A flagged state $\varepsilon$-close in $\ell_2$ to $A^{-1}\lvert b\rangle/\lVert A^{-1}\lvert b\rangle\rVert$. It does not return $\lVert x\rVert$, any entry of $x$, or any classical functional of $x$ — those cost extra and are decided a layer above.

• Prepare an input state

  Map $|0\ldots0⟩$ to a state whose amplitudes are proportional to a specified vector $b$, to within $\varepsilon$. The cost is set by which description of $b$ you hold, not by the algorithm that consumes it.

  The filter is applied to a state $|\psi> = \gamma|\psi_\lambda> + |\perp>$ with $<\psi_\lambda|\perp> = 0$, supplied by an oracle $O_\psi$; the block-encoding of $P_\lambda$ succeeds with probability at least $\gamma^2$, so oracle and filter are run on average $O(1/\gamma^2)$ times, and amplitude amplification would only reduce that to $O(1/\gamma)$. For the linear system the right-hand side enters through $O_B|0> = |b>$: the Zeno route starts from $|x(0)> = |b>$ itself, and the AQC route runs AQC(p) to constant precision to obtain $|\tilde x_0> = \gamma_0|0>|x> + \gamma_1|1>|b> + |\perp>$. assumption: the starting state has non-trivial overlap with the target eigenstate, $\gamma > 0$ — and in the QLSP application $|\gamma_0| = \Omega(1)$ is guaranteed, which is what turns the $O(1/\gamma^2)$ repetition into a constant and makes amplitude amplification unnecessary.

  assumption

Lin and Tong report one run, and it is classical: §4.3 with Fig. 2 presents numerical results obtained on a classical computer, testing the AQC-seeded variant. The test matrix $A$ is a randomly generated symmetric positive definite tridiagonal matrix $B$ added to a scalar multiple of the identity and then rescaled so that the eigenvalues of $A$ lie in $[-1,1]$. The off-diagonal entries of $B$ are drawn uniformly from $[-1,0]$, each diagonal entry is the negative of the sum of the two adjacent entries in its row, and the $(0,0)$ and $(N-1,N-1)$ entries are made slightly larger so that $B$ is positive definite; the smallest eigenvalue of $B$ therefore sits very close to $0$, and the authors chose the construction so that the condition number can be estimated with reasonable accuracy without computing eigenvalues. $|b>$ is drawn from the uniform distribution on the unit sphere. The initial state is prepared by running AQC(p) for $T = 0.2\kappa$ with $p = 1.5$, which reaches a fidelity of about $0.6$, and the filter $R_\ell(x; 1/(d\kappa))$ of degree $2\ell$ is then applied. The reported outcome is the fidelity $\eta = |<x|\tilde{x}>|$ of the resulting state: at $\kappa = 30$, $60$ and $90$ alike, $\eta$ converges to $1$ exponentially as $\ell$ grows, plotted as $\log_{10}(1-\eta^2)$ falling steadily over degrees running to a few hundred, and the smallest $\ell$ reaching a fixed fidelity — the two levels shown are $\eta^2 = 1-10^{-3}$ and $\eta^2 = 1-10^{-4}$ — grows linearly in $\kappa$. Two limits of this run should be stated plainly rather than glossed. First, the matrix dimension is never given: $N$ appears only as a symbol naming the last row and column of $B$, and no numerical value for it is stated in §4.3, in the caption of Fig. 2, or anywhere else in the paper, so none is quoted here. Second, the simulation applies the filtering polynomial to the state directly rather than compiling it, so no block-encoding, no phase sequence, no ancilla measurement and no sparse-access oracle is exercised. What Fig. 2 validates is the complexity estimate — how the filter degree has to grow with $\kappa$ and with the target fidelity — and not a circuit.

Classical simulation · Section 4.3, Figure 2 of arXiv:1910.14596

given  a block-encoding of the Hamiltonian -- for a linear system, the
       Hamiltonian built from A and |b>, whose null eigenstate is |x> --
       and a reasonable lower bound on the spectral gap

supply an initial state with non-trivial overlap with the target
    eigenstate
    # Lin and Tong give two ways of supplying it:
    #   (a) seeded by time-optimal adiabatic evolution
    #   (b) walking a Zeno path of intermediate Hamiltonians

construct the minimax-optimal polynomial that is 1 at a target
    eigenvalue and uniformly small outside a spectral gap
    # no degree is stated for it on this record, and no construction
apply it through quantum signal processing

# one application of the filter solves it, once a starting state with
# non-trivial overlap is supplied
# Lin and Tong's abstract states that neither algorithm uses phase
# estimation or amplitude amplification

# near-optimal O~(d kappa log(1/epsilon)) query complexity for a
# d-sparse matrix, for both variants, with kappa the condition number
# and epsilon the desired precision

# stated for a d-sparse A whose singular values lie in [1/kappa, 1], and
# the theorems are about singular values, not eigenvalues -- the filter
# is nonetheless described as being 1 at a target eigenvalue, and this
# listing leaves that where the record leaves it

Lin and Tong: both QLSP variants achieve the near-optimal $\tilde{O}(d \kappa \log(1/\varepsilon))$ query complexity for a $d$-sparse matrix, where $\kappa$ is the condition number and $\varepsilon$ the desired precision. Their abstract states that neither algorithm uses phase estimation or amplitude amplification.

• AQC(p)-seeded eigenstate filtering

  • Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems

    Lin Lin, Yu Tong · 2019

  About

  The QLSP solver of §4. $A$ is $d$-sparse with singular values in $[1/\kappa, 1]$, reached through the sparse-access oracles $O_{A,1}$ and $O_{A,2}$, and $|b>$ through an oracle $O_B$; the task is to produce $|x> \propto A^{-1}|b>$ with fidelity $1-\varepsilon$. What names this variant is how it supplies the starting state for the filter: time-optimal adiabatic evolution, run only to constant precision.

  Methods

  None found yet.

  Data

  Everything enters through oracles: $O_{A,1}$ and $O_{A,2}$ for sparse access to $A$, and $O_B$ for $|b>$. The only concrete instances put through the algorithm are the random symmetric positive definite tridiagonal matrices of §4.3, whose construction is described in the example.

  Code

  None found yet.

  Results

  Theorem 8: fidelity $1-\varepsilon$ with success probability $\Omega(1)$, flagged by an ancilla measurement outcome, using $O(d\kappa(\log\log(d\kappa)/\log(d\kappa) + \log(1/\varepsilon)))$ queries to $O_{A,1}$, $O_{A,2}$ and $O_B$; $O(d\kappa(n\log(1/\varepsilon) + (n + \log(d\kappa))\log\log(d\kappa)/\log(d\kappa)))$ other primitive gates; and $O(n + \log(d\kappa))$ qubits. Of those qubits only $O(\log(d\kappa))$ come from anywhere other than the block-encoding of $A$, and they are mainly the cost of the time-dependent Hamiltonian simulation. When the oracles have $\mathrm{poly}(n)$ gate complexity the total gate complexity, and hence the runtime, is $\tilde{O}(\mathrm{poly}(n) d\kappa \log(1/\varepsilon))$. This is the variant the numerical test of §4.3 exercises, and that test ran on a classical computer; no simulator package and no hardware is named.

• Zeno-path eigenstate filtering

  • Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems

    Lin Lin, Yu Tong · 2019

  About

  The QLSP solver of §5: same input model and same target as the AQC-seeded variant, built so that no time-dependent Hamiltonian simulation is needed at all. Rather than evolving continuously from the null eigenstate of $H_0$ to the null eigenstate of $H_1$, it traverses the eigenpath by a series of approximate projections — the quantum Zeno variant the authors take from Boixo, Knill and Somma. Performing each projection by eigenstate filtering rather than by quantum phase estimation or phase randomization is what turns the error dependence from $O(1/\varepsilon)$ into $O(\log(1/\varepsilon))$.

  Methods

  The path is cut at $f_j = f(j/M)$ with the schedule $f(s) = (1-\kappa^{-s})/(1-\kappa^{-1})$, which splits $[0,1]$ into $M$ segments of equal $L^*$-length; without a schedule the algorithm would carry an unfavourable square dependence on the minimum spectral gap along the eigenpath. Step 1 fixes $M = \lceil 4\log^2(\kappa)/(1-1/\kappa)^2 \rceil$ and $\varepsilon_P = 1/(162M^2)$. Each $H(f)$ is given a $(1-f+fd, n+6, 0)$-block-encoding $U_H(f)$, and eigenstate filtering to precision $\varepsilon_P$ turns it into a $(1, n+8, \varepsilon_P)$-block-encoding of the projector $P_0(f) = |x(f)><x(f)|$. Starting from $|\tilde{x}(0)> = |b>$, each turn applies that block-encoding and measures the $n+8$ ancilla qubits: all zeros advances the walk to $|\tilde{x}(f_j)>$, and any other outcome aborts and restarts from $|b>$. The final turn runs the filter to accuracy $\varepsilon/4$ instead of $\varepsilon_P$, and that is deliberate — the earlier turns' filtering errors affect only the success probability, while the last turn alone controls the fidelity of the output.

  Data

  None found yet.

  Code

  None found yet.

  Results

  Theorem 11: fidelity $1-\varepsilon$ with success probability $\Omega(1)$, using $O(d\kappa(\log(\kappa)\log\log(\kappa) + \log(1/\varepsilon)))$ queries to $O_{A,1}$, $O_{A,2}$ and $O_B$, $O(nd\kappa(\log(\kappa)\log\log(\kappa) + \log(1/\varepsilon)))$ other primitive gates, and $O(n)$ qubits. Only $O(1)$ of those are extra ancillas, against $O(\log(d\kappa))$ for the AQC-seeded variant, precisely because nothing here does time-dependent Hamiltonian simulation. Assuming error-free projections the success probability is bounded below by $1/4$, and with $\varepsilon_P$ chosen as in Step 1 it is still bounded below by a constant. The authors say plainly that the constant factors they prove, particularly those in the success-probability estimate for this solver, are rather loose, and that tighter estimates would help an actual implementation. They also note, without carrying it out, that using fixed-point amplitude amplification to move from $|x(f_j)>$ to $|x(f_{j+1})>$ would shave a further $\log(\kappa)$ factor up to $\log\log$ terms. No numerics are reported for this variant: the run in Fig. 2 is the AQC-seeded one.

• Chebyshev LCU compilation of the filter

  • Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems

    Lin Lin, Yu Tong · 2019

  About

  Named but not built, and this entry exists to record exactly that. Both solvers above compile the filter through quantum signal processing; a remark in §3 says the filtering procedure can also be implemented by alternative methods such as LCU, and gives the two numbers that would govern the swap. Nobody has run it, in this paper or in anything cited from it here.

  Methods

  $R_\ell(\cdot; \tilde{\Delta})$ expands exactly into the first $2\ell+1$ Chebyshev polynomials, and since $|R_\ell(x; \tilde{\Delta})| \le 1$ the $1$-norm of the expansion coefficients is bounded above by $2\ell+2$. The price of the swap is $O(\log \ell)$ additional qubits for the LCU expansion. Nothing beyond those two statements is given: no circuit, no query count, no gate count and no run.

  Data

  None found yet.

  Code

  None found yet.

  Results

  None found yet.