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:2511.17960

The Harrow-Hassidim-Lloyd algorithm with qutrits

Tushti Patel, V. S. Prasannaa

quant-phphysics.atom-phphysics.chem-phSubmitted Nov 22, 2025• Announced Nov 25, 2025• 1 citation• Revised Aug 30, 2026 (v3)
v1 · Nov 22, 2025v2 · Mar 4, 2026v3 · Aug 30, 2026
arXivHTMLPDF

Abstract

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.

Comments
In v3, we have fixed some details related to Weyl-Heisenberg gadgets. Comments are welcome!

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

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

Peniel Bertrand Tsemo, Akshaya Jayashankar, Kenji Sugisaki +3 more

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.

arXiv:2407.21641•Physical Review Research•May 29, 2025•14 citations

Solving the Hele–Shaw flow using the Harrow–Hassidim–Lloyd algorithm on superconducting devices: A study of efficiency and challenges

Muralikrishnan Gopalakrishnan Meena, Kalyana C. Gottiparthi, Justin G. Lietz +2 more

The development of quantum processors for practical fluid flow problems is a promising yet distant goal. Recent advances in quantum linear solvers have highlighted their potential for classical fluid dynamics. In this study, we evaluate the Harrow–Hassidim–Lloyd (HHL) quantum linear systems algorithm (QLSA) for solving the idealized Hele–Shaw flow. Our focus is on the accuracy and computational cost of the HHL solver, which we find to be sensitive to the condition number, scaling exponentially with problem size. This emphasizes the need for preconditioning to enhance the practical use of QLSAs in fluid flow applications. Moreover, we perform shots-based simulations on quantum simulators and test the HHL solver on superconducting quantum devices, where noise, large circuit depths, and gate errors limit performance. Error suppression and mitigation techniques improve accuracy, suggesting that such fluid flow problems can benchmark noise mitigation efforts. Our findings provide a foundation for future, more complex application of QLSAs in fluid flow simulations.

arXiv:2409.10857•Physics of Fluids•Oct 1, 2024•10 citations

A quantum linear system solver

Steven Herbert

Abstract In a sense, gate-based quantum computers are just machines that apply (extremely) large matrices to input states (vectors), and so it is natural to ask whether linear algebra applications can benefit from quantum computing. In the case of solving linear systems, this question has been answered with an emphatic ‘yes’. In 2009, Aram Harrow, Avinatan Hassidim, and Seth Lloyd proposed a quantum algorithm to solve linear systems exponentially faster than the best classical counterpart. The quantum linear systems solver is ubiquitously known by the initials of its inventors, ‘HHL’. As well as detailing HHL, this chapter also explores some of the quantum machine learning applications that have been proposed based on HHL along with results showing that these algorithms are often ‘dequantised’ in the problem space of interest – i.e., there exists an efficient classical ‘quantum-inspired’ algorithm.

Oxford University Press eBooks•Dec 8, 2025•0 citations

Digital-Analog Co-Design of the Harrow-Hassidim-Lloyd Algorithm

Ana Martin, Rubén Ibarrondo, Mikel Sanz

The Harrow-Hassidim-Lloyd quantum algorithm was proposed to solve linear systems of equations $A\stackrel{\ensuremath{\rightarrow}}{x}=\stackrel{\ensuremath{\rightarrow}}{b}$ and it is the core of various applications. However, there is no explicit quantum circuit for the subroutine that maps the inverse of the problem matrix $A$ into an ancillary qubit. This makes implementation in current quantum devices challenging, forcing us to use hybrid approaches. Here, we propose a systematic method to implement this subroutine, which can be adapted to other functions $f(A)$ of matrix $A$, we present a co-designed quantum processor that reduces the depth of the algorithm, and we introduce its digital-analog implementation. The depth of our proposal scales with precision $ϵ$ as $\mathcal{O}({ϵ}^{\ensuremath{-}1})$, which is bounded by the number of samples allowed for a certain experiment. The co-design of the Harrow-Hassidim-Lloyd algorithm leads to a ``kitelike'' architecture, which allows us to reduce the number of required swap gates. Finally, merging a co-design quantum processor architecture with a digital-analog implementation contributes to the reduction of noise sources during the experimental realization of the algorithm.

arXiv:2207.13528•Physical Review Applied•Jun 20, 2023•16 citations
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.
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.
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.
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.
The development of quantum processors for practical fluid flow problems is a promising yet distant goal. Recent advances in quantum linear solvers have highlighted their potential for classical fluid dynamics. In this study, we evaluate the Harrow–Hassidim–Lloyd (HHL) quantum linear systems algorithm (QLSA) for solving the idealized Hele–Shaw flow. Our focus is on the accuracy and computational cost of the HHL solver, which we find to be sensitive to the condition number, scaling exponentially with problem size. This emphasizes the need for preconditioning to enhance the practical use of QLSAs in fluid flow applications. Moreover, we perform shots-based simulations on quantum simulators and test the HHL solver on superconducting quantum devices, where noise, large circuit depths, and gate errors limit performance. Error suppression and mitigation techniques improve accuracy, suggesting that such fluid flow problems can benchmark noise mitigation efforts. Our findings provide a foundation for future, more complex application of QLSAs in fluid flow simulations.
Abstract In a sense, gate-based quantum computers are just machines that apply (extremely) large matrices to input states (vectors), and so it is natural to ask whether linear algebra applications can benefit from quantum computing. In the case of solving linear systems, this question has been answered with an emphatic ‘yes’. In 2009, Aram Harrow, Avinatan Hassidim, and Seth Lloyd proposed a quantum algorithm to solve linear systems exponentially faster than the best classical counterpart. The quantum linear systems solver is ubiquitously known by the initials of its inventors, ‘HHL’. As well as detailing HHL, this chapter also explores some of the quantum machine learning applications that have been proposed based on HHL along with results showing that these algorithms are often ‘dequantised’ in the problem space of interest – i.e., there exists an efficient classical ‘quantum-inspired’ algorithm.
The Harrow-Hassidim-Lloyd quantum algorithm was proposed to solve linear systems of equations $A\stackrel{\ensuremath{\rightarrow}}{x}=\stackrel{\ensuremath{\rightarrow}}{b}$ and it is the core of various applications. However, there is no explicit quantum circuit for the subroutine that maps the inverse of the problem matrix AAA into an ancillary qubit. This makes implementation in current quantum devices challenging, forcing us to use hybrid approaches. Here, we propose a systematic method to implement this subroutine, which can be adapted to other functions f(A)f(A)f(A) of matrix AAA, we present a co-designed quantum processor that reduces the depth of the algorithm, and we introduce its digital-analog implementation. The depth of our proposal scales with precision ϵϵϵ as $\mathcal{O}({ϵ}^{\ensuremath{-}1})$, which is bounded by the number of samples allowed for a certain experiment. The co-design of the Harrow-Hassidim-Lloyd algorithm leads to a ``kitelike'' architecture, which allows us to reduce the number of required swap gates. Finally, merging a co-design quantum processor architecture with a digital-analog implementation contributes to the reduction of noise sources during the experimental realization of the algorithm.