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:2207.13528 · Physical Review Applied

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

Ana Martin, Rubén Ibarrondo, Mikel Sanz

Published Jun 20, 2023• 13 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1103/physrevapplied.19.064056

Related papers

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

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.

Cureus Journal of Computer Science.•May 14, 2026•0 citations

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

Hybrid quantum linear equation algorithm and its experimental test on IBM Quantum Experience

Yonghae Lee, Jaewoo Joo, Soojoon Lee

We propose a hybrid quantum algorithm based on the Harrow-Hassidim-Lloyd (HHL) algorithm for solving a system of linear equations. In this paper, we show that our hybrid algorithm can reduce a circuit depth from the original HHL algorithm by means of a classical information feed-forward after the quantum phase estimation algorithm, and the results of the hybrid algorithm are identical to those of the HHL algorithm. In addition, it is experimentally examined with four qubits in the IBM Quantum Experience setups, and the experimental results of our algorithm show higher accurate performance on specific systems of linear equations than that of the HHL algorithm.

arXiv:1807.10651•Scientific Reports•Mar 18, 2019•77 citations

A near-term quantum algorithm for solving linear systems of equations based on the Woodbury identity

Daniel O’Malley, Henderson, Jessie M., Pelofske, Elijah +5 more

Quantum algorithms for solving linear systems of equations have generated excitement because of the potential speed-ups involved and the importance of solving linear equations in many applications. However, applying these algorithms can be challenging. The Harrow-Hassidim-Lloyd algorithm and improvements thereof require complex subroutines suitable for fault-tolerant hardware such as Hamiltonian simulation, making it ill-suited to current hardware. Variational algorithms, on the other hand, involve expensive optimization loops, which can be prone to barren plateaus and local optima. We describe a quantum algorithm for solving linear systems of equations that avoids these problems. Our algorithm is based on the Woodbury identity, which analytically describes the inverse of a matrix that is a low-rank modification of another (easily-invertible) matrix. This approach only utilizes basic quantum subroutines like the Hadamard test or the swap test, so it is well-suited to current hardware. There is no optimization loop, so barren plateaus and local optima do not present a problem. The low-rank aspect of the identity enables us to efficiently transfer information to and from the quantum computer. This approach can produce accurate results on current hardware. As evidence of this, we estimate an inner product involving the solution of a system of more than 16 million equations with 2% error using IBM's Auckland quantum computer. To our knowledge, no system of equations this large has previously been solved to this level of accuracy on a quantum computer.

arXiv:2205.00645•May 2, 2022•2 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

Quantum linear systems algorithms: a primer

Danial Dervovic, Mark Herbster, Peter Mountney +3 more

The Harrow-Hassidim-Lloyd (HHL) quantum algorithm for sampling from the solution of a linear system provides an exponential speed-up over its classical counterpart. The problem of solving a system of linear equations has a wide scope of applications, and thus HHL constitutes an important algorithmic primitive. In these notes, we present the HHL algorithm and its improved versions in detail, including explanations of the constituent sub- routines. More specifically, we discuss various quantum subroutines such as quantum phase estimation and amplitude amplification, as well as the important question of loading data into a quantum computer, via quantum RAM. The improvements to the original algorithm exploit variable-time amplitude amplification as well as a method for implementing linear combinations of unitary operations (LCUs) based on a decomposition of the operators using Fourier and Chebyshev series. Finally, we discuss a linear solver based on the quantum singular value estimation (QSVE) subroutine.

arXiv:1802.08227•Feb 22, 2018•62 citations
The Harrow-Hassidim-Lloyd quantum algorithm was proposed to solve linear systems of equations Ax\ensuremath→=b\ensuremath→A\stackrel{\ensuremath{\rightarrow}}{x}=\stackrel{\ensuremath{\rightarrow}}{b}Ax\ensuremath→=b\ensuremath→​ 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 O(ϵ\ensuremath−1)\mathcal{O}({ϵ}^{\ensuremath{-}1})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.
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 propose a hybrid quantum algorithm based on the Harrow-Hassidim-Lloyd (HHL) algorithm for solving a system of linear equations. In this paper, we show that our hybrid algorithm can reduce a circuit depth from the original HHL algorithm by means of a classical information feed-forward after the quantum phase estimation algorithm, and the results of the hybrid algorithm are identical to those of the HHL algorithm. In addition, it is experimentally examined with four qubits in the IBM Quantum Experience setups, and the experimental results of our algorithm show higher accurate performance on specific systems of linear equations than that of the HHL algorithm.
Quantum algorithms for solving linear systems of equations have generated excitement because of the potential speed-ups involved and the importance of solving linear equations in many applications. However, applying these algorithms can be challenging. The Harrow-Hassidim-Lloyd algorithm and improvements thereof require complex subroutines suitable for fault-tolerant hardware such as Hamiltonian simulation, making it ill-suited to current hardware. Variational algorithms, on the other hand, involve expensive optimization loops, which can be prone to barren plateaus and local optima. We describe a quantum algorithm for solving linear systems of equations that avoids these problems. Our algorithm is based on the Woodbury identity, which analytically describes the inverse of a matrix that is a low-rank modification of another (easily-invertible) matrix. This approach only utilizes basic quantum subroutines like the Hadamard test or the swap test, so it is well-suited to current hardware. There is no optimization loop, so barren plateaus and local optima do not present a problem. The low-rank aspect of the identity enables us to efficiently transfer information to and from the quantum computer. This approach can produce accurate results on current hardware. As evidence of this, we estimate an inner product involving the solution of a system of more than 16 million equations with 2% error using IBM's Auckland quantum computer. To our knowledge, no system of equations this large has previously been solved to this level of accuracy on a quantum computer.
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) quantum algorithm for sampling from the solution of a linear system provides an exponential speed-up over its classical counterpart. The problem of solving a system of linear equations has a wide scope of applications, and thus HHL constitutes an important algorithmic primitive. In these notes, we present the HHL algorithm and its improved versions in detail, including explanations of the constituent sub- routines. More specifically, we discuss various quantum subroutines such as quantum phase estimation and amplitude amplification, as well as the important question of loading data into a quantum computer, via quantum RAM. The improvements to the original algorithm exploit variable-time amplitude amplification as well as a method for implementing linear combinations of unitary operations (LCUs) based on a decomposition of the operators using Fourier and Chebyshev series. Finally, we discuss a linear solver based on the quantum singular value estimation (QSVE) subroutine.