Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Cureus Journal of Computer Science.

Hybrid Quantum-Classical Implementation of the Harrow–Hassidim–Lloyd Algorithm: Bounded-Error Quantum Polynomial Time (BQP)-Completeness of Matrix Inversion and Error Mitigation for Noisy Intermediate-Scale Quantum (NISQ) Devices

Zefree Lazarus Mayaluri, Panda Ganapati

Published May 14, 2026• 0 citations
Publisher

Abstract

We propose a hybrid quantum-classical implementation of the Harrow-Hassidim-Lloyd (HHL) algorithm for the matrix inversion (linear-systems) problem, a key subroutine in quantum computing. Rather than claiming a new complexity result, we provide an assumption-explicit proof sketch, aligned with established literature, that contextualizes matrix inversion as Bounded-Error Quantum Polynomial Time (BQP)-complete and offers reduction-based intuition via Grover-type amplitude amplification. We implement HHL for 2 × 2, 4 × 4, and 8 × 8 Hermitian matrices using Qiskit and evaluate performance using simulator-based experiments with calibrated noise models and executions on IBM Quantum and IonQ backends. To enhance robustness on Noisy Intermediate-Scale Quantum (NISQ) hardware, we integrate measurement-error mitigation, zero-noise extrapolation, and post-selection, and we quantify performance using fidelity and mean squared error. Results from noiseless simulation, calibrated-noise simulation, and real-device execution show that mitigation improves reconstruction fidelity for small Hermitian systems, particularly for deeper circuits. These findings support mitigation-aware feasibility on current NISQ devices; however, they do not establish present-day runtime advantage over optimized classical solvers. The proposed workflow is relevant to quantum optimization, quantum machine learning, and quantum chemistry, where linear-system primitives arise frequently. Future work will focus on reducing phase-estimation depth (e.g., iterative or semiclassical variants), improving compilation and benchmarking transparency, and re-evaluating larger instances on higher-fidelity hardware.

DOI
10.7759/s44389-025-00066-8

Related papers

Solving linear systems on quantum hardware with hybrid HHL++

Romina Yalovetzky, Pierre Minssen, Dylan Herman +1 more

The limited capabilities of current quantum hardware significantly constrain the scale of experimental demonstrations of most quantum algorithmic primitives. This makes it challenging to perform benchmarking of the current hardware using useful quantum algorithms, i.e., application-oriented benchmarking. In particular, the Harrow-Hassidim-Lloyd (HHL) algorithm is a critical quantum linear algebra primitive, but the majority of the components of HHL are far out of the reach of noisy intermediate-scale quantum devices, which has led to the proposal of hybrid classical-quantum variants. The goal of this work is to further bridge the gap between proposed near-term friendly implementations of HHL and the kinds of quantum circuits that can be executed on noisy hardware. Our proposal adds to the existing literature of hybrid quantum algorithms for linear algebra that are more compatible with the current scale of quantum devices. Specifically, we propose two modifications to the Hybrid HHL algorithm proposed by Lee et al., leading to our algorithm Hybrid $$\hbox {HHL}^{++}$$ : (1) propose a novel algorithm for determining a scaling factor for the linear system matrix that maximizes the utility of the amount of ancillary qubits allocated to the phase estimation component of HHL, and (2) introduce a heuristic for compressing the HHL circuit. We demonstrate the efficacy of our work by running our modified Hybrid HHL on Quantinuum System Model H-series trapped-ion quantum computers to solve different problem instances of small-scale portfolio optimization problems, leading to the largest experimental demonstrations of HHL for an application to date.

arXiv:2110.15958•Scientific Reports•Sep 10, 2024•18 citations

An Enhanced Hybrid HHL Algorithm

Jack Morgan, Éric Ghysels, Hamed Mohammadbagherpoor

We present a classical enhancement to improve the accuracy of the Hybrid variant (Hybrid HHL) of the quantum algorithm for solving linear systems of equations proposed by Harrow, Hassidim, and Lloyd (HHL). We achieve this by using higher precision quantum estimates of the eigenvalues relevant to the linear system, and a new classical step to guide the eigenvalue inversion part of Hybrid HHL. We show that eigenvalue estimates with just two extra bits of precision result in tighter error bounds for our Enhanced Hybrid HHL compared to HHL. Our enhancement reduces the error of Hybrid HHL by an average of 57 percent on an ideal quantum processor for a representative sample of 2x2 systems. On IBM Torino and IonQ Aria-1 hardware, we see that the error of Enhanced Hybrid HHL is on average 13 percent and 20 percent (respectively) less than that of HHL for the same set of systems.

arXiv:2404.10103•Apr 15, 2024•0 citations

Quantum Speedup for Linear Systems: An Analysis of the HHL Algorithm Using IBM Qiskit

V Shwetha, Abinaya Selvarajan, A Aarthi +1 more

One of the most significant developments in quantum computing is the Harrow-Hassidim-Lloyd (HHL) method, which can solve linear equation systems at exponential speedup. Because linear systems are essential to many scientific fields, including physics, engineering, and machine learning, this approach has great potential to revolutionize computational paradigms. The HHL algorithm is thoroughly examined in this work, with particular attention paid to its theoretical framework, real-world application utilizing IBM's Qiskit platform, and the difficulties in simulating quantum algorithms on noisy intermediate-scale quantum (NISQ) devices. Using parameters like fidelity, time complexity, and scalability, the research further evaluates the HHL algorithm's performance in comparison to traditional methods. According to the findings, quantum simulations work well for small-scale matrices like 2x2 and 4x4, but expanding the approach to bigger systems is still difficult because of hardware and software constraints. Finally, the research emphasizes the key directions for advancing quantum hardware and algorithms to overcome current scalability challenges, enabling broader applicability of the HHL algorithm in solving complex linear systems.

Journal of Electronics and Informatics•Jan 9, 2025•0 citations

Improved circuit implementation of the HHL algorithm and its simulations on QISKIT

Meng Zhang, Lihua Dong, Yong Zeng +1 more

In 2019, Yonghae Lee et al. combined the circuit implementation of the Harrow-Hassidim-Lloyd (HHL) algorithm with a classical computer, and designed a hybrid HHL algorithm to reduce experimental errors caused by decoherence and so on. However, the improvement is achieved only in the auxiliary quantum coding phase, and no quantum resource reduction is done on the quantum phase estimation and inverse quantum phase estimation stages. At the same time, the circuit improvement illustration on a [Formula: see text] linear system just has the result and no specific process. In this paper, based on the idea of the hybrid HHL algorithm and a generic circuit of HHL algorithm, an improved circuit implementation of the HHL algorithm is proposed. The feasibility of the improved circuit implementation of the HHL algorithm is verified by IBM's qiskit. The improved circuit illustrations on a [Formula: see text] linear system show that the improved circuit implementation of the HHL algorithm can effectively reduce quantum resources without losing the fidelity of the results. Thus the improved circuit implementation of the HHL algorithm can further avoid some result errors than the existing implementation methods.

Scientific Reports•Aug 2, 2022•19 citations

Adapting the Harrow-Hassidim-Lloyd algorithm to quantum many-body theory

Nishanth Baskaran, Abhishek Singh Rawat, Akshaya Jayashankar +6 more

Rapid progress in developing near- and long-term quantum algorithms for quantum chemistry has provided us with an impetus to move beyond traditional approaches and explore new ways to apply quantum computing to electronic structure calculations. In this work, we identify the connection between quantum many-body theory and a quantum linear solver, and implement the Harrow-Hassidim-Lloyd (HHL) algorithm to make precise predictions of correlation energies for light molecular systems via the (nonunitary) linearized coupled cluster theory, where the term ``light molecular systems'' refers to those molecules whose constituent atoms have low atomic number. For the purposes of practical computations, we make suitable changes to the HHL framework. This entails two aspects: (1) Adapt, prescribing a novel scaling approach that allows one to scale any arbitrary Hermitian matrix, $A$, that in turn dictates the controlled-rotation angles without having to precompute the eigenvalues of $A$, and yet achieve a reasonably high precision in $|x\ensuremath{\rangle}$, and (2) Lite, for which we devise techniques that reduce the depth of the relevant quantum circuit. In this context, we introduce the following variants of HHL for different eras of quantum computing: AdaptHHLite in its appropriate forms for noisy intermediate-scale quantum (NISQ), late-NISQ, and the early fault-tolerant eras, as well as AdaptHHL for the fault-tolerant quantum computing era. We demonstrate the ability of the NISQ variant of AdaptHHLite to capture correlation energy precisely, while simultaneously being resource lean, using simulation as well as the 11-qubit IonQ quantum hardware.

Physical Review Research•Nov 3, 2023•14 citations

Optimization of the HHL Algorithm

Dhruv Sood, Nilmani Mathur, Vikram Tripathi

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.

quant-pharXiv:2603.15756•Mar 18, 2026•0 citations
We propose a hybrid quantum-classical implementation of the Harrow-Hassidim-Lloyd (HHL) algorithm for the matrix inversion (linear-systems) problem, a key subroutine in quantum computing. Rather than claiming a new complexity result, we provide an assumption-explicit proof sketch, aligned with established literature, that contextualizes matrix inversion as Bounded-Error Quantum Polynomial Time (BQP)-complete and offers reduction-based intuition via Grover-type amplitude amplification. We implement HHL for 2 × 2, 4 × 4, and 8 × 8 Hermitian matrices using Qiskit and evaluate performance using simulator-based experiments with calibrated noise models and executions on IBM Quantum and IonQ backends. To enhance robustness on Noisy Intermediate-Scale Quantum (NISQ) hardware, we integrate measurement-error mitigation, zero-noise extrapolation, and post-selection, and we quantify performance using fidelity and mean squared error. Results from noiseless simulation, calibrated-noise simulation, and real-device execution show that mitigation improves reconstruction fidelity for small Hermitian systems, particularly for deeper circuits. These findings support mitigation-aware feasibility on current NISQ devices; however, they do not establish present-day runtime advantage over optimized classical solvers. The proposed workflow is relevant to quantum optimization, quantum machine learning, and quantum chemistry, where linear-system primitives arise frequently. Future work will focus on reducing phase-estimation depth (e.g., iterative or semiclassical variants), improving compilation and benchmarking transparency, and re-evaluating larger instances on higher-fidelity hardware.
The limited capabilities of current quantum hardware significantly constrain the scale of experimental demonstrations of most quantum algorithmic primitives. This makes it challenging to perform benchmarking of the current hardware using useful quantum algorithms, i.e., application-oriented benchmarking. In particular, the Harrow-Hassidim-Lloyd (HHL) algorithm is a critical quantum linear algebra primitive, but the majority of the components of HHL are far out of the reach of noisy intermediate-scale quantum devices, which has led to the proposal of hybrid classical-quantum variants. The goal of this work is to further bridge the gap between proposed near-term friendly implementations of HHL and the kinds of quantum circuits that can be executed on noisy hardware. Our proposal adds to the existing literature of hybrid quantum algorithms for linear algebra that are more compatible with the current scale of quantum devices. Specifically, we propose two modifications to the Hybrid HHL algorithm proposed by Lee et al., leading to our algorithm Hybrid HHL++\hbox {HHL}^{++}HHL++ : (1) propose a novel algorithm for determining a scaling factor for the linear system matrix that maximizes the utility of the amount of ancillary qubits allocated to the phase estimation component of HHL, and (2) introduce a heuristic for compressing the HHL circuit. We demonstrate the efficacy of our work by running our modified Hybrid HHL on Quantinuum System Model H-series trapped-ion quantum computers to solve different problem instances of small-scale portfolio optimization problems, leading to the largest experimental demonstrations of HHL for an application to date.
We present a classical enhancement to improve the accuracy of the Hybrid variant (Hybrid HHL) of the quantum algorithm for solving linear systems of equations proposed by Harrow, Hassidim, and Lloyd (HHL). We achieve this by using higher precision quantum estimates of the eigenvalues relevant to the linear system, and a new classical step to guide the eigenvalue inversion part of Hybrid HHL. We show that eigenvalue estimates with just two extra bits of precision result in tighter error bounds for our Enhanced Hybrid HHL compared to HHL. Our enhancement reduces the error of Hybrid HHL by an average of 57 percent on an ideal quantum processor for a representative sample of 2x2 systems. On IBM Torino and IonQ Aria-1 hardware, we see that the error of Enhanced Hybrid HHL is on average 13 percent and 20 percent (respectively) less than that of HHL for the same set of systems.
One of the most significant developments in quantum computing is the Harrow-Hassidim-Lloyd (HHL) method, which can solve linear equation systems at exponential speedup. Because linear systems are essential to many scientific fields, including physics, engineering, and machine learning, this approach has great potential to revolutionize computational paradigms. The HHL algorithm is thoroughly examined in this work, with particular attention paid to its theoretical framework, real-world application utilizing IBM's Qiskit platform, and the difficulties in simulating quantum algorithms on noisy intermediate-scale quantum (NISQ) devices. Using parameters like fidelity, time complexity, and scalability, the research further evaluates the HHL algorithm's performance in comparison to traditional methods. According to the findings, quantum simulations work well for small-scale matrices like 2x2 and 4x4, but expanding the approach to bigger systems is still difficult because of hardware and software constraints. Finally, the research emphasizes the key directions for advancing quantum hardware and algorithms to overcome current scalability challenges, enabling broader applicability of the HHL algorithm in solving complex linear systems.
In 2019, Yonghae Lee et al. combined the circuit implementation of the Harrow-Hassidim-Lloyd (HHL) algorithm with a classical computer, and designed a hybrid HHL algorithm to reduce experimental errors caused by decoherence and so on. However, the improvement is achieved only in the auxiliary quantum coding phase, and no quantum resource reduction is done on the quantum phase estimation and inverse quantum phase estimation stages. At the same time, the circuit improvement illustration on a [Formula: see text] linear system just has the result and no specific process. In this paper, based on the idea of the hybrid HHL algorithm and a generic circuit of HHL algorithm, an improved circuit implementation of the HHL algorithm is proposed. The feasibility of the improved circuit implementation of the HHL algorithm is verified by IBM's qiskit. The improved circuit illustrations on a [Formula: see text] linear system show that the improved circuit implementation of the HHL algorithm can effectively reduce quantum resources without losing the fidelity of the results. Thus the improved circuit implementation of the HHL algorithm can further avoid some result errors than the existing implementation methods.
Rapid progress in developing near- and long-term quantum algorithms for quantum chemistry has provided us with an impetus to move beyond traditional approaches and explore new ways to apply quantum computing to electronic structure calculations. In this work, we identify the connection between quantum many-body theory and a quantum linear solver, and implement the Harrow-Hassidim-Lloyd (HHL) algorithm to make precise predictions of correlation energies for light molecular systems via the (nonunitary) linearized coupled cluster theory, where the term ``light molecular systems'' refers to those molecules whose constituent atoms have low atomic number. For the purposes of practical computations, we make suitable changes to the HHL framework. This entails two aspects: (1) Adapt, prescribing a novel scaling approach that allows one to scale any arbitrary Hermitian matrix, AAA, that in turn dictates the controlled-rotation angles without having to precompute the eigenvalues of AAA, and yet achieve a reasonably high precision in $|x\ensuremath{\rangle}$, and (2) Lite, for which we devise techniques that reduce the depth of the relevant quantum circuit. In this context, we introduce the following variants of HHL for different eras of quantum computing: AdaptHHLite in its appropriate forms for noisy intermediate-scale quantum (NISQ), late-NISQ, and the early fault-tolerant eras, as well as AdaptHHL for the fault-tolerant quantum computing era. We demonstrate the ability of the NISQ variant of AdaptHHLite to capture correlation energy precisely, while simultaneously being resource lean, using simulation as well as the 11-qubit IonQ quantum hardware.
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.