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

arXiv:2407.21641 · Physical Review Research

Enhancing the Harrow-Hassidim-Lloyd (HHL) algorithm in systems with large condition numbers

Peniel Bertrand Tsemo, Akshaya Jayashankar, Kenji Sugisaki, Nishanth Baskaran, Sayan Chakraborty, V. S. Prasannaa

Published May 29, 2025• 8 citations
arXivHTMLPDF

Abstract

Although the Harrow-Hassidim-Lloyd (HHL) algorithm offers an exponential speedup in system size for treating linear equations of the form A x ⃗ = b ⃗ on quantum computers when compared to their traditional counterparts, it faces a challenge related to the condition number ( κ ) scaling of the A matrix. In this work, we address the issue by introducing the postselection-improved HHL (Psi-HHL) framework that operates on a simple yet effective premise: subtracting mixed and wrong signals to extract correct signals while providing the benefit of optimal scaling in the condition number of A (denoted as κ ) for large κ scenarios. This approach, which leads to minimal increase in circuit depth, has the important practical implication of having to use substantially fewer shots relative to the traditional HHL algorithm. The term “signal” refers to a feature of | x 〉 . We design circuits for overlap and expectation value estimation in the Psi-HHL framework. We demonstrate performance of Psi-HHL via numerical simulations. We carry out two sets of computations, where we go up to 26-qubit calculations, to demonstrate the ability of Psi-HHL to handle situations involving large- κ matrices via (a) a set of toy matrices, for which we go up to size 64 × 64 and κ values of up to ≈ 1 × 10 6 , and (b) application to quantum chemistry, where we consider matrices up to size 256 × 256 that reach κ of about 393. The molecular systems that we consider are Li 2 , KH, RbH, and CsH.

DOI
10.1103/msvx-1drx

Related papers

Harrow-Hassidim-Lloyd algorithm without ancilla postselection

Бабухин Данила Валерьевич

Harrow-Hassidim-Lloyd algorithm (HHL) allows for the exponentially faster solution of a system of linear equations. However, this algorithm requires the postselection of an ancilla qubit to obtain the solution. This postselection makes the algorithm result probabilistic. Here we show conditions when the HHL algorithm can work without postselection of the ancilla qubit. We derive expectation values for an observable $M$ on the HHL outcome state when ancilla qubit is measured in $|0\ensuremath{\rangle}$ and $|1\ensuremath{\rangle}$ and show a condition for postselection-free HHL running. We provide an explicit example of a practically interesting input matrix and an observable, which satisfies the postselection-free HHL condition. Our work can improve the performance of the HHL-based algorithms.

arXiv:2208.02200•Physical Review A•Apr 6, 2023•13 citations

The Harrow-Hassidim-Lloyd algorithm with qutrits

Tushti Patel, V. S. Prasannaa

We extend the Harrow-Hassidim-Lloyd (HHL) algorithm, which is well-studied in the qubit framework, to its qutrit counterpart (which we call qutrit HHL, as opposed to qubit HHL, which is HHL using qubits), and develop a program for its implementation. We design Weyl-Heisenberg gadgets, the qutrit equivalents of Pauli gadgets, and come up with a practical implementation scheme for qutrit HHL. We test HHL with qutrits for simple matrices and verify the results against the expected outcomes. We apply the algorithm to quantum chemistry, and in particular, to the potential energy curve calculations of the model problem of the Hydrogen molecule in the split valence basis. We do so for two cases: 1-qutrit and 2-qutrit input states, where the latter makes use of our gadgets. We compare the number of qudits and the number of gates required between qubit and qutrit HHL implementations. In general, we find that for a fixed precision, the qutrit HHL circuit requires fewer number of qudits and comparable number of two-qudit gates than its qubit counterpart.

quant-pharXiv:2511.17960•Nov 25, 2025•0 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

Optimization of the HHL Algorithm

Dhruv Sood, Nilmani Mathur A, 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.

International Symposium on Lattice Field Theory (LATTICE)•Jul 5, 2026•0 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

Adapting the HHL 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 (non-unitary) linearised coupled cluster theory. We alter the HHL algorithm to integrate two novel aspects- (a) we prescribe a novel scaling approach that allows one to scale any arbitrary symmetric positive definite matrix A, to solve for Ax = b and achieve x with reasonable precision, all the while without having to compute the eigenvalues of A, and (b) we devise techniques that reduce the depth of the overall 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.

arXiv:2212.14781•Dec 30, 2022•0 citations
Although the Harrow-Hassidim-Lloyd (HHL) algorithm offers an exponential speedup in system size for treating linear equations of the form A x ⃗ = b ⃗ on quantum computers when compared to their traditional counterparts, it faces a challenge related to the condition number ( κ ) scaling of the A matrix. In this work, we address the issue by introducing the postselection-improved HHL (Psi-HHL) framework that operates on a simple yet effective premise: subtracting mixed and wrong signals to extract correct signals while providing the benefit of optimal scaling in the condition number of A (denoted as κ ) for large κ scenarios. This approach, which leads to minimal increase in circuit depth, has the important practical implication of having to use substantially fewer shots relative to the traditional HHL algorithm. The term “signal” refers to a feature of | x 〉 . We design circuits for overlap and expectation value estimation in the Psi-HHL framework. We demonstrate performance of Psi-HHL via numerical simulations. We carry out two sets of computations, where we go up to 26-qubit calculations, to demonstrate the ability of Psi-HHL to handle situations involving large- κ matrices via (a) a set of toy matrices, for which we go up to size 64 × 64 and κ values of up to ≈ 1 × 10 6 , and (b) application to quantum chemistry, where we consider matrices up to size 256 × 256 that reach κ of about 393. The molecular systems that we consider are Li 2 , KH, RbH, and CsH.
Harrow-Hassidim-Lloyd algorithm (HHL) allows for the exponentially faster solution of a system of linear equations. However, this algorithm requires the postselection of an ancilla qubit to obtain the solution. This postselection makes the algorithm result probabilistic. Here we show conditions when the HHL algorithm can work without postselection of the ancilla qubit. We derive expectation values for an observable MMM on the HHL outcome state when ancilla qubit is measured in $|0\ensuremath{\rangle}$ and $|1\ensuremath{\rangle}$ and show a condition for postselection-free HHL running. We provide an explicit example of a practically interesting input matrix and an observable, which satisfies the postselection-free HHL condition. Our work can improve the performance of the HHL-based algorithms.
We extend the Harrow-Hassidim-Lloyd (HHL) algorithm, which is well-studied in the qubit framework, to its qutrit counterpart (which we call qutrit HHL, as opposed to qubit HHL, which is HHL using qubits), and develop a program for its implementation. We design Weyl-Heisenberg gadgets, the qutrit equivalents of Pauli gadgets, and come up with a practical implementation scheme for qutrit HHL. We test HHL with qutrits for simple matrices and verify the results against the expected outcomes. We apply the algorithm to quantum chemistry, and in particular, to the potential energy curve calculations of the model problem of the Hydrogen molecule in the split valence basis. We do so for two cases: 1-qutrit and 2-qutrit input states, where the latter makes use of our gadgets. We compare the number of qudits and the number of gates required between qubit and qutrit HHL implementations. In general, we find that for a fixed precision, the qutrit HHL circuit requires fewer number of qudits and comparable number of two-qudit gates than its qubit counterpart.
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.
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.
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.
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 (non-unitary) linearised coupled cluster theory. We alter the HHL algorithm to integrate two novel aspects- (a) we prescribe a novel scaling approach that allows one to scale any arbitrary symmetric positive definite matrix A, to solve for Ax = b and achieve x with reasonable precision, all the while without having to compute the eigenvalues of A, and (b) we devise techniques that reduce the depth of the overall 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.