Optimization of the HHL Algorithm
Vikram Tripathi · 2026
Read Optimization of the HHL Algorithm by Vikram Tripathi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-15756.txt.
Introduction
Sood, Mathur, and Tripathi tune the HHL quantum algorithm for near-term simulators. HHL solves linear equation systems with a promised exponential edge. Real runs lose fidelity as matrices grow denser. The team tests two fixes across four sparsity levels. Suzuki-Trotter splitting handles the time evolution operator. Block encoding embeds the matrix in a larger unitary. Structured matrices reach near-ideal fidelity in their runs. Block encoding wins on mid-density cases. Trotter steps stay qubit-cheap for sparse ones.
Catalog record
| CREATOR | Vikram Tripathi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 17771 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.15756
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Optimization of the HHL Algorithm Vikram Tripathi Abstract The Harrow–Hassidim–Lloyd (HHL) algorithm is a quantum algorithm for solving systems of linear equations that, in principle, offers an exponential improvement in scaling with the system size compared to classical approaches. In this work, we investigate the practical implementation and optimisation of the HHL algorithm with a focus on improving its performance on near-term quantum simulators. After outlining the algorithm, we examine two optimisation strategies aimed at improving fidelity and scalability: Suzuki–Trotter decomposition of the Hamiltonian evolution operator and a block-encoding approach that embeds the problem matrix into a larger unitary operator. The performance of these methods is evaluated through simulations on matrices with varying sparsity, including diagonal, tridiagonal, moderately dense, and fully dense cases. Our results show that while HHL achieves near-ideal fidelity for highly structured matrices, performance degrades as sparsity decreases due to the increasing cost of Hamiltonian simulation and reduced post-selection probability due to higher condition number. Block encoding is found to provide improved fidelity for moderately dense matrices, whereas Trotterisation offers a qubit-efficient approach for sparse systems. These results highlight the importance of matrix structure in determining the practical efficiency of HHL and inform future implementations that combine algorithmic optimisation with hardware-aware design. Dhruv Sood 1 Introduction Quantum mechanics emerged in the 1900s to try and explain phenomena at the scales of atoms and revolutionised our understanding of nature, leading to advances across all fields of science and technology. Its success brought with itself the realisation that the classical picture of the world could not hope to describe the subtleties that characterise the physics of very small scales. Indeed, since the world is being proved to be inherently quantum on these scales, it is only natural that any purely classical method of studying it will fail to grasp all aspects of the physical system of interest. Quantum computation offers a solution to this problem, replacing the manipulation of classical bits with those of qubits whose evolution is governed by the laws of quantum mechanics. Such applications are often quantum algorithms that are able to solve certain problems much faster than the corresponding classical algorithms. Prototypical examples of these are Shor’s [ 14 ] algorithm - which allows one to find the prime factors of integers in polynomial time - and Grover’s [ 9 ] algorithm - which solves the unstructured search problem in O(\sqrt{N}) time as opposed to the classical O(N) . In this work, we will describe results obtained regarding another such quantum algorithm that is able to solve a system of linear equations faster than standard classical algorithms that try to achieve the same. Linear Systems of equations are ubiquitous in all fields of science. A more efficient procedure of solving them has the potential to drastically accelerate studies of physical systems. Classically O(N^{2.81}) is the best one can currently achieve for matrix multiplication [ 1 ] , and the solution of A\mathbf{x}=\mathbf{b} will obviously be bounded by this. So a quantum algorithm that can achieve an exponential speedup can greatly benefit any computation that can be reduced to such a problem. The algorithm of interest is the HHL algorithm presented by by Harrow, Hassidim and Lloyd [ 10 ] . in 2009. It allows one to find an (approximate) solution to the linear system of equations A\mathbf{x}=\mathbf{b} , given some previous knowledge of the spectrum of A and that the matrix A matrix that is Hermitian, sparse and well-conditioned. The HHL algorithm is able to solve such a problem in time that scales logarithmically in N and polynomially in the condition number \kappa of the problem. The solution is obtained as the amplitudes of a quantum state, so it lends itself naturally to situations where one is not interested in the solution itself, but in some linear function of the same. The first step in this direction was the HHL algorithm of Harrow, Hassidim and Lloyd [ 10 ] . It allows one to find an (approximate) solution to the linear system of equations A\mathbf{x}=\mathbf{b} , given some knowledge of the nature of the spectrum of A and requiring that the matrix A is Hermitian, sparse and well-conditioned. Under reasonable assumptions (efficient access to A and \ket{b} , A is s -sparse, the query complexity of the HHL algorithm scales as \text{poly}(\log N)s^{2}\kappa^{2}/\epsilon, where \kappa is the condition number of the problem and \epsilon is a measure of the precision. The exponential speedup in N thus comes at the cost of polynomial overhead in \kappa and \epsilon . The solution is obtained as the amplitudes of a quantum state, so it lends itself naturally to situations where one is not interested in the solution itself, but in expectation values of operators in the solution state. The HHL algorithm has had a significant impact on the state of both current and future prospects of quantum computation and many applications of the same have already been proposed. For eg. Clader et al. [ 5 ] have proposed its application in speeding up the calculation of electromagnetic scattering cross-sections while Wang et al. [ 17 ] have put forward using it to estimate the resistances of electrical networks. There is also recent interest in studying it’s implementation and it’s extensions to matrices with higher condition numbers [ 16 ] . 2 The HHL Algorithm The core idea of the HHL algorithm is to encode the input vector \mathbf{b} into a quantum state \ket{b} and then use quantum operations to transform this state into the state \ket{x} that is proportional to the solution \mathbf{x}=A^{-1}\mathbf{b} for an N\times N matrix A . This is achieved by exploiting the completeness of the eigenstates of A to write \ket{b}=\sum_{i=0}^{N-1}b_{i}\ket{v_{i}} . Similarly their orthonormality leads to, \displaystyle\ket{x} \displaystyle=\frac{A^{-1}\ket{b}}{||A^{-1}\ket{b}||_{2}}, (1) \displaystyle=\frac{1}{||A^{-1}\ket{b}||_{2}}\sum_{j=0}^{N-1}\frac{\ket{v_{k}}\bra{v_{k}}}{\lambda_{k}}\sum_{k=0}^{N-1}b_{j}\ket{v_{j}}, \displaystyle=\frac{1}{\sqrt{\sum_{j=0}^{N-1}|b_{j}|^{2}/\lambda_{j}^{2}}}\sum_{j=0}^{N-1}\frac{b_{j}}{\lambda_{j}}\ket{v_{j}}. This is implemented in two main steps. The first step extracts the eigenvalues of A into a separate register of qubits using Quantum Phase Estimation. Following that, a set of controlled rotations by this register insert the desired factor of the inverse eigenvalues. Figure 1 shows a schematic diagram of a circuit that implements this. Figure 1: HHL Circuit Diagram The first phase of the circuit, Quantum Phase Estimation, takes a unitary matrix U with eigenstates \ket{v_{j}} with eigenvalues \mathrm{e}^{2\pi i\theta_{j}} and stores the the binary representation of the phase angle \theta in a qubit state. These qubits carrying the phase information are named “clock qubits". In the HHL algorithm, if \ket{v_{j}} is an eigenstate of a Hermitian matrix A with eigenvalue \lambda_{j} , by constructing a unitary matrix U=\mathrm{e}^{itA} with a scale factor t , the state \ket{v_{j}} becomes an eigenstate of U with eigenvalue \mathrm{e}^{it\lambda_{j}} . Therefore, the eigenvalue \lambda_{j} can be estimated using the QPE algorithm. The second step uses an ancillary qubit and these encoded eigenvalues to insert the desired factor of 1/\lambda_{j} to obtain the solution. Finally, the un-compute step returns the clock qubits to their original state before measurement. Without circuit optimization, the increase in the system size exponentially increases the gate counts in HHL circuits. Every extra clock qubit leads to an extra controlled U^{2^{n_{c}}-1} in the QPE section. As a result, QPE involves \sum_{j=0}^{n_{c}-1}2^{j}=2^{n_{c}}-1 applications of U . Hence, the primary focus for using