Linear systems

A linear system asks for a vector x such that A x = b. The quantum algorithm in this library does not return that vector as a list. HHL prepares a quantum state whose amplitudes encode the solution, under sparsity, a bound on the condition number, and a procedure that prepares the right-hand side as a state. The 2009 runtime, the BQP-completeness reduction, and the later query bound of Childs, Kothari, and Somma are on that page. This stub only keeps the comparisons that are easy to drop when the algorithm is mentioned alone.

Quantum phase estimation is the subroutine that reads the eigenvalues of the simulated matrix. Its precision bound assumes an eigenstate, or a state with inverse-polynomial overlap, and controlled powers one can actually run. HHL spends those powers inside Hamiltonian simulation. A quotation of the 2009 linear-systems runtime remains a quotation of HHL's accounting for the simulation subroutine they cite. The later product-formula and qubitization bounds are on the simulation page.

The output limit is the one to say first. An expectation value of an observable on the output state is a classical number, and HHL's Theorem 6 says that estimating it to error ε in time polylogarithmic in 1/ε would imply BQP equals PP. The logarithmic precision in the 2017 paper is for the state. Aaronson's commentary lists the same boundary in four operational pieces: loading b, simulating A, the size of the condition number, and the fact that one measurement does not print x. His rough product for the runtime is not the bound this library quotes.

Dequantization does not erase the 2009 theorem. Gilyén, Lloyd, and Tang give a classical algorithm that samples from the solution of a low-rank system when the matrix is offered by length-square sampling. The cost is polylogarithmic in the dimension and a high-degree polynomial in the rank, the condition number, the Frobenius norm, and the error. That is a result about sampling access. It is not a classical algorithm for the sparse oracle problem HHL prove BQP-complete.

This page does not survey differential equations, machine-learning subroutines, or preconditioners. Those applications are real only when someone checks the access model and the condition number for the instance in front of them. What belongs here is the split between the state-preparation theorem, the estimation problem, and the low-rank sampling algorithm.