HHL: eigenvalue inversion by phase estimation

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

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

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

Example

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

Cost, as the source states it

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

Implementations

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

  • Quantum algorithm for solving linear systems of equations

  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.

  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.

  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.

  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

  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.

  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.

  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.

  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

  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.

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

  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.

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

What it needs

Every step this method names is listed under Requires above. It walks its own span in one hop and calls out to the rest — that is a fact about the recorded route, not a claim that the span is simple.

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.

• Polynomial approximation

  Given a target function, a domain and an error $\varepsilon$, return a polynomial of definite parity, bounded on $[-1,1]$, that is $\varepsilon$-close to the target on that domain, with an explicit degree.

• QSP phase factors

  Given an admissible polynomial, compute the phase sequence $Φ$ that makes the quantum-signal-processing product reproduce it to accuracy $\varepsilon$ in classical finite-precision arithmetic.

Other ways to fill the same slot

Different approaches

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

• 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

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

Sources

• Quantum algorithm for solving linear systems of equations↗Aram W. Harrow, Avinatan Hassidim, Seth Lloyd · 2008theory yes · simulation no · hardware no
• Quantum tomography using state-preparation unitaries↗Joran van Apeldoorn, Arjan Cornelissen, András Gilyén, Giacomo Nannicini · 2022theory yes · simulation ? · hardware no
• Optimal scaling quantum linear systems solver via discrete adiabatic theorem↗Pedro C. S. Costa, Dong An, Yuval R. Sanders, Yuan Su, Ryan Babbush, Dominic W. Berry · 2021theory yes · simulation yes · hardware no