Eigenstate filtering inversion

What it fills

• 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.

When it applies

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.

Requires

These do not move the route along. The method needs each of them alongside its own work, and the cost of getting them is part of what the method costs.

• 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

Example

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

Cost, as the source states 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.

Implementations

• AQC(p)-seeded eigenstate filtering

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

  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.

  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.

  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

  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))$.

  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.

  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

  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.

  $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.

What it needs

1. Block-encode a matrix 4 methods

   Wrap an operator $A$ inside a larger unitary $U$ so that $A/α$ sits in $U$'s top-left block, giving every routine above it one uniform way to touch the matrix. The subnormalization $α$ and the ancilla count are outputs of this layer, not free parameters.

2. Matrix function 2 methods

   Given a block-encoding of $A$ and a target function $f$ bounded on $[-1,1]$, produce a circuit whose designated block is an $\varepsilon$-approximation of $f$ applied to the singular values (or eigenvalues) of $A$.

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.

• Amplify a success branch

  Take a routine whose output lands in the wanted subspace only with probability $a$, and raise that probability to near 1 using quadratically fewer repetitions than restarting the routine would need.

Other ways to fill the same slot

Different approaches

• HHL: eigenvalue inversion by phase estimation

  Prepare $|b>$, run phase estimation against $e^{-iAt}$ to write eigenvalue estimates into an ancilla register, apply a controlled rotation with amplitude proportional to $1/λ̃$, uncompute the estimation and post-select on the rotation ancilla. The success amplitude is about $1/κ$, so the procedure is amplified $O(κ)$ times.

• QSVT matrix inversion

  Block-encode $A$, apply the quantum singular value transformation with an odd polynomial approximating a scaled $1/x$ away from the origin, then amplify. Because it acts on singular values, $A$ need not be Hermitian or sparse — only block-encodable.

• Chebyshev LCU inversion

  Expand an approximation of $1/x$ in Chebyshev polynomials and implement that expansion directly through the quantum walk associated with a sparse $A$, rather than through Hamiltonian simulation. Phase estimation is never used, which is what removes the $\mathrm{poly}(1/\varepsilon)$ bottleneck.

• Discrete adiabatic inversion

  Encode the solution as the null eigenstate of a Hamiltonian path built from $A$ and $|b>$, follow that path with a sequence of qubitization walk operators to fixed precision, then finish with an eigenstate filter implemented as a linear combination of walk operators rather than by quantum signal processing. Costa and co-authors prove an adiabatic theorem for intrinsically discrete-time evolutions, which removes the residual $\log(κ)$ that continuous adiabatic treatments carried.

In the Atlas

No record in the Atlas covers this yet. The catalogue is circuits and primitives; this part of the literature is not in it.

Sources

• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems↗Lin Lin, Yu Tong · 2019theory yes · simulation yes · hardware no