Requires a projected unitary encoding of $A$ whose non-zero singular values are all at least $δ$ (so $δ = 1/κ$ after normalisation), with $0 < ε ≤ δ ≤ 1/2$. What the transform produces is $(δ/2)·A^+$, the Moore-Penrose pseudoinverse carrying a subnormalisation, so the raw output is not the normalised solution state — converting it is what the amplification step is for.

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 runs m = O((1/δ) log(1/ε)) applications of U and U†

   The route touches $A$ only through a projected unitary encoding $A = \tilde{\Pi} U \Pi$, of which a block-encoding — $A = \alpha(\langle 0|^{\otimes a} \otimes I) U (|0\rangle^{\otimes a} \otimes I)$ — is the special case. The transformation queries it $m = O((1/\delta)\log(1/\varepsilon))$ times as $U$ and $U^\dagger$, coherently, with a single ancilla qubit carrying the phase shifts. assumption: Every non-zero singular value of $A = \tilde{\Pi} U \Pi$ is at least $\delta$, which is $\delta = 1/\kappa$ after normalisation. assumption: For the end-to-end form, Chakraborty, Gilyén and Jeffery need the encoding's own error to be $o(\varepsilon/(\kappa^2 \log^3(\kappa/\varepsilon)))$, and its subnormalisation $\alpha$ multiplies the query count.

   assumption

   The loop stays coherent: nothing is measured between turns. The preparation may still be reapplied every turn — what the loop never pays is a readout and a restart from classical data. The price is depth, and a success probability that multiplies down the chain. Gilyén, Su, Low and Wiebe's Theorem 41 count, and δ = 1/κ after normalisation — so this is the condition number, appearing as a number of turns rather than as a mysterious factor. The log(1/ε) is what an approximating polynomial of that degree costs, and it is why this route's precision dependence is logarithmic where phase-estimation inversion's is not.

   Open this step

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

   With every non-zero singular value at least $\delta$, an odd real polynomial $P_<$ that $\varepsilon$-approximates $\delta/(2x)$ on $[-1,1] \setminus (-\delta,\delta)$ gives $P_<^{(SV)}(A^\dagger) = \Pi U_\Phi^\dagger \tilde{\Pi}$, which $\varepsilon$-approximates $(\delta/2)A^{+}$. approximation: $1/x$ is replaced by $f(x) = (1-(1-x^2)^b)/x$ with $b = \lceil \kappa^2 \log(\kappa/\varepsilon) \rceil$, which is $\varepsilon$-close to $1/x$ only on $[-1,1] \setminus (-1/\kappa, 1/\kappa)$, and $f$ in turn by an odd Chebyshev expansion of degree $O(\kappa \log(\kappa/\varepsilon))$. assumption: Singular value transformation by real polynomials requires $P_<$ to have parity $n \bmod 2$ and to satisfy $|P_<(x)| \le 1$ for every $x \in [-1,1]$; the construction secures the bound by taking $P_< = P \cdot (1 - P')$ with $P'$ an even polynomial approximating a rectangle function.

   approximationassumption

   Open this step

3. Block-encoding of f(A) → Solution as a stateapply the assembled pseudoinverse

   Assembled: for $0 < \varepsilon \le \delta \le 1/2$ there is an $m = O((1/\delta)\log(1/\varepsilon))$ and an efficiently computable $\Phi \in \mathbb{R}^m$ whose circuit $U_\Phi$, restricted to the singular-value subspaces that are zero or at least $\delta$, implements $(\delta/2) \cdot A^{+}$ to error $\varepsilon$ — using a single ancilla qubit, $m$ uses of $U$ and $U^\dagger$, $m$ uses of $C_\Pi\mathrm{NOT}$ and $C_{\tilde{\Pi}}\mathrm{NOT}$, and $m$ single-qubit gates. Because the transform acts on singular values, it applies to an arbitrary matrix rather than only a Hermitian or normal one. assumption: $0 < \varepsilon \le \delta \le 1/2$; the authors call the $\varepsilon \le \delta$ part quite natural but not necessary, removable through their Corollary 69.

   assumption

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 problem this hop feeds is stated with a procedure that computes $|b\rangle$ in the image of $A$, the target being a state within $\varepsilon$ of $A^{+}|b\rangle / \lVert A^{+}|b\rangle \rVert$. assumption: $|b\rangle$ lies in the image of $A$ — in Chakraborty, Gilyén and Jeffery's Theorem 30 it is an input state spanned by the eigenvectors of $H$. Preparing it costs $T_b$, and that cost enters the end-to-end bill multiplied by the condition number, as the $\kappa T_b \log(1/\varepsilon)$ term.

  assumption

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

  The flagged branch carries the subnormalisation: applying the $(2\kappa,\, a + O(\log(\kappa \log(1/\varepsilon))),\, \varepsilon)$-block-encoding of $A^{-1}$ to $|b\rangle$ leaves $\frac{1}{2\kappa}|0\rangle^{\otimes a}(A^{-1}|b\rangle) + |0^{\perp}\rangle$, so standard amplitude amplification needs a number of rounds linear in $\kappa$ and the overall dependence on $\kappa$ comes out quadratic. Chakraborty, Gilyén and Jeffery recover a linear $\kappa$ by using variable-time amplitude amplification in its place. assumption: Variable-time amplitude amplification needs the solver recast as a variable-stopping-time algorithm — a sequence of $\lceil \log_2 \kappa \rceil + 1$ steps $A_1, A_2, \ldots$, each with its own single-qubit clock register, where step $j$ runs gapped phase estimation on $e^{iA}$ at precision $2^{-j}$ and inverts only the branch that step flags.

  assumption

Gilyén, Su, Low and Wiebe report no numerical work whatever — their only figures are circuit diagrams for the gate sequences of Theorem 17 — and Chakraborty, Gilyén and Jeffery have no figures at all. The numbers the register finds are Lin and Tong's Section 4.3 with Figure 2, and they measure the eigenstate-filtering route, which is written up on the `eigenstate-filtering-inversion` record.

given  a projected unitary encoding of A whose non-zero singular values are
       all at least d  (d = 1/k after normalisation), with 0 < e <= d <= 1/2

block-encode A
prepare |b>
apply the quantum singular value transformation with an odd polynomial
    approximating a scaled 1/x away from the origin
    # m = O((1/d) log(1/e)) applications of U and U^-1, coherently -- the
    # condition number appearing as a number of turns, not as a factor

# what the transform produces is (d/2) A^+, the Moore-Penrose pseudoinverse
# carrying a subnormalisation. This is NOT yet the normalised solution state.

amplify                               # which is what converts it

# A need not be Hermitian or sparse -- only block-encodable, because the
# transform acts on singular values

Gilyén, Su, Low and Wiebe (Theorem 41) implement $(\delta/2)·A^+$ to error $\varepsilon$ with $m = O((1/\delta) \log(1/\varepsilon))$ applications of $U$ and $U\dagger$, using a single ancilla qubit. Chakraborty, Gilyén and Jeffery (Theorem 30) give the block-encoded end-to-end form $\tilde{O}(\alpha \kappa T_U \log³(1/\varepsilon) + \kappa T_b \log(1/\varepsilon))$, where $\alpha$ is the subnormalisation, $T_U$ the cost of the block-encoding and $T_b$ the cost of preparing $|b>$.

The $O(\kappa \log(1/\varepsilon))$ figure is a query count against the block-encoding, not a gate count, and it carries neither $\alpha$ nor the amplification. Lin and Tong summarise the end-to-end QSP/QSVT query complexity as $O(\kappa² \mathrm{polylog}(\kappa/\varepsilon))$, reduced to $O(\kappa \mathrm{polylog}(\kappa/\varepsilon))$ only by variable-time amplitude amplification — and they state that the performance of that technique for this problem has not been quantitatively reported in the literature.

• Direct Moore-Penrose pseudoinverse by singular value transformation (Theorem 41)

  • Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

    András Gilyén, Yuan Su, Guang Hao Low, Nathan Wiebe · 2018

  About

  Section 3.7, and the paper's own framing is that once singular values can be transformed the pseudoinverse costs nothing extra to state. If $\tilde{\Pi}U\Pi = A$ and $A = W\Sigma V^\dagger$ is a singular value decomposition, then $A^{+} = V\Sigma^{+}W^\dagger$, where $\Sigma^{+}$ inverts the diagonal entries except that zeros stay zero. So the whole construction reduces to finding one odd polynomial and feeding it to the singular value transformation machinery of Theorem 17 and Corollary 18. Nothing about the matrix is assumed beyond a projected unitary encoding of it and a lower bound $\delta$ on the non-zero singular values.

  Methods

  An odd real polynomial $P_<$ that $\varepsilon$-approximates $\delta/(2x)$ on $[-1,1] \setminus (-\delta,\delta)$ gives $P_<^{(SV)}(A^\dagger) = \Pi U_\Phi^\dagger \tilde{\Pi}$, which $\varepsilon$-approximates $(\delta/2)A^{+}$. The polynomial is built in three pieces. Lemma 40 borrows Childs, Kothari and Somma's Lemmas 17 to 19: with $b = \lceil \kappa^2\log(\kappa/\varepsilon) \rceil$ the odd function $f(x) = (1-(1-x^2)^b)/x$ is $\varepsilon$-close to $1/x$ on $[-1,1] \setminus (-1/\kappa, 1/\kappa)$, and with $J = \lceil \sqrt{b\log(4b/\varepsilon)} \rceil$ an odd Chebyshev sum of degree $O(\kappa\log(\kappa/\varepsilon))$ is $\varepsilon$-close to $f$ on $[-1,1]$, bounded there by $4J$. The proof of Theorem 41 then takes a $P$ of degree $O(\log(1/\varepsilon)/\delta)$ that $(\varepsilon/3)$-approximates $\delta/(2x)$ on $[-1,1] \setminus (-\delta/2, \delta/2)$, an even $P'$ of the same order of degree from Lemma 29 with $t = 3\delta/4$, its own $\delta' = \delta/4$ and $\varepsilon' = \min(\varepsilon/3, 1/P_{\max})$ approximating the rectangle function, and sets $P_< = P\cdot(1-P')$, which is odd, of degree $m = O(\log(1/\varepsilon)/\delta)$, and bounded by $1$ in absolute value on $[-1,1]$ so that Corollary 18 applies; the gate count follows from Lemma 19. The statement is that for $0 < \varepsilon \le \delta \le 1/2$ there are an $m = O((1/\delta)\log(1/\varepsilon))$ and an efficiently computable $\Phi \in \mathbb{R}^m$ with the operator norm of $(\langle +| \otimes \tilde{\Pi}_{0,\ge\delta}) U_\Phi (|+\rangle \otimes \Pi_{0,\ge\delta}) - \tilde{\Pi}_{0,\ge\delta}(\delta/2)A^{+}\Pi_{0,\ge\delta}$ at most $\varepsilon$, where $\Pi_{0,\ge\delta} = \Pi_{=0} + \Pi_{\ge\delta}$. The circuit uses a single ancilla qubit, $m$ uses of $U$ and $U^\dagger$, $m$ uses of $C_\Pi\mathrm{NOT}$ and $C_{\tilde{\Pi}}\mathrm{NOT}$, and $m$ single-qubit gates. The authors add that the hypothesis $\varepsilon \le \delta$ is quite natural but not necessary and can be removed through Corollary 69.

  Data

  No instance is fixed. $A$ enters only as a projected unitary encoding and the bounds are stated in $\delta$, $\varepsilon$ and $\kappa$ alone; no matrix, no dimension and no right-hand side appears anywhere in the section.

  Code

  No software artefact is named or released. The phase sequence is called efficiently computable and the paper says what that means: the proofs of its Theorems 3 to 5 are constructive, and the hardest step is finding all roots of a degree-$d$ univariate complex polynomial, which can be done to precision $\varepsilon$ on a classical computer in time $O(\mathrm{poly}(d, \log(1/\varepsilon)))$.

  Results

  No numerics. The paper's only figures are the circuit diagrams of Figure 1, showing how to implement a $C_\Pi\mathrm{NOT}$ gate, how to implement $e^{i\phi(2\Pi-I)}$ with one ancilla qubit, two $C_\Pi\mathrm{NOT}$ gates and an $e^{-i\phi\sigma_z}$ gate, and the complete circuit used in Theorem 17. Nothing is simulated and no device is named.

• Threshold pseudoinverse for principal component regression (Corollary 42)

  • Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics

    András Gilyén, Yuan Su, Guang Hao Low, Nathan Wiebe · 2018

  About

  Section 3.8, where the same singular value transformation is pointed at principal component regression. The object wanted there is not $A^{+}$ but $\Pi_{\ge\varsigma}A^{+}\tilde{\Pi}_{\ge\varsigma}$, the pseudoinverse restricted to the singular directions above a threshold $\varsigma$, because the regression's optimal solution is $x = \Pi_{\ge\varsigma}A^{+}\tilde{\Pi}_{\ge\varsigma}b$. This is a second inversion construction rather than an application of the first, and the paper says why in the proof.

  Methods

  For $\varepsilon, \delta \in (0,1/2]$ and $0 < \varsigma < 1$ there are an $m = O((1/\delta)\log(1/\varepsilon))$ and an efficiently computable $\Phi \in \mathbb{R}^m$ such that $(\langle +| \otimes (\Pi - \Pi_{[\varsigma-\delta,\varsigma+\delta]})) U_\Phi (|+\rangle \otimes (\tilde{\Pi} - \tilde{\Pi}_{[\varsigma-\delta,\varsigma+\delta]}))$ is within $\varepsilon$ of $\Pi_{\ge\varsigma}(\varsigma/2)A^{+}\tilde{\Pi}_{\ge\varsigma}$, at the same gate budget as Theorem 41: one ancilla qubit, $m$ uses of $U$ and $U^\dagger$, $m$ uses of $C_\Pi\mathrm{NOT}$ and $C_{\tilde{\Pi}}\mathrm{NOT}$, and $m$ single-qubit gates. The construction is deliberately not a composition: applying the singular value threshold projector of Theorem 31 and then the pseudoinverse of Theorem 41 is stated to be suboptimal, so instead the two theorems' polynomials are multiplied together and the singular value transformation is performed once, according to the product polynomial. To solve regression one applies the result to $|b\rangle$ and then amplitude amplifies. The paper states the caveat itself: strictly one would need $|b\rangle$ to have no overlap with left singular vectors whose singular values fall in $[\varsigma-\delta, \varsigma+\delta]$ and a non-negligible overlap with those above $\varsigma+\delta$, but a left singular vector $|w_j\rangle$ inside that band is still mapped meaningfully, to $f(\varsigma_j)|v_j\rangle$ with $f(\varsigma_j) \in [-1,1]$.

  Data

  No instance is fixed; as with Theorem 41 the statement is entirely in $\varepsilon$, $\delta$ and the threshold $\varsigma$.

  Code

  None found yet.

  Results

  No numerics are reported for this construction either.

• Block-encoding of the inverse from negative matrix powers, with standard amplification

  • The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation

    Shantanav Chakraborty, András Gilyén, Stacey Jeffery · 2018

  About

  Section 4.3. The problem is stated as: given access to an $N \times N$ matrix $A$ and a procedure computing a quantum state $|b\rangle$ in the image of $A$, prepare a state within $\varepsilon$ of $A^{+}|b\rangle / \lVert A^{+}|b\rangle \rVert$, with $A$ supplied as a block-encoding rather than through sparse access. This entry is the straightforward route the paper writes first, and it is worth separating from the variable-time one because the paper separates them and because the two differ in exactly the $\kappa$-dependence this record's reservations are about.

  Methods

  Lemma 9 at $c = 1$ is the inversion step: for a Hermitian $H$ with $I/\kappa \preceq H \preceq I$ and an $(\alpha, a, \delta)$-block-encoding $U$ of it costing $T_U$ elementary gates, with $\delta = o(\varepsilon/(\kappa^2\log^3(\kappa/\varepsilon)))$, one can implement a $(2\kappa,\, a + O(\log(\kappa\log(1/\varepsilon))),\, \varepsilon)$-block-encoding of $A^{-1}$ in complexity $O(\alpha\kappa(a + T_U)\,\mathrm{polylog}(\kappa/\varepsilon))$. It is worth being exact about how that lemma is proved, because it is not by a phase sequence: the authors build on van Apeldoorn, Gilyén, Gribling and de Wolf's general techniques for implementing smooth functions of a Hamiltonian, which access $H$ only through controlled Hamiltonian simulation, and the paper's own speed-up comes from doing that simulation faster in the block-encoding model. The solve is then as simple as it sounds, namely apply the unitary to $|b\rangle$ and amplitude amplify, and the subnormalisation is what it costs: because the encoding carries $2\kappa$, the number of amplification rounds is linear in $\kappa$ and the overall dependence on $\kappa$ comes out quadratic. Footnote 18 records the sign handling: when the eigenvalues lie in $[-1,-1/\kappa]$ one replaces $A$ by $-A$, and in general quantum phase estimation first separates the projection of $|b\rangle$ onto the positive eigenspace from its projection onto the negative one, with $A^{-1}$ or $-(-A)^{-1}$ applied controlled on that.

  Data

  No instance is fixed anywhere in the paper.

  Code

  None found yet.

  Results

  No numerics. The paper reports no numerical experiment, names no simulator or device, and contains no figures at all.

• Variable-time quantum linear systems algorithm (Theorem 30)

  • The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation

    Shantanav Chakraborty, András Gilyén, Stacey Jeffery · 2018

  About

  The same section's second construction, which exists to remove the quadratic $\kappa$ the first one pays. Sparse-access solvers already had a linear dependence on $\kappa$ through Ambainis' variable-time amplitude amplification, applied in a setting close to this one by Childs, Kothari and Somma; the authors follow their notation and proof to get the same for the block-encoding model.

  Methods

  The solver is recast as a variable-stopping-time algorithm $A = A_m \cdots A_1$ with $m = \lceil \log_2\kappa \rceil + 1$ steps, on $m$ single-qubit clock registers $C_1,\dots,C_m$, an input register $I$ holding $|\psi\rangle$, a single-qubit flag register $F$, $m$ workspace registers $P_1,\dots,P_m$ for gapped phase estimation, and an $a$-qubit ancilla register $Q$ for the block-encoding. With $\varepsilon' = \varepsilon/(m\alpha_{\max})$, step $A_j$ does two things: if $C_1,\dots,C_{j-1}$ are in $|0\rangle^{\otimes(j-1)}$ it applies gapped phase estimation to $e^{iA}$ at precision $2^{-j}$ and accuracy $\varepsilon'$, using $P_j$ as workspace and writing its output qubit into $C_j$; and if $C_j$ is then $|1\rangle$ it applies $W(2^{-j}, \varepsilon')$ on $I \otimes F \otimes Q$. Gapped phase estimation is Lemma 28, restated from Childs, Kothari and Somma: it decides whether an eigenphase satisfies $0 \le |\lambda| \le \phi$ or $2\phi \le |\lambda| \le 1$, at cost $O((T_U/\phi)\log(1/\varepsilon))$. The inversion inside it is Corollary 29, itself a corollary of Lemma 9 at $c = 1$, followed by a rotation controlled on $Q$ being $|0\rangle$ that replaces $\lambda/2$ by a constant $\alpha_{\max}^{-1}$ independent of $\lambda$, with $\alpha_{\max} = O(\kappa)$. Variable-time amplitude amplification (their Theorem 23) is then applied to $A$, and $(A')^\dagger$ erases the ancillas, leaving the whole thing in block-encoded form. Theorem 30 states the result: for $\kappa \ge 2$ and Hermitian $H$ whose non-zero eigenvalues lie in $[-1,-1/\kappa] \cup [1/\kappa,1]$, given $\delta = o(\varepsilon/(\kappa^2\log^3(\kappa/\varepsilon)))$, an $(\alpha,a,\delta)$-block-encoding $U$ implementable in $T_U$ elementary gates, and an input state $|\psi\rangle$ spanning the eigenvectors of $H$ preparable in time $T_\psi$, the output is $\varepsilon$-close to $H^{-1}|\psi\rangle / \lVert H^{-1}|\psi\rangle \rVert$ at cost $O(\kappa(\alpha(T_U + a\log^2(\kappa/\varepsilon)) + T_\psi\log\kappa))$. Footnote 21 removes the Hermiticity: any $C \in \mathbb{C}^{M \times N}$ dilates to a Hermitian matrix of dimension $M+N$ whose eigenvalues are $\pm$ the singular values of $C$, so the theorem and its corollaries apply to non-symmetric matrices too.

  Data

  No instance is fixed anywhere in the paper.

  Code

  None found yet.

  Results

  No numerics. The bound is proved and never measured, and Lin and Tong note the consequence from outside: to the extent of their knowledge the performance of variable-time amplitude amplification for solving the quantum linear system problem has not been quantitatively reported in the literature.