$A$ Hermitian (the general case is reduced by dilation), $s$-sparse with efficient entry oracles, $‖A‖ \approx 1$ with the relevant spectrum in $[1/\kappa, 1]$, $\kappa$ known or upper-bounded, and $|b>$ preparable in $\mathrm{poly}(\log N)$ time. Only the well-conditioned part of $|b>$ is inverted; the ill-conditioned part is flagged and discarded. The eigenvalue reciprocal is realised by phase estimation plus a conditional rotation, so no polynomial approximation and no phase sequence are ever computed. The paper's own headline comparison is for the case where a summary statistic $x†Mx$ is wanted, not $x$ itself.

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 staterotate by the inverse eigenvalue, post-select

   The map wanted is the one taking $|\lambda_j\rangle$ to $C\lambda_j^{-1}|\lambda_j\rangle$ for a normalising constant $C$; it is not unitary, so it has some probability of failing. It is realised by adjoining an ancilla qubit and rotating conditioned on $|\tilde{\lambda}_k\rangle$, which yields the branch $\sqrt{1 - C^2/\tilde{\lambda}_k^2}\,|0\rangle + (C/\tilde{\lambda}_k)|1\rangle$ with $C = O(1/\kappa)$; the phase estimation is then undone to uncompute the $\tilde{\lambda}_k$ and the last qubit is measured, and conditioned on seeing $1$ the state is proportional to $\sum_j \beta_j (C/\lambda_j)|u_j\rangle$, which is $|x\rangle = \sum_j \beta_j\lambda_j^{-1}|u_j\rangle$ up to normalisation — the normalisation factor being determined from the probability of obtaining $1$. approximation: what is produced is not $\sum_j \lambda_j^{-1}\beta_j|u_j\rangle$ but a state close to $\sum_{j,\lambda_j \ge 1/\kappa} \lambda_j^{-1}\beta_j|u_j\rangle|\mathrm{well}\rangle + \sum_{j,\lambda_j < 1/\kappa} \beta_j|u_j\rangle|\mathrm{ill}\rangle$; only the well-conditioned part is inverted, eigenvectors with eigenvalue $\le 1/\kappa' = 1/2\kappa$ are flagged as ill-conditioned without being inverted, and the two behaviours are interpolated for $1/\kappa' < |\lambda| < 1/\kappa$, because no eigenvalue can be resolved exactly. assumption: $C = O(1/\kappa)$ together with $\lambda \le 1$ is what leaves the post-selection a success probability of at least $\Omega(1/\kappa^2)$; correctness is guaranteed under $\|A\| \le 1$ and $\|A^{-1}\| \le \kappa$, with $\kappa$ supplied as a chosen cutoff.

   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 runs O(κ) times — once per amplification round

  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 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. The rotation ancilla carries a success amplitude of about 1/κ, so the whole prepare-estimate-rotate-uncompute block is amplified O(κ) times and |b⟩ is prepared afresh inside every one of them. This is where one of the two κ factors in Õ(log(N) s² κ²/ε) comes from, and it is the reason the state-preparation query count is a headline number for this family rather than a footnote: a route whose |b⟩ is expensive pays for it κ times here and once in the all-at-once encodings.

  $|b\rangle = \sum_j \beta_j |u_j\rangle$ is produced by an efficiently implementable unitary $B$ applied to $|\mathrm{initial}\rangle$, whose gate count is $T_B$. $B$ and $B^\dagger$ sit inside the amplification iterate $U_{\mathrm{invert}} B R_{\mathrm{init}} B^\dagger U_{\mathrm{invert}}^\dagger R_{\mathrm{succ}}$, so $|b\rangle$ is prepared afresh in each of the $O(\kappa)$ rounds and appears in the run-time $\tilde{O}(\kappa T_B + \kappa^2 s^2 \log(N)/\varepsilon)$ as the term $\kappa T_B$. assumption: nothing beyond efficient implementability is assumed of $B$ — it may produce $|b\rangle$ "possibly along with garbage in an ancilla register" — and the possibility that $B$ errs in producing $|b\rangle$ is neglected, since without another way of producing or verifying $|b\rangle$ there is no way to mitigate those errors, so any error there translates directly into error in the final $|x\rangle$.

  assumption

• Simulate Hamiltonian evolution runs O(κ) times — once per amplification round

  Implement $e^{-iHt}$ to error $\varepsilon$ given some access model for $H$. It is an application in its own right and also the engine inside phase estimation and several linear-system solvers.

  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. Inside the same amplified block as the preparation above: phase estimation runs against e^{-iAt} with t_0 = O(κ/ε), and that whole estimation is repeated by the amplification. The two κ's compose, which is the second factor in Õ(log(N) s² κ²/ε).

  The conditional Hamiltonian evolution $\sum_{\tau=0}^{T-1} |\tau\rangle\langle\tau| \otimes e^{iA\tau t_0/T}$ is applied to $|\Psi_0\rangle |b\rangle$ and the first register is Fourier transformed, giving $\sum_{j,k} \alpha_{k|j}\beta_j |k\rangle |u_j\rangle$, in which $|\alpha_{k|j}|$ is large if and only if $\lambda_j \approx 2\pi k/t_0 =: \tilde{\lambda}_k$. For $s$-sparse $A$ and $t \le t_0$ this costs $T_H = \tilde{O}(\log(N)s^2 t_0)$ to error $\varepsilon_H$, and with $t_0 = O(\kappa/\varepsilon)$ the amplification repeats the whole estimation $O(\kappa)$ times. approximation: the eigenvalues are replaced by the phase estimates $\tilde{\lambda}_k = 2\pi k/t_0$; phase estimation is "the dominant source of error", erring by $O(1/t_0)$ in estimating $\lambda$, which translates into a relative error of $O(1/\lambda t_0)$ in $\lambda^{-1}$, so for $\lambda \ge 1/\kappa$ taking $t_0 = O(\kappa/\varepsilon)$ induces a final error of $\varepsilon$. assumption: $A$ is $s$-sparse and efficiently row computable — at most $s$ nonzero entries per row, computable in time $O(s)$ given a row index — and this is the only step of the algorithm where sparsity of $A$ is required.

  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 $S$ after $U_{\mathrm{invert}}$ and obtaining the outcome 'well' has approximately applied an operator proportional to $A^{-1}$, with success probability $\tilde{p}$; rather than repeating $1/\tilde{p}$ times, amplitude amplification obtains the same result in $O(1/\sqrt{\tilde{p}})$ repetitions of $U_{\mathrm{invert}} B R_{\mathrm{init}} B^\dagger U_{\mathrm{invert}}^\dagger R_{\mathrm{succ}}$ applied to $U_{\mathrm{invert}} B |\mathrm{initial}\rangle$, where $R_{\mathrm{succ}} = I^S - 2|\mathrm{well}\rangle\langle\mathrm{well}|^S$ and $R_{\mathrm{init}} = I - 2|\mathrm{initial}\rangle\langle\mathrm{initial}|$. Since $C = O(1/\kappa)$ and $\lambda \le 1$ the post-selection succeeds with probability at least $\Omega(1/\kappa^2)$, so the ideal repetition count $\pi/4\sqrt{\tilde{p}}$ is $O(\kappa)$. assumption: $\tilde{p}$ is initially unknown, so the entire procedure is repeated with a geometrically increasing number of repetitions — $1, 2, 4, 8, \ldots$ — until a power of two $\ge \kappa$ is reached, which yields a constant probability of success using $\le 4\kappa$ repetitions and therefore needs the cutoff $\kappa$, which is an input to the algorithm.

  assumption

Harrow, Hassidim and Lloyd (arXiv:0811.3171) carry no numerical work: no figure, no table, no simulated instance, no simulator and no hardware. The only concrete matrix written down anywhere is assembled in Appendix A 5 out of a quantum circuit to prove matrix inversion BQP-complete — an argument about an instance rather than an instance that was solved. The numerics the register finds belong to Costa et al. and measure the discrete adiabatic walk, which has its own record.

given  A Hermitian (the general case reduced by dilation), s-sparse with
       efficient entry oracles, ||A|| ~ 1 with the relevant spectrum in
       [1/k, 1], k known or upper-bounded, and |b> preparable in poly(log N)

repeat O(k) times, coherently -- the amplification rounds:
    prepare |b>                       # afresh inside every round
    run phase estimation against exp(-iAt), writing eigenvalue estimates
        into an ancilla register
    apply a controlled rotation with amplitude proportional to 1/lambda~
    uncompute the phase estimation
    post-select on the rotation ancilla

# the success amplitude is about 1/k, which is why there are O(k) rounds --
# and preparing |b> inside each of them is one of the two k factors

# only the well-conditioned part of |b> is inverted; the ill-conditioned
# part is flagged and discarded
# no polynomial approximation and no phase sequence is ever computed: the
# eigenvalue reciprocal is phase estimation plus a conditional rotation

Harrow, Hassidim and Lloyd state the runtime as $\tilde{O}(\log(N) s² \kappa²/\varepsilon)$, with $N$ the dimension, $s$ the sparsity, $\kappa$ the condition number and $\varepsilon$ the additive error; the phase-estimation time is set to $t_0 = O(\kappa/\varepsilon)$.

The headline exponential speedup is over a different deliverable. Learning the full solution vector rather than a functional of it takes $Θ̃(d/ε)$ applications of the preparation unitary and its inverse to obtain an $\varepsilon$-l2 approximation of a $d$-dimensional pure state (here $d$ is the dimension, written $N$ above; elsewhere in this group $d$ denotes the sparsity) — a characterised complexity, not a loose upper bound — and that linear-in-dimension factor cancels the log-dimension advantage. The $\kappa²$ is also superseded: later solvers reach $O(\kappa \log(1/\varepsilon))$.

• U_invert with filter functions, inside the amplitude-amplification loop (Appendix A 1)

  • Quantum algorithm for solving linear systems of equations

    Aram W. Harrow, Avinatan Hassidim, Seth Lloyd · 2008

  About

  The paper's own full-detail construction, and it says so against the Letter body: "While the body of the paper attempted to convey the spirit of the procedure and left out various improvements, here we take the opposite approach and describe everything, albeit possibly in a less intuitive way." The problem it is built for is stated with its inputs rather than as a theorem: given a procedure producing $|b\rangle$, a method of producing the at most $s$ non-zero elements of any row of $A$, and a choice of cutoff $\kappa$, produce $|x\rangle$ proportional to $A^{-1}|b\rangle$ up to an error $\varepsilon$ that is also part of the input, with correctness guaranteed when $\lVert A \rVert \le 1$ and $\lVert A^{-1} \rVert \le \kappa$. Error is measured as distance between vectors, $\lVert\,|\alpha\rangle - |\beta\rangle\,\rVert = \sqrt{2(1 - \mathrm{Re}\langle\alpha|\beta\rangle)}$, and since ancillas are imperfectly uncomputed the output is compared against $|x\rangle|000\ldots\rangle$ with the ancillas suppressed in the notation.

  Methods

  The subroutine $U_{\mathrm{invert}}$ is five steps. Prepare $|\Psi_0\rangle = \sqrt{2/T}\sum_{\tau=0}^{T-1}\sin\frac{\pi(\tau + 1/2)}{T}|\tau\rangle$ from $|0\rangle$ up to error $\epsilon_\Psi$, in time $\mathrm{poly}\log(T/\epsilon_\Psi)$; the coefficients are the ones that minimise a quadratic loss appearing in the error analysis, not a uniform superposition. Apply $\sum_{\tau=0}^{T-1}|\tau\rangle\langle\tau|^C \otimes e^{iA\tau t_0/T}$ up to error $\epsilon_H$, at cost $T_H = O(\log(N)(\log^*(N))^2 s^2 t_0 9^{\sqrt{\log(s^2 t_0/\epsilon_H)}}) = \tilde{O}(\log(N)s^2 t_0)$, which scales better than any power of $1/\epsilon_H$ and is the only step requiring sparsity. Fourier transform the register $C$, writing $\tilde{\lambda}_k := 2\pi k/t_0$. Adjoin a three-dimensional register $S$ in $|h(\tilde{\lambda}_k)\rangle = \sqrt{1 - f(\tilde{\lambda}_k)^2 - g(\tilde{\lambda}_k)^2}|\mathrm{nothing}\rangle + f(\tilde{\lambda}_k)|\mathrm{well}\rangle + g(\tilde{\lambda}_k)|\mathrm{ill}\rangle$. Reverse steps 1 to 3, uncomputing any garbage. The filter functions are required only to satisfy $f(\lambda) = 1/C\kappa\lambda$ for $\lambda \ge 1/\kappa$, $g(\lambda) = 1/C$ for $\lambda \le 1/\kappa' := 1/2\kappa$, $f^2 + g^2 \le 1$ and a continuity property, with $C > 1$; otherwise they are arbitrary, and Eq. (A3) gives one choice that interpolates by $\frac{1}{2}\sin\big(\frac{\pi}{2}\cdot\frac{\lambda - 1/\kappa'}{1/\kappa - 1/\kappa'}\big)$ and $\frac{1}{2}\cos$ of the same argument on $1/\kappa' \le \lambda < 1/\kappa$. The outer loop is amplitude amplification: start from $U_{\mathrm{invert}}B|\mathrm{initial}\rangle$ and repeatedly apply $U_{\mathrm{invert}} B R_{\mathrm{init}} B^\dagger U_{\mathrm{invert}}^\dagger R_{\mathrm{succ}}$ with $R_{\mathrm{succ}} = I^S - 2|\mathrm{well}\rangle\langle\mathrm{well}|^S$ and $R_{\mathrm{init}} = I - 2|\mathrm{initial}\rangle\langle\mathrm{initial}|$, measuring $S$ and stopping on 'well'. The ideal count $\pi/4\sqrt{\tilde{p}}$ is $O(\kappa)$; because $\tilde{p}$ is unknown the whole procedure is rerun with $1, 2, 4, 8, \ldots$ repetitions until a power of two at least $\kappa$ is reached, giving constant success probability in at most $4\kappa$ repetitions.

  Data

  No dataset, and no instance. The inputs are three objects and two numbers: an efficiently implementable unitary $B$ taking $|\mathrm{initial}\rangle$ to $|b\rangle$, possibly along with garbage in an ancilla register, costing $T_B$ gates, about which nothing further is assumed — it may be another part of a larger algorithm, or a standard state-preparation procedure — and whose own possible failure is explicitly not modelled, so any error there translates directly into error in $|x\rangle$; a row procedure returning the at most $s$ non-zero entries of a given row of $A$ in time $O(s)$; the cutoff $\kappa$, which is chosen and need not be the true condition number; the target error $\varepsilon$; and the phase-estimation time $t_0$. The Letter notes that $|b\rangle$ can be prepared by the procedure of Ref. [14] when $b_i$ and $\sum_{i=i_1}^{i_2}|b_i|^2$ are efficiently computable.

  Code

  None found yet.

  Results

  Counted, never executed. Theorem 1 bounds the error three ways, all $O(\kappa/t_0)$: without post-selection $\lVert \tilde{U} - U \rVert \le O(\kappa/t_0)$; post-selecting on the flag register lying in the span of $\{|\mathrm{well}\rangle, |\mathrm{ill}\rangle\}$, $\lVert\,|\tilde{x}\rangle - |x\rangle\,\rVert \le O(\kappa/t_0)$; and, when $|b\rangle$ lies entirely in the well-conditioned subspace and the post-selection is on $|\mathrm{well}\rangle$, the same bound, which the paper calls the case of most practical interest. Taking $t_0 = O(\kappa/\varepsilon)$ therefore costs $\varepsilon$ of error, and the assembled run-time is $\tilde{O}(\kappa(T_B + t_0 s^2\log(N)))= \tilde{O}(\kappa T_B + \kappa^2 s^2\log(N)/\varepsilon)$, the $\tilde{O}$ suppressing $(\log^*(N))^2$, $\exp(O(1/\sqrt{\log(t_0/\epsilon_H)}))$ and $\mathrm{poly}\log(T/\epsilon_\Psi)$. No instance is inverted, no simulator or hardware is named anywhere in the paper, and no figure or table appears in it, so this exists as a specified algorithm with proved bounds and not as an executed one.

• Hermitian dilation for non-Hermitian and non-square A (Appendix A 4)

  • Quantum algorithm for solving linear systems of equations

    Aram W. Harrow, Avinatan Hassidim, Seth Lloyd · 2008

  About

  The reduction the rest of the paper assumes has already been applied, and the reason this record's conditions can say "the general case is reduced by dilation". The body states it in one line — if $A$ is not Hermitian, define $C = \begin{pmatrix}0 & A\\ A^\dagger & 0\end{pmatrix}$, solve $C\vec{y} = \begin{pmatrix}\vec{b}\\ 0\end{pmatrix}$ and read $\vec{y} = \begin{pmatrix}0\\ \vec{x}\end{pmatrix}$ — and Appendix A 4 works out what the dilation does to rectangular and rank-deficient problems, which is where it stops being a formality. The Discussion adds that it is what makes non-square matrices invertible by the algorithm at all.

  Methods

  For $A \in \mathbb{C}^{M \times N}$ with $M \le N$, take the singular value decomposition $A = \sum_{j=1}^{M}\lambda_j |u_j\rangle\langle v_j|$ with $|u_j\rangle \in \mathbb{C}^M$, $|v_j\rangle \in \mathbb{C}^N$ and $\lambda_1 \ge \cdots \ge \lambda_M \ge 0$, and set $V = \mathrm{span}\{|v_1\rangle,\ldots,|v_M\rangle\}$. Then $H = \begin{pmatrix}0 & A\\ A^\dagger & 0\end{pmatrix}$ is Hermitian with eigenvalues $\pm\lambda_1,\ldots,\pm\lambda_M$ on the eigenvectors $|w_j^{\pm}\rangle = \frac{1}{\sqrt{2}}(|0\rangle|u_j\rangle \pm |1\rangle|v_j\rangle)$, together with $N - M$ zero eigenvalues on the orthogonal complement of $V$. The algorithm is run on the input $|0\rangle|b\rangle$; writing $|b\rangle = \sum_j \beta_j|u_j\rangle$ gives $|0\rangle|b\rangle = \sum_j \beta_j\frac{1}{\sqrt{2}}(|w_j^{+}\rangle + |w_j^{-}\rangle)$ and $H^{-1}|0\rangle|b\rangle = \sum_j \beta_j\lambda_j^{-1}|1\rangle|v_j\rangle$, and dropping the leading $|1\rangle$ defines the solution.

  Data

  None. The construction acts on the matrix and the right-hand side as objects, not on any instance of them, and the paper states no dimensions.

  Code

  None found yet.

  Results

  Structural rather than numerical, and stated as two cases. Under-constrained, $M < N$: the algorithm produces no component in $V^{\perp}$, although such components would also have given valid solutions, so "in this sense, it could be said to be finding the $|x\rangle$ that minimizes $\langle x|x\rangle$ while solving $A|x\rangle = |b\rangle$". Over-constrained, $M \ge N$: with $U = \mathrm{span}\{|u_1\rangle,\ldots,|u_N\rangle\}$, the equation is satisfiable only if $|b\rangle \in U$, and any weight of $|b\rangle$ in $U^{\perp}$ lands in the zero eigenspace of $H$, where the filter functions flag it as ill-conditioned; choosing to ignore that part returns an $|x\rangle$ satisfying $A|x\rangle = \sum_{j=1}^{N}|u_j\rangle\langle u_j|\,|b\rangle$. No cost is quoted separately for the dilation itself.

• Matrix inversion instances built from a quantum circuit (Appendix A 5)

  • Quantum algorithm for solving linear systems of equations

    Aram W. Harrow, Avinatan Hassidim, Seth Lloyd · 2008

  About

  The one place in the paper where a concrete matrix is written down rather than assumed behind an oracle, and it is written down to prove hardness rather than to be solved. The claim it serves is that a quantum circuit on $n$ qubits with $T$ gates can be simulated by inverting an $O(1)$-sparse $A$ of dimension $N = O(2^n\kappa)$, with $\kappa = O(T^2)$ if $A$ must be positive definite and $O(T)$ if not. It is worth having on this card precisely because it is easy to mistake for an instance: it fixes a matrix, a right-hand side, a condition number and a dimension, and it never computes a number.

  Methods

  Let $C$ be a circuit on $n = \log N$ qubits applying $T$ two-qubit gates $U_1,\ldots,U_T$ to $|0\rangle^{\otimes n}$, with the answer read from the first qubit. Adjoin an ancilla register of dimension $3T$ and define $U = \sum_{t=1}^{T}|t{+}1\rangle\langle t| \otimes U_t + |t{+}T{+}1\rangle\langle t{+}T| \otimes I + |t{+}2T{+}1 \bmod 3T\rangle\langle t{+}2T| \otimes U^\dagger_{3T+1-t}$, chosen so that for $T + 1 \le t \le 2T$ applying $U^t$ to $|1\rangle|\psi\rangle$ yields $|t{+}1\rangle \otimes U_T\cdots U_1|\psi\rangle$. Setting $A = I - Ue^{-1/T}$ gives $\kappa(A) = O(T)$ and $A^{-1} = \sum_{k \ge 0}U^k e^{-k/T}$, which is read as applying $U^t$ for a geometrically distributed $t$; since $U^{3T} = I$ one may assume $1 \le t \le 3T$, and measuring the first register into the window $T + 1 \le t \le 2T$, which happens with probability $e^{-2}/(1 + e^{-2} + e^{-4}) \ge 1/10$, leaves the second register holding $U_T\cdots U_1|\psi\rangle$. The Hermitian form of Eq. (A34) is $A = \begin{pmatrix}0 & I - Ue^{-1/T}\\ I - U^\dagger e^{-1/T} & 0\end{pmatrix}$, with $\kappa \le 2T$ and dimension $N = 6T2^n$. To measure only the first qubit, Eq. (A36) defines $B = \begin{pmatrix}0 & I_{6T2^n}\\ 0 & I_{3T2^n} - Ue^{-1/T}\end{pmatrix}$, and permuting its rows and columns into $\tilde{B}$ gives $C = \begin{pmatrix}0 & \tilde{B}\\ \tilde{B}^\dagger & 0\end{pmatrix}$ with the same condition number and $N = 18T2^n$.

  Data

  No dataset and no measured input. The instance is generated from a circuit, so its parameters are functions of that circuit's gate count $T$ and qubit count $n$, and they stay symbolic. The single place the paper substitutes anything is in the proof of Theorem 5, where converting Simon's algorithm — a $3n$-qubit, $2n{+}1$-gate computation run $O(n)$ times with a $\mathrm{poly}(n)$ classical post-processing — yields $\kappa \approx 4n$ and $N \approx 36n2^{3n}$; these too are formulas in $n$, and no value of $n$ is ever fixed.

  Code

  None found yet.

  Results

  Nothing was computed; what the instance yields is a set of conditional statements. Theorem 4: a quantum algorithm for matrix inversion running in time $\kappa^{1-\delta}\mathrm{poly}\log(N)$ for some $\delta > 0$ would give $\mathrm{BQP} = \mathrm{PSPACE}$; no relativizing quantum algorithm can run in that time; and a classical algorithm running in $\mathrm{poly}(\kappa, \log(N))$ would give $\mathrm{BPP} = \mathrm{BQP}$. Theorem 5: no relativizing classical matrix inversion algorithm can run in time $N^{\alpha}2^{\beta\kappa}$ unless $3\alpha + 4\beta \ge 1/2$, the bound becoming $N^{\alpha}2^{\beta\sqrt{\kappa}}$ on positive-definite matrices. Theorem 6, on the matrix inversion estimation problem of outputting a number within $\varepsilon$ of $\langle x|M|x\rangle$ with probability at least $2/3$: a quantum algorithm in $\mathrm{poly}(\kappa, \log(N), \log(1/\varepsilon))$ would give $\mathrm{BQP} = \mathrm{PP}$, and no relativizing quantum algorithm can run in $N^{\alpha}\mathrm{poly}(\kappa)/\varepsilon^{\beta}$ unless $\alpha + \beta \ge 1$. The paper's own summary is that matrix inversion is BQP-complete, and that even improving the $\kappa$-dependence to $\kappa^{1-\delta}$ would let any time-$T$ quantum algorithm be simulated in time $o(T)$. Along the way it records that its own algorithm solves the estimation problem in $\tilde{O}(\log(N)\kappa^2 s^2/\varepsilon^3)$, by producing $|x\rangle$ to trace distance $\varepsilon/2$ and taking $1/3\varepsilon^2$ samples of a bit whose variance is at most $1/4$.

• HHL linear-systems reference · Qiskit

  From the repository — run, not written up from a paper · native

  About

  A linear-algebra reference that forces the catalog to show input loading, conditioning, and output observability.

  Methods

  None found yet.

  Data

  None found yet.

  Code

  Qiskit

  Results

  Algorithm boundary documented · end-to-end application benchmark pending

• Hybrid HHL++ for portfolio optimization · Qiskit

  From the repository — run, not written up from a paper · unsupported

  About

  Adapt the Harrow-Hassidim-Lloyd (HHL) quantum linear-systems algorithm, most of whose components current noisy quantum hardware cannot reach, into a form that near-term devices can actually execute, and demonstrate it on an application.

  Methods

  None found yet.

  Data

  None found yet.

  Code

  Qiskit

  Results

  Literature record · the algorithm a Classiq library entry demonstrates, checked against that algorithm's primary reference on its arXiv abs page

• HHL linear-systems reference

  A linear-algebra reference that forces the catalog to show input loading, conditioning, and output observability.

• Hybrid HHL++ for portfolio optimization

  Adapt the Harrow-Hassidim-Lloyd (HHL) quantum linear-systems algorithm, most of whose components current noisy quantum hardware cannot reach, into a form that near-term devices can actually execute, and demonstrate it on an application.