QSVT matrix 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 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.

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

Example

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

Cost, as the source states it

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

Implementations

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

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

  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.

  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.

  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.

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

  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

  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.

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

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

  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

  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.

  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.

  No instance is fixed anywhere in the paper.

  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

  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.

  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.

  No instance is fixed anywhere in the paper.

  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.

What it needs

1. Block-encode a matrix 4 methodsruns m = O((1/δ) log(1/ε)) applications of U and U†

   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.

   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.

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

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.

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

• Eigenstate filtering inversion

  Construct the minimax-optimal polynomial that is 1 at a target eigenvalue and uniformly small outside a spectral gap, and apply it through quantum signal processing. For a linear system $|x>$ is the null eigenstate of a Hamiltonian built from $A$ and $|b>$, so one application of the filter solves it once a starting state with non-trivial overlap is supplied.

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

• Quantum singular value transformation and beyond: exponential improvements for quantum matrix arithmetics↗András Gilyén, Yuan Su, Guang Hao Low, Nathan Wiebe · 2018theory yes · simulation no · hardware no
• The power of block-encoded matrix powers: improved regression techniques via faster Hamiltonian simulation↗Shantanav Chakraborty, András Gilyén, Stacey Jeffery · 2018theory yes · simulation no · hardware no
• Optimal polynomial based quantum eigenstate filtering with application to solving quantum linear systems↗Lin Lin, Yu Tong · 2019theory yes · simulation yes · hardware no