Applies to sparse matrices only: it uses the entry oracle $P_A$ directly. The normalisation $‖A‖ = 1$, a known $\kappa$ and $\mathrm{poly}(\log N)$-time preparation of $|b>$ are assumed as elsewhere in this family. Childs, Kothari and Somma state that their Fourier route and this Chebyshev route are incomparable — the Fourier approach is more general and slightly better in the sparsity $d$, the Chebyshev approach is more efficient in $\kappa$ and $\varepsilon$ but applies only to sparse 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 → Solution as a statecombine Chebyshev walks by LCU

   $A^{-1}$ is applied as a linear combination of unitaries: with $M=\sum_i\alpha_i T_i$ and $\alpha_i>0$, $U=\sum_i|i\rangle\langle i|\otimes U_i$ and $V|0^m\rangle=\alpha^{-1/2}\sum_i\sqrt{\alpha_i}\,|i\rangle$ with $\alpha=\sum_i\alpha_i$, the operator $V^\dagger U V$ sends $|0^r\rangle|b\rangle$ to $\frac{1}{\alpha}|0^r\rangle M|b\rangle+|\Xi^\perp\rangle$, so the all-zeros branch carries $M|b\rangle$. The building blocks $T_i$ are the Chebyshev polynomials $T_n(A/d)$, implemented by steps of the sparse-access quantum walk, so the entry oracle $P_A$ is used directly and neither $e^{-iAt}$ nor phase estimation appears anywhere in the construction. approximation: A combination that is $\varepsilon$-close to $f$ on the spectrum yields a state $4\varepsilon$-close to $f(A)|b\rangle/\|f(A)|b\rangle\|$, provided $|f(x)|\ge1$ there — Corollary 10, applied to $f(x)=1/x$ on $D_\kappa=[-1,-1/\kappa]\cup[1/\kappa,1]$. assumption: $A$ is Hermitian and $d$-sparse with $\|A\|=1$ and known condition number $\kappa$, reached through the entry oracle $P_A$ of Problem 1.

   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.

  This route consumes its right-hand side as a procedure $P_B$ with $P_B|0^s\rangle=|b\rangle$, where $|b\rangle\propto\sum_i b_i|i\rangle$, and Theorem 4 charges $O(\kappa\log(d\kappa/\varepsilon))$ uses of it. assumption: $P_B$ prepares $|b\rangle$ in time $O(\mathrm{poly}(\log N))$ — part of Problem 1's definition of the QLSP, not something the algorithm establishes. assumption: Multiple copies of $|b\rangle$ can be created, which is the authors' stated reason the construction needs no oblivious amplitude amplification — a tool that would not work anyway when $M$ is far from unitary.

  assumption

• Matrix function

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

  The object to be applied is $H^{-1}$ for $H:=A/d$, and $1/x$ is first tamed to $f(x)=\bigl(1-(1-x^2)^b\bigr)/x$, which is bounded at the origin. approximation: $f$ is $\varepsilon$-close to $1/x$ on $D_{\kappa d}=[-1,-1/(\kappa d)]\cup[1/(\kappa d),1]$ for any integer $b\ge(\kappa d)^2\log(\kappa d/\varepsilon)$ (Lemma 17). Being a polynomial of degree $2b-1$, $f$ is then represented exactly by odd Chebyshev polynomials $T_{2j+1}$, $j\le b-1$, with coefficients $4(-1)^j\,2^{-2b}\sum_{i=j+1}^{b}\binom{2b}{b+i}$ (Lemma 18). approximation: The series is truncated at $j_0=\sqrt{b\log(4b/\varepsilon)}$; each discarded bracket is the probability of more than $b+j$ heads in $2b$ fair flips and is bounded by $e^{-j^2/b}$, so the surviving degree is $O(j_0)=O(d\kappa\log(d\kappa/\varepsilon))$ (Lemma 19). Every surviving term is applied by powers of the quantum walk $W=S(2TT^\dagger-1)$, for which $W^nT|\psi\rangle=T\,T_n(H)|\psi\rangle+|\perp_\psi\rangle$, at $O(n)$ queries to $P_A$. assumption: $\|H\|\le1$ because $A$ is $d$-sparse with $\|A\|_{\max}\le1$, and the expansion need only be correct on $D_{\kappa d}$ because the eigenvalues of $A$ are known to lie in $D_\kappa$.

  approximationassumption

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

  Measuring the flag register of $V^\dagger U V\,|0^r\rangle|b\rangle=\frac{1}{\alpha}|0^r\rangle M|b\rangle+|\Xi^\perp\rangle$ returns $M|b\rangle/\|M|b\rangle\|$ only with probability $(\|M|b\rangle\|/\alpha)^2$, so the branch is amplified rather than merely retried. Amplitude amplification produces it after $O(\alpha/\|M|b\rangle\|)$ uses of $V^\dagger U V$ and $P_B$ in expectation, which is $O(\alpha)$ here because $|f(x)|\ge1$ on $D_\kappa$ forces $\|f(A)|b\rangle\|\ge1$; with $\alpha\le 4j_0/d$ that is $O(\kappa\log(d\kappa/\varepsilon))$ uses of $P_B$. assumption: A reflection about the starting state $|0^r\rangle|b\rangle$ is available; it is built as $P_B(1-2|0^{r+s}\rangle\langle0^{r+s}|)P_B^\dagger$ from two uses of $P_B$, one performed in reverse. assumption: The expected cost needs no estimate of $\|M|b\rangle\|$, but a worst-case guarantee needs an upper bound on the success probability — $\alpha$ is known, so running ten times the expected running time gives the $O(\alpha)$ worst case.

  assumption

Childs, Kothari and Somma's paper is a complexity result and carries no numerical section; a full-text read (2026-08-12) confirmed it, and the register row moved to a full-text basis with that reading. The numerics on the neighbouring `eigenstate-filtering-inversion` record are Lin and Tong's and test a different construction.

given  a sparse A only -- the entry oracle P_A is used directly -- with
       the normalisation ||A|| = 1, kappa known, and |b> preparable in
       poly(log N) time, as elsewhere in this family

prepare |b>

expand an approximation of 1/x in Chebyshev polynomials
    # the record states no truncation degree for that expansion
implement that expansion directly through the quantum walk associated
    with the sparse A
    # rather than through Hamiltonian simulation
    # phase estimation is never used, which is what removes the
    # poly(1/epsilon) bottleneck

amplify

# Theorem 4: O(d kappa^2 log^2(d kappa/epsilon)) queries to P_A and
# O(kappa log(d kappa/epsilon)) uses of P_B, where d is the sparsity,
# kappa the condition number and epsilon the state-vector error

# that kappa^2 is the pre-amplification figure. The same paper's Theorem
# 5 brings the kappa-dependence down to near-linear, but it does so by
# reintroducing a low-precision (gapped) phase estimation to bucket the
# spectrum, and it applies to either the Fourier or the Chebyshev route.
# Describing that near-linear result as phase-estimation-free is
# incorrect, which is why it is not the route written above.

# the same authors' Fourier route is not displaced by this one: they
# state that the two are incomparable -- the Fourier approach is more
# general and slightly better in the sparsity d, the Chebyshev approach
# is more efficient in kappa and epsilon but applies only to sparse
# Hamiltonians

Childs, Kothari and Somma (Theorem 4): $O(d \kappa² \log²(d \kappa/\varepsilon))$ queries to $P_A$ and $O(\kappa \log(d \kappa/\varepsilon))$ uses of $P_B$, where $d$ is the sparsity, $\kappa$ the condition number and $\varepsilon$ the state-vector error.

The $\kappa²$ here is the pre-amplification figure. The same paper's Theorem 5 brings the $\kappa$-dependence down to near-linear, but it does so by reintroducing a low-precision ('gapped') phase estimation to bucket the spectrum, and it applies to either the Fourier or the Chebyshev route. Describing that near-linear result as phase-estimation-free is incorrect.

• Chebyshev-series linear combination of unitaries (section 4)

  • Quantum algorithm for systems of linear equations with exponentially improved dependence on precision

    Andrew M. Childs, Robin Kothari, Rolando D. Somma · 2015

  About

  The paper's second of two approaches, and the one this record is named for: it "uses a Chebyshev expansion to implement $A^{-1}$ without appealing directly to Hamiltonian simulation", using the oracle for the entries of $A$ directly and achieving better dependence on $\varepsilon$ than the first. The problem it is built for is Problem 1, the QLSP: given an $N \times N$ Hermitian $A$ with known condition number $\kappa$, $\lVert A\rVert = 1$ and at most $d$ nonzero entries in any row or column, given a procedure $P_A$ computing the entries of $A$ and a procedure $P_B$ preparing $|b\rangle$ in time $O(\mathrm{poly}(\log N))$, output a state $|\tilde{x}\rangle$ with $\lVert |\tilde{x}\rangle - |x\rangle\rVert \le \varepsilon$, succeeding with probability at least $1/2$ and with a flag indicating success.

  Methods

  The route is an instance of the paper's own linear-combination-of-unitaries framework (section 2): for $M = \sum_i \alpha_i T_i$ with $\alpha_i > 0$, $U := \sum_i |i\rangle\langle i| \otimes U_i$ and $V|0^m\rangle := \alpha^{-1/2}\sum_i \sqrt{\alpha_i}\,|i\rangle$ with $\alpha := \sum_i \alpha_i$, the operator $W = V^\dagger U V$ satisfies $W|0^r\rangle|b\rangle = \frac{1}{\alpha}|0^r\rangle M|b\rangle + |\Xi^\perp\rangle$ (Lemmas 6 and 7), and Corollary 10 converts a combination that is $\varepsilon$-close on the spectrum into a state $4\varepsilon$-close to $f(A)|b\rangle/\lVert f(A)|b\rangle\rVert$. The building blocks are $T_n(H)$ for $H := A/d$. The function is tamed first: $f(x) = (1-(1-x^2)^b)/x$ is $\varepsilon$-close to $1/x$ on $D_{\kappa d}$ for any integer $b \ge (\kappa d)^2\log(\kappa d/\varepsilon)$, because on that domain the numerator differs most from $1$ at $x = 1/(\kappa d)$, where $(1 - 1/(\kappa d)^2)^b \le e^{-b/(\kappa d)^2} \le \varepsilon/(\kappa d)$ (Lemma 17). Being a polynomial of degree $2b-1$, $f$ is then represented exactly rather than approximately by odd Chebyshev polynomials, $f(x) = 4\sum_{j=0}^{b-1}(-1)^j\bigl[2^{-2b}\sum_{i=j+1}^{b}\binom{2b}{b+i}\bigr]T_{2j+1}(x)$, proved by substituting $x = \cos\theta$ and checking that the coefficients of $\cos(2r\theta)$ agree on both sides for every $r \in \{0,1,\dots,b\}$ (Lemma 18). The series is then truncated at $j_0 = \sqrt{b\log(4b/\varepsilon)}$: each bracket is the probability of seeing more than $b+j$ heads on flipping $2b$ fair coins, the Chernoff bound puts it below $e^{-j^2/b}$, and since $|T_n(x)| \le 1$ on $[-1,1]$ the discarded tail is at most $4be^{-j_0^2/b} = \varepsilon$ (Lemma 19). The surviving degree is $O(j_0) = O(d\kappa\log(d\kappa/\varepsilon))$. What is implemented is $\frac{1}{d}g(H)$ rather than $g$ itself, since $\lVert H^{-1} - g(H)\rVert \le \varepsilon$ gives $\lVert A^{-1} - \frac{1}{d}g(H)\rVert \le \varepsilon/d \le \varepsilon$. Its coefficient sum is $\alpha = \frac{4}{d}\sum_{j=0}^{j_0}\bigl[2^{-2b}\sum_{i=j+1}^{b}\binom{2b}{b+i}\bigr] \le 4j_0/d$, because every bracket is a probability and so is at most $1$, and it is this $\alpha$ that the amplitude amplification of Corollary 10 is charged against.

  Data

  No dataset. The inputs are the two black-box procedures of Problem 1. $P_A$ performs $|j,\ell\rangle \mapsto |j,\nu(j,\ell)\rangle$, where $\nu:[N]\times[d]\to[N]$ computes the row index of the $\ell$th nonzero entry of the $j$th column, and also $|j,k,z\rangle \mapsto |j,k,z\oplus A_{jk}\rangle$, with the entries of $A$ assumed representable exactly, or to sufficiently high precision that any error can be neglected. $P_B$ prepares $|b\rangle$ in time $O(\mathrm{poly}(\log N))$. The in-place form of the first map is an assumption the paper flags rather than hides: it holds when both $(j,\ell)\mapsto\nu(j,\ell)$ and its reverse are efficiently computable, costs an extra factor of $\log d$ by binary search when $\nu$ returns the nonzero entries in ascending order, and costs a further $O(\sqrt{d})$ using Grover's algorithm in the worst case where the entries are unordered. No particular matrix $A$ and no particular vector $b$ is named anywhere.

  Code

  None found yet.

  Results

  The construction is carried as far as counted complexity and no further. Theorem 4 gives $O(d\kappa^2\log^2(d\kappa/\varepsilon))$ queries to $P_A$ — the product $O(\alpha j_0)$ of the amplification rounds and the highest Chebyshev order used — together with $O(\kappa\log(d\kappa/\varepsilon))$ uses of $P_B$ and gate complexity $O(d\kappa^2\log^2(d\kappa/\varepsilon)(\log N + \log^{2.5}(d\kappa/\varepsilon)))$, so the gate cost exceeds the query cost only by the factor $O(\log N + \log^{2.5}(\kappa d/\varepsilon))$ that one walk step carries; $V$ creates a state in a space of dimension $j_0$ with $O(j_0)$ two-qubit gates, which is less than the cost of $U$ and is neglected. There is no run. The paper reports no numerical experiment, names no hardware and no simulator, and contains no figure and no table; the one place it computes anything numerically is a remark inside the other route's error analysis, recorded under the Fourier entry. A reader sent to this paper looking for a worked instance of this algorithm will not find one.

• Fourier-series linear combination of unitaries (section 3)

  • Quantum algorithm for systems of linear equations with exponentially improved dependence on precision

    Andrew M. Childs, Robin Kothari, Rolando D. Somma · 2015

  About

  The paper's first approach, and it is presented as a separate algorithm rather than a variant of the second. It uses the same section-2 framework but takes $e^{-iAt}$ as its building blocks instead of $T_n(A/d)$, so Hamiltonian simulation is used as a black box; for sparse $A$ the paper substitutes the method of Berry, Childs and Kothari. The two routes are stated to be incomparable: "The Fourier approach is more general, applying whenever the Hamiltonian $A$ can be efficiently simulated (even if it is not necessarily sparse), and has slightly better dependence on $d$. The Chebyshev approach is more efficient in its dependence on $\kappa$ and $\varepsilon$, but applies only to sparse Hamiltonians." It is recorded here because it is the sibling this method is defined against, and because the paper reports that it has already been picked up: an algorithm for estimating hitting times of Markov chains "uses the framework laid out in this paper (in Section 2) and closely follows our first approach, which we call the Fourier approach".

  Methods

  The same Lemma 7 and Corollary 10, with the $T_i$ taken to be $e^{-iAt_i}$. The representation starts from $1/x = \int_0^\infty dy\, f(xy)$ for $x \ne 0$, which holds for any odd $f:\mathbb{R}\to\mathbb{R}$ with $\int_0^\infty dy\, f(y) = 1$; the paper chooses $f(y) = ye^{-y^2/2}$ so that both the function and its Fourier transform decay rapidly, and writes $f(y) = \frac{i}{\sqrt{2\pi}}\int_{-\infty}^{\infty} dz\, ze^{-z^2/2}e^{-iyz}$. The double integral is cut off at $y_J = \Theta(\kappa\sqrt{\log(\kappa/\varepsilon)})$ and $z_K = \Theta(\sqrt{\log(\kappa/\varepsilon)})$, using $|x| \ge 1/\kappa$ and a Gaussian tail bound from Abramowitz and Stegun, and then discretised into $h(x) = \frac{i}{\sqrt{2\pi}}\Delta_y\sum_{j=0}^{J-1}\sum_{k=-K}^{K}\Delta_z z_k e^{-z_k^2/2}e^{-ixy_jz_k}$ with $y_j := j\Delta_y$, $z_k := k\Delta_z$, $J = \Theta((\kappa/\varepsilon)\log(\kappa/\varepsilon))$, $K = \Theta(\kappa\log(\kappa/\varepsilon))$, $\Delta_y = \Theta(\varepsilon/\sqrt{\log(\kappa/\varepsilon)})$ and $\Delta_z = \Theta((\kappa\sqrt{\log(\kappa/\varepsilon)})^{-1})$, which is $\varepsilon$-close to $1/x$ on $D_\kappa$ (Lemma 11). The discretisation error can be driven arbitrarily low for free, because the query complexity that comes out of Corollary 10 does not depend on the number of terms in the linear combination. The coefficient sum is $\alpha = \Theta(y_J) = O(\kappa\sqrt{\log(\kappa/\varepsilon)})$, the longest evolution time appearing is $t = O(y_Jz_K) = O(\kappa\log(\kappa/\varepsilon))$, and since simulation is invoked $\Theta(\alpha)$ times each invocation must run to error $\varepsilon' = O(\varepsilon/\alpha)$. The controlled operation $U = i\sum_{j=0}^{J-1}\sum_{k=-K}^{K}|j,k\rangle\langle j,k|\otimes \mathrm{sgn}(k)e^{-iAy_jz_k}$ is built as powers of the single unitary $Y = e^{-iA\Delta_y\Delta_z}$, the largest being $Y^{JK}$ with $JK = (\kappa^2/\varepsilon)\log^2(\kappa/\varepsilon)$, so only the $O(\log JK)$ repeated squarings are ever formed. $V$ is $O(\log J)$ Hadamard gates for the uniform superposition over $j$ and $O(K)$ further gates for the superposition over $k$, and its cost is dominated by that of $U$. One wrinkle is recorded rather than passed over: $\Delta_y\Delta_z = \Theta(\varepsilon/\kappa)$ is so short an evolution time that the quoted simulation gate bound does not explicitly cover it, so the paper patches the bound by replacing its leading $d\lVert A\rVert_{\max}t$ with $d\lVert A\rVert_{\max}t + 1$ and treating every logarithm as the maximum of its original expression and $1$.

  Data

  No dataset. The same Problem 1 oracles, but reached differently: this route needs only the ability to implement $\exp(-iAt)$, so $P_A$ enters through whichever Hamiltonian simulation algorithm is chosen, and the query figures quoted are those of the sparse-access method of Berry, Childs and Kothari. No matrix and no right-hand side is instantiated.

  Code

  None found yet.

  Results

  Counted only, again. Theorem 3 gives $O(\kappa\sqrt{\log(\kappa/\varepsilon)})$ uses of a Hamiltonian simulation algorithm approximating $\exp(-iAt)$ for $t = O(\kappa\log(\kappa/\varepsilon))$ with precision $O(\varepsilon/(\kappa\sqrt{\log(\kappa/\varepsilon)}))$; with the best known such algorithm that is $O(d\kappa^2\log^{2.5}(\kappa/\varepsilon))$ queries to $P_A$, $O(\kappa\sqrt{\log(\kappa/\varepsilon)})$ uses of $P_B$, and gate complexity $O(d\kappa^2\log^{2.5}(\kappa/\varepsilon)(\log N + \log^{2.5}(\kappa/\varepsilon)))$. This entry is also where the paper's only computed quantity lives, and it is worth naming precisely so that nobody mistakes it for a run. In the error analysis of section 3.1 the bound $\lvert 1/(1-e^{-ix}) - 1/(ix)\rvert < 1$ for all $x \in [-1,1]$ is asserted "as is easily verified by plotting the left-hand side". That is a plot of a scalar function of one real variable, used to close one inequality in a proof. It fixes no matrix, no dimension $N$, no sparsity $d$, no condition number and no error target, it produces no state and no measured quantity, and it is not a run of this algorithm or of the Chebyshev one.

• Sparse-access quantum walk realising the Chebyshev polynomials (section 4.1)

  • Quantum algorithm for systems of linear equations with exponentially improved dependence on precision

    Andrew M. Childs, Robin Kothari, Rolando D. Somma · 2015

  About

  The primitive the Chebyshev route is built on, and not this paper's invention — the walk "has previously been applied to Hamiltonian simulation" and the paper says so. What section 4.1 supplies is the property the expansion consumes: powers of the walk realise Chebyshev polynomials of $H = A/d$ in a block of a unitary, which is exactly the form Corollary 10 requires of its $T_i$. It is recorded separately because it is the only way the Chebyshev route touches $A$ at all, so the route's claim to avoid Hamiltonian simulation and phase estimation stands or falls with it.

  Methods

  For a $d$-sparse $N \times N$ Hamiltonian $A$ with $\lVert A\rVert_{\max} \le 1$, define for each $j \in [N]$ the state $|\psi_j\rangle := |j\rangle \otimes \frac{1}{\sqrt{d}}\sum_{k \in [N]: A_{jk}\ne 0}\bigl(\sqrt{A^*_{jk}}\,|k\rangle + \sqrt{1-|A_{jk}|}\,|k+N\rangle\bigr)$ in $\mathbb{C}^{2N}\otimes\mathbb{C}^{2N}$; the square root is ambiguous when $A_{jk}$ is complex and the results hold for any consistent choice of it. The oracle is assumed to return exactly $d$ nonzero entries for a given $j$, which is without loss of generality because it can be modified to treat some zero entries as nonzero — on those values of $k$ it returns the value $0$, and they still contribute through the $\sqrt{1-|A_{jk}|}\,|k+N\rangle$ term. With the isometry $T := \sum_{j\in[N]}|\psi_j\rangle\langle j|$ and the swap $S|j,k\rangle = |k,j\rangle$ on $[2N]$, the walk operator is $W := S(2TT^\dagger - 1)$, implementable with $O(1)$ queries to $P_A$. From $T^\dagger T = 1$ and $T^\dagger S T = H$, Lemma 15 shows that within the invariant subspace $\mathrm{span}\{T|\lambda\rangle, ST|\lambda\rangle\}$ of an eigenvector $|\lambda\rangle$ of $H$ with $|\lambda|<1$, $W$ has the block form with $\lambda$ on the diagonal and $\mp\sqrt{1-\lambda^2}$ off it, while $WT|\lambda\rangle = \lambda T|\lambda\rangle$ when $|\lambda| = 1$. Lemma 16 raises that block to the $n$th power by induction on the identities $T_{n+1}(\lambda) = \lambda T_n(\lambda) - (1-\lambda^2)U_{n-1}(\lambda)$ and $U_n(\lambda) = T_n(\lambda) + \lambda U_{n-1}(\lambda)$, giving $T_n(\lambda)$ on the diagonal and $\pm\sqrt{1-\lambda^2}U_{n-1}(\lambda)$ off it, with $U_n$ the Chebyshev polynomial of the second kind. Hence $W^nT|\lambda\rangle = T_n(\lambda)T|\lambda\rangle + \sqrt{1-\lambda^2}U_{n-1}(\lambda)|\perp_\lambda\rangle$, and since the eigenvectors of $H$ span $\mathbb{C}^N$ and the pairs $\{T|\lambda\rangle,|\perp_\lambda\rangle\}$ are invariant, $W^nT|\psi\rangle = T\,T_n(H)|\psi\rangle + |\perp_\psi\rangle$ for every $|\psi\rangle$. Given a unitary circuit implementing the isometry, that is, mapping $|0^m\rangle|\psi\rangle$ to $T|\psi\rangle$ with $m = \lceil\log 2N\rceil + 1$, applying it, then $W^n$, then its inverse implements $|0^m\rangle|\psi\rangle \mapsto |0^m\rangle T_n(H)|\psi\rangle + |\Phi^\perp\rangle$ with $\Pi|\Phi^\perp\rangle = 0$ for $\Pi := |0^m\rangle\langle 0^m|\otimes 1$.

  Data

  None found yet.

  Code

  None found yet.

  Results

  Section 4.1 ends at a query count and section 4.3 at a gate count. Because $W$ and $T$ each cost $O(1)$ queries to $P_A$, the map producing $T_n(H)$ costs $O(n)$ queries, which is what makes the Chebyshev route's query complexity the product of its amplification rounds and its highest surviving degree. A single step of the walk can be performed up to error $\varepsilon'$ with gate complexity $O(\log N + \log^{2.5}(\kappa d/\varepsilon'))$. Nothing here is executed: the walk is specified, counted and proved correct, and no instance of $A$, no simulator and no device appears.