How do quantum computers solve linear systems of equations?

Quantum computers solve linear systems of equations using algorithms like the Harrow-Hassidim-Lloyd (HHL) algorithm, which leverages quantum mechanics to perform certain linear algebra operations more efficiently than classical methods for specific problem types. The core idea is to encode the system Ax = b into quantum states, where A is a matrix and b is a vector. The solution x is represented as a quantum state that can be measured to extract useful information. HHL works best when A is sparse and well-conditioned, and when the goal is to compute properties of x (like an expectation value) rather than the full classical solution, which would require exponentially many measurements.

The HHL algorithm proceeds in three main steps. First, b is encoded as a quantum state |b⟩ using amplitude encoding. Next, quantum phase estimation is applied to decompose |b⟩ into the eigenbasis of matrix A, effectively calculating the eigenvalues of A. These eigenvalues are then inverted using a controlled rotation—a quantum operation that adjusts the amplitudes of the solution state based on the inverses of the eigenvalues. Finally, an ancilla qubit is measured to conditionally collapse the system into the solution state |x⟩. Importantly, this process avoids explicitly constructing A⁻¹, which is computationally expensive classically. For example, if A is a diagonal matrix with entries λᵢ, the inversion step directly scales the amplitudes of |b⟩ by 1/λᵢ, producing |x⟩.

However, practical limitations exist. The algorithm assumes A is efficiently implementable as a quantum circuit (e.g., sparse matrices with low-depth Hamiltonian simulation). The solution state |x⟩ isn’t directly readable—only specific features (like ⟨x|M|x⟩ for some operator M) can be estimated through measurements. Additionally, error rates in current quantum hardware restrict problem sizes. For instance, solving a 2x2 system on a real quantum computer would require error correction and multiple shots to mitigate noise. Despite these challenges, HHL demonstrates potential for applications where partial solutions suffice, such as optimizing parameters in machine learning models or solving differential equations in physics simulations.